rsalz@uunet.uu.net (Rich Salz) (06/23/89)
Submitted-by: Vern Paxson <vern@csam.lbl.gov> Posting-number: Volume 19, Issue 59 Archive-name: flex2/part05 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 5 (of 7)." # Contents: flex/dfa.c flex/tblcmp.c # Wrapped by rsalz@prune.bbn.com on Thu Jun 22 19:01:49 1989 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test -f 'flex/dfa.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'flex/dfa.c'\" else echo shar: Extracting \"'flex/dfa.c'\" \(22852 characters\) sed "s/^X//" >'flex/dfa.c' <<'END_OF_FILE' X/* dfa - DFA construction routines */ X X/* X * Copyright (c) 1989 The Regents of the University of California. X * All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Vern Paxson. X * X * The United States Government has rights in this work pursuant to X * contract no. DE-AC03-76SF00098 between the United States Department of X * Energy and the University of California. X * X * Redistribution and use in source and binary forms are permitted X * provided that the above copyright notice and this paragraph are X * duplicated in all such forms and that any documentation, X * advertising materials, and other materials related to such X * distribution and use acknowledge that the software was developed X * by the University of California, Berkeley. The name of the X * University may not be used to endorse or promote products derived X * from this software without specific prior written permission. X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. X */ X X#ifndef lint X Xstatic char copyright[] = X "@(#) Copyright (c) 1989 The Regents of the University of California.\n"; Xstatic char CR_continuation[] = "@(#) All rights reserved.\n"; X Xstatic char rcsid[] = X "@(#) $Header: dfa.c,v 2.0 89/06/20 15:49:30 vern Locked $ (LBL)"; X X#endif X X#include "flexdef.h" X X X/* check_for_backtracking - check a DFA state for backtracking X * X * synopsis X * int ds, state[numecs]; X * check_for_backtracking( ds, state ); X * X * ds is the number of the state to check and state[] is its out-transitions, X * indexed by equivalence class, and state_rules[] is the set of rules X * associated with this state X */ X Xcheck_for_backtracking( ds, state ) Xint ds; Xint state[]; X X { X if ( (reject && ! dfaacc[ds].dfaacc_set) || ! dfaacc[ds].dfaacc_state ) X { /* state is non-accepting */ X ++num_backtracking; X X if ( backtrack_report ) X { X fprintf( backtrack_file, "State #%d is non-accepting -\n", ds ); X X /* identify the state */ X dump_associated_rules( backtrack_file, ds ); X X /* now identify it further using the out- and jam-transitions */ X dump_transitions( backtrack_file, state ); X X putc( '\n', backtrack_file ); X } X } X } X X X/* check_trailing_context - check to see if NFA state set constitutes X * "dangerous" trailing context X * X * synopsis X * int nfa_states[num_states+1], num_states; X * int accset[nacc+1], nacc; X * int check_trailing_context(); X * true/false = check_trailing_context( nfa_states, num_states, X * accset, nacc ); X * X * NOTES X * Trailing context is "dangerous" if both the head and the trailing X * part are of variable size \and/ there's a DFA state which contains X * both an accepting state for the head part of the rule and NFA states X * which occur after the beginning of the trailing context. X * When such a rule is matched, it's impossible to tell if having been X * in the DFA state indicates the beginning of the trailing context X * or further-along scanning of the pattern. In these cases, a warning X * message is issued. X * X * nfa_states[1 .. num_states] is the list of NFA states in the DFA. X * accset[1 .. nacc] is the list of accepting numbers for the DFA state. X */ X Xint check_trailing_context( nfa_states, num_states, accset, nacc ) Xint *nfa_states, num_states; Xint *accset; Xregister int nacc; X X { X register int i, j; X X for ( i = 1; i <= num_states; ++i ) X { X int ns = nfa_states[i]; X register int type = state_type[ns]; X register int ar = assoc_rule[ns]; X X if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE ) X { /* do nothing */ X } X X else if ( type == STATE_TRAILING_CONTEXT ) X { X /* potential trouble. Scan set of accepting numbers for X * the one marking the end of the "head". We assume that X * this looping will be fairly cheap since it's rare that X * an accepting number set is large. X */ X for ( j = 1; j <= nacc; ++j ) X if ( accset[j] & YY_TRAILING_HEAD_MASK ) X { X fprintf( stderr, X "flex: Dangerous trailing context in rule at line %d\n", X rule_linenum[ar] ); X return; X } X } X } X } X X X/* dump_associated_rules - list the rules associated with a DFA state X * X * synopisis X * int ds; X * FILE *file; X * dump_associated_rules( file, ds ); X * X * goes through the set of NFA states associated with the DFA and X * extracts the first MAX_ASSOC_RULES unique rules, sorts them, X * and writes a report to the given file X */ X Xdump_associated_rules( file, ds ) XFILE *file; Xint ds; X X { X register int i, j; X register int num_associated_rules = 0; X int rule_set[MAX_ASSOC_RULES + 1]; X int *dset = dss[ds]; X int size = dfasiz[ds]; X X for ( i = 1; i <= size; ++i ) X { X register rule_num = rule_linenum[assoc_rule[dset[i]]]; X X for ( j = 1; j <= num_associated_rules; ++j ) X if ( rule_num == rule_set[j] ) X break; X X if ( j > num_associated_rules ) X { /* new rule */ X if ( num_associated_rules < MAX_ASSOC_RULES ) X rule_set[++num_associated_rules] = rule_num; X } X } X X bubble( rule_set, num_associated_rules ); X X fprintf( file, " associated rules:" ); X X for ( i = 1; i <= num_associated_rules; ++i ) X { X if ( i % 8 == 1 ) X putc( '\n', file ); X X fprintf( file, "\t%d", rule_set[i] ); X } X X putc( '\n', file ); X } X X X/* dump_transitions - list the transitions associated with a DFA state X * X * synopisis X * int state[numecs]; X * FILE *file; X * dump_transitions( file, state ); X * X * goes through the set of out-transitions and lists them in human-readable X * form (i.e., not as equivalence classes); also lists jam transitions X * (i.e., all those which are not out-transitions, plus EOF). The dump X * is done to the given file. X */ X Xdump_transitions( file, state ) XFILE *file; Xint state[]; X X { X register int i, ec; X int out_char_set[CSIZE + 1]; X X for ( i = 1; i <= CSIZE; ++i ) X { X ec = ecgroup[i]; X X if ( ec < 0 ) X ec = -ec; X X out_char_set[i] = state[ec]; X } X X fprintf( file, " out-transitions: " ); X X list_character_set( file, out_char_set ); X X /* now invert the members of the set to get the jam transitions */ X for ( i = 1; i <= CSIZE; ++i ) X out_char_set[i] = ! out_char_set[i]; X X fprintf( file, "\n jam-transitions: EOF " ); X X list_character_set( file, out_char_set ); X X putc( '\n', file ); X } X X X/* epsclosure - construct the epsilon closure of a set of ndfa states X * X * synopsis X * int t[current_max_dfa_size], numstates, accset[num_rules + 1], nacc; X * int hashval; X * int *epsclosure(); X * t = epsclosure( t, &numstates, accset, &nacc, &hashval ); X * X * NOTES X * the epsilon closure is the set of all states reachable by an arbitrary X * number of epsilon transitions which themselves do not have epsilon X * transitions going out, unioned with the set of states which have non-null X * accepting numbers. t is an array of size numstates of nfa state numbers. X * Upon return, t holds the epsilon closure and numstates is updated. accset X * holds a list of the accepting numbers, and the size of accset is given X * by nacc. t may be subjected to reallocation if it is not large enough X * to hold the epsilon closure. X * X * hashval is the hash value for the dfa corresponding to the state set X */ X Xint *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr ) Xint *t, *ns_addr, accset[], *nacc_addr, *hv_addr; X X { X register int stkpos, ns, tsp; X int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum; X int stkend, nstate; X static int did_stk_init = false, *stk; X X#define MARK_STATE(state) \ X trans1[state] = trans1[state] - MARKER_DIFFERENCE; X X#define IS_MARKED(state) (trans1[state] < 0) X X#define UNMARK_STATE(state) \ X trans1[state] = trans1[state] + MARKER_DIFFERENCE; X X#define CHECK_ACCEPT(state) \ X { \ X nfaccnum = accptnum[state]; \ X if ( nfaccnum != NIL ) \ X accset[++nacc] = nfaccnum; \ X } X X#define DO_REALLOCATION \ X { \ X current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \ X ++num_reallocs; \ X t = reallocate_integer_array( t, current_max_dfa_size ); \ X stk = reallocate_integer_array( stk, current_max_dfa_size ); \ X } \ X X#define PUT_ON_STACK(state) \ X { \ X if ( ++stkend >= current_max_dfa_size ) \ X DO_REALLOCATION \ X stk[stkend] = state; \ X MARK_STATE(state) \ X } X X#define ADD_STATE(state) \ X { \ X if ( ++numstates >= current_max_dfa_size ) \ X DO_REALLOCATION \ X t[numstates] = state; \ X hashval = hashval + state; \ X } X X#define STACK_STATE(state) \ X { \ X PUT_ON_STACK(state) \ X CHECK_ACCEPT(state) \ X if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \ X ADD_STATE(state) \ X } X X if ( ! did_stk_init ) X { X stk = allocate_integer_array( current_max_dfa_size ); X did_stk_init = true; X } X X nacc = stkend = hashval = 0; X X for ( nstate = 1; nstate <= numstates; ++nstate ) X { X ns = t[nstate]; X X /* the state could be marked if we've already pushed it onto X * the stack X */ X if ( ! IS_MARKED(ns) ) X PUT_ON_STACK(ns) X X CHECK_ACCEPT(ns) X hashval = hashval + ns; X } X X for ( stkpos = 1; stkpos <= stkend; ++stkpos ) X { X ns = stk[stkpos]; X transsym = transchar[ns]; X X if ( transsym == SYM_EPSILON ) X { X tsp = trans1[ns] + MARKER_DIFFERENCE; X X if ( tsp != NO_TRANSITION ) X { X if ( ! IS_MARKED(tsp) ) X STACK_STATE(tsp) X X tsp = trans2[ns]; X X if ( tsp != NO_TRANSITION ) X if ( ! IS_MARKED(tsp) ) X STACK_STATE(tsp) X } X } X } X X /* clear out "visit" markers */ X X for ( stkpos = 1; stkpos <= stkend; ++stkpos ) X { X if ( IS_MARKED(stk[stkpos]) ) X { X UNMARK_STATE(stk[stkpos]) X } X else X flexfatal( "consistency check failed in epsclosure()" ); X } X X *ns_addr = numstates; X *hv_addr = hashval; X *nacc_addr = nacc; X X return ( t ); X } X X X/* increase_max_dfas - increase the maximum number of DFAs */ X Xincrease_max_dfas() X X { X current_max_dfas += MAX_DFAS_INCREMENT; X X ++num_reallocs; X X base = reallocate_integer_array( base, current_max_dfas ); X def = reallocate_integer_array( def, current_max_dfas ); X dfasiz = reallocate_integer_array( dfasiz, current_max_dfas ); X accsiz = reallocate_integer_array( accsiz, current_max_dfas ); X dhash = reallocate_integer_array( dhash, current_max_dfas ); X dss = reallocate_int_ptr_array( dss, current_max_dfas ); X dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas ); X } X X X/* ntod - convert an ndfa to a dfa X * X * synopsis X * ntod(); X * X * creates the dfa corresponding to the ndfa we've constructed. the X * dfa starts out in state #1. X */ Xntod() X X { X int *accset, ds, nacc, newds; X int duplist[CSIZE + 1], sym, hashval, numstates, dsize; X int targfreq[CSIZE + 1], targstate[CSIZE + 1], state[CSIZE + 1]; X int *nset, *dset; X int targptr, totaltrans, i, comstate, comfreq, targ; X int *epsclosure(), snstods(), symlist[CSIZE + 1]; X int num_start_states; X int todo_head, todo_next; X X /* this is so find_table_space(...) will know where to start looking in X * chk/nxt for unused records for space to put in the state X */ X if ( fullspd ) X firstfree = 0; X X accset = allocate_integer_array( num_rules + 1 ); X nset = allocate_integer_array( current_max_dfa_size ); X X /* the "todo" queue is represented by the head, which is the DFA X * state currently being processed, and the "next", which is the X * next DFA state number available (not in use). We depend on the X * fact that snstods() returns DFA's \in increasing order/, and thus X * need only know the bounds of the dfas to be processed. X */ X todo_head = todo_next = 0; X X for ( i = 0; i <= CSIZE; ++i ) X { X duplist[i] = NIL; X symlist[i] = false; X } X X for ( i = 0; i <= num_rules; ++i ) X accset[i] = NIL; X X if ( trace ) X { X dumpnfa( scset[1] ); X fputs( "\n\nDFA Dump:\n\n", stderr ); X } X X inittbl(); X X if ( fullspd ) X { X for ( i = 0; i <= numecs; ++i ) X state[i] = 0; X place_state( state, 0, 0 ); X } X X if ( fulltbl ) X { X /* declare it "short" because it's a real long-shot that that X * won't be large enough X */ X printf( "static short int %s[][%d] =\n {\n", NEXTARRAY, X numecs + 1 ); /* '}' so vi doesn't get too confused */ X X /* generate 0 entries for state #0 */ X for ( i = 0; i <= numecs; ++i ) X mk2data( 0 ); X X /* force ',' and dataflush() next call to mk2data */ X datapos = NUMDATAITEMS; X X /* force extra blank line next dataflush() */ X dataline = NUMDATALINES; X } X X /* create the first states */ X X num_start_states = lastsc * 2; X X for ( i = 1; i <= num_start_states; ++i ) X { X numstates = 1; X X /* for each start condition, make one state for the case when X * we're at the beginning of the line (the '%' operator) and X * one for the case when we're not X */ X if ( i % 2 == 1 ) X nset[numstates] = scset[(i / 2) + 1]; X else X nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] ); X X nset = epsclosure( nset, &numstates, accset, &nacc, &hashval ); X X if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) ) X { X numas += nacc; X totnst += numstates; X ++todo_next; X X if ( variable_trailing_context_rules && nacc > 0 ) X check_trailing_context( nset, numstates, accset, nacc ); X } X } X X if ( ! fullspd ) X { X if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) ) X flexfatal( "could not create unique end-of-buffer state" ); X X ++numas; X ++num_start_states; X ++todo_next; X } X X while ( todo_head < todo_next ) X { X targptr = 0; X totaltrans = 0; X X for ( i = 1; i <= numecs; ++i ) X state[i] = 0; X X ds = ++todo_head; X X dset = dss[ds]; X dsize = dfasiz[ds]; X X if ( trace ) X fprintf( stderr, "state # %d:\n", ds ); X X sympartition( dset, dsize, symlist, duplist ); X X for ( sym = 1; sym <= numecs; ++sym ) X { X if ( symlist[sym] ) X { X symlist[sym] = 0; X X if ( duplist[sym] == NIL ) X { /* symbol has unique out-transitions */ X numstates = symfollowset( dset, dsize, sym, nset ); X nset = epsclosure( nset, &numstates, accset, X &nacc, &hashval ); X X if ( snstods( nset, numstates, accset, X nacc, hashval, &newds ) ) X { X totnst = totnst + numstates; X ++todo_next; X numas += nacc; X X if ( variable_trailing_context_rules && nacc > 0 ) X check_trailing_context( nset, numstates, X accset, nacc ); X } X X state[sym] = newds; X X if ( trace ) X fprintf( stderr, "\t%d\t%d\n", sym, newds ); X X targfreq[++targptr] = 1; X targstate[targptr] = newds; X ++numuniq; X } X X else X { X /* sym's equivalence class has the same transitions X * as duplist(sym)'s equivalence class X */ X targ = state[duplist[sym]]; X state[sym] = targ; X X if ( trace ) X fprintf( stderr, "\t%d\t%d\n", sym, targ ); X X /* update frequency count for destination state */ X X i = 0; X while ( targstate[++i] != targ ) X ; X X ++targfreq[i]; X ++numdup; X } X X ++totaltrans; X duplist[sym] = NIL; X } X } X X numsnpairs = numsnpairs + totaltrans; X X if ( caseins && ! useecs ) X { X register int j; X X for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j ) X state[i] = state[j]; X } X X if ( ds > num_start_states ) X check_for_backtracking( ds, state ); X X if ( fulltbl ) X { X /* supply array's 0-element */ X if ( ds == end_of_buffer_state ) X mk2data( -end_of_buffer_state ); X else X mk2data( end_of_buffer_state ); X X for ( i = 1; i <= numecs; ++i ) X /* jams are marked by negative of state number */ X mk2data( state[i] ? state[i] : -ds ); X X /* force ',' and dataflush() next call to mk2data */ X datapos = NUMDATAITEMS; X X /* force extra blank line next dataflush() */ X dataline = NUMDATALINES; X } X X else if ( fullspd ) X place_state( state, ds, totaltrans ); X X else if ( ds == end_of_buffer_state ) X /* special case this state to make sure it does what it's X * supposed to, i.e., jam on end-of-buffer X */ X stack1( ds, 0, 0, JAMSTATE ); X X else /* normal, compressed state */ X { X /* determine which destination state is the most common, and X * how many transitions to it there are X */ X X comfreq = 0; X comstate = 0; X X for ( i = 1; i <= targptr; ++i ) X if ( targfreq[i] > comfreq ) X { X comfreq = targfreq[i]; X comstate = targstate[i]; X } X X bldtbl( state, ds, totaltrans, comstate, comfreq ); X } X } X X if ( fulltbl ) X dataend(); X X else if ( ! fullspd ) X { X cmptmps(); /* create compressed template entries */ X X /* create tables for all the states with only one out-transition */ X while ( onesp > 0 ) X { X mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp], X onedef[onesp] ); X --onesp; X } X X mkdeftbl(); X } X } X X X/* snstods - converts a set of ndfa states into a dfa state X * X * synopsis X * int sns[numstates], numstates, newds, accset[num_rules + 1], nacc, hashval; X * int snstods(); X * is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds ); X * X * on return, the dfa state number is in newds. X */ X Xint snstods( sns, numstates, accset, nacc, hashval, newds_addr ) Xint sns[], numstates, accset[], nacc, hashval, *newds_addr; X X { X int didsort = 0; X register int i, j; X int newds, *oldsns; X char *malloc(); X X for ( i = 1; i <= lastdfa; ++i ) X if ( hashval == dhash[i] ) X { X if ( numstates == dfasiz[i] ) X { X oldsns = dss[i]; X X if ( ! didsort ) X { X /* we sort the states in sns so we can compare it to X * oldsns quickly. we use bubble because there probably X * aren't very many states X */ X bubble( sns, numstates ); X didsort = 1; X } X X for ( j = 1; j <= numstates; ++j ) X if ( sns[j] != oldsns[j] ) X break; X X if ( j > numstates ) X { X ++dfaeql; X *newds_addr = i; X return ( 0 ); X } X X ++hshcol; X } X X else X ++hshsave; X } X X /* make a new dfa */ X X if ( ++lastdfa >= current_max_dfas ) X increase_max_dfas(); X X newds = lastdfa; X X dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) ); X X if ( ! dss[newds] ) X flexfatal( "dynamic memory failure in snstods()" ); X X /* if we haven't already sorted the states in sns, we do so now, so that X * future comparisons with it can be made quickly X */ X X if ( ! didsort ) X bubble( sns, numstates ); X X for ( i = 1; i <= numstates; ++i ) X dss[newds][i] = sns[i]; X X dfasiz[newds] = numstates; X dhash[newds] = hashval; X X if ( nacc == 0 ) X { X if ( reject ) X dfaacc[newds].dfaacc_set = (int *) 0; X else X dfaacc[newds].dfaacc_state = 0; X X accsiz[newds] = 0; X } X X else if ( reject ) X { X /* we sort the accepting set in increasing order so the disambiguating X * rule that the first rule listed is considered match in the event of X * ties will work. We use a bubble sort since the list is probably X * quite small. X */ X X bubble( accset, nacc ); X X dfaacc[newds].dfaacc_set = X (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) ); X X if ( ! dfaacc[newds].dfaacc_set ) X flexfatal( "dynamic memory failure in snstods()" ); X X /* save the accepting set for later */ X for ( i = 1; i <= nacc; ++i ) X dfaacc[newds].dfaacc_set[i] = accset[i]; X X accsiz[newds] = nacc; X } X X else X { /* find lowest numbered rule so the disambiguating rule will work */ X j = num_rules + 1; X X for ( i = 1; i <= nacc; ++i ) X if ( accset[i] < j ) X j = accset[i]; X X dfaacc[newds].dfaacc_state = j; X } X X *newds_addr = newds; X X return ( 1 ); X } X X X/* symfollowset - follow the symbol transitions one step X * X * synopsis X * int ds[current_max_dfa_size], dsize, transsym; X * int nset[current_max_dfa_size], numstates; X * numstates = symfollowset( ds, dsize, transsym, nset ); X */ X Xint symfollowset( ds, dsize, transsym, nset ) Xint ds[], dsize, transsym, nset[]; X X { X int ns, tsp, sym, i, j, lenccl, ch, numstates; X int ccllist; X X numstates = 0; X X for ( i = 1; i <= dsize; ++i ) X { /* for each nfa state ns in the state set of ds */ X ns = ds[i]; X sym = transchar[ns]; X tsp = trans1[ns]; X X if ( sym < 0 ) X { /* it's a character class */ X sym = -sym; X ccllist = cclmap[sym]; X lenccl = ccllen[sym]; X X if ( cclng[sym] ) X { X for ( j = 0; j < lenccl; ++j ) X { /* loop through negated character class */ X ch = ccltbl[ccllist + j]; X X if ( ch > transsym ) X break; /* transsym isn't in negated ccl */ X X else if ( ch == transsym ) X /* next 2 */ goto bottom; X } X X /* didn't find transsym in ccl */ X nset[++numstates] = tsp; X } X X else X for ( j = 0; j < lenccl; ++j ) X { X ch = ccltbl[ccllist + j]; X X if ( ch > transsym ) X break; X X else if ( ch == transsym ) X { X nset[++numstates] = tsp; X break; X } X } X } X X else if ( sym >= 'A' && sym <= 'Z' && caseins ) X flexfatal( "consistency check failed in symfollowset" ); X X else if ( sym == SYM_EPSILON ) X { /* do nothing */ X } X X else if ( ecgroup[sym] == transsym ) X nset[++numstates] = tsp; X Xbottom: X ; X } X X return ( numstates ); X } X X X/* sympartition - partition characters with same out-transitions X * X * synopsis X * integer ds[current_max_dfa_size], numstates, duplist[numecs]; X * symlist[numecs]; X * sympartition( ds, numstates, symlist, duplist ); X */ X Xsympartition( ds, numstates, symlist, duplist ) Xint ds[], numstates, duplist[]; Xint symlist[]; X X { X int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich; X X /* partitioning is done by creating equivalence classes for those X * characters which have out-transitions from the given state. Thus X * we are really creating equivalence classes of equivalence classes. X */ X X for ( i = 1; i <= numecs; ++i ) X { /* initialize equivalence class list */ X duplist[i] = i - 1; X dupfwd[i] = i + 1; X } X X duplist[1] = NIL; X dupfwd[numecs] = NIL; X X for ( i = 1; i <= numstates; ++i ) X { X ns = ds[i]; X tch = transchar[ns]; X X if ( tch != SYM_EPSILON ) X { X if ( tch < -lastccl || tch > CSIZE ) X flexfatal( "bad transition character detected in sympartition()" ); X X if ( tch > 0 ) X { /* character transition */ X mkechar( ecgroup[tch], dupfwd, duplist ); X symlist[ecgroup[tch]] = 1; X } X X else X { /* character class */ X tch = -tch; X X lenccl = ccllen[tch]; X cclp = cclmap[tch]; X mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs ); X X if ( cclng[tch] ) X { X j = 0; X X for ( k = 0; k < lenccl; ++k ) X { X ich = ccltbl[cclp + k]; X X for ( ++j; j < ich; ++j ) X symlist[j] = 1; X } X X for ( ++j; j <= numecs; ++j ) X symlist[j] = 1; X } X X else X for ( k = 0; k < lenccl; ++k ) X { X ich = ccltbl[cclp + k]; X symlist[ich] = 1; X } X } X } X } X } END_OF_FILE if test 22852 -ne `wc -c <'flex/dfa.c'`; then echo shar: \"'flex/dfa.c'\" unpacked with wrong size! fi # end of 'flex/dfa.c' fi if test -f 'flex/tblcmp.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'flex/tblcmp.c'\" else echo shar: Extracting \"'flex/tblcmp.c'\" \(24794 characters\) sed "s/^X//" >'flex/tblcmp.c' <<'END_OF_FILE' X/* tblcmp - table compression routines */ X X/* X * Copyright (c) 1989 The Regents of the University of California. X * All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Vern Paxson. X * X * The United States Government has rights in this work pursuant to X * contract no. DE-AC03-76SF00098 between the United States Department of X * Energy and the University of California. X * X * Redistribution and use in source and binary forms are permitted X * provided that the above copyright notice and this paragraph are X * duplicated in all such forms and that any documentation, X * advertising materials, and other materials related to such X * distribution and use acknowledge that the software was developed X * by the University of California, Berkeley. The name of the X * University may not be used to endorse or promote products derived X * from this software without specific prior written permission. X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. X */ X X#ifndef lint X Xstatic char copyright[] = X "@(#) Copyright (c) 1989 The Regents of the University of California.\n"; Xstatic char CR_continuation[] = "@(#) All rights reserved.\n"; X Xstatic char rcsid[] = X "@(#) $Header: tblcmp.c,v 2.0 89/06/20 15:50:21 vern Locked $ (LBL)"; X X#endif X X#include "flexdef.h" X X/* bldtbl - build table entries for dfa state X * X * synopsis X * int state[numecs], statenum, totaltrans, comstate, comfreq; X * bldtbl( state, statenum, totaltrans, comstate, comfreq ); X * X * State is the statenum'th dfa state. It is indexed by equivalence class and X * gives the number of the state to enter for a given equivalence class. X * totaltrans is the total number of transitions out of the state. Comstate X * is that state which is the destination of the most transitions out of State. X * Comfreq is how many transitions there are out of State to Comstate. X * X * A note on terminology: X * "protos" are transition tables which have a high probability of X * either being redundant (a state processed later will have an identical X * transition table) or nearly redundant (a state processed later will have X * many of the same out-transitions). A "most recently used" queue of X * protos is kept around with the hope that most states will find a proto X * which is similar enough to be usable, and therefore compacting the X * output tables. X * "templates" are a special type of proto. If a transition table is X * homogeneous or nearly homogeneous (all transitions go to the same X * destination) then the odds are good that future states will also go X * to the same destination state on basically the same character set. X * These homogeneous states are so common when dealing with large rule X * sets that they merit special attention. If the transition table were X * simply made into a proto, then (typically) each subsequent, similar X * state will differ from the proto for two out-transitions. One of these X * out-transitions will be that character on which the proto does not go X * to the common destination, and one will be that character on which the X * state does not go to the common destination. Templates, on the other X * hand, go to the common state on EVERY transition character, and therefore X * cost only one difference. X */ X Xbldtbl( state, statenum, totaltrans, comstate, comfreq ) Xint state[], statenum, totaltrans, comstate, comfreq; X X { X int extptr, extrct[2][CSIZE + 1]; X int mindiff, minprot, i, d; X int checkcom; X X /* If extptr is 0 then the first array of extrct holds the result of the X * "best difference" to date, which is those transitions which occur in X * "state" but not in the proto which, to date, has the fewest differences X * between itself and "state". If extptr is 1 then the second array of X * extrct hold the best difference. The two arrays are toggled X * between so that the best difference to date can be kept around and X * also a difference just created by checking against a candidate "best" X * proto. X */ X X extptr = 0; X X /* if the state has too few out-transitions, don't bother trying to X * compact its tables X */ X X if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) ) X mkentry( state, numecs, statenum, JAMSTATE, totaltrans ); X X else X { X /* checkcom is true if we should only check "state" against X * protos which have the same "comstate" value X */ X X checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; X X minprot = firstprot; X mindiff = totaltrans; X X if ( checkcom ) X { X /* find first proto which has the same "comstate" */ X for ( i = firstprot; i != NIL; i = protnext[i] ) X if ( protcomst[i] == comstate ) X { X minprot = i; X mindiff = tbldiff( state, minprot, extrct[extptr] ); X break; X } X } X X else X { X /* since we've decided that the most common destination out X * of "state" does not occur with a high enough frequency, X * we set the "comstate" to zero, assuring that if this state X * is entered into the proto list, it will not be considered X * a template. X */ X comstate = 0; X X if ( firstprot != NIL ) X { X minprot = firstprot; X mindiff = tbldiff( state, minprot, extrct[extptr] ); X } X } X X /* we now have the first interesting proto in "minprot". If X * it matches within the tolerances set for the first proto, X * we don't want to bother scanning the rest of the proto list X * to see if we have any other reasonable matches. X */ X X if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE ) X { /* not a good enough match. Scan the rest of the protos */ X for ( i = minprot; i != NIL; i = protnext[i] ) X { X d = tbldiff( state, i, extrct[1 - extptr] ); X if ( d < mindiff ) X { X extptr = 1 - extptr; X mindiff = d; X minprot = i; X } X } X } X X /* check if the proto we've decided on as our best bet is close X * enough to the state we want to match to be usable X */ X X if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE ) X { X /* no good. If the state is homogeneous enough, we make a X * template out of it. Otherwise, we make a proto. X */ X X if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE ) X mktemplate( state, statenum, comstate ); X X else X { X mkprot( state, statenum, comstate ); X mkentry( state, numecs, statenum, JAMSTATE, totaltrans ); X } X } X X else X { /* use the proto */ X mkentry( extrct[extptr], numecs, statenum, X prottbl[minprot], mindiff ); X X /* if this state was sufficiently different from the proto X * we built it from, make it, too, a proto X */ X X if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE ) X mkprot( state, statenum, comstate ); X X /* since mkprot added a new proto to the proto queue, it's possible X * that "minprot" is no longer on the proto queue (if it happened X * to have been the last entry, it would have been bumped off). X * If it's not there, then the new proto took its physical place X * (though logically the new proto is at the beginning of the X * queue), so in that case the following call will do nothing. X */ X X mv2front( minprot ); X } X } X } X X X/* cmptmps - compress template table entries X * X * synopsis X * cmptmps(); X * X * template tables are compressed by using the 'template equivalence X * classes', which are collections of transition character equivalence X * classes which always appear together in templates - really meta-equivalence X * classes. until this point, the tables for templates have been stored X * up at the top end of the nxt array; they will now be compressed and have X * table entries made for them. X */ X Xcmptmps() X X { X int tmpstorage[CSIZE + 1]; X register int *tmp = tmpstorage, i, j; X int totaltrans, trans; X X peakpairs = numtemps * numecs + tblend; X X if ( usemecs ) X { X /* create equivalence classes base on data gathered on template X * transitions X */ X X nummecs = cre8ecs( tecfwd, tecbck, numecs ); X } X X else X nummecs = numecs; X X if ( lastdfa + numtemps + 1 >= current_max_dfas ) X increase_max_dfas(); X X /* loop through each template */ X X for ( i = 1; i <= numtemps; ++i ) X { X totaltrans = 0; /* number of non-jam transitions out of this template */ X X for ( j = 1; j <= numecs; ++j ) X { X trans = tnxt[numecs * i + j]; X X if ( usemecs ) X { X /* the absolute value of tecbck is the meta-equivalence class X * of a given equivalence class, as set up by cre8ecs X */ X if ( tecbck[j] > 0 ) X { X tmp[tecbck[j]] = trans; X X if ( trans > 0 ) X ++totaltrans; X } X } X X else X { X tmp[j] = trans; X X if ( trans > 0 ) X ++totaltrans; X } X } X X /* it is assumed (in a rather subtle way) in the skeleton that X * if we're using meta-equivalence classes, the def[] entry for X * all templates is the jam template, i.e., templates never default X * to other non-jam table entries (e.g., another template) X */ X X /* leave room for the jam-state after the last real state */ X mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans ); X } X } X X X X/* expand_nxt_chk - expand the next check arrays */ X Xexpand_nxt_chk() X X { X register int old_max = current_max_xpairs; X X current_max_xpairs += MAX_XPAIRS_INCREMENT; X X ++num_reallocs; X X nxt = reallocate_integer_array( nxt, current_max_xpairs ); X chk = reallocate_integer_array( chk, current_max_xpairs ); X X bzero( (char *) (chk + old_max), X MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) ); X } X X X/* find_table_space - finds a space in the table for a state to be placed X * X * synopsis X * int *state, numtrans, block_start; X * int find_table_space(); X * X * block_start = find_table_space( state, numtrans ); X * X * State is the state to be added to the full speed transition table. X * Numtrans is the number of out-transitions for the state. X * X * find_table_space() returns the position of the start of the first block (in X * chk) able to accommodate the state X * X * In determining if a state will or will not fit, find_table_space() must take X * into account the fact that an end-of-buffer state will be added at [0], X * and an action number will be added in [-1]. X */ X Xint find_table_space( state, numtrans ) Xint *state, numtrans; X X { X /* firstfree is the position of the first possible occurrence of two X * consecutive unused records in the chk and nxt arrays X */ X register int i; X register int *state_ptr, *chk_ptr; X register int *ptr_to_last_entry_in_state; X X /* if there are too many out-transitions, put the state at the end of X * nxt and chk X */ X if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT ) X { X /* if table is empty, return the first available spot in chk/nxt, X * which should be 1 X */ X if ( tblend < 2 ) X return ( 1 ); X X i = tblend - numecs; /* start searching for table space near the X * end of chk/nxt arrays X */ X } X X else X i = firstfree; /* start searching for table space from the X * beginning (skipping only the elements X * which will definitely not hold the new X * state) X */ X X while ( 1 ) /* loops until a space is found */ X { X if ( i + numecs > current_max_xpairs ) X expand_nxt_chk(); X X /* loops until space for end-of-buffer and action number are found */ X while ( 1 ) X { X if ( chk[i - 1] == 0 ) /* check for action number space */ X { X if ( chk[i] == 0 ) /* check for end-of-buffer space */ X break; X X else X i += 2; /* since i != 0, there is no use checking to X * see if (++i) - 1 == 0, because that's the X * same as i == 0, so we skip a space X */ X } X X else X ++i; X X if ( i + numecs > current_max_xpairs ) X expand_nxt_chk(); X } X X /* if we started search from the beginning, store the new firstfree for X * the next call of find_table_space() X */ X if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT ) X firstfree = i + 1; X X /* check to see if all elements in chk (and therefore nxt) that are X * needed for the new state have not yet been taken X */ X X state_ptr = &state[1]; X ptr_to_last_entry_in_state = &chk[i + numecs + 1]; X X for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state; X ++chk_ptr ) X if ( *(state_ptr++) != 0 && *chk_ptr != 0 ) X break; X X if ( chk_ptr == ptr_to_last_entry_in_state ) X return ( i ); X X else X ++i; X } X } X X X/* inittbl - initialize transition tables X * X * synopsis X * inittbl(); X * X * Initializes "firstfree" to be one beyond the end of the table. Initializes X * all "chk" entries to be zero. Note that templates are built in their X * own tbase/tdef tables. They are shifted down to be contiguous X * with the non-template entries during table generation. X */ Xinittbl() X X { X register int i; X X bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) ); X X tblend = 0; X firstfree = tblend + 1; X numtemps = 0; X X if ( usemecs ) X { X /* set up doubly-linked meta-equivalence classes X * these are sets of equivalence classes which all have identical X * transitions out of TEMPLATES X */ X X tecbck[1] = NIL; X X for ( i = 2; i <= numecs; ++i ) X { X tecbck[i] = i - 1; X tecfwd[i - 1] = i; X } X X tecfwd[numecs] = NIL; X } X } X X X/* mkdeftbl - make the default, "jam" table entries X * X * synopsis X * mkdeftbl(); X */ X Xmkdeftbl() X X { X int i; X X jamstate = lastdfa + 1; X X ++tblend; /* room for transition on end-of-buffer character */ X X if ( tblend + numecs > current_max_xpairs ) X expand_nxt_chk(); X X /* add in default end-of-buffer transition */ X nxt[tblend] = end_of_buffer_state; X chk[tblend] = jamstate; X X for ( i = 1; i <= numecs; ++i ) X { X nxt[tblend + i] = 0; X chk[tblend + i] = jamstate; X } X X jambase = tblend; X X base[jamstate] = jambase; X def[jamstate] = 0; X X tblend += numecs; X ++numtemps; X } X X X/* mkentry - create base/def and nxt/chk entries for transition array X * X * synopsis X * int state[numchars + 1], numchars, statenum, deflink, totaltrans; X * mkentry( state, numchars, statenum, deflink, totaltrans ); X * X * "state" is a transition array "numchars" characters in size, "statenum" X * is the offset to be used into the base/def tables, and "deflink" is the X * entry to put in the "def" table entry. If "deflink" is equal to X * "JAMSTATE", then no attempt will be made to fit zero entries of "state" X * (i.e., jam entries) into the table. It is assumed that by linking to X * "JAMSTATE" they will be taken care of. In any case, entries in "state" X * marking transitions to "SAME_TRANS" are treated as though they will be X * taken care of by whereever "deflink" points. "totaltrans" is the total X * number of transitions out of the state. If it is below a certain threshold, X * the tables are searched for an interior spot that will accommodate the X * state array. X */ X Xmkentry( state, numchars, statenum, deflink, totaltrans ) Xregister int *state; Xint numchars, statenum, deflink, totaltrans; X X { X register int minec, maxec, i, baseaddr; X int tblbase, tbllast; X X if ( totaltrans == 0 ) X { /* there are no out-transitions */ X if ( deflink == JAMSTATE ) X base[statenum] = JAMSTATE; X else X base[statenum] = 0; X X def[statenum] = deflink; X return; X } X X for ( minec = 1; minec <= numchars; ++minec ) X { X if ( state[minec] != SAME_TRANS ) X if ( state[minec] != 0 || deflink != JAMSTATE ) X break; X } X X if ( totaltrans == 1 ) X { X /* there's only one out-transition. Save it for later to fill X * in holes in the tables. X */ X stack1( statenum, minec, state[minec], deflink ); X return; X } X X for ( maxec = numchars; maxec > 0; --maxec ) X { X if ( state[maxec] != SAME_TRANS ) X if ( state[maxec] != 0 || deflink != JAMSTATE ) X break; X } X X /* Whether we try to fit the state table in the middle of the table X * entries we have already generated, or if we just take the state X * table at the end of the nxt/chk tables, we must make sure that we X * have a valid base address (i.e., non-negative). Note that not only are X * negative base addresses dangerous at run-time (because indexing the X * next array with one and a low-valued character might generate an X * array-out-of-bounds error message), but at compile-time negative X * base addresses denote TEMPLATES. X */ X X /* find the first transition of state that we need to worry about. */ X if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE ) X { /* attempt to squeeze it into the middle of the tabls */ X baseaddr = firstfree; X X while ( baseaddr < minec ) X { X /* using baseaddr would result in a negative base address below X * find the next free slot X */ X for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr ) X ; X } X X if ( baseaddr + maxec - minec >= current_max_xpairs ) X expand_nxt_chk(); X X for ( i = minec; i <= maxec; ++i ) X if ( state[i] != SAME_TRANS ) X if ( state[i] != 0 || deflink != JAMSTATE ) X if ( chk[baseaddr + i - minec] != 0 ) X { /* baseaddr unsuitable - find another */ X for ( ++baseaddr; X baseaddr < current_max_xpairs && X chk[baseaddr] != 0; X ++baseaddr ) X ; X X if ( baseaddr + maxec - minec >= current_max_xpairs ) X expand_nxt_chk(); X X /* reset the loop counter so we'll start all X * over again next time it's incremented X */ X X i = minec - 1; X } X } X X else X { X /* ensure that the base address we eventually generate is X * non-negative X */ X baseaddr = max( tblend + 1, minec ); X } X X tblbase = baseaddr - minec; X tbllast = tblbase + maxec; X X if ( tbllast >= current_max_xpairs ) X expand_nxt_chk(); X X base[statenum] = tblbase; X def[statenum] = deflink; X X for ( i = minec; i <= maxec; ++i ) X if ( state[i] != SAME_TRANS ) X if ( state[i] != 0 || deflink != JAMSTATE ) X { X nxt[tblbase + i] = state[i]; X chk[tblbase + i] = statenum; X } X X if ( baseaddr == firstfree ) X /* find next free slot in tables */ X for ( ++firstfree; chk[firstfree] != 0; ++firstfree ) X ; X X tblend = max( tblend, tbllast ); X } X X X/* mk1tbl - create table entries for a state (or state fragment) which X * has only one out-transition X * X * synopsis X * int state, sym, onenxt, onedef; X * mk1tbl( state, sym, onenxt, onedef ); X */ X Xmk1tbl( state, sym, onenxt, onedef ) Xint state, sym, onenxt, onedef; X X { X if ( firstfree < sym ) X firstfree = sym; X X while ( chk[firstfree] != 0 ) X if ( ++firstfree >= current_max_xpairs ) X expand_nxt_chk(); X X base[state] = firstfree - sym; X def[state] = onedef; X chk[firstfree] = state; X nxt[firstfree] = onenxt; X X if ( firstfree > tblend ) X { X tblend = firstfree++; X X if ( firstfree >= current_max_xpairs ) X expand_nxt_chk(); X } X } X X X/* mkprot - create new proto entry X * X * synopsis X * int state[], statenum, comstate; X * mkprot( state, statenum, comstate ); X */ X Xmkprot( state, statenum, comstate ) Xint state[], statenum, comstate; X X { X int i, slot, tblbase; X X if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE ) X { X /* gotta make room for the new proto by dropping last entry in X * the queue X */ X slot = lastprot; X lastprot = protprev[lastprot]; X protnext[lastprot] = NIL; X } X X else X slot = numprots; X X protnext[slot] = firstprot; X X if ( firstprot != NIL ) X protprev[firstprot] = slot; X X firstprot = slot; X prottbl[slot] = statenum; X protcomst[slot] = comstate; X X /* copy state into save area so it can be compared with rapidly */ X tblbase = numecs * (slot - 1); X X for ( i = 1; i <= numecs; ++i ) X protsave[tblbase + i] = state[i]; X } X X X/* mktemplate - create a template entry based on a state, and connect the state X * to it X * X * synopsis X * int state[], statenum, comstate, totaltrans; X * mktemplate( state, statenum, comstate, totaltrans ); X */ X Xmktemplate( state, statenum, comstate ) Xint state[], statenum, comstate; X X { X int i, numdiff, tmpbase, tmp[CSIZE + 1]; X char transset[CSIZE + 1]; X int tsptr; X X ++numtemps; X X tsptr = 0; X X /* calculate where we will temporarily store the transition table X * of the template in the tnxt[] array. The final transition table X * gets created by cmptmps() X */ X X tmpbase = numtemps * numecs; X X if ( tmpbase + numecs >= current_max_template_xpairs ) X { X current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT; X X ++num_reallocs; X X tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs ); X } X X for ( i = 1; i <= numecs; ++i ) X if ( state[i] == 0 ) X tnxt[tmpbase + i] = 0; X else X { X transset[tsptr++] = i; X tnxt[tmpbase + i] = comstate; X } X X if ( usemecs ) X mkeccl( transset, tsptr, tecfwd, tecbck, numecs ); X X mkprot( tnxt + tmpbase, -numtemps, comstate ); X X /* we rely on the fact that mkprot adds things to the beginning X * of the proto queue X */ X X numdiff = tbldiff( state, firstprot, tmp ); X mkentry( tmp, numecs, statenum, -numtemps, numdiff ); X } X X X/* mv2front - move proto queue element to front of queue X * X * synopsis X * int qelm; X * mv2front( qelm ); X */ X Xmv2front( qelm ) Xint qelm; X X { X if ( firstprot != qelm ) X { X if ( qelm == lastprot ) X lastprot = protprev[lastprot]; X X protnext[protprev[qelm]] = protnext[qelm]; X X if ( protnext[qelm] != NIL ) X protprev[protnext[qelm]] = protprev[qelm]; X X protprev[qelm] = NIL; X protnext[qelm] = firstprot; X protprev[firstprot] = qelm; X firstprot = qelm; X } X } X X X/* place_state - place a state into full speed transition table X * X * synopsis X * int *state, statenum, transnum; X * place_state( state, statenum, transnum ); X * X * State is the statenum'th state. It is indexed by equivalence class and X * gives the number of the state to enter for a given equivalence class. X * Transnum is the number of out-transitions for the state. X */ X Xplace_state( state, statenum, transnum ) Xint *state, statenum, transnum; X X { X register int i; X register int *state_ptr; X int position = find_table_space( state, transnum ); X X /* base is the table of start positions */ X base[statenum] = position; X X /* put in action number marker; this non-zero number makes sure that X * find_table_space() knows that this position in chk/nxt is taken X * and should not be used for another accepting number in another state X */ X chk[position - 1] = 1; X X /* put in end-of-buffer marker; this is for the same purposes as above */ X chk[position] = 1; X X /* place the state into chk and nxt */ X state_ptr = &state[1]; X X for ( i = 1; i <= numecs; ++i, ++state_ptr ) X if ( *state_ptr != 0 ) X { X chk[position + i] = i; X nxt[position + i] = *state_ptr; X } X X if ( position + numecs > tblend ) X tblend = position + numecs; X } X X X/* stack1 - save states with only one out-transition to be processed later X * X * synopsis X * int statenum, sym, nextstate, deflink; X * stack1( statenum, sym, nextstate, deflink ); X * X * if there's room for another state one the "one-transition" stack, the X * state is pushed onto it, to be processed later by mk1tbl. If there's X * no room, we process the sucker right now. X */ X Xstack1( statenum, sym, nextstate, deflink ) Xint statenum, sym, nextstate, deflink; X X { X if ( onesp >= ONE_STACK_SIZE - 1 ) X mk1tbl( statenum, sym, nextstate, deflink ); X X else X { X ++onesp; X onestate[onesp] = statenum; X onesym[onesp] = sym; X onenext[onesp] = nextstate; X onedef[onesp] = deflink; X } X } X X X/* tbldiff - compute differences between two state tables X * X * synopsis X * int state[], pr, ext[]; X * int tbldiff, numdifferences; X * numdifferences = tbldiff( state, pr, ext ) X * X * "state" is the state array which is to be extracted from the pr'th X * proto. "pr" is both the number of the proto we are extracting from X * and an index into the save area where we can find the proto's complete X * state table. Each entry in "state" which differs from the corresponding X * entry of "pr" will appear in "ext". X * Entries which are the same in both "state" and "pr" will be marked X * as transitions to "SAME_TRANS" in "ext". The total number of differences X * between "state" and "pr" is returned as function value. Note that this X * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". X */ X Xint tbldiff( state, pr, ext ) Xint state[], pr, ext[]; X X { X register int i, *sp = state, *ep = ext, *protp; X register int numdiff = 0; X X protp = &protsave[numecs * (pr - 1)]; X X for ( i = numecs; i > 0; --i ) X { X if ( *++protp == *++sp ) X *++ep = SAME_TRANS; X else X { X *++ep = *sp; X ++numdiff; X } X } X X return ( numdiff ); X } END_OF_FILE if test 24794 -ne `wc -c <'flex/tblcmp.c'`; then echo shar: \"'flex/tblcmp.c'\" unpacked with wrong size! fi # end of 'flex/tblcmp.c' fi echo shar: End of archive 5 \(of 7\). cp /dev/null ark5isdone MISSING="" for I in 1 2 3 4 5 6 7 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 7 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0 -- Please send comp.sources.unix-related mail to rsalz@uunet.uu.net. Use a domain-based address or give alternate paths, or you may lose out.