Deleted Added
sdiff udiff text old ( 8874 ) new ( 16519 )
full compact
dfa.c (8874) dfa.c (16519)
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.
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.
9 *
9 *
10 * The United States Government has rights in this work pursuant
11 * to contract no. DE-AC03-76SF00098 between the United States
12 * Department of Energy and the University of California.
13 *
14 * Redistribution and use in source and binary forms are permitted provided
15 * that: (1) source distributions retain this entire copyright notice and
16 * comment, and (2) distributions including binaries display the following
17 * acknowledgement: ``This product includes software developed by the
18 * University of California, Berkeley and its contributors'' in the
19 * documentation or other materials provided with the distribution and in
20 * all advertising materials mentioning features or use of this software.
21 * Neither the name of the University nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
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
10 * The United States Government has rights in this work pursuant
11 * to contract no. DE-AC03-76SF00098 between the United States
12 * Department of Energy and the University of California.
13 *
14 * Redistribution and use in source and binary forms are permitted provided
15 * that: (1) source distributions retain this entire copyright notice and
16 * comment, and (2) distributions including binaries display the following
17 * acknowledgement: ``This product includes software developed by the
18 * University of California, Berkeley and its contributors'' in the
19 * documentation or other materials provided with the distribution and in
20 * all advertising materials mentioning features or use of this software.
21 * Neither the name of the University nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
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/ncvs/src/usr.bin/lex/dfa.c,v 1.1.1.1 1994/08/24 13:10:33 csgr Exp $ */
29/* $Header: /home/ncvs/src/usr.bin/lex/dfa.c,v 1.1.1.2 1996/06/19 20:26:04 nate Exp $ */
30
31#include "flexdef.h"
32
33
34/* declare functions that have forward references */
35
36void dump_associated_rules PROTO((FILE*, int));
37void dump_transitions PROTO((FILE*, int[]));

--- 17 unchanged lines hidden (view full) ---

55 if ( (reject && ! dfaacc[ds].dfaacc_set) ||
56 (! reject && ! dfaacc[ds].dfaacc_state) )
57 { /* state is non-accepting */
58 ++num_backing_up;
59
60 if ( backing_up_report )
61 {
62 fprintf( backing_up_file,
30
31#include "flexdef.h"
32
33
34/* declare functions that have forward references */
35
36void dump_associated_rules PROTO((FILE*, int));
37void dump_transitions PROTO((FILE*, int[]));

--- 17 unchanged lines hidden (view full) ---

55 if ( (reject && ! dfaacc[ds].dfaacc_set) ||
56 (! reject && ! dfaacc[ds].dfaacc_state) )
57 { /* state is non-accepting */
58 ++num_backing_up;
59
60 if ( backing_up_report )
61 {
62 fprintf( backing_up_file,
63 "State #%d is non-accepting -\n", ds );
63 _( "State #%d is non-accepting -\n" ), ds );
64
65 /* identify the state */
66 dump_associated_rules( backing_up_file, ds );
67
68 /* Now identify it further using the out- and
69 * jam-transitions.
70 */
71 dump_transitions( backing_up_file, state );

--- 24 unchanged lines hidden (view full) ---

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
101void check_trailing_context( nfa_states, num_states, accset, nacc )
102int *nfa_states, num_states;
103int *accset;
64
65 /* identify the state */
66 dump_associated_rules( backing_up_file, ds );
67
68 /* Now identify it further using the out- and
69 * jam-transitions.
70 */
71 dump_transitions( backing_up_file, state );

--- 24 unchanged lines hidden (view full) ---

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
101void check_trailing_context( nfa_states, num_states, accset, nacc )
102int *nfa_states, num_states;
103int *accset;
104register int nacc;
104int nacc;
105 {
106 register int i, j;
107
108 for ( i = 1; i <= num_states; ++i )
109 {
110 int ns = nfa_states[i];
111 register int type = state_type[ns];
112 register int ar = assoc_rule[ns];

--- 9 unchanged lines hidden (view full) ---

122 * assume that this looping will be fairly cheap
123 * since it's rare that an accepting number set
124 * is large.
125 */
126 for ( j = 1; j <= nacc; ++j )
127 if ( accset[j] & YY_TRAILING_HEAD_MASK )
128 {
129 line_warning(
105 {
106 register int i, j;
107
108 for ( i = 1; i <= num_states; ++i )
109 {
110 int ns = nfa_states[i];
111 register int type = state_type[ns];
112 register int ar = assoc_rule[ns];

--- 9 unchanged lines hidden (view full) ---

122 * assume that this looping will be fairly cheap
123 * since it's rare that an accepting number set
124 * is large.
125 */
126 for ( j = 1; j <= nacc; ++j )
127 if ( accset[j] & YY_TRAILING_HEAD_MASK )
128 {
129 line_warning(
130 "dangerous trailing context",
130 _( "dangerous trailing context" ),
131 rule_linenum[ar] );
132 return;
133 }
134 }
135 }
136 }
137
138

--- 26 unchanged lines hidden (view full) ---

165 { /* new rule */
166 if ( num_associated_rules < MAX_ASSOC_RULES )
167 rule_set[++num_associated_rules] = rule_num;
168 }
169 }
170
171 bubble( rule_set, num_associated_rules );
172
131 rule_linenum[ar] );
132 return;
133 }
134 }
135 }
136 }
137
138

--- 26 unchanged lines hidden (view full) ---

165 { /* new rule */
166 if ( num_associated_rules < MAX_ASSOC_RULES )
167 rule_set[++num_associated_rules] = rule_num;
168 }
169 }
170
171 bubble( rule_set, num_associated_rules );
172
173 fprintf( file, " associated rule line numbers:" );
173 fprintf( file, _( " associated rule line numbers:" ) );
174
175 for ( i = 1; i <= num_associated_rules; ++i )
176 {
177 if ( i % 8 == 1 )
178 putc( '\n', file );
179
180 fprintf( file, "\t%d", rule_set[i] );
181 }

