1 /*************************************** 2 $Header: /cvs/src/dfasyn/n2d.h,v 1.2 2003/03/02 23:42:11 richard Exp $ 3 4 Header file for NFA->DFA conversion utility. 5 ***************************************/ 6 7 /* 8 ********************************************************************** 9 * Copyright (C) Richard P. Curnow 2001-2003,2005 10 * 11 * This program is free software; you can redistribute it and/or modify 12 * it under the terms of version 2 of the GNU General Public License as 13 * published by the Free Software Foundation. 14 * 15 * This program is distributed in the hope that it will be useful, but 16 * WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License along 21 * with this program; if not, write to the Free Software Foundation, Inc., 22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 23 * 24 ********************************************************************** 25 */ 26 27 #ifndef N2D_H 28 #define N2D_H 29 30 #include <stdio.h> 31 #include <stdlib.h> 32 #include <string.h> 33 34 #define new(T) ((T *) malloc(sizeof(T))) 35 #define new_array(T,N) ((T *) malloc((N) * sizeof(T))) 36 #define resize_array(T,arr,newN) ((T *) ((arr) ? realloc(arr,(newN)*sizeof(T)) : malloc((newN)*sizeof(T)))) 37 #define new_string(s) strcpy((char *)malloc((strlen(s)+1)*sizeof(char)),s) 38 39 /* For typecasting, especially useful for declarations of local ptrs to args 40 of a qsort comparison fn */ 41 #define Castdecl(x, T, nx) T nx = (T) x 42 43 #define Castderef(x, T, nx) T nx = *(T*) x 44 45 /* Globally visible options to control reporting */ 46 extern FILE *report; 47 extern int verbose; 48 49 struct State; 50 struct Block; 51 52 typedef struct Translist { 53 struct Translist *next; 54 int token; 55 char *ds_name; 56 struct State *ds_ref; 57 } Translist; 58 59 typedef struct Stringlist { 60 struct Stringlist *next; 61 char *string; 62 } Stringlist; 63 64 typedef struct InlineBlock { 65 char *type; /* Block type */ 66 char *in; /* Name of input node */ 67 char *out; /* Name of output node */ 68 } InlineBlock; 69 70 typedef struct InlineBlockList { 71 struct InlineBlockList *next; 72 InlineBlock *ib; 73 } InlineBlockList; 74 75 typedef struct State { 76 char *name; 77 int index; /* Array index in containing block */ 78 struct Block *parent; 79 Translist *transitions; 80 Stringlist *exitvals; 81 Stringlist *attributes; 82 83 /* Pointers to the nodes in the 'transitions' list, sorted into canonical order */ 84 Translist **ordered_trans; 85 int n_transitions; 86 87 unsigned char removed; /* Flag indicating state has been pruned by compression stage */ 88 } State; 89 90 typedef struct S_Stateset { 91 State **states; 92 int nstates; 93 int maxstates; 94 } Stateset; 95 96 #define HASH_BUCKETS 64 97 #define HASH_MASK (HASH_BUCKETS-1) 98 99 typedef struct Block { 100 char *name; 101 102 /* The master table of states within this block. This has to be in a flat 103 array because we have to work with respect to state indices when doing the 104 2D bitmap stuff for the subset construction. */ 105 State **states; 106 int nstates; 107 int maxstates; 108 109 /* Hash table for getting rapid access to a state within the block, given 110 its name */ 111 Stateset state_hash[HASH_BUCKETS]; 112 113 int subcount; /* Number for generating substates */ 114 int subblockcount; /* Number for generating inline subblocks */ 115 } Block; 116 117 typedef struct { 118 unsigned long *nfas; 119 unsigned long signature; /* All the longwords in the nfas array xor'ed together */ 120 int index; /* Entry's own index in the array */ 121 int *map; /* index by token code */ 122 int from_state; /* the state which provided the first transition to this one (leading to its creation) */ 123 int via_token; /* the token through which we got to this state the first time. */ 124 Stringlist *nfa_exit_sl; /* NFA exit values */ 125 Stringlist *nfa_attr_sl; /* NFA exit values */ 126 char *result; /* Result token, computed by boolean expressions defined in input text */ 127 int result_early; /* If !=0, the scanner is expected to exit immediately this DFA state is entered. 128 It means that no out-bound transitions have to be created. */ 129 char *attribute; /* Attribute token, computed by boolean expressions defined in input text */ 130 131 /* Fields calculated in compdfa.c */ 132 133 /* The equivalence class the state is in. */ 134 int eq_class; 135 136 /* Temp. storage for the new eq. class within a single pass of the splitting alg. */ 137 int new_eq_class; 138 139 /* Signature field from above is also re-used. */ 140 141 int is_rep; /* Set if state is chosen as the representative of its equivalence class. */ 142 int new_index; /* New index assigned to the state. */ 143 144 /* Fields calculated in tabcompr.c */ 145 146 unsigned long transition_sig; 147 148 /* Default state, i.e. the one that supplies transitions for tokens not 149 explicitly listed for this one. */ 150 int defstate; 151 152 /* Number of transitions that this state has different to those in the 153 default state. */ 154 int best_diff; 155 156 } DFANode; 157 158 159 void yyerror(const char *s); 160 extern int yylex(void); 161 162 /* Constants for 'create' args */ 163 #define USE_OLD_MUST_EXIST 0 164 #define CREATE_MUST_NOT_EXIST 1 165 #define CREATE_OR_USE_OLD 2 166 167 State *get_curstate(void); 168 169 struct Abbrev; 170 extern struct Abbrev * create_abbrev(char *name); 171 extern void add_tok_to_abbrev(struct Abbrev *abbrev, char *tok); 172 173 int lookup_token(char *name, int create); 174 Block *lookup_block(char *name, int create); 175 State *lookup_state(Block *in_block, char *name, int create); 176 Stringlist * add_token(Stringlist *existing, char *token); 177 void add_transitions(State *curstate, Stringlist *tokens, char *destination); 178 State * add_transitions_to_internal(Block *curblock, State *addtostate, Stringlist *tokens); 179 void add_exit_value(State *curstate, char *value); 180 void set_state_attribute(State *curstate, char *name); 181 InlineBlock *create_inline_block(char *type, char *in, char *out); 182 InlineBlockList *add_inline_block(InlineBlockList *existing, InlineBlock *nib); 183 State * add_inline_block_transitions(Block *curblock, State *addtostate, InlineBlockList *ibl); 184 void instantiate_block(Block *curblock, char *block_name, char *instance_name); 185 void fixup_state_refs(Block *b); 186 187 void compress_nfa(Block *b); 188 189 /* In expr.c */ 190 typedef struct Expr Expr; 191 192 typedef struct evaluator Evaluator; 193 extern Evaluator *exit_evaluator; 194 extern Evaluator *attr_evaluator; 195 196 Expr * new_wild_expr(void); 197 Expr * new_not_expr(Expr *c); 198 Expr * new_and_expr(Expr *c1, Expr *c2); 199 Expr * new_or_expr(Expr *c1, Expr *c2); 200 Expr * new_xor_expr(Expr *c1, Expr *c2); 201 Expr * new_cond_expr(Expr *c1, Expr *c2, Expr *c3); 202 Expr * new_sym_expr(char *sym_name); 203 204 void define_symbol(Evaluator *x, char *name, Expr *e); 205 void define_result(Evaluator *x, char *string, Expr *e, int early); 206 void define_symresult(Evaluator *x, char *string, Expr *e, int early); 207 void define_defresult(Evaluator *x, char *string); 208 void clear_symbol_values(Evaluator *x); 209 void set_symbol_value(Evaluator *x, char *sym_name); 210 int evaluate_result(Evaluator *x, char **, int *); 211 int evaluator_is_used(Evaluator *x); 212 void define_defresult(Evaluator *x, char *text); 213 void define_type(Evaluator *x, char *text); 214 char* get_defresult(Evaluator *x); 215 char* get_result_type(Evaluator *x); 216 void eval_initialise(void); 217 218 void compress_transition_table(DFANode **dfas, int ndfas, int ntokens); 219 unsigned long increment(unsigned long x, int field); 220 unsigned long count_bits_set(unsigned long x); 221 222 /* Return new number of DFA states */ 223 int compress_dfa(DFANode **dfas, int ndfas, int ntokens); 224 225 #endif /* N2D_H */ 226 227