IDZEBRA 2.2.11
Data Structures | Macros | Functions | Variables
dfa.c File Reference
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <yaz/snprintf.h>
#include <idzebra/util.h>
#include "dfap.h"
#include "imalloc.h"

Go to the source code of this file.

Data Structures

struct  Tnode
struct  Tblock

Macros

#define CAT   16000
#define OR   16001
#define STAR   16002
#define PLUS   16003
#define EPSILON   16004
#define TADD   64
#define STATE_HASH   199
#define POSET_CHUNK   100
#define L_LP   1
#define L_RP   2
#define L_CHAR   3
#define L_CHARS   4
#define L_ANY   5
#define L_ALT   6
#define L_ANYZ   7
#define L_WILD   8
#define L_QUEST   9
#define L_CLOS1   10
#define L_CLOS0   11
#define L_END   12
#define L_START   13

Functions

static struct Tnode * mk_Tnode (struct DFA_parse *parse_info)
static struct Tnode * mk_Tnode_cset (struct DFA_parse *parse_info, BSet charset)
static void term_Tnode (struct DFA_parse *parse_info)
static void del_followpos (struct DFA_parse *parse_info)
static void init_pos (struct DFA_parse *parse_info)
static void del_pos (struct DFA_parse *parse_info)
static void mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void add_follow (struct DFA_parse *parse_info, DFASet lastpos, DFASet firstpos)
static void dfa_trav (struct DFA_parse *parse_info, struct Tnode *n)
static void init_followpos (struct DFA_parse *parse_info)
static void pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void pr_followpos (struct DFA_parse *parse_info)
static void out_char (int c)
static void lex (struct DFA_parse *parse_info)
static int nextchar (struct DFA_parse *parse_info, int *esc)
static int read_charset (struct DFA_parse *parse_info)
static const char * str_char (unsigned c)
static struct Tnode * expr_1 (struct DFA_parse *parse_info)
static struct Tnode * expr_2 (struct DFA_parse *parse_info)
static struct Tnode * expr_3 (struct DFA_parse *parse_info)
static struct Tnode * expr_4 (struct DFA_parse *parse_info)
static void do_parse (struct DFA_parse *parse_info, const char **s, struct Tnode **tnp)
static int nextchar_set (struct DFA_parse *parse_info, int *esc)
static int map_l_char (struct DFA_parse *parse_info)
static int lex_sub (struct DFA_parse *parse_info)
void dfa_parse_cmap_clean (struct DFA *d)
void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
void dfa_parse_cmap_del (struct DFA *d, int from)
void dfa_parse_cmap_add (struct DFA *d, int from, int to)
void dfa_parse_cmap_thompson (struct DFA *d)
static struct DFA_parse * dfa_parse_init (void)
static void rm_dfa_parse (struct DFA_parse **dfap)
static struct DFA_states * mk_dfas (struct DFA_parse *dfap, int poset_chunk)
struct DFA * dfa_init (void)
void dfa_anyset_includes_nl (struct DFA *dfa)
void dfa_set_cmap (struct DFA *dfa, void *vp, const char **(*cmap)(void *vp, const char **from, int len))
int dfa_get_last_rule (struct DFA *dfa)
int dfa_parse (struct DFA *dfa, const char **pattern)
void dfa_mkstate (struct DFA *dfa)
void dfa_delete (struct DFA **dfap)

Variables

int debug_dfa_trav = 0
int debug_dfa_tran = 0
int debug_dfa_followpos = 0
int dfa_verbose = 0

Macro Definition Documentation

◆ CAT

#define CAT   16000

Definition at line 37 of file dfa.c.

Referenced by dfa_trav(), do_parse(), and expr_2().

◆ EPSILON

#define EPSILON   16004

Definition at line 41 of file dfa.c.

Referenced by dfa_trav(), expr_3(), expr_4(), and mk_Tnode_cset().

◆ L_ALT

#define L_ALT   6

Definition at line 102 of file dfa.c.

◆ L_ANY

#define L_ANY   5

Definition at line 101 of file dfa.c.

◆ L_ANYZ

#define L_ANYZ   7

Definition at line 103 of file dfa.c.

◆ L_CHAR

#define L_CHAR   3

Definition at line 99 of file dfa.c.

◆ L_CHARS

#define L_CHARS   4

Definition at line 100 of file dfa.c.

◆ L_CLOS0

