Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume19/flex2/part05

Internet Message Format | 1989-06-21 | 50.3 KB

Subject:  v19i059:  Flex, a fast LEX replacement, Part05/07
Newsgroups: comp.sources.unix
Sender: sources
Approved: [e-mail]

Submitted-by: Vern Paxson <[e-mail]>
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 [e-mail] 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