--- 21 unchanged lines hidden (view full) ---

203 int out_char_set[CSIZE];
204
205 for ( i = 0; i < csize; ++i )
206 {
207 ec = ABS( ecgroup[i] );
208 out_char_set[i] = state[ec];
209 }
210
174
175 for ( i = 1; i <= num_associated_rules; ++i )
176 {
177 if ( i % 8 == 1 )
178 putc( '\n', file );
179
180 fprintf( file, "\t%d", rule_set[i] );
181 }

--- 21 unchanged lines hidden (view full) ---

203 int out_char_set[CSIZE];
204
205 for ( i = 0; i < csize; ++i )
206 {
207 ec = ABS( ecgroup[i] );
208 out_char_set[i] = state[ec];
209 }
210
211 fprintf( file, " out-transitions: " );
211 fprintf( file, _( " out-transitions: " ) );
212
213 list_character_set( file, out_char_set );
214
215 /* now invert the members of the set to get the jam transitions */
216 for ( i = 0; i < csize; ++i )
217 out_char_set[i] = ! out_char_set[i];
218
212
213 list_character_set( file, out_char_set );
214
215 /* now invert the members of the set to get the jam transitions */
216 for ( i = 0; i < csize; ++i )
217 out_char_set[i] = ! out_char_set[i];
218
219 fprintf( file, "\n jam-transitions: EOF " );
219 fprintf( file, _( "\n jam-transitions: EOF " ) );
220
221 list_character_set( file, out_char_set );
222
223 putc( '\n', file );
224 }
225
226
227/* epsclosure - construct the epsilon closure of a set of ndfa states

--- 17 unchanged lines hidden (view full) ---

245 */
246
247int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
248int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
249 {
250 register int stkpos, ns, tsp;
251 int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
252 int stkend, nstate;
220
221 list_character_set( file, out_char_set );
222
223 putc( '\n', file );
224 }
225
226
227/* epsclosure - construct the epsilon closure of a set of ndfa states

--- 17 unchanged lines hidden (view full) ---

245 */
246
247int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
248int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
249 {
250 register int stkpos, ns, tsp;
251 int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
252 int stkend, nstate;
253 static int did_stk_init = false, *stk;
253 static int did_stk_init = false, *stk;
254
255#define MARK_STATE(state) \
256trans1[state] = trans1[state] - MARKER_DIFFERENCE;
257
258#define IS_MARKED(state) (trans1[state] < 0)
259
260#define UNMARK_STATE(state) \
261trans1[state] = trans1[state] + MARKER_DIFFERENCE;

--- 85 unchanged lines hidden (view full) ---

347
348 /* Clear out "visit" markers. */
349
350 for ( stkpos = 1; stkpos <= stkend; ++stkpos )
351 {
352 if ( IS_MARKED(stk[stkpos]) )
353 UNMARK_STATE(stk[stkpos])
354 else
254
255#define MARK_STATE(state) \
256trans1[state] = trans1[state] - MARKER_DIFFERENCE;
257
258#define IS_MARKED(state) (trans1[state] < 0)
259
260#define UNMARK_STATE(state) \
261trans1[state] = trans1[state] + MARKER_DIFFERENCE;

--- 85 unchanged lines hidden (view full) ---

347
348 /* Clear out "visit" markers. */
349
350 for ( stkpos = 1; stkpos <= stkend; ++stkpos )
351 {
352 if ( IS_MARKED(stk[stkpos]) )
353 UNMARK_STATE(stk[stkpos])
354 else
355 flexfatal( "consistency check failed in epsclosure()" );
355 flexfatal(
356 _( "consistency check failed in epsclosure()" ) );
356 }
357
358 *ns_addr = numstates;
359 *hv_addr = hashval;
360 *nacc_addr = nacc;
361
362 return t;
363 }

--- 29 unchanged lines hidden (view full) ---

393
394void ntod()
395 {
396 int *accset, ds, nacc, newds;
397 int sym, hashval, numstates, dsize;
398 int num_full_table_rows; /* used only for -f */
399 int *nset, *dset;
400 int targptr, totaltrans, i, comstate, comfreq, targ;
357 }
358
359 *ns_addr = numstates;
360 *hv_addr = hashval;
361 *nacc_addr = nacc;
362
363 return t;
364 }

