2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.1 1994-09-26 10:17:43 adam
8 * Dfa-module header files.
23 typedef struct Tnode_ {
25 struct Tnode_ *p[2]; /* CAT,OR,STAR,PLUS (left,right) */
26 short ch[2]; /* if ch[0] >= 0 then this Tnode represents */
27 /* a character in range [ch[0]..ch[1]] */
28 /* otherwise ch[0] represents */
29 /* accepting no (-acceptno) */
31 unsigned pos : 15; /* CAT/OR/STAR/EPSILON or non-neg. position */
32 unsigned nullable : 1;
33 Set firstpos; /* first positions */
34 Set lastpos; /* last positions */
37 typedef struct Tblock_ { /* Tnode bucket (block) */
38 struct Tblock_ *next; /* pointer to next bucket */
39 Tnode *tarray; /* array of nodes in bucket */
43 Tnode *root; /* root of regular syntax tree */
44 Tnode *top; /* regular tree top (returned by parse_dfa) */
45 int position; /* no of positions so far */
46 int rule; /* no of rules so far */
47 BSetHandle *charset; /* character set type */
48 BSet anyset; /* character recognized by `.' */
49 int use_Tnode; /* used Tnodes */
50 int max_Tnode; /* allocated Tnodes */
51 Tblock *start; /* start block of Tnodes */
52 Tblock *end; /* end block of Tnodes */
56 unsigned char ch[2]; /* transition on ch[0] <= c <= ch[1] to */
57 unsigned short to; /* this state */
60 typedef struct DFA_trans_ {
61 struct DFA_trans_ *next; /* next DFA transition block */
62 DFA_tran *tran_block; /* pointer to transitions */
63 int ptr; /* index of next transition in tran_block */
64 int size; /* allocated size of tran_block */
67 typedef struct DFA_state_ {
68 struct DFA_state_ *next; /* next entry in free/unmarked/marked list */
69 struct DFA_state_ *link; /* link to next entry in hash chain */
70 DFA_tran *trans; /* transition list */
71 Set set; /* set of positions (important nfa states) */
72 short no; /* no of this state */
73 short tran_no; /* no of transitions to other states */
74 short rule_no; /* if non-zero, this holds accept rule no */
77 typedef struct DFA_stateb_ {
78 struct DFA_stateb_ *next;
79 DFA_state *state_block;
83 DFA_state *freelist; /* chain of unused (but allocated) DFA states */
84 DFA_state *unmarked; /* chain of unmarked DFA states */
85 DFA_state *marked; /* chain of marked DFA states */
86 DFA_stateb *statemem; /* state memory */
87 int no; /* no of states (unmarked+marked) */
88 SetType st; /* Position set type */
89 int hash; /* no hash entries in hasharray */
90 DFA_state **hasharray; /* hash pointers */
91 DFA_state **sortarray; /* sorted DFA states */
92 DFA_trans *transmem; /* transition memory */
95 DFA * init_dfa (void);
96 void rm_dfa (DFA **dfap);
97 int parse_dfa (DFA *, char **, const unsigned short *);
98 DFA_states* mk_dfas (DFA *, int poset_chunk);
99 void rm_dfas (DFA_states **dfas);
101 Tnode * mk_Tnode (void);
102 Tnode * mk_Tnode_cset (BSet charset);
103 void term_Tnode (void);
105 int init_DFA_states (DFA_states **dfasp, SetType st, int hash);
106 int rm_DFA_states (DFA_states **dfasp);
107 int add_DFA_state (DFA_states *dfas, Set *s, DFA_state **sp);
108 DFA_state *get_DFA_state (DFA_states *dfas);
109 void sort_DFA_states (DFA_states *dfas);
110 void add_DFA_tran (DFA_states *, DFA_state *, int, int, int);
112 extern int debug_dfa_trav;
113 extern int debug_dfa_tran;
114 extern int debug_dfa_followpos;
115 extern int dfa_verbose;
117 extern unsigned short