#define L_CLOS0   11

Definition at line 107 of file dfa.c.

◆ L_CLOS1

#define L_CLOS1   10

Definition at line 106 of file dfa.c.

◆ L_END

#define L_END   12

Definition at line 108 of file dfa.c.

◆ L_LP

#define L_LP   1

Definition at line 97 of file dfa.c.

◆ L_QUEST

#define L_QUEST   9

Definition at line 105 of file dfa.c.

◆ L_RP

#define L_RP   2

Definition at line 98 of file dfa.c.

◆ L_START

#define L_START   13

Definition at line 109 of file dfa.c.

◆ L_WILD

#define L_WILD   8

Definition at line 104 of file dfa.c.

◆ OR

#define OR   16001

Definition at line 38 of file dfa.c.

Referenced by dfa_parse(), dfa_trav(), expr_1(), expr_3(), expr_4(), and mk_Tnode_cset().

◆ PLUS

#define PLUS   16003

Definition at line 40 of file dfa.c.

Referenced by dfa_trav(), and expr_3().

◆ POSET_CHUNK

#define POSET_CHUNK   100

Definition at line 64 of file dfa.c.

Referenced by dfa_mkstate().

◆ STAR

#define STAR   16002

Definition at line 39 of file dfa.c.

Referenced by dfa_trav(), expr_3(), and expr_4().

◆ STATE_HASH

#define STATE_HASH   199

Definition at line 63 of file dfa.c.

Referenced by mk_dfas().

◆ TADD

#define TADD   64

Definition at line 62 of file dfa.c.

Referenced by mk_Tnode().

Function Documentation

◆ add_follow()

void add_follow ( struct DFA_parse * parse_info,
DFASet lastpos,
DFASet firstpos )

Definition at line 638 of file dfa.c.

References Tnode::firstpos, DFA_parse::followpos, Tnode::lastpos, DFASetElement_::next, DFA_parse::poset, union_DFASet(), and DFASetElement_::value.

Referenced by dfa_trav().

◆ del_followpos()

void del_followpos ( struct DFA_parse * parse_info)
static

Definition at line 622 of file dfa.c.

References DFA_parse::followpos, and ifree().

Referenced by mk_dfas().

◆ del_pos()

void del_pos ( struct DFA_parse * parse_info)

Definition at line 633 of file dfa.c.

References ifree(), and DFA_parse::posar.

Referenced by mk_dfas().

◆ dfa_anyset_includes_nl()

void dfa_anyset_includes_nl ( struct DFA * dfa)

Definition at line 1104 of file dfa.c.

References add_BSet(), DFA_parse::anyset, DFA_parse::charset, and DFA::parse_info.

Referenced by dict_lookup_grep().

◆ dfa_delete()

void dfa_delete ( struct DFA ** dfap)

Definition at line 1158 of file dfa.c.

References ifree(), rm_dfa_parse(), and rm_DFA_states().

Referenced by actionListDel(), data1_absyn_destroy(), data1_read_absyn(), dict_lookup_grep(), lexContextDestroy(), main(), and tst().

◆ dfa_get_last_rule()

int dfa_get_last_rule ( struct DFA * dfa)

Definition at line 1116 of file dfa.c.

References DFA::parse_info, and DFA_parse::rule.

◆ dfa_init()

struct DFA * dfa_init ( void )

Definition at line 1092 of file dfa.c.

References dfa_parse_cmap_thompson(), dfa_parse_init(), imalloc(), DFA::parse_info, DFA::state_info, and DFA::states.

Referenced by data1_read_absyn(), dict_lookup_grep(), lexSpecDFA(), main(), and tst().

◆ dfa_mkstate()

void dfa_mkstate ( struct DFA * dfa)

Definition at line 1148 of file dfa.c.

References mk_dfas(), DFA_states::no, DFA::no_states, DFA::parse_info, POSET_CHUNK, rm_dfa_parse(), DFA_states::sortarray, DFA::state_info, and DFA::states.

Referenced by actionListMk(), data1_read_absyn(), dict_lookup_grep(), main(), and readFileSpec().

◆ dfa_parse()

int dfa_parse ( struct DFA * dfa,
const char ** pattern )

Definition at line 1121 of file dfa.c.

References do_parse(), DFA_parse::err_code, mk_Tnode(), OR, Tnode::p, DFA::parse_info, Tnode::pos, DFA_parse::root, and Tnode::u.