--- 29 unchanged lines hidden (view full) ---

394
395void ntod()
396 {
397 int *accset, ds, nacc, newds;
398 int sym, hashval, numstates, dsize;
399 int num_full_table_rows; /* used only for -f */
400 int *nset, *dset;
401 int targptr, totaltrans, i, comstate, comfreq, targ;
401 int *epsclosure(), snstods(), symlist[CSIZE + 1];
402 int symlist[CSIZE + 1];
402 int num_start_states;
403 int todo_head, todo_next;
404
405 /* Note that the following are indexed by *equivalence classes*
406 * and not by characters. Since equivalence classes are indexed
407 * beginning with 1, even if the scanner accepts NUL's, this
408 * means that (since every character is potentially in its own
409 * equivalence class) these arrays must have room for indices

--- 20 unchanged lines hidden (view full) ---

430 }
431
432 for ( i = 0; i <= num_rules; ++i )
433 accset[i] = NIL;
434
435 if ( trace )
436 {
437 dumpnfa( scset[1] );
403 int num_start_states;
404 int todo_head, todo_next;
405
406 /* Note that the following are indexed by *equivalence classes*
407 * and not by characters. Since equivalence classes are indexed
408 * beginning with 1, even if the scanner accepts NUL's, this
409 * means that (since every character is potentially in its own
410 * equivalence class) these arrays must have room for indices

--- 20 unchanged lines hidden (view full) ---

431 }
432
433 for ( i = 0; i <= num_rules; ++i )
434 accset[i] = NIL;
435
436 if ( trace )
437 {
438 dumpnfa( scset[1] );
438 fputs( "\n\nDFA Dump:\n\n", stderr );
439 fputs( _( "\n\nDFA Dump:\n\n" ), stderr );
439 }
440
441 inittbl();
442
443 /* Check to see whether we should build a separate table for
444 * transitions on NUL characters. We don't do this for full-speed
445 * (-F) scanners, since for them we don't have a simple state
446 * number lying around with which to index the table. We also

--- 58 unchanged lines hidden (view full) ---

505
506
507 if ( fullspd )
508 {
509 for ( i = 0; i <= numecs; ++i )
510 state[i] = 0;
511
512 place_state( state, 0, 0 );
440 }
441
442 inittbl();
443
444 /* Check to see whether we should build a separate table for
445 * transitions on NUL characters. We don't do this for full-speed
446 * (-F) scanners, since for them we don't have a simple state
447 * number lying around with which to index the table. We also

--- 58 unchanged lines hidden (view full) ---

506
507
508 if ( fullspd )
509 {
510 for ( i = 0; i <= numecs; ++i )
511 state[i] = 0;
512
513 place_state( state, 0, 0 );
513 dfaacc[i].dfaacc_state = 0;
514 dfaacc[0].dfaacc_state = 0;
514 }
515
516 else if ( fulltbl )
517 {
518 if ( nultrans )
519 /* We won't be including NUL's transitions in the
520 * table, so build it for entries from 0 .. numecs - 1.
521 */

--- 4 unchanged lines hidden (view full) ---

526 * the NUL entries in the transition table. Build it
527 * from 0 .. numecs.
528 */
529 num_full_table_rows = numecs + 1;
530
531 /* Unless -Ca, declare it "short" because it's a real
532 * long-shot that that won't be large enough.
533 */
515 }
516
517 else if ( fulltbl )
518 {
519 if ( nultrans )
520 /* We won't be including NUL's transitions in the
521 * table, so build it for entries from 0 .. numecs - 1.
522 */

--- 4 unchanged lines hidden (view full) ---

527 * the NUL entries in the transition table. Build it
528 * from 0 .. numecs.
529 */
530 num_full_table_rows = numecs + 1;
531
532 /* Unless -Ca, declare it "short" because it's a real
533 * long-shot that that won't be large enough.
534 */
534 printf( "static const %s yy_nxt[][%d] =\n {\n",
535 out_str_dec( "static yyconst %s yy_nxt[][%d] =\n {\n",
535 /* '}' so vi doesn't get too confused */
536 long_align ? "long" : "short", num_full_table_rows );
537
536 /* '}' so vi doesn't get too confused */
537 long_align ? "long" : "short", num_full_table_rows );
538
539 outn( " {" );
540
538 /* Generate 0 entries for state #0. */
539 for ( i = 0; i < num_full_table_rows; ++i )
540 mk2data( 0 );
541
541 /* Generate 0 entries for state #0. */
542 for ( i = 0; i < num_full_table_rows; ++i )
543 mk2data( 0 );
544
542 /* Force ',' and dataflush() next call to mk2data().*/
543 datapos = NUMDATAITEMS;
544
545 /* Force extra blank line next dataflush(). */
546 dataline = NUMDATALINES;
545 dataflush();
546 outn( " },\n" );
547 }
548
549 /* Create the first states. */
550
551 num_start_states = lastsc * 2;
552
553 for ( i = 1; i <= num_start_states; ++i )
554 {

--- 22 unchanged lines hidden (view full) ---

577 accset, nacc );
578 }
579 }
580
581 if ( ! fullspd )
582 {
583 if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
584 flexfatal(
547 }
548
549 /* Create the first states. */
550
551 num_start_states = lastsc * 2;
552
553 for ( i = 1; i <= num_start_states; ++i )
554 {

--- 22 unchanged lines hidden (view full) ---

577 accset, nacc );
578 }
579 }
580
581 if ( ! fullspd )
582 {
583 if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
584 flexfatal(
585 "could not create unique end-of-buffer state" );
585 _( "could not create unique end-of-buffer state" ) );
586
587 ++numas;
588 ++num_start_states;
589 ++todo_next;
590 }
591
592 while ( todo_head < todo_next )
593 {

--- 4 unchanged lines hidden (view full) ---

598 state[i] = 0;
599
600 ds = ++todo_head;
601
602 dset = dss[ds];
603 dsize = dfasiz[ds];
604
605 if ( trace )
586
587 ++numas;
588 ++num_start_states;
589 ++todo_next;
590 }
591
592 while ( todo_head < todo_next )
593 {

--- 4 unchanged lines hidden (view full) ---

598 state[i] = 0;
599
600 ds = ++todo_head;
601
602 dset = dss[ds];
603 dsize = dfasiz[ds];
604
605 if ( trace )
606 fprintf( stderr, "state # %d:\n", ds );
606 fprintf( stderr, _( "state # %d:\n" ), ds );
607
608 sympartition( dset, dsize, symlist, duplist );
609
610 for ( sym = 1; sym <= numecs; ++sym )
611 {
612 if ( symlist[sym] )
613 {
614 symlist[sym] = 0;

--- 57 unchanged lines hidden (view full) ---

672 ++numdup;
673 }
674
675 ++totaltrans;
676 duplist[sym] = NIL;
677 }
678 }
679
607
608 sympartition( dset, dsize, symlist, duplist );
609
610 for ( sym = 1; sym <= numecs; ++sym )
611 {
612 if ( symlist[sym] )
613 {
614 symlist[sym] = 0;

--- 57 unchanged lines hidden (view full) ---

672 ++numdup;
673 }
674
675 ++totaltrans;
676 duplist[sym] = NIL;
677 }
678 }
679
680 numsnpairs = numsnpairs + totaltrans;
681
682 if ( caseins && ! useecs )
683 {
684 register int j;
685
686 for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
680 if ( caseins && ! useecs )
681 {
682 register int j;
683
684 for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
685 {
686 if ( state[i] == 0 && state[j] != 0 )
687 /* We're adding a transition. */
688 ++totaltrans;
689
690 else if ( state[i] != 0 && state[j] == 0 )
691 /* We're taking away a transition. */
692 --totaltrans;
693
687 state[i] = state[j];
694 state[i] = state[j];
695 }
688 }
689
696 }
697
698 numsnpairs += totaltrans;
699
690 if ( ds > num_start_states )
691 check_for_backing_up( ds, state );
692
693 if ( nultrans )
694 {
695 nultrans[ds] = state[NUL_ec];
696 state[NUL_ec] = 0; /* remove transition */
697 }
698
699 if ( fulltbl )
700 {
700 if ( ds > num_start_states )
701 check_for_backing_up( ds, state );
702
703 if ( nultrans )
704 {
705 nultrans[ds] = state[NUL_ec];
706 state[NUL_ec] = 0; /* remove transition */
707 }
708
709 if ( fulltbl )
710 {
711 outn( " {" );
712
701 /* Supply array's 0-element. */
702 if ( ds == end_of_buffer_state )
703 mk2data( -end_of_buffer_state );
704 else
705 mk2data( end_of_buffer_state );
706
707 for ( i = 1; i < num_full_table_rows; ++i )
708 /* Jams are marked by negative of state
709 * number.
710 */
711 mk2data( state[i] ? state[i] : -ds );
712
713 /* Supply array's 0-element. */
714 if ( ds == end_of_buffer_state )
715 mk2data( -end_of_buffer_state );
716 else
717 mk2data( end_of_buffer_state );
718
719 for ( i = 1; i < num_full_table_rows; ++i )
720 /* Jams are marked by negative of state
721 * number.
722 */
723 mk2data( state[i] ? state[i] : -ds );
724
713 /* Force ',' and dataflush() next call to mk2data().*/
714 datapos = NUMDATAITEMS;
715
716 /* Force extra blank line next dataflush(). */
717 dataline = NUMDATALINES;
725 dataflush();
726 outn( " },\n" );
718 }
719
720 else if ( fullspd )
721 place_state( state, ds, totaltrans );
722
723 else if ( ds == end_of_buffer_state )
724 /* Special case this state to make sure it does what
725 * it's supposed to, i.e., jam on end-of-buffer.

--- 246 unchanged lines hidden (view full) ---

972 {
973 nset[++numstates] = tsp;
974 break;
975 }
976 }
977 }
978
979 else if ( sym >= 'A' && sym <= 'Z' && caseins )
727 }
728
729 else if ( fullspd )
730 place_state( state, ds, totaltrans );
731
732 else if ( ds == end_of_buffer_state )
733 /* Special case this state to make sure it does what
734 * it's supposed to, i.e., jam on end-of-buffer.

--- 246 unchanged lines hidden (view full) ---

981 {
982 nset[++numstates] = tsp;
983 break;
984 }
985 }
986 }
987
988 else if ( sym >= 'A' && sym <= 'Z' && caseins )
980 flexfatal( "consistency check failed in symfollowset" );
989 flexfatal(
990 _( "consistency check failed in symfollowset" ) );
981
982 else if ( sym == SYM_EPSILON )
983 { /* do nothing */
984 }
985
986 else if ( ABS( ecgroup[sym] ) == transsym )
987 nset[++numstates] = tsp;
988

