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