Referenced by actionListMk(), data1_read_absyn(), dict_lookup_grep(), main(), read_rules(), readOneSpec(), and test_parse().

◆ dfa_parse_cmap_add()

void dfa_parse_cmap_add ( struct DFA * d,
int from,
int to )

Definition at line 978 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, ifree(), imalloc(), and DFA::parse_info.

Referenced by lexSpecDFA().

◆ dfa_parse_cmap_clean()

void dfa_parse_cmap_clean ( struct DFA * d)

Definition at line 926 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, imalloc(), and DFA::parse_info.

◆ dfa_parse_cmap_del()

void dfa_parse_cmap_del ( struct DFA * d,
int from )

Definition at line 960 of file dfa.c.

References DFA_parse::charMap, and DFA::parse_info.

Referenced by lexSpecDFA().

◆ dfa_parse_cmap_new()

void dfa_parse_cmap_new ( struct DFA * d,
const int * cmap )

Definition at line 940 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, DFA_parse::cmap, ifree(), imalloc(), and DFA::parse_info.

Referenced by dfa_parse_cmap_thompson().

◆ dfa_parse_cmap_thompson()

void dfa_parse_cmap_thompson ( struct DFA * d)

Definition at line 1006 of file dfa.c.

References dfa_parse_cmap_new(), L_ALT, L_ANY, L_CLOS0, L_CLOS1, L_END, L_LP, L_QUEST, L_RP, and L_START.

Referenced by dfa_init().

◆ dfa_parse_init()

struct DFA_parse * dfa_parse_init ( void )
static

Definition at line 1027 of file dfa.c.

References add_BSet(), DFA_parse::anyset, DFA_parse::charMap, DFA_parse::charMapSize, DFA_parse::charset, DFA_parse::cmap, com_BSet(), DFA_parse::end, imalloc(), DFA_parse::max_Tnode, mk_BSet(), mk_BSetHandle(), DFA_parse::position, res_BSet(), DFA_parse::root, DFA_parse::rule, DFA_parse::start, and DFA_parse::use_Tnode.

Referenced by dfa_init().

◆ dfa_set_cmap()

void dfa_set_cmap ( struct DFA * dfa,
void * vp,
const char **(* cmap )(void *vp, const char **from, int len) )

Definition at line 1109 of file dfa.c.

References DFA_parse::cmap, DFA_parse::cmap_data, and DFA::parse_info.

Referenced by dict_lookup_grep().

◆ dfa_trav()

void dfa_trav ( struct DFA_parse * parse_info,
struct Tnode * n )

Definition at line 650 of file dfa.c.

References add_DFASet(), add_follow(), CAT, Tnode::ch, debug_dfa_trav, dfa_trav(), EPSILON, Tnode::firstpos, Tnode::lastpos, merge_DFASet(), mk_DFASet(), Tnode::nullable, OR, out_char(), Tnode::p, PLUS, Tnode::pos, DFA_parse::posar, DFA_parse::poset, pr_DFASet(), rm_DFASet(), STAR, Tnode::u, and union_DFASet().

Referenced by dfa_trav(), and mk_dfas().

◆ do_parse()

void do_parse ( struct DFA_parse * parse_info,
const char ** s,
struct Tnode ** tnp )
static

Definition at line 246 of file dfa.c.

References CAT, Tnode::ch, DFA_ERR_LP, DFA_ERR_RP, DFA_ERR_SYNTAX, DFA_parse::err_code, expr_1(), DFA_parse::expr_ptr, DFA_parse::inside_string, L_END, L_LP, L_RP, L_START, lex(), DFA_parse::lookahead, mk_Tnode(), Tnode::p, Tnode::pos, DFA_parse::position, DFA_parse::rule, and Tnode::u.

Referenced by dfa_parse().

◆ expr_1()

struct Tnode * expr_1 ( struct DFA_parse * parse_info)
static

Definition at line 117 of file dfa.c.

References expr_2(), L_ALT, lex(), DFA_parse::lookahead, mk_Tnode(), OR, Tnode::p, Tnode::pos, and Tnode::u.

Referenced by do_parse(), and expr_4().

◆ expr_2()

struct Tnode * expr_2 ( struct DFA_parse * parse_info)

Definition at line 138 of file dfa.c.

