dfa.c (99112) | dfa.c (179549) |
---|---|
1/* dfa - DFA construction routines */ 2 3/*- 4 * Copyright (c) 1990 The Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Vern Paxson. --- 14 unchanged lines hidden (view full) --- 23 * specific prior written permission. 24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 27 */ 28 29/* $Header: /home/daffy/u0/vern/flex/RCS/dfa.c,v 2.26 95/04/20 13:53:14 vern Exp $ */ 30#include <sys/cdefs.h> | 1/* dfa - DFA construction routines */ 2 3/*- 4 * Copyright (c) 1990 The Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Vern Paxson. --- 14 unchanged lines hidden (view full) --- 23 * specific prior written permission. 24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 27 */ 28 29/* $Header: /home/daffy/u0/vern/flex/RCS/dfa.c,v 2.26 95/04/20 13:53:14 vern Exp $ */ 30#include <sys/cdefs.h> |
31__FBSDID("$FreeBSD: head/usr.bin/lex/dfa.c 99112 2002-06-30 05:25:07Z obrien $"); | 31__FBSDID("$FreeBSD: head/usr.bin/lex/dfa.c 179549 2008-06-04 19:50:34Z dwmalone $"); |
32 33#include "flexdef.h" 34 35 36/* declare functions that have forward references */ 37 38void dump_associated_rules PROTO((FILE*, int)); 39void dump_transitions PROTO((FILE*, int[])); --- 60 unchanged lines hidden (view full) --- 100 * accset[1 .. nacc] is the list of accepting numbers for the DFA state. 101 */ 102 103void check_trailing_context( nfa_states, num_states, accset, nacc ) 104int *nfa_states, num_states; 105int *accset; 106int nacc; 107 { | 32 33#include "flexdef.h" 34 35 36/* declare functions that have forward references */ 37 38void dump_associated_rules PROTO((FILE*, int)); 39void dump_transitions PROTO((FILE*, int[])); --- 60 unchanged lines hidden (view full) --- 100 * accset[1 .. nacc] is the list of accepting numbers for the DFA state. 101 */ 102 103void check_trailing_context( nfa_states, num_states, accset, nacc ) 104int *nfa_states, num_states; 105int *accset; 106int nacc; 107 { |
108 register int i, j; | 108 int i, j; |
109 110 for ( i = 1; i <= num_states; ++i ) 111 { 112 int ns = nfa_states[i]; | 109 110 for ( i = 1; i <= num_states; ++i ) 111 { 112 int ns = nfa_states[i]; |
113 register int type = state_type[ns]; 114 register int ar = assoc_rule[ns]; | 113 int type = state_type[ns]; 114 int ar = assoc_rule[ns]; |
115 116 if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE ) 117 { /* do nothing */ 118 } 119 120 else if ( type == STATE_TRAILING_CONTEXT ) 121 { 122 /* Potential trouble. Scan set of accepting numbers --- 21 unchanged lines hidden (view full) --- 144 * extracts the first MAX_ASSOC_RULES unique rules, sorts them, 145 * and writes a report to the given file. 146 */ 147 148void dump_associated_rules( file, ds ) 149FILE *file; 150int ds; 151 { | 115 116 if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE ) 117 { /* do nothing */ 118 } 119 120 else if ( type == STATE_TRAILING_CONTEXT ) 121 { 122 /* Potential trouble. Scan set of accepting numbers --- 21 unchanged lines hidden (view full) --- 144 * extracts the first MAX_ASSOC_RULES unique rules, sorts them, 145 * and writes a report to the given file. 146 */ 147 148void dump_associated_rules( file, ds ) 149FILE *file; 150int ds; 151 { |
152 register int i, j; 153 register int num_associated_rules = 0; | 152 int i, j; 153 int num_associated_rules = 0; |
154 int rule_set[MAX_ASSOC_RULES + 1]; 155 int *dset = dss[ds]; 156 int size = dfasiz[ds]; 157 158 for ( i = 1; i <= size; ++i ) 159 { | 154 int rule_set[MAX_ASSOC_RULES + 1]; 155 int *dset = dss[ds]; 156 int size = dfasiz[ds]; 157 158 for ( i = 1; i <= size; ++i ) 159 { |
160 register int rule_num = rule_linenum[assoc_rule[dset[i]]]; | 160 int rule_num = rule_linenum[assoc_rule[dset[i]]]; |
161 162 for ( j = 1; j <= num_associated_rules; ++j ) 163 if ( rule_num == rule_set[j] ) 164 break; 165 166 if ( j > num_associated_rules ) 167 { /* new rule */ 168 if ( num_associated_rules < MAX_ASSOC_RULES ) --- 27 unchanged lines hidden (view full) --- 196 * (i.e., all those which are not out-transitions, plus EOF). The dump 197 * is done to the given file. 198 */ 199 200void dump_transitions( file, state ) 201FILE *file; 202int state[]; 203 { | 161 162 for ( j = 1; j <= num_associated_rules; ++j ) 163 if ( rule_num == rule_set[j] ) 164 break; 165 166 if ( j > num_associated_rules ) 167 { /* new rule */ 168 if ( num_associated_rules < MAX_ASSOC_RULES ) --- 27 unchanged lines hidden (view full) --- 196 * (i.e., all those which are not out-transitions, plus EOF). The dump 197 * is done to the given file. 198 */ 199 200void dump_transitions( file, state ) 201FILE *file; 202int state[]; 203 { |
204 register int i, ec; | 204 int i, ec; |
205 int out_char_set[CSIZE]; 206 207 for ( i = 0; i < csize; ++i ) 208 { 209 ec = ABS( ecgroup[i] ); 210 out_char_set[i] = state[ec]; 211 } 212 --- 31 unchanged lines hidden (view full) --- 244 * large enough to hold the epsilon closure. 245 * 246 * hashval is the hash value for the dfa corresponding to the state set. 247 */ 248 249int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr ) 250int *t, *ns_addr, accset[], *nacc_addr, *hv_addr; 251 { | 205 int out_char_set[CSIZE]; 206 207 for ( i = 0; i < csize; ++i ) 208 { 209 ec = ABS( ecgroup[i] ); 210 out_char_set[i] = state[ec]; 211 } 212 --- 31 unchanged lines hidden (view full) --- 244 * large enough to hold the epsilon closure. 245 * 246 * hashval is the hash value for the dfa corresponding to the state set. 247 */ 248 249int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr ) 250int *t, *ns_addr, accset[], *nacc_addr, *hv_addr; 251 { |
252 register int stkpos, ns, tsp; | 252 int stkpos, ns, tsp; |
253 int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum; 254 int stkend, nstate; 255 static int did_stk_init = false, *stk; 256 257#define MARK_STATE(state) \ 258trans1[state] = trans1[state] - MARKER_DIFFERENCE; 259 260#define IS_MARKED(state) (trans1[state] < 0) --- 415 unchanged lines hidden (view full) --- 676 677 ++totaltrans; 678 duplist[sym] = NIL; 679 } 680 } 681 682 if ( caseins && ! useecs ) 683 { | 253 int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum; 254 int stkend, nstate; 255 static int did_stk_init = false, *stk; 256 257#define MARK_STATE(state) \ 258trans1[state] = trans1[state] - MARKER_DIFFERENCE; 259 260#define IS_MARKED(state) (trans1[state] < 0) --- 415 unchanged lines hidden (view full) --- 676 677 ++totaltrans; 678 duplist[sym] = NIL; 679 } 680 } 681 682 if ( caseins && ! useecs ) 683 { |
684 register int j; | 684 int j; |
685 686 for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j ) 687 { 688 if ( state[i] == 0 && state[j] != 0 ) 689 /* We're adding a transition. */ 690 ++totaltrans; 691 692 else if ( state[i] != 0 && state[j] == 0 ) --- 98 unchanged lines hidden (view full) --- 791 * 792 * On return, the dfa state number is in newds. 793 */ 794 795int snstods( sns, numstates, accset, nacc, hashval, newds_addr ) 796int sns[], numstates, accset[], nacc, hashval, *newds_addr; 797 { 798 int didsort = 0; | 685 686 for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j ) 687 { 688 if ( state[i] == 0 && state[j] != 0 ) 689 /* We're adding a transition. */ 690 ++totaltrans; 691 692 else if ( state[i] != 0 && state[j] == 0 ) --- 98 unchanged lines hidden (view full) --- 791 * 792 * On return, the dfa state number is in newds. 793 */ 794 795int snstods( sns, numstates, accset, nacc, hashval, newds_addr ) 796int sns[], numstates, accset[], nacc, hashval, *newds_addr; 797 { 798 int didsort = 0; |
799 register int i, j; | 799 int i, j; |
800 int newds, *oldsns; 801 802 for ( i = 1; i <= lastdfa; ++i ) 803 if ( hashval == dhash[i] ) 804 { 805 if ( numstates == dfasiz[i] ) 806 { 807 oldsns = dss[i]; --- 290 unchanged lines hidden --- | 800 int newds, *oldsns; 801 802 for ( i = 1; i <= lastdfa; ++i ) 803 if ( hashval == dhash[i] ) 804 { 805 if ( numstates == dfasiz[i] ) 806 { 807 oldsns = dss[i]; --- 290 unchanged lines hidden --- |