![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dfa.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / lex|
Return to dfa.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / lex |
1.1 root 1: /*-
2: * Copyright (c) 1990 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * This code is derived from software contributed to Berkeley by
6: * Vern Paxson.
7: *
8: * The United States Government has rights in this work pursuant
9: * to contract no. DE-AC03-76SF00098 between the United States
10: * Department of Energy and the University of California.
11: *
12: * Redistribution and use in source and binary forms are permitted provided
13: * that: (1) source distributions retain this entire copyright notice and
14: * comment, and (2) distributions including binaries display the following
15: * acknowledgement: ``This product includes software developed by the
16: * University of California, Berkeley and its contributors'' in the
17: * documentation or other materials provided with the distribution and in
18: * all advertising materials mentioning features or use of this software.
19: * Neither the name of the University nor the names of its contributors may
20: * be used to endorse or promote products derived from this software without
21: * specific prior written permission.
22: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
23: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
24: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
25: */
26:
27: #ifndef lint
28: static char sccsid[] = "@(#)dfa.c 5.2 (Berkeley) 6/18/90";
29: #endif /* not lint */
30:
31: /* dfa - DFA construction routines */
32:
33: #include "flexdef.h"
34:
35: /* declare functions that have forward references */
36:
37: void dump_associated_rules PROTO((FILE*, int));
38: void dump_transitions PROTO((FILE*, int[]));
39: void sympartition PROTO((int[], int, int[], int[]));
40: int symfollowset PROTO((int[], int, int, int[]));
41:
42:
43: /* check_for_backtracking - check a DFA state for backtracking
44: *
45: * synopsis
46: * int ds, state[numecs];
47: * check_for_backtracking( ds, state );
48: *
49: * ds is the number of the state to check and state[] is its out-transitions,
50: * indexed by equivalence class, and state_rules[] is the set of rules
51: * associated with this state
52: */
53:
54: void check_for_backtracking( ds, state )
55: int ds;
56: int state[];
57:
58: {
59: if ( (reject && ! dfaacc[ds].dfaacc_set) || ! dfaacc[ds].dfaacc_state )
60: { /* state is non-accepting */
61: ++num_backtracking;
62:
63: if ( backtrack_report )
64: {
65: fprintf( backtrack_file, "State #%d is non-accepting -\n", ds );
66:
67: /* identify the state */
68: dump_associated_rules( backtrack_file, ds );
69:
70: /* now identify it further using the out- and jam-transitions */
71: dump_transitions( backtrack_file, state );
72:
73: putc( '\n', backtrack_file );
74: }
75: }
76: }
77:
78:
79: /* check_trailing_context - check to see if NFA state set constitutes
80: * "dangerous" trailing context
81: *
82: * synopsis
83: * int nfa_states[num_states+1], num_states;
84: * int accset[nacc+1], nacc;
85: * check_trailing_context( nfa_states, num_states, accset, nacc );
86: *
87: * NOTES
88: * Trailing context is "dangerous" if both the head and the trailing
89: * part are of variable size \and/ there's a DFA state which contains
90: * both an accepting state for the head part of the rule and NFA states
91: * which occur after the beginning of the trailing context.
92: * When such a rule is matched, it's impossible to tell if having been
93: * in the DFA state indicates the beginning of the trailing context
94: * or further-along scanning of the pattern. In these cases, a warning
95: * message is issued.
96: *
97: * nfa_states[1 .. num_states] is the list of NFA states in the DFA.
98: * accset[1 .. nacc] is the list of accepting numbers for the DFA state.
99: */
100:
101: void check_trailing_context( nfa_states, num_states, accset, nacc )
102: int *nfa_states, num_states;
103: int *accset;
104: register int nacc;
105:
106: {
107: register int i, j;
108:
109: for ( i = 1; i <= num_states; ++i )
110: {
111: int ns = nfa_states[i];
112: register int type = state_type[ns];
113: register int ar = assoc_rule[ns];
114:
115: if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE )
116: { /* do nothing */
117: }
118:
119: else if ( type == STATE_TRAILING_CONTEXT )
120: {
121: /* potential trouble. Scan set of accepting numbers for
122: * the one marking the end of the "head". We assume that
123: * this looping will be fairly cheap since it's rare that
124: * an accepting number set is large.
125: */
126: for ( j = 1; j <= nacc; ++j )
127: if ( accset[j] & YY_TRAILING_HEAD_MASK )
128: {
129: fprintf( stderr,
130: "%s: Dangerous trailing context in rule at line %d\n",
131: program_name, rule_linenum[ar] );
132: return;
133: }
134: }
135: }
136: }
137:
138:
139: /* dump_associated_rules - list the rules associated with a DFA state
140: *
141: * synopisis
142: * int ds;
143: * FILE *file;
144: * dump_associated_rules( file, ds );
145: *
146: * goes through the set of NFA states associated with the DFA and
147: * extracts the first MAX_ASSOC_RULES unique rules, sorts them,
148: * and writes a report to the given file
149: */
150:
151: void dump_associated_rules( file, ds )
152: FILE *file;
153: int ds;
154:
155: {
156: register int i, j;
157: register int num_associated_rules = 0;
158: int rule_set[MAX_ASSOC_RULES + 1];
159: int *dset = dss[ds];
160: int size = dfasiz[ds];
161:
162: for ( i = 1; i <= size; ++i )
163: {
164: register rule_num = rule_linenum[assoc_rule[dset[i]]];
165:
166: for ( j = 1; j <= num_associated_rules; ++j )
167: if ( rule_num == rule_set[j] )
168: break;
169:
170: if ( j > num_associated_rules )
171: { /* new rule */
172: if ( num_associated_rules < MAX_ASSOC_RULES )
173: rule_set[++num_associated_rules] = rule_num;
174: }
175: }
176:
177: bubble( rule_set, num_associated_rules );
178:
179: fprintf( file, " associated rule line numbers:" );
180:
181: for ( i = 1; i <= num_associated_rules; ++i )
182: {
183: if ( i % 8 == 1 )
184: putc( '\n', file );
185:
186: fprintf( file, "\t%d", rule_set[i] );
187: }
188:
189: putc( '\n', file );
190: }
191:
192:
193: /* dump_transitions - list the transitions associated with a DFA state
194: *
195: * synopisis
196: * int state[numecs];
197: * FILE *file;
198: * dump_transitions( file, state );
199: *
200: * goes through the set of out-transitions and lists them in human-readable
201: * form (i.e., not as equivalence classes); also lists jam transitions
202: * (i.e., all those which are not out-transitions, plus EOF). The dump
203: * is done to the given file.
204: */
205:
206: void dump_transitions( file, state )
207: FILE *file;
208: int state[];
209:
210: {
211: register int i, ec;
212: int out_char_set[CSIZE];
213:
214: for ( i = 0; i < csize; ++i )
215: {
216: ec = abs( ecgroup[i] );
217: out_char_set[i] = state[ec];
218: }
219:
220: fprintf( file, " out-transitions: " );
221:
222: list_character_set( file, out_char_set );
223:
224: /* now invert the members of the set to get the jam transitions */
225: for ( i = 0; i < csize; ++i )
226: out_char_set[i] = ! out_char_set[i];
227:
228: fprintf( file, "\n jam-transitions: EOF " );
229:
230: list_character_set( file, out_char_set );
231:
232: putc( '\n', file );
233: }
234:
235:
236: /* epsclosure - construct the epsilon closure of a set of ndfa states
237: *
238: * synopsis
239: * int t[current_max_dfa_size], numstates, accset[num_rules + 1], nacc;
240: * int hashval;
241: * int *epsclosure();
242: * t = epsclosure( t, &numstates, accset, &nacc, &hashval );
243: *
244: * NOTES
245: * the epsilon closure is the set of all states reachable by an arbitrary
246: * number of epsilon transitions which themselves do not have epsilon
247: * transitions going out, unioned with the set of states which have non-null
248: * accepting numbers. t is an array of size numstates of nfa state numbers.
249: * Upon return, t holds the epsilon closure and numstates is updated. accset
250: * holds a list of the accepting numbers, and the size of accset is given
251: * by nacc. t may be subjected to reallocation if it is not large enough
252: * to hold the epsilon closure.
253: *
254: * hashval is the hash value for the dfa corresponding to the state set
255: */
256:
257: int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
258: int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
259:
260: {
261: register int stkpos, ns, tsp;
262: int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
263: int stkend, nstate;
264: static int did_stk_init = false, *stk;
265:
266: #define MARK_STATE(state) \
267: trans1[state] = trans1[state] - MARKER_DIFFERENCE;
268:
269: #define IS_MARKED(state) (trans1[state] < 0)
270:
271: #define UNMARK_STATE(state) \
272: trans1[state] = trans1[state] + MARKER_DIFFERENCE;
273:
274: #define CHECK_ACCEPT(state) \
275: { \
276: nfaccnum = accptnum[state]; \
277: if ( nfaccnum != NIL ) \
278: accset[++nacc] = nfaccnum; \
279: }
280:
281: #define DO_REALLOCATION \
282: { \
283: current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
284: ++num_reallocs; \
285: t = reallocate_integer_array( t, current_max_dfa_size ); \
286: stk = reallocate_integer_array( stk, current_max_dfa_size ); \
287: } \
288:
289: #define PUT_ON_STACK(state) \
290: { \
291: if ( ++stkend >= current_max_dfa_size ) \
292: DO_REALLOCATION \
293: stk[stkend] = state; \
294: MARK_STATE(state) \
295: }
296:
297: #define ADD_STATE(state) \
298: { \
299: if ( ++numstates >= current_max_dfa_size ) \
300: DO_REALLOCATION \
301: t[numstates] = state; \
302: hashval = hashval + state; \
303: }
304:
305: #define STACK_STATE(state) \
306: { \
307: PUT_ON_STACK(state) \
308: CHECK_ACCEPT(state) \
309: if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
310: ADD_STATE(state) \
311: }
312:
313: if ( ! did_stk_init )
314: {
315: stk = allocate_integer_array( current_max_dfa_size );
316: did_stk_init = true;
317: }
318:
319: nacc = stkend = hashval = 0;
320:
321: for ( nstate = 1; nstate <= numstates; ++nstate )
322: {
323: ns = t[nstate];
324:
325: /* the state could be marked if we've already pushed it onto
326: * the stack
327: */
328: if ( ! IS_MARKED(ns) )
329: PUT_ON_STACK(ns)
330:
331: CHECK_ACCEPT(ns)
332: hashval = hashval + ns;
333: }
334:
335: for ( stkpos = 1; stkpos <= stkend; ++stkpos )
336: {
337: ns = stk[stkpos];
338: transsym = transchar[ns];
339:
340: if ( transsym == SYM_EPSILON )
341: {
342: tsp = trans1[ns] + MARKER_DIFFERENCE;
343:
344: if ( tsp != NO_TRANSITION )
345: {
346: if ( ! IS_MARKED(tsp) )
347: STACK_STATE(tsp)
348:
349: tsp = trans2[ns];
350:
351: if ( tsp != NO_TRANSITION )
352: if ( ! IS_MARKED(tsp) )
353: STACK_STATE(tsp)
354: }
355: }
356: }
357:
358: /* clear out "visit" markers */
359:
360: for ( stkpos = 1; stkpos <= stkend; ++stkpos )
361: {
362: if ( IS_MARKED(stk[stkpos]) )
363: {
364: UNMARK_STATE(stk[stkpos])
365: }
366: else
367: flexfatal( "consistency check failed in epsclosure()" );
368: }
369:
370: *ns_addr = numstates;
371: *hv_addr = hashval;
372: *nacc_addr = nacc;
373:
374: return ( t );
375: }
376:
377:
378: /* increase_max_dfas - increase the maximum number of DFAs */
379:
380: void increase_max_dfas()
381:
382: {
383: current_max_dfas += MAX_DFAS_INCREMENT;
384:
385: ++num_reallocs;
386:
387: base = reallocate_integer_array( base, current_max_dfas );
388: def = reallocate_integer_array( def, current_max_dfas );
389: dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
390: accsiz = reallocate_integer_array( accsiz, current_max_dfas );
391: dhash = reallocate_integer_array( dhash, current_max_dfas );
392: dss = reallocate_int_ptr_array( dss, current_max_dfas );
393: dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
394:
395: if ( nultrans )
396: nultrans = reallocate_integer_array( nultrans, current_max_dfas );
397: }
398:
399:
400: /* ntod - convert an ndfa to a dfa
401: *
402: * synopsis
403: * ntod();
404: *
405: * creates the dfa corresponding to the ndfa we've constructed. the
406: * dfa starts out in state #1.
407: */
408:
409: void ntod()
410:
411: {
412: int *accset, ds, nacc, newds;
413: int sym, hashval, numstates, dsize;
414: int num_full_table_rows; /* used only for -f */
415: int *nset, *dset;
416: int targptr, totaltrans, i, comstate, comfreq, targ;
417: int *epsclosure(), snstods(), symlist[CSIZE + 1];
418: int num_start_states;
419: int todo_head, todo_next;
420:
421: /* note that the following are indexed by *equivalence classes*
422: * and not by characters. Since equivalence classes are indexed
423: * beginning with 1, even if the scanner accepts NUL's, this
424: * means that (since every character is potentially in its own
425: * equivalence class) these arrays must have room for indices
426: * from 1 to CSIZE, so their size must be CSIZE + 1.
427: */
428: int duplist[CSIZE + 1], state[CSIZE + 1];
429: int targfreq[CSIZE + 1], targstate[CSIZE + 1];
430:
431: /* this is so find_table_space(...) will know where to start looking in
432: * chk/nxt for unused records for space to put in the state
433: */
434: if ( fullspd )
435: firstfree = 0;
436:
437: accset = allocate_integer_array( num_rules + 1 );
438: nset = allocate_integer_array( current_max_dfa_size );
439:
440: /* the "todo" queue is represented by the head, which is the DFA
441: * state currently being processed, and the "next", which is the
442: * next DFA state number available (not in use). We depend on the
443: * fact that snstods() returns DFA's \in increasing order/, and thus
444: * need only know the bounds of the dfas to be processed.
445: */
446: todo_head = todo_next = 0;
447:
448: for ( i = 0; i <= csize; ++i )
449: {
450: duplist[i] = NIL;
451: symlist[i] = false;
452: }
453:
454: for ( i = 0; i <= num_rules; ++i )
455: accset[i] = NIL;
456:
457: if ( trace )
458: {
459: dumpnfa( scset[1] );
460: fputs( "\n\nDFA Dump:\n\n", stderr );
461: }
462:
463: inittbl();
464:
465: /* check to see whether we should build a separate table for transitions
466: * on NUL characters. We don't do this for full-speed (-F) scanners,
467: * since for them we don't have a simple state number lying around with
468: * which to index the table. We also don't bother doing it for scanners
469: * unless (1) NUL is in its own equivalence class (indicated by a
470: * positive value of ecgroup[NUL]), (2) NUL's equilvalence class is
471: * the last equivalence class, and (3) the number of equivalence classes
472: * is the same as the number of characters. This latter case comes about
473: * when useecs is false or when its true but every character still
474: * manages to land in its own class (unlikely, but it's cheap to check
475: * for). If all these things are true then the character code needed
476: * to represent NUL's equivalence class for indexing the tables is
477: * going to take one more bit than the number of characters, and therefore
478: * we won't be assured of being able to fit it into a YY_CHAR variable.
479: * This rules out storing the transitions in a compressed table, since
480: * the code for interpreting them uses a YY_CHAR variable (perhaps it
481: * should just use an integer, though; this is worth pondering ... ###).
482: *
483: * Finally, for full tables, we want the number of entries in the
484: * table to be a power of two so the array references go fast (it
485: * will just take a shift to compute the major index). If encoding
486: * NUL's transitions in the table will spoil this, we give it its
487: * own table (note that this will be the case if we're not using
488: * equivalence classes).
489: */
490:
491: /* note that the test for ecgroup[0] == numecs below accomplishes
492: * both (1) and (2) above
493: */
494: if ( ! fullspd && ecgroup[0] == numecs )
495: { /* NUL is alone in its equivalence class, which is the last one */
496: int use_NUL_table = (numecs == csize);
497:
498: if ( fulltbl && ! use_NUL_table )
499: { /* we still may want to use the table if numecs is a power of 2 */
500: int power_of_two;
501:
502: for ( power_of_two = 1; power_of_two <= csize; power_of_two *= 2 )
503: if ( numecs == power_of_two )
504: {
505: use_NUL_table = true;
506: break;
507: }
508: }
509:
510: if ( use_NUL_table )
511: nultrans = allocate_integer_array( current_max_dfas );
512: /* from now on, nultrans != nil indicates that we're
513: * saving null transitions for later, separate encoding
514: */
515: }
516:
517:
518: if ( fullspd )
519: {
520: for ( i = 0; i <= numecs; ++i )
521: state[i] = 0;
522: place_state( state, 0, 0 );
523: }
524:
525: else if ( fulltbl )
526: {
527: if ( nultrans )
528: /* we won't be including NUL's transitions in the table,
529: * so build it for entries from 0 .. numecs - 1
530: */
531: num_full_table_rows = numecs;
532:
533: else
534: /* take into account the fact that we'll be including
535: * the NUL entries in the transition table. Build it
536: * from 0 .. numecs.
537: */
538: num_full_table_rows = numecs + 1;
539:
540: /* declare it "short" because it's a real long-shot that that
541: * won't be large enough.
542: */
543: printf( "static short int yy_nxt[][%d] =\n {\n",
544: /* '}' so vi doesn't get too confused */
545: num_full_table_rows );
546:
547: /* generate 0 entries for state #0 */
548: for ( i = 0; i < num_full_table_rows; ++i )
549: mk2data( 0 );
550:
551: /* force ',' and dataflush() next call to mk2data */
552: datapos = NUMDATAITEMS;
553:
554: /* force extra blank line next dataflush() */
555: dataline = NUMDATALINES;
556: }
557:
558: /* create the first states */
559:
560: num_start_states = lastsc * 2;
561:
562: for ( i = 1; i <= num_start_states; ++i )
563: {
564: numstates = 1;
565:
566: /* for each start condition, make one state for the case when
567: * we're at the beginning of the line (the '%' operator) and
568: * one for the case when we're not
569: */
570: if ( i % 2 == 1 )
571: nset[numstates] = scset[(i / 2) + 1];
572: else
573: nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] );
574:
575: nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
576:
577: if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
578: {
579: numas += nacc;
580: totnst += numstates;
581: ++todo_next;
582:
583: if ( variable_trailing_context_rules && nacc > 0 )
584: check_trailing_context( nset, numstates, accset, nacc );
585: }
586: }
587:
588: if ( ! fullspd )
589: {
590: if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
591: flexfatal( "could not create unique end-of-buffer state" );
592:
593: ++numas;
594: ++num_start_states;
595: ++todo_next;
596: }
597:
598: while ( todo_head < todo_next )
599: {
600: targptr = 0;
601: totaltrans = 0;
602:
603: for ( i = 1; i <= numecs; ++i )
604: state[i] = 0;
605:
606: ds = ++todo_head;
607:
608: dset = dss[ds];
609: dsize = dfasiz[ds];
610:
611: if ( trace )
612: fprintf( stderr, "state # %d:\n", ds );
613:
614: sympartition( dset, dsize, symlist, duplist );
615:
616: for ( sym = 1; sym <= numecs; ++sym )
617: {
618: if ( symlist[sym] )
619: {
620: symlist[sym] = 0;
621:
622: if ( duplist[sym] == NIL )
623: { /* symbol has unique out-transitions */
624: numstates = symfollowset( dset, dsize, sym, nset );
625: nset = epsclosure( nset, &numstates, accset,
626: &nacc, &hashval );
627:
628: if ( snstods( nset, numstates, accset,
629: nacc, hashval, &newds ) )
630: {
631: totnst = totnst + numstates;
632: ++todo_next;
633: numas += nacc;
634:
635: if ( variable_trailing_context_rules && nacc > 0 )
636: check_trailing_context( nset, numstates,
637: accset, nacc );
638: }
639:
640: state[sym] = newds;
641:
642: if ( trace )
643: fprintf( stderr, "\t%d\t%d\n", sym, newds );
644:
645: targfreq[++targptr] = 1;
646: targstate[targptr] = newds;
647: ++numuniq;
648: }
649:
650: else
651: {
652: /* sym's equivalence class has the same transitions
653: * as duplist(sym)'s equivalence class
654: */
655: targ = state[duplist[sym]];
656: state[sym] = targ;
657:
658: if ( trace )
659: fprintf( stderr, "\t%d\t%d\n", sym, targ );
660:
661: /* update frequency count for destination state */
662:
663: i = 0;
664: while ( targstate[++i] != targ )
665: ;
666:
667: ++targfreq[i];
668: ++numdup;
669: }
670:
671: ++totaltrans;
672: duplist[sym] = NIL;
673: }
674: }
675:
676: numsnpairs = numsnpairs + totaltrans;
677:
678: if ( caseins && ! useecs )
679: {
680: register int j;
681:
682: for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
683: state[i] = state[j];
684: }
685:
686: if ( ds > num_start_states )
687: check_for_backtracking( ds, state );
688:
689: if ( nultrans )
690: {
691: nultrans[ds] = state[NUL_ec];
692: state[NUL_ec] = 0; /* remove transition */
693: }
694:
695: if ( fulltbl )
696: {
697: /* supply array's 0-element */
698: if ( ds == end_of_buffer_state )
699: mk2data( -end_of_buffer_state );
700: else
701: mk2data( end_of_buffer_state );
702:
703: for ( i = 1; i < num_full_table_rows; ++i )
704: /* jams are marked by negative of state number */
705: mk2data( state[i] ? state[i] : -ds );
706:
707: /* force ',' and dataflush() next call to mk2data */
708: datapos = NUMDATAITEMS;
709:
710: /* force extra blank line next dataflush() */
711: dataline = NUMDATALINES;
712: }
713:
714: else if ( fullspd )
715: place_state( state, ds, totaltrans );
716:
717: else if ( ds == end_of_buffer_state )
718: /* special case this state to make sure it does what it's
719: * supposed to, i.e., jam on end-of-buffer
720: */
721: stack1( ds, 0, 0, JAMSTATE );
722:
723: else /* normal, compressed state */
724: {
725: /* determine which destination state is the most common, and
726: * how many transitions to it there are
727: */
728:
729: comfreq = 0;
730: comstate = 0;
731:
732: for ( i = 1; i <= targptr; ++i )
733: if ( targfreq[i] > comfreq )
734: {
735: comfreq = targfreq[i];
736: comstate = targstate[i];
737: }
738:
739: bldtbl( state, ds, totaltrans, comstate, comfreq );
740: }
741: }
742:
743: if ( fulltbl )
744: dataend();
745:
746: else if ( ! fullspd )
747: {
748: cmptmps(); /* create compressed template entries */
749:
750: /* create tables for all the states with only one out-transition */
751: while ( onesp > 0 )
752: {
753: mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
754: onedef[onesp] );
755: --onesp;
756: }
757:
758: mkdeftbl();
759: }
760: }
761:
762:
763: /* snstods - converts a set of ndfa states into a dfa state
764: *
765: * synopsis
766: * int sns[numstates], numstates, newds, accset[num_rules + 1], nacc, hashval;
767: * int snstods();
768: * is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
769: *
770: * on return, the dfa state number is in newds.
771: */
772:
773: int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
774: int sns[], numstates, accset[], nacc, hashval, *newds_addr;
775:
776: {
777: int didsort = 0;
778: register int i, j;
779: int newds, *oldsns;
780:
781: for ( i = 1; i <= lastdfa; ++i )
782: if ( hashval == dhash[i] )
783: {
784: if ( numstates == dfasiz[i] )
785: {
786: oldsns = dss[i];
787:
788: if ( ! didsort )
789: {
790: /* we sort the states in sns so we can compare it to
791: * oldsns quickly. we use bubble because there probably
792: * aren't very many states
793: */
794: bubble( sns, numstates );
795: didsort = 1;
796: }
797:
798: for ( j = 1; j <= numstates; ++j )
799: if ( sns[j] != oldsns[j] )
800: break;
801:
802: if ( j > numstates )
803: {
804: ++dfaeql;
805: *newds_addr = i;
806: return ( 0 );
807: }
808:
809: ++hshcol;
810: }
811:
812: else
813: ++hshsave;
814: }
815:
816: /* make a new dfa */
817:
818: if ( ++lastdfa >= current_max_dfas )
819: increase_max_dfas();
820:
821: newds = lastdfa;
822:
823: dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) );
824:
825: if ( ! dss[newds] )
826: flexfatal( "dynamic memory failure in snstods()" );
827:
828: /* if we haven't already sorted the states in sns, we do so now, so that
829: * future comparisons with it can be made quickly
830: */
831:
832: if ( ! didsort )
833: bubble( sns, numstates );
834:
835: for ( i = 1; i <= numstates; ++i )
836: dss[newds][i] = sns[i];
837:
838: dfasiz[newds] = numstates;
839: dhash[newds] = hashval;
840:
841: if ( nacc == 0 )
842: {
843: if ( reject )
844: dfaacc[newds].dfaacc_set = (int *) 0;
845: else
846: dfaacc[newds].dfaacc_state = 0;
847:
848: accsiz[newds] = 0;
849: }
850:
851: else if ( reject )
852: {
853: /* we sort the accepting set in increasing order so the disambiguating
854: * rule that the first rule listed is considered match in the event of
855: * ties will work. We use a bubble sort since the list is probably
856: * quite small.
857: */
858:
859: bubble( accset, nacc );
860:
861: dfaacc[newds].dfaacc_set =
862: (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );
863:
864: if ( ! dfaacc[newds].dfaacc_set )
865: flexfatal( "dynamic memory failure in snstods()" );
866:
867: /* save the accepting set for later */
868: for ( i = 1; i <= nacc; ++i )
869: dfaacc[newds].dfaacc_set[i] = accset[i];
870:
871: accsiz[newds] = nacc;
872: }
873:
874: else
875: { /* find lowest numbered rule so the disambiguating rule will work */
876: j = num_rules + 1;
877:
878: for ( i = 1; i <= nacc; ++i )
879: if ( accset[i] < j )
880: j = accset[i];
881:
882: dfaacc[newds].dfaacc_state = j;
883: }
884:
885: *newds_addr = newds;
886:
887: return ( 1 );
888: }
889:
890:
891: /* symfollowset - follow the symbol transitions one step
892: *
893: * synopsis
894: * int ds[current_max_dfa_size], dsize, transsym;
895: * int nset[current_max_dfa_size], numstates;
896: * numstates = symfollowset( ds, dsize, transsym, nset );
897: */
898:
899: int symfollowset( ds, dsize, transsym, nset )
900: int ds[], dsize, transsym, nset[];
901:
902: {
903: int ns, tsp, sym, i, j, lenccl, ch, numstates;
904: int ccllist;
905:
906: numstates = 0;
907:
908: for ( i = 1; i <= dsize; ++i )
909: { /* for each nfa state ns in the state set of ds */
910: ns = ds[i];
911: sym = transchar[ns];
912: tsp = trans1[ns];
913:
914: if ( sym < 0 )
915: { /* it's a character class */
916: sym = -sym;
917: ccllist = cclmap[sym];
918: lenccl = ccllen[sym];
919:
920: if ( cclng[sym] )
921: {
922: for ( j = 0; j < lenccl; ++j )
923: { /* loop through negated character class */
924: ch = ccltbl[ccllist + j];
925:
926: if ( ch == 0 )
927: ch = NUL_ec;
928:
929: if ( ch > transsym )
930: break; /* transsym isn't in negated ccl */
931:
932: else if ( ch == transsym )
933: /* next 2 */ goto bottom;
934: }
935:
936: /* didn't find transsym in ccl */
937: nset[++numstates] = tsp;
938: }
939:
940: else
941: for ( j = 0; j < lenccl; ++j )
942: {
943: ch = ccltbl[ccllist + j];
944:
945: if ( ch == 0 )
946: ch = NUL_ec;
947:
948: if ( ch > transsym )
949: break;
950:
951: else if ( ch == transsym )
952: {
953: nset[++numstates] = tsp;
954: break;
955: }
956: }
957: }
958:
959: else if ( sym >= 'A' && sym <= 'Z' && caseins )
960: flexfatal( "consistency check failed in symfollowset" );
961:
962: else if ( sym == SYM_EPSILON )
963: { /* do nothing */
964: }
965:
966: else if ( abs( ecgroup[sym] ) == transsym )
967: nset[++numstates] = tsp;
968:
969: bottom:
970: ;
971: }
972:
973: return ( numstates );
974: }
975:
976:
977: /* sympartition - partition characters with same out-transitions
978: *
979: * synopsis
980: * integer ds[current_max_dfa_size], numstates, duplist[numecs];
981: * symlist[numecs];
982: * sympartition( ds, numstates, symlist, duplist );
983: */
984:
985: void sympartition( ds, numstates, symlist, duplist )
986: int ds[], numstates, duplist[];
987: int symlist[];
988:
989: {
990: int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
991:
992: /* partitioning is done by creating equivalence classes for those
993: * characters which have out-transitions from the given state. Thus
994: * we are really creating equivalence classes of equivalence classes.
995: */
996:
997: for ( i = 1; i <= numecs; ++i )
998: { /* initialize equivalence class list */
999: duplist[i] = i - 1;
1000: dupfwd[i] = i + 1;
1001: }
1002:
1003: duplist[1] = NIL;
1004: dupfwd[numecs] = NIL;
1005:
1006: for ( i = 1; i <= numstates; ++i )
1007: {
1008: ns = ds[i];
1009: tch = transchar[ns];
1010:
1011: if ( tch != SYM_EPSILON )
1012: {
1013: if ( tch < -lastccl || tch > csize )
1014: {
1015: if ( tch > csize && tch <= CSIZE )
1016: flexerror( "scanner requires -8 flag" );
1017:
1018: else
1019: flexfatal(
1020: "bad transition character detected in sympartition()" );
1021: }
1022:
1023: if ( tch >= 0 )
1024: { /* character transition */
1025: /* abs() needed for fake %t ec's */
1026: int ec = abs( ecgroup[tch] );
1027:
1028: mkechar( ec, dupfwd, duplist );
1029: symlist[ec] = 1;
1030: }
1031:
1032: else
1033: { /* character class */
1034: tch = -tch;
1035:
1036: lenccl = ccllen[tch];
1037: cclp = cclmap[tch];
1038: mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs,
1039: NUL_ec );
1040:
1041: if ( cclng[tch] )
1042: {
1043: j = 0;
1044:
1045: for ( k = 0; k < lenccl; ++k )
1046: {
1047: ich = ccltbl[cclp + k];
1048:
1049: if ( ich == 0 )
1050: ich = NUL_ec;
1051:
1052: for ( ++j; j < ich; ++j )
1053: symlist[j] = 1;
1054: }
1055:
1056: for ( ++j; j <= numecs; ++j )
1057: symlist[j] = 1;
1058: }
1059:
1060: else
1061: for ( k = 0; k < lenccl; ++k )
1062: {
1063: ich = ccltbl[cclp + k];
1064:
1065: if ( ich == 0 )
1066: ich = NUL_ec;
1067:
1068: symlist[ich] = 1;
1069: }
1070: }
1071: }
1072: }
1073: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.