References CAT, expr_3(), L_ANY, L_ANYZ, L_CHAR, L_CHARS, L_LP, L_WILD, DFA_parse::lookahead, mk_Tnode(), Tnode::p, Tnode::pos, and Tnode::u.

Referenced by expr_1().

◆ expr_3()

struct Tnode * expr_3 ( struct DFA_parse * parse_info)

Definition at line 163 of file dfa.c.

References EPSILON, expr_4(), L_CLOS0, L_CLOS1, L_QUEST, lex(), DFA_parse::lookahead, mk_Tnode(), OR, Tnode::p, PLUS, Tnode::pos, STAR, and Tnode::u.

Referenced by expr_2().

◆ expr_4()

struct Tnode * expr_4 ( struct DFA_parse * parse_info)

Definition at line 198 of file dfa.c.

References DFA_parse::anyset, Tnode::ch, EPSILON, expr_1(), L_ANY, L_ANYZ, L_CHAR, L_CHARS, L_LP, L_RP, L_WILD, lex(), DFA_parse::look_ch, DFA_parse::look_chars, DFA_parse::lookahead, mk_Tnode(), mk_Tnode_cset(), OR, Tnode::p, Tnode::pos, DFA_parse::position, STAR, and Tnode::u.

Referenced by expr_3().

◆ init_followpos()

void init_followpos ( struct DFA_parse * parse_info)

Definition at line 754 of file dfa.c.

References DFA_parse::followpos, imalloc(), mk_DFASet(), DFA_parse::poset, and DFA_parse::position.

Referenced by mk_dfas().

◆ init_pos()

void init_pos ( struct DFA_parse * parse_info)

Definition at line 627 of file dfa.c.

References imalloc(), DFA_parse::posar, and DFA_parse::position.

Referenced by dict_lookup_grep(), grep(), and mk_dfas().

◆ lex()

void lex ( struct DFA_parse * parse_info)

Definition at line 503 of file dfa.c.

References lex_sub(), and DFA_parse::lookahead.

Referenced by do_parse(), expr_1(), expr_3(), expr_4(), and main().

◆ lex_sub()

int lex_sub ( struct DFA_parse * parse_info)
static

Definition at line 474 of file dfa.c.

References DFA_parse::charMap, DFA_parse::expr_ptr, DFA_parse::inside_string, DFA_parse::look_ch, map_l_char(), nextchar(), and read_charset().

Referenced by lex().

◆ map_l_char()

int map_l_char ( struct DFA_parse * parse_info)
static

Definition at line 450 of file dfa.c.

References DFA_parse::cmap, DFA_parse::cmap_data, DFA_parse::expr_ptr, L_CHAR, and DFA_parse::look_ch.

Referenced by lex_sub().

◆ mk_dfa_tran()

void mk_dfa_tran ( struct DFA_parse * parse_info,
struct DFA_states * dfas )

Definition at line 764 of file dfa.c.

References add_DFA_state(), add_DFA_tran(), Tnode::ch, DFA_parse::charset, cp_DFASet(), Tnode::firstpos, DFA_parse::followpos, get_DFA_state(), ifree(), imalloc(), mk_DFASet(), DFASetElement_::next, DFA_state::no, Tnode::pos, DFA_parse::posar, DFA_parse::poset, DFA_parse::position, DFA_parse::root, DFA_state::rule_nno, DFA_state::rule_no, DFA_state::set, BSetHandle_::size, sort_DFA_states(), Tnode::u, union_DFASet(), and DFASetElement_::value.

Referenced by mk_dfas().

◆ mk_dfas()

struct DFA_states * mk_dfas ( struct DFA_parse * dfap,
int poset_chunk )
static

Definition at line 1062 of file dfa.c.

References debug_dfa_followpos, debug_dfa_tran, del_followpos(), del_pos(), dfa_trav(), dfa_verbose, init_DFA_states(), init_followpos(), init_pos(), mk_dfa_tran(), mk_DFASetType(), DFA_parse::poset, pr_followpos(), pr_tran(), pr_verbose(), rm_DFASetType(), DFA_parse::root, and STATE_HASH.

Referenced by dfa_mkstate().

◆ mk_Tnode()

struct Tnode * mk_Tnode ( struct DFA_parse * parse_info)
static

Definition at line 563 of file dfa.c.

References DFA_parse::end, imalloc(), DFA_parse::max_Tnode, Tblock::next, DFA_parse::start, TADD, Tblock::tarray, and DFA_parse::use_Tnode.

