diff options
author | Vern Paxson <vern@ee.lbl.gov> | 1989-05-19 14:12:45 +0000 |
---|---|---|
committer | Vern Paxson <vern@ee.lbl.gov> | 1989-05-19 14:12:45 +0000 |
commit | 4a69f03f712f9ad2d522e162fc1aed3389c66156 (patch) | |
tree | 931bb229e5b01554e8e032a60821070c1036d636 /tblcmp.c | |
parent | 478a3d9a52416dc02471a306d75bf2e1b724f2de (diff) |
moved table generation code to gen.c
moved ntod() to dfa.c
Diffstat (limited to 'tblcmp.c')
-rw-r--r-- | tblcmp.c | 768 |
1 files changed, 7 insertions, 761 deletions
@@ -396,423 +396,6 @@ int *state, numtrans; } -/* genctbl - generates full speed compressed transition table - * - * synopsis - * genctbl(); - */ - -genctbl() - - { - register int i; - - /* table of verify for transition and offset to next state */ - printf( "static struct yy_trans_info yy_transition[%d] =\n", - tblend + numecs + 1 ); - printf( " {\n" ); - - /* We want the transition to be represented as the offset to the - * next state, not the actual state number, which is what it currently is. - * The offset is base[nxt[i]] - base[chk[i]]. That's just the - * difference between the starting points of the two involved states - * (to - from). - * - * first, though, we need to find some way to put in our end-of-buffer - * flags and states. We do this by making a state with absolutely no - * transitions. We put it at the end of the table. - */ - /* at this point, we're guaranteed that there's enough room in nxt[] - * and chk[] to hold tblend + numecs entries. We need just two slots. - * One for the action and one for the end-of-buffer transition. We - * now *assume* that we're guaranteed the only character we'll try to - * index this nxt/chk pair with is EOB, i.e., 0, so we don't have to - * make sure there's room for jam entries for other characters. - */ - - base[lastdfa + 1] = tblend + 2; - nxt[tblend + 1] = END_OF_BUFFER_ACTION; - chk[tblend + 1] = numecs + 1; - chk[tblend + 2] = 1; /* anything but EOB */ - nxt[tblend + 2] = 0; /* so that "make test" won't show arb. differences */ - - /* make sure every state has a end-of-buffer transition and an action # */ - for ( i = 0; i <= lastdfa; ++i ) - { - register int anum = dfaacc[i].dfaacc_state; - - chk[base[i]] = EOB_POSITION; - chk[base[i] - 1] = ACTION_POSITION; - nxt[base[i] - 1] = anum ? anum : accnum + 1; /* action number */ - } - - dataline = 0; - datapos = 0; - - for ( i = 0; i <= tblend; ++i ) - { - if ( chk[i] == EOB_POSITION ) - transition_struct_out( 0, base[lastdfa + 1] - i ); - - else if ( chk[i] == ACTION_POSITION ) - transition_struct_out( 0, nxt[i] ); - - else if ( chk[i] > numecs || chk[i] == 0 ) - transition_struct_out( 0, 0 ); /* unused slot */ - - else /* verify, transition */ - transition_struct_out( chk[i], base[nxt[i]] - (i - chk[i]) ); - } - - - /* here's the final, end-of-buffer state */ - transition_struct_out( chk[tblend + 1], nxt[tblend + 1] ); - transition_struct_out( chk[tblend + 2], nxt[tblend + 2] ); - - printf( " };\n" ); - printf( "\n" ); - - /* table of pointers to start states */ - printf( "static struct yy_trans_info *yy_state_ptr[%d] =\n", - lastsc * 2 + 1 ); - printf( " {\n" ); - - for ( i = 0; i <= lastsc * 2; ++i ) - printf( " &yy_transition[%d],\n", base[i] ); - - printf( " };\n" ); - - if ( useecs ) - genecs(); - } - - -/* genftbl - generates full transition table - * - * synopsis - * genftbl(); - */ - -genftbl() - - { - register int i; - - /* *everything* is done in terms of arrays starting at 1, so provide - * a null entry for the zero element of all C arrays - */ - static char C_short_decl[] = "static short int %c[%d] =\n { 0,\n"; - static char C_char_decl[] = "static char %c[%d] =\n { 0,\n"; - -#ifdef UNSIGNED_CHAR - printf( C_short_decl, ALIST, lastdfa + 1 ); -#else - printf( accnum > 127 ? C_short_decl : C_char_decl, ALIST, lastdfa + 1 ); -#endif - - for ( i = 1; i <= lastdfa; ++i ) - { - register int anum = dfaacc[i].dfaacc_state; - - if ( i == end_of_buffer_state ) - mkdata( END_OF_BUFFER_ACTION ); - - else - mkdata( anum ? anum : accnum + 1 ); - - if ( trace && anum ) - fprintf( stderr, "state # %d accepts: [%d]\n", i, anum ); - } - - dataend(); - - if ( useecs ) - genecs(); - - /* don't have to dump the actual full table entries - they were created - * on-the-fly - */ - } - - -/* gentabs - generate data statements for the transition tables - * - * synopsis - * gentabs(); - */ - -gentabs() - - { - int i, j, k, *accset, nacc, *acc_array, total_states; - - /* *everything* is done in terms of arrays starting at 1, so provide - * a null entry for the zero element of all C arrays - */ - static char C_long_decl[] = "static long int %c[%d] =\n { 0,\n"; - static char C_short_decl[] = "static short int %c[%d] =\n { 0,\n"; - static char C_char_decl[] = "static char %c[%d] =\n { 0,\n"; - - acc_array = allocate_integer_array( current_max_dfas ); - nummt = 0; - - printf( "#define YY_JAM %d\n", jamstate ); - printf( "#define YY_JAM_BASE %d\n", jambase ); - - if ( usemecs ) - printf( "#define YY_TEMPLATE %d\n", lastdfa + 2 ); - - if ( reject ) - { - /* write out accepting list and pointer list - * first we generate the ACCEPT array. In the process, we compute - * the indices that will go into the ALIST array, and save the - * indices in the dfaacc array - */ - - printf( accnum > 127 ? C_short_decl : C_char_decl, - ACCEPT, max( numas, 1 ) + 1 ); - - j = 1; /* index into ACCEPT array */ - - for ( i = 1; i <= lastdfa; ++i ) - { - acc_array[i] = j; - - if ( accsiz[i] != 0 ) - { - accset = dfaacc[i].dfaacc_set; - nacc = accsiz[i]; - - if ( trace ) - fprintf( stderr, "state # %d accepts: ", i ); - - for ( k = 1; k <= nacc; ++k ) - { - ++j; - mkdata( accset[k] ); - - if ( trace ) - { - fprintf( stderr, "[%d]", accset[k] ); - - if ( k < nacc ) - fputs( ", ", stderr ); - else - putc( '\n', stderr ); - } - } - } - } - - /* add accepting number for the "jam" state */ - acc_array[i] = j; - - dataend(); - } - - else - { - for ( i = 1; i <= lastdfa; ++i ) - acc_array[i] = dfaacc[i].dfaacc_state; - - /* add accepting number for jam state */ - acc_array[i] = 0; - } - - /* spit out ALIST array. If we're doing "reject", it'll be pointers - * into the ACCEPT array. Otherwise it's actual accepting numbers. - * In either case, we just dump the numbers. - */ - - /* "lastdfa + 2" is the size of ALIST; includes room for C arrays - * beginning at 0 and for "jam" state - */ - k = lastdfa + 2; - - if ( reject ) - /* we put a "cap" on the table associating lists of accepting - * numbers with state numbers. This is needed because we tell - * where the end of an accepting list is by looking at where - * the list for the next state starts. - */ - ++k; - -#ifdef UNSIGNED_CHAR - printf( C_short_decl, ALIST, k ); -#else - printf( ((reject && numas > 126) || accnum > 127) ? - C_short_decl : C_char_decl, ALIST, k ); -#endif - - for ( i = 1; i <= lastdfa; ++i ) - { - mkdata( acc_array[i] ); - - if ( ! reject && trace && acc_array[i] ) - fprintf( stderr, "state # %d accepts: [%d]\n", i, acc_array[i] ); - } - - /* add entry for "jam" state */ - mkdata( acc_array[i] ); - - if ( reject ) - /* add "cap" for the list */ - mkdata( acc_array[i] ); - - dataend(); - - if ( useecs ) - genecs(); - - if ( usemecs ) - { - /* write out meta-equivalence classes (used to index templates with) */ - - if ( trace ) - fputs( "\n\nMeta-Equivalence Classes:\n", stderr ); - - printf( C_char_decl, MATCHARRAY, numecs + 1 ); - - for ( i = 1; i <= numecs; ++i ) - { - if ( trace ) - fprintf( stderr, "%d = %d\n", i, abs( tecbck[i] ) ); - - mkdata( abs( tecbck[i] ) ); - } - - dataend(); - } - - total_states = lastdfa + numtemps; - - printf( tblend > MAX_SHORT ? C_long_decl : C_short_decl, - BASEARRAY, total_states + 1 ); - - for ( i = 1; i <= lastdfa; ++i ) - { - register int d = def[i]; - - if ( base[i] == JAMSTATE ) - base[i] = jambase; - - if ( d == JAMSTATE ) - def[i] = jamstate; - - else if ( d < 0 ) - { - /* template reference */ - ++tmpuses; - def[i] = lastdfa - d + 1; - } - - mkdata( base[i] ); - } - - /* generate jam state's base index */ - mkdata( base[i] ); - - for ( ++i /* skip jam state */; i <= total_states; ++i ) - { - mkdata( base[i] ); - def[i] = jamstate; - } - - dataend(); - - printf( tblend > MAX_SHORT ? C_long_decl : C_short_decl, - DEFARRAY, total_states + 1 ); - - for ( i = 1; i <= total_states; ++i ) - mkdata( def[i] ); - - dataend(); - - printf( lastdfa > MAX_SHORT ? C_long_decl : C_short_decl, - NEXTARRAY, tblend + 1 ); - - for ( i = 1; i <= tblend; ++i ) - { - if ( nxt[i] == 0 || chk[i] == 0 ) - nxt[i] = jamstate; /* new state is the JAM state */ - - mkdata( nxt[i] ); - } - - dataend(); - - printf( lastdfa > MAX_SHORT ? C_long_decl : C_short_decl, - CHECKARRAY, tblend + 1 ); - - for ( i = 1; i <= tblend; ++i ) - { - if ( chk[i] == 0 ) - ++nummt; - - mkdata( chk[i] ); - } - - dataend(); - } - - -/* generate equivalence-class tables */ - -genecs() - - { - register int i, j; - static char C_char_decl[] = "static char %c[%d] =\n { 0,\n"; - int numrows; - char clower(); - - printf( C_char_decl, ECARRAY, CSIZE + 1 ); - - for ( i = 1; i <= CSIZE; ++i ) - { - if ( caseins && (i >= 'A') && (i <= 'Z') ) - ecgroup[i] = ecgroup[clower( i )]; - - ecgroup[i] = abs( ecgroup[i] ); - mkdata( ecgroup[i] ); - } - - dataend(); - - if ( trace ) - { - fputs( "\n\nEquivalence Classes:\n\n", stderr ); - - numrows = (CSIZE + 1) / 8; - - for ( j = 1; j <= numrows; ++j ) - { - for ( i = j; i <= CSIZE; i = i + numrows ) - { - if ( i >= 1 && i <= 31 ) - fprintf( stderr, "^%c = %-2d", - 'A' + i - 1, ecgroup[i] ); - - else if ( i >= 32 && i <= 126 ) - fprintf( stderr, " %c = %-2d", i, ecgroup[i] ); - - else if ( i == 127 ) - fprintf( stderr, "^@ = %-2d", ecgroup[i] ); - - else - fprintf( stderr, "\nSomething Weird: %d = %d\n", i, - ecgroup[i] ); - - putc( '\t', stderr ); - } - - putc( '\n', stderr ); - } - } - } - - /* inittbl - initialize transition tables * * synopsis @@ -854,68 +437,6 @@ inittbl() } -/* make_tables - generate transition tables - * - * synopsis - * make_tables(); - * - * Generates transition tables and finishes generating output file - */ - -make_tables() - - { - if ( fullspd ) - { /* need to define YY_TRANS_OFFSET_TYPE as a size large - * enough to hold the biggest offset - */ - int total_table_size = tblend + numecs + 1; - - printf( "#define YY_TRANS_OFFSET_TYPE %s\n", - total_table_size > MAX_SHORT ? "long" : "short" ); - } - - if ( fullspd || fulltbl ) - { - skelout(); - - if ( num_backtracking > 0 ) - { - printf( "#define FLEX_USES_BACKTRACKING\n" ); - printf( "#define YY_BACK_TRACK %d\n", accnum + 1 ); - } - - if ( fullspd ) - genctbl(); - else - genftbl(); - } - - else - gentabs(); - - skelout(); - - (void) fclose( temp_action_file ); - temp_action_file = fopen( action_file_name, "r" ); - - /* copy prolog from action_file to output file */ - action_out(); - - skelout(); - - /* copy actions from action_file to output file */ - action_out(); - - skelout(); - - /* copy remainder of input to output */ - - line_directive_out( stdout ); - (void) flexscan(); /* copy remainder of input to output */ - } - - /* mkdeftbl - make the default, "jam" table entries * * synopsis @@ -929,9 +450,15 @@ mkdeftbl() jamstate = lastdfa + 1; + ++tblend; /* room for transition on end-of-buffer character */ + if ( tblend + numecs > current_max_xpairs ) expand_nxt_chk(); + /* add in default end-of-buffer transition */ + nxt[tblend] = end_of_buffer_state; + chk[tblend] = jamstate; + for ( i = 1; i <= numecs; ++i ) { nxt[tblend + i] = 0; @@ -941,11 +468,7 @@ mkdeftbl() jambase = tblend; base[jamstate] = jambase; - - /* should generate a run-time array bounds check if - * ever used as a default - */ - def[jamstate] = BAD_SUBSCRIPT; + def[jamstate] = 0; tblend += numecs; ++numtemps; @@ -1261,283 +784,6 @@ int qelm; } -/* ntod - convert an ndfa to a dfa - * - * synopsis - * ntod(); - * - * creates the dfa corresponding to the ndfa we've constructed. the - * dfa starts out in state #1. - */ -ntod() - - { - int *accset, ds, nacc, newds; - int duplist[CSIZE + 1], sym, hashval, numstates, dsize; - int targfreq[CSIZE + 1], targstate[CSIZE + 1], state[CSIZE + 1]; - int *nset, *dset; - int targptr, totaltrans, i, comstate, comfreq, targ; - int *epsclosure(), snstods(), symlist[CSIZE + 1]; - int num_start_states; - - /* this is so find_table_space(...) will know where to start looking in - * chk/nxt for unused records for space to put in the state - */ - if ( fullspd ) - firstfree = 0; - - accset = allocate_integer_array( accnum + 1 ); - nset = allocate_integer_array( current_max_dfa_size ); - - todo_head = todo_next = 0; - -#define ADD_QUEUE_ELEMENT(element) \ - if ( ++element >= current_max_dfas ) \ - { /* check for queue overflowing */ \ - if ( todo_head == 0 ) \ - increase_max_dfas(); \ - else \ - element = 0; \ - } - -#define NEXT_QUEUE_ELEMENT(element) ((element + 1) % (current_max_dfas + 1)) - - for ( i = 0; i <= CSIZE; ++i ) - { - duplist[i] = NIL; - symlist[i] = false; - } - - for ( i = 0; i <= accnum; ++i ) - accset[i] = NIL; - - if ( trace ) - { - dumpnfa( scset[1] ); - fputs( "\n\nDFA Dump:\n\n", stderr ); - } - - inittbl(); - - if ( fullspd ) - { - for ( i = 0; i <= numecs; ++i ) - state[i] = 0; - place_state( state, 0, 0 ); - } - - if ( fulltbl ) - { - /* declare it "short" because it's a real long-shot that that - * won't be large enough - */ - printf( "static short int %c[][%d] =\n {\n", NEXTARRAY, - numecs + 1 ); /* '}' so vi doesn't get too confused */ - - /* generate 0 entries for state #0 */ - for ( i = 0; i <= numecs; ++i ) - mk2data( 0 ); - - /* force ',' and dataflush() next call to mk2data */ - datapos = NUMDATAITEMS; - - /* force extra blank line next dataflush() */ - dataline = NUMDATALINES; - } - - /* create the first states */ - - num_start_states = lastsc * 2; - - for ( i = 1; i <= num_start_states; ++i ) - { - numstates = 1; - - /* for each start condition, make one state for the case when - * we're at the beginning of the line (the '%' operator) and - * one for the case when we're not - */ - if ( i % 2 == 1 ) - nset[numstates] = scset[(i / 2) + 1]; - else - nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] ); - - nset = epsclosure( nset, &numstates, accset, &nacc, &hashval ); - - if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) ) - { - numas = numas + nacc; - totnst = totnst + numstates; - - todo[todo_next] = ds; - ADD_QUEUE_ELEMENT(todo_next); - } - } - - if ( fulltbl ) - { - if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) ) - flexfatal( "could not create unique end-of-buffer state" ); - - numas += 1; - ++num_start_states; - - todo[todo_next] = end_of_buffer_state; - ADD_QUEUE_ELEMENT(todo_next); - } - - while ( todo_head != todo_next ) - { - targptr = 0; - totaltrans = 0; - - for ( i = 1; i <= numecs; ++i ) - state[i] = 0; - - ds = todo[todo_head]; - todo_head = NEXT_QUEUE_ELEMENT(todo_head); - - dset = dss[ds]; - dsize = dfasiz[ds]; - - if ( trace ) - fprintf( stderr, "state # %d:\n", ds ); - - sympartition( dset, dsize, symlist, duplist ); - - for ( sym = 1; sym <= numecs; ++sym ) - { - if ( symlist[sym] ) - { - symlist[sym] = 0; - - if ( duplist[sym] == NIL ) - { /* symbol has unique out-transitions */ - numstates = symfollowset( dset, dsize, sym, nset ); - nset = epsclosure( nset, &numstates, accset, - &nacc, &hashval ); - - if ( snstods( nset, numstates, accset, - nacc, hashval, &newds ) ) - { - totnst = totnst + numstates; - todo[todo_next] = newds; - ADD_QUEUE_ELEMENT(todo_next); - numas = numas + nacc; - } - - state[sym] = newds; - - if ( trace ) - fprintf( stderr, "\t%d\t%d\n", sym, newds ); - - targfreq[++targptr] = 1; - targstate[targptr] = newds; - ++numuniq; - } - - else - { - /* sym's equivalence class has the same transitions - * as duplist(sym)'s equivalence class - */ - targ = state[duplist[sym]]; - state[sym] = targ; - - if ( trace ) - fprintf( stderr, "\t%d\t%d\n", sym, targ ); - - /* update frequency count for destination state */ - - i = 0; - while ( targstate[++i] != targ ) - ; - - ++targfreq[i]; - ++numdup; - } - - ++totaltrans; - duplist[sym] = NIL; - } - } - - numsnpairs = numsnpairs + totaltrans; - - if ( caseins && ! useecs ) - { - register int j; - - for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j ) - state[i] = state[j]; - } - - if ( ds > num_start_states ) - check_for_backtracking( ds, state ); - - if ( fulltbl ) - { - /* supply array's 0-element */ - if ( ds == end_of_buffer_state ) - mk2data( -end_of_buffer_state ); - else - mk2data( end_of_buffer_state ); - - for ( i = 1; i <= numecs; ++i ) - /* jams are marked by negative of state number */ - mk2data( state[i] ? state[i] : -ds ); - - /* force ',' and dataflush() next call to mk2data */ - datapos = NUMDATAITEMS; - - /* force extra blank line next dataflush() */ - dataline = NUMDATALINES; - } - - else if ( fullspd ) - place_state( state, ds, totaltrans ); - - else - { - /* determine which destination state is the most common, and - * how many transitions to it there are - */ - - comfreq = 0; - comstate = 0; - - for ( i = 1; i <= targptr; ++i ) - if ( targfreq[i] > comfreq ) - { - comfreq = targfreq[i]; - comstate = targstate[i]; - } - - bldtbl( state, ds, totaltrans, comstate, comfreq ); - } - } - - if ( fulltbl ) - dataend(); - - else if ( ! fullspd ) - { - cmptmps(); /* create compressed template entries */ - - /* create tables for all the states with only one out-transition */ - while ( onesp > 0 ) - { - mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp], - onedef[onesp] ); - --onesp; - } - - mkdeftbl(); - } - - } - - /* place_state - place a state into full speed transition table * * synopsis |