--- 36 unchanged lines hidden (view full) ---

1025 ns = ds[i];
1026 tch = transchar[ns];
1027
1028 if ( tch != SYM_EPSILON )
1029 {
1030 if ( tch < -lastccl || tch >= csize )
1031 {
1032 flexfatal(
991
992 else if ( sym == SYM_EPSILON )
993 { /* do nothing */
994 }
995
996 else if ( ABS( ecgroup[sym] ) == transsym )
997 nset[++numstates] = tsp;
998

--- 36 unchanged lines hidden (view full) ---

1035 ns = ds[i];
1036 tch = transchar[ns];
1037
1038 if ( tch != SYM_EPSILON )
1039 {
1040 if ( tch < -lastccl || tch >= csize )
1041 {
1042 flexfatal(
1033 "bad transition character detected in sympartition()" );
1043 _( "bad transition character detected in sympartition()" ) );
1034 }
1035
1036 if ( tch >= 0 )
1037 { /* character transition */
1038 int ec = ecgroup[tch];
1039
1040 mkechar( ec, dupfwd, duplist );
1041 symlist[ec] = 1;

--- 44 unchanged lines hidden --- 		1044 }
1045
1046 if ( tch >= 0 )
1047 { /* character transition */
1048 int ec = ecgroup[tch];
1049
1050 mkechar( ec, dupfwd, duplist );
1051 symlist[ec] = 1;

--- 44 unchanged lines hidden ---