Referenced by dfa_parse(), do_parse(), expr_1(), expr_2(), expr_3(), expr_4(), and mk_Tnode_cset().

◆ mk_Tnode_cset()

struct Tnode * mk_Tnode_cset ( struct DFA_parse * parse_info,
BSet charset )
static

Definition at line 584 of file dfa.c.

References Tnode::ch, DFA_parse::charset, EPSILON, mk_Tnode(), OR, Tnode::p, Tnode::pos, DFA_parse::position, BSetHandle_::size, trav_BSet(), travi_BSet(), and Tnode::u.

Referenced by expr_4().

◆ nextchar()

int nextchar ( struct DFA_parse * parse_info,
int * esc )
static

Definition at line 314 of file dfa.c.

References DFA_parse::expr_ptr.

Referenced by lex_sub(), nextchar_set(), and read_charset().

◆ nextchar_set()

int nextchar_set ( struct DFA_parse * parse_info,
int * esc )
static

Definition at line 348 of file dfa.c.

References DFA_parse::expr_ptr, and nextchar().

Referenced by read_charset().

◆ out_char()

void out_char ( int c)

Definition at line 547 of file dfa.c.

References str_char().

Referenced by dfa_trav(), and pr_followpos().

◆ pr_followpos()

void pr_followpos ( struct DFA_parse * parse_info)

Definition at line 897 of file dfa.c.

References Tnode::ch, DFA_parse::followpos, out_char(), DFA_parse::posar, DFA_parse::poset, DFA_parse::position, pr_DFASet(), and Tnode::u.

Referenced by mk_dfas().

◆ pr_tran()

void pr_tran ( struct DFA_parse * parse_info,
struct DFA_states * dfas )

Definition at line 846 of file dfa.c.

References DFA_tran::ch, DFA_state::no, DFA_states::no, DFA_parse::poset, pr_DFASet(), DFA_state::rule_nno, DFA_state::rule_no, DFA_state::set, DFA_states::sortarray, str_char(), DFA_tran::to, DFA_state::tran_no, and DFA_state::trans.

Referenced by mk_dfas().

◆ pr_verbose()

void pr_verbose ( struct DFA_parse * parse_info,
struct DFA_states * dfas )

Definition at line 883 of file dfa.c.

References DFA_parse::charset, inf_BSetHandle(), inf_DFASetType(), DFA_parse::max_Tnode, DFA_states::no, DFA_parse::poset, and DFA_parse::use_Tnode.

Referenced by mk_dfas().

◆ read_charset()

int read_charset ( struct DFA_parse * parse_info)

ch0 is last met character ch1 is "next" char

Definition at line 358 of file dfa.c.

References add_BSet(), DFA_parse::charset, DFA_parse::cmap, DFA_parse::cmap_data, com_BSet(), L_CHARS, DFA_parse::look_chars, mk_BSet(), nextchar(), nextchar_set(), and res_BSet().

Referenced by lex_sub().

◆ rm_dfa_parse()

void rm_dfa_parse ( struct DFA_parse ** dfap)
static

Definition at line 1051 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charset, ifree(), rm_BSetHandle(), and term_Tnode().

Referenced by dfa_delete(), and dfa_mkstate().

◆ str_char()

const char * str_char ( unsigned c)
static

Definition at line 508 of file dfa.c.

Referenced by out_char(), and pr_tran().

◆ term_Tnode()

void term_Tnode ( struct DFA_parse * parse_info)
static

Definition at line 552 of file dfa.c.

References ifree(), Tblock::next, DFA_parse::start, and Tblock::tarray.

Referenced by rm_dfa_parse().

Variable Documentation

◆ debug_dfa_followpos

int debug_dfa_followpos = 0

Definition at line 68 of file dfa.c.

Referenced by agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().

◆ debug_dfa_tran

int debug_dfa_tran = 0

Definition at line 67 of file dfa.c.

Referenced by actionListMk(), agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().

◆ debug_dfa_trav

int debug_dfa_trav = 0

Definition at line 66 of file dfa.c.

Referenced by agrep_options(), dfa_trav(), dict_lookup_grep(), lexer_options(), main(), and readFileSpec().

◆ dfa_verbose

int dfa_verbose = 0

Definition at line 69 of file dfa.c.

Referenced by agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().

Generated by doxygen 1.16.1