| /* dfa - DFA construction routines */ |
| |
| /* Copyright (c) 1990 The Regents of the University of California. */ |
| /* All rights reserved. */ |
| |
| /* This code is derived from software contributed to Berkeley by */ |
| /* Vern Paxson. */ |
| |
| /* The United States Government has rights in this work pursuant */ |
| /* to contract no. DE-AC03-76SF00098 between the United States */ |
| /* Department of Energy and the University of California. */ |
| |
| /* Redistribution and use in source and binary forms, with or without */ |
| /* modification, are permitted provided that the following conditions */ |
| /* are met: */ |
| |
| /* 1. Redistributions of source code must retain the above copyright */ |
| /* notice, this list of conditions and the following disclaimer. */ |
| /* 2. Redistributions in binary form must reproduce the above copyright */ |
| /* notice, this list of conditions and the following disclaimer in the */ |
| /* documentation and/or other materials provided with the distribution. */ |
| |
| /* Neither the name of the University nor the names of its contributors */ |
| /* may be used to endorse or promote products derived from this software */ |
| /* without specific prior written permission. */ |
| |
| /* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ |
| /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ |
| /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ |
| /* PURPOSE. */ |
| |
| #include "flexdef.h" |
| #include "tables.h" |
| |
| /* declare functions that have forward references */ |
| |
| void dump_associated_rules(FILE *, int); |
| void dump_transitions(FILE *, int[]); |
| void sympartition(int[], int, int[], int[]); |
| int symfollowset(int[], int, int, int[]); |
| |
| |
| /* check_for_backing_up - check a DFA state for backing up |
| * |
| * synopsis |
| * void check_for_backing_up( int ds, int state[numecs] ); |
| * |
| * ds is the number of the state to check and state[] is its out-transitions, |
| * indexed by equivalence class. |
| */ |
| |
| void check_for_backing_up (int ds, int state[]) |
| { |
| if ((reject && !dfaacc[ds].dfaacc_set) || (!reject && !dfaacc[ds].dfaacc_state)) { /* state is non-accepting */ |
| ++num_backing_up; |
| |
| if (backing_up_report) { |
| fprintf (backing_up_file, |
| _("State #%d is non-accepting -\n"), ds); |
| |
| /* identify the state */ |
| dump_associated_rules (backing_up_file, ds); |
| |
| /* Now identify it further using the out- and |
| * jam-transitions. |
| */ |
| dump_transitions (backing_up_file, state); |
| |
| putc ('\n', backing_up_file); |
| } |
| } |
| } |
| |
| |
| /* check_trailing_context - check to see if NFA state set constitutes |
| * "dangerous" trailing context |
| * |
| * synopsis |
| * void check_trailing_context( int nfa_states[num_states+1], int num_states, |
| * int accset[nacc+1], int nacc ); |
| * |
| * NOTES |
| * Trailing context is "dangerous" if both the head and the trailing |
| * part are of variable size \and/ there's a DFA state which contains |
| * both an accepting state for the head part of the rule and NFA states |
| * which occur after the beginning of the trailing context. |
| * |
| * When such a rule is matched, it's impossible to tell if having been |
| * in the DFA state indicates the beginning of the trailing context or |
| * further-along scanning of the pattern. In these cases, a warning |
| * message is issued. |
| * |
| * nfa_states[1 .. num_states] is the list of NFA states in the DFA. |
| * accset[1 .. nacc] is the list of accepting numbers for the DFA state. |
| */ |
| |
| void check_trailing_context (int *nfa_states, int num_states, int *accset, int nacc) |
| { |
| int i, j; |
| |
| for (i = 1; i <= num_states; ++i) { |
| int ns = nfa_states[i]; |
| int type = state_type[ns]; |
| int ar = assoc_rule[ns]; |
| |
| if (type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE) { /* do nothing */ |
| } |
| |
| else if (type == STATE_TRAILING_CONTEXT) { |
| /* Potential trouble. Scan set of accepting numbers |
| * for the one marking the end of the "head". We |
| * assume that this looping will be fairly cheap |
| * since it's rare that an accepting number set |
| * is large. |
| */ |
| for (j = 1; j <= nacc; ++j) |
| if (accset[j] & YY_TRAILING_HEAD_MASK) { |
| line_warning (_ |
| ("dangerous trailing context"), |
| rule_linenum[ar]); |
| return; |
| } |
| } |
| } |
| } |
| |
| |
| /* dump_associated_rules - list the rules associated with a DFA state |
| * |
| * Goes through the set of NFA states associated with the DFA and |
| * extracts the first MAX_ASSOC_RULES unique rules, sorts them, |
| * and writes a report to the given file. |
| */ |
| |
| void dump_associated_rules (FILE *file, int ds) |
| { |
| int i, j; |
| int num_associated_rules = 0; |
| int rule_set[MAX_ASSOC_RULES + 1]; |
| int *dset = dss[ds]; |
| int size = dfasiz[ds]; |
| |
| for (i = 1; i <= size; ++i) { |
| int rule_num = rule_linenum[assoc_rule[dset[i]]]; |
| |
| for (j = 1; j <= num_associated_rules; ++j) |
| if (rule_num == rule_set[j]) |
| break; |
| |
| if (j > num_associated_rules) { /* new rule */ |
| if (num_associated_rules < MAX_ASSOC_RULES) |
| rule_set[++num_associated_rules] = |
| rule_num; |
| } |
| } |
| |
| qsort (&rule_set [1], (size_t) num_associated_rules, sizeof (rule_set [1]), intcmp); |
| |
| fprintf (file, _(" associated rule line numbers:")); |
| |
| for (i = 1; i <= num_associated_rules; ++i) { |
| if (i % 8 == 1) |
| putc ('\n', file); |
| |
| fprintf (file, "\t%d", rule_set[i]); |
| } |
| |
| putc ('\n', file); |
| } |
| |
| |
| /* dump_transitions - list the transitions associated with a DFA state |
| * |
| * synopsis |
| * dump_transitions( FILE *file, int state[numecs] ); |
| * |
| * Goes through the set of out-transitions and lists them in human-readable |
| * form (i.e., not as equivalence classes); also lists jam transitions |
| * (i.e., all those which are not out-transitions, plus EOF). The dump |
| * is done to the given file. |
| */ |
| |
| void dump_transitions (FILE *file, int state[]) |
| { |
| int i, ec; |
| int out_char_set[CSIZE]; |
| |
| for (i = 0; i < csize; ++i) { |
| ec = ABS (ecgroup[i]); |
| out_char_set[i] = state[ec]; |
| } |
| |
| fprintf (file, _(" out-transitions: ")); |
| |
| list_character_set (file, out_char_set); |
| |
| /* now invert the members of the set to get the jam transitions */ |
| for (i = 0; i < csize; ++i) |
| out_char_set[i] = !out_char_set[i]; |
| |
| fprintf (file, _("\n jam-transitions: EOF ")); |
| |
| list_character_set (file, out_char_set); |
| |
| putc ('\n', file); |
| } |
| |
| |
| /* epsclosure - construct the epsilon closure of a set of ndfa states |
| * |
| * synopsis |
| * int *epsclosure( int t[num_states], int *numstates_addr, |
| * int accset[num_rules+1], int *nacc_addr, |
| * int *hashval_addr ); |
| * |
| * NOTES |
| * The epsilon closure is the set of all states reachable by an arbitrary |
| * number of epsilon transitions, which themselves do not have epsilon |
| * transitions going out, unioned with the set of states which have non-null |
| * accepting numbers. t is an array of size numstates of nfa state numbers. |
| * Upon return, t holds the epsilon closure and *numstates_addr is updated. |
| * accset holds a list of the accepting numbers, and the size of accset is |
| * given by *nacc_addr. t may be subjected to reallocation if it is not |
| * large enough to hold the epsilon closure. |
| * |
| * hashval is the hash value for the dfa corresponding to the state set. |
| */ |
| |
| int *epsclosure (int *t, int *ns_addr, int accset[], int *nacc_addr, int *hv_addr) |
| { |
| int stkpos, ns, tsp; |
| int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum; |
| int stkend, nstate; |
| static int did_stk_init = false, *stk; |
| |
| #define MARK_STATE(state) \ |
| do{ trans1[state] = trans1[state] - MARKER_DIFFERENCE;} while(0) |
| |
| #define IS_MARKED(state) (trans1[state] < 0) |
| |
| #define UNMARK_STATE(state) \ |
| do{ trans1[state] = trans1[state] + MARKER_DIFFERENCE;} while(0) |
| |
| #define CHECK_ACCEPT(state) \ |
| do{ \ |
| nfaccnum = accptnum[state]; \ |
| if ( nfaccnum != NIL ) \ |
| accset[++nacc] = nfaccnum; \ |
| }while(0) |
| |
| #define DO_REALLOCATION() \ |
| do { \ |
| current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \ |
| ++num_reallocs; \ |
| t = reallocate_integer_array( t, current_max_dfa_size ); \ |
| stk = reallocate_integer_array( stk, current_max_dfa_size ); \ |
| }while(0) \ |
| |
| #define PUT_ON_STACK(state) \ |
| do { \ |
| if ( ++stkend >= current_max_dfa_size ) \ |
| DO_REALLOCATION(); \ |
| stk[stkend] = state; \ |
| MARK_STATE(state); \ |
| }while(0) |
| |
| #define ADD_STATE(state) \ |
| do { \ |
| if ( ++numstates >= current_max_dfa_size ) \ |
| DO_REALLOCATION(); \ |
| t[numstates] = state; \ |
| hashval += state; \ |
| }while(0) |
| |
| #define STACK_STATE(state) \ |
| do { \ |
| PUT_ON_STACK(state); \ |
| CHECK_ACCEPT(state); \ |
| if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \ |
| ADD_STATE(state); \ |
| }while(0) |
| |
| |
| if (!did_stk_init) { |
| stk = allocate_integer_array (current_max_dfa_size); |
| did_stk_init = true; |
| } |
| |
| nacc = stkend = hashval = 0; |
| |
| for (nstate = 1; nstate <= numstates; ++nstate) { |
| ns = t[nstate]; |
| |
| /* The state could be marked if we've already pushed it onto |
| * the stack. |
| */ |
| if (!IS_MARKED (ns)) { |
| PUT_ON_STACK (ns); |
| CHECK_ACCEPT (ns); |
| hashval += ns; |
| } |
| } |
| |
| for (stkpos = 1; stkpos <= stkend; ++stkpos) { |
| ns = stk[stkpos]; |
| transsym = transchar[ns]; |
| |
| if (transsym == SYM_EPSILON) { |
| tsp = trans1[ns] + MARKER_DIFFERENCE; |
| |
| if (tsp != NO_TRANSITION) { |
| if (!IS_MARKED (tsp)) |
| STACK_STATE (tsp); |
| |
| tsp = trans2[ns]; |
| |
| if (tsp != NO_TRANSITION |
| && !IS_MARKED (tsp)) |
| STACK_STATE (tsp); |
| } |
| } |
| } |
| |
| /* Clear out "visit" markers. */ |
| |
| for (stkpos = 1; stkpos <= stkend; ++stkpos) { |
| if (IS_MARKED (stk[stkpos])) |
| UNMARK_STATE (stk[stkpos]); |
| else |
| flexfatal (_ |
| ("consistency check failed in epsclosure()")); |
| } |
| |
| *ns_addr = numstates; |
| *hv_addr = hashval; |
| *nacc_addr = nacc; |
| |
| return t; |
| } |
| |
| |
| /* increase_max_dfas - increase the maximum number of DFAs */ |
| |
| void increase_max_dfas (void) |
| { |
| current_max_dfas += MAX_DFAS_INCREMENT; |
| |
| ++num_reallocs; |
| |
| base = reallocate_integer_array (base, current_max_dfas); |
| def = reallocate_integer_array (def, current_max_dfas); |
| dfasiz = reallocate_integer_array (dfasiz, current_max_dfas); |
| accsiz = reallocate_integer_array (accsiz, current_max_dfas); |
| dhash = reallocate_integer_array (dhash, current_max_dfas); |
| dss = reallocate_int_ptr_array (dss, current_max_dfas); |
| dfaacc = reallocate_dfaacc_union (dfaacc, current_max_dfas); |
| |
| if (nultrans) |
| nultrans = |
| reallocate_integer_array (nultrans, |
| current_max_dfas); |
| } |
| |
| |
| /* ntod - convert an ndfa to a dfa |
| * |
| * Creates the dfa corresponding to the ndfa we've constructed. The |
| * dfa starts out in state #1. |
| */ |
| |
| void ntod (void) |
| { |
| int *accset, ds, nacc, newds; |
| int sym, hashval, numstates, dsize; |
| int num_full_table_rows=0; /* used only for -f */ |
| int *nset, *dset; |
| int targptr, totaltrans, i, comstate, comfreq, targ; |
| int symlist[CSIZE + 1]; |
| int num_start_states; |
| int todo_head, todo_next; |
| |
| struct yytbl_data *yynxt_tbl = 0; |
| flex_int32_t *yynxt_data = 0, yynxt_curr = 0; |
| |
| /* Note that the following are indexed by *equivalence classes* |
| * and not by characters. Since equivalence classes are indexed |
| * beginning with 1, even if the scanner accepts NUL's, this |
| * means that (since every character is potentially in its own |
| * equivalence class) these arrays must have room for indices |
| * from 1 to CSIZE, so their size must be CSIZE + 1. |
| */ |
| int duplist[CSIZE + 1], state[CSIZE + 1]; |
| int targfreq[CSIZE + 1] = {0}, targstate[CSIZE + 1]; |
| |
| /* accset needs to be large enough to hold all of the rules present |
| * in the input, *plus* their YY_TRAILING_HEAD_MASK variants. |
| */ |
| accset = allocate_integer_array ((num_rules + 1) * 2); |
| nset = allocate_integer_array (current_max_dfa_size); |
| |
| /* The "todo" queue is represented by the head, which is the DFA |
| * state currently being processed, and the "next", which is the |
| * next DFA state number available (not in use). We depend on the |
| * fact that snstods() returns DFA's \in increasing order/, and thus |
| * need only know the bounds of the dfas to be processed. |
| */ |
| todo_head = todo_next = 0; |
| |
| for (i = 0; i <= csize; ++i) { |
| duplist[i] = NIL; |
| symlist[i] = false; |
| } |
| |
| for (i = 0; i <= num_rules; ++i) |
| accset[i] = NIL; |
| |
| if (trace) { |
| dumpnfa (scset[1]); |
| fputs (_("\n\nDFA Dump:\n\n"), stderr); |
| } |
| |
| inittbl (); |
| |
| /* Check to see whether we should build a separate table for |
| * transitions on NUL characters. We don't do this for full-speed |
| * (-F) scanners, since for them we don't have a simple state |
| * number lying around with which to index the table. We also |
| * don't bother doing it for scanners unless (1) NUL is in its own |
| * equivalence class (indicated by a positive value of |
| * ecgroup[NUL]), (2) NUL's equivalence class is the last |
| * equivalence class, and (3) the number of equivalence classes is |
| * the same as the number of characters. This latter case comes |
| * about when useecs is false or when it's true but every character |
| * still manages to land in its own class (unlikely, but it's |
| * cheap to check for). If all these things are true then the |
| * character code needed to represent NUL's equivalence class for |
| * indexing the tables is going to take one more bit than the |
| * number of characters, and therefore we won't be assured of |
| * being able to fit it into a YY_CHAR variable. This rules out |
| * storing the transitions in a compressed table, since the code |
| * for interpreting them uses a YY_CHAR variable (perhaps it |
| * should just use an integer, though; this is worth pondering ... |
| * ###). |
| * |
| * Finally, for full tables, we want the number of entries in the |
| * table to be a power of two so the array references go fast (it |
| * will just take a shift to compute the major index). If |
| * encoding NUL's transitions in the table will spoil this, we |
| * give it its own table (note that this will be the case if we're |
| * not using equivalence classes). |
| */ |
| |
| /* Note that the test for ecgroup[0] == numecs below accomplishes |
| * both (1) and (2) above |
| */ |
| if (!fullspd && ecgroup[0] == numecs) { |
| /* NUL is alone in its equivalence class, which is the |
| * last one. |
| */ |
| int use_NUL_table = (numecs == csize); |
| |
| if (fulltbl && !use_NUL_table) { |
| /* We still may want to use the table if numecs |
| * is a power of 2. |
| */ |
| if (numecs <= csize && is_power_of_2(numecs)) { |
| use_NUL_table = true; |
| } |
| } |
| |
| if (use_NUL_table) |
| nultrans = |
| allocate_integer_array (current_max_dfas); |
| |
| /* From now on, nultrans != nil indicates that we're |
| * saving null transitions for later, separate encoding. |
| */ |
| } |
| |
| |
| if (fullspd) { |
| for (i = 0; i <= numecs; ++i) |
| state[i] = 0; |
| |
| place_state (state, 0, 0); |
| dfaacc[0].dfaacc_state = 0; |
| } |
| |
| else if (fulltbl) { |
| if (nultrans) |
| /* We won't be including NUL's transitions in the |
| * table, so build it for entries from 0 .. numecs - 1. |
| */ |
| num_full_table_rows = numecs; |
| |
| else |
| /* Take into account the fact that we'll be including |
| * the NUL entries in the transition table. Build it |
| * from 0 .. numecs. |
| */ |
| num_full_table_rows = numecs + 1; |
| |
| /* Begin generating yy_nxt[][] |
| * This spans the entire LONG function. |
| * This table is tricky because we don't know how big it will be. |
| * So we'll have to realloc() on the way... |
| * we'll wait until we can calculate yynxt_tbl->td_hilen. |
| */ |
| yynxt_tbl = calloc(1, sizeof (struct yytbl_data)); |
| |
| yytbl_data_init (yynxt_tbl, YYTD_ID_NXT); |
| yynxt_tbl->td_hilen = 1; |
| yynxt_tbl->td_lolen = (flex_uint32_t) num_full_table_rows; |
| yynxt_tbl->td_data = yynxt_data = |
| calloc(yynxt_tbl->td_lolen * |
| yynxt_tbl->td_hilen, |
| sizeof (flex_int32_t)); |
| yynxt_curr = 0; |
| |
| buf_prints (&yydmap_buf, |
| "\t{YYTD_ID_NXT, (void**)&yy_nxt, sizeof(%s)},\n", |
| long_align ? "flex_int32_t" : "flex_int16_t"); |
| |
| /* Unless -Ca, declare it "short" because it's a real |
| * long-shot that that won't be large enough. |
| */ |
| if (gentables) |
| out_str_dec |
| ("static const %s yy_nxt[][%d] =\n {\n", |
| long_align ? "flex_int32_t" : "flex_int16_t", |
| num_full_table_rows); |
| else { |
| out_dec ("#undef YY_NXT_LOLEN\n#define YY_NXT_LOLEN (%d)\n", num_full_table_rows); |
| out_str ("static const %s *yy_nxt =0;\n", |
| long_align ? "flex_int32_t" : "flex_int16_t"); |
| } |
| |
| |
| if (gentables) |
| outn (" {"); |
| |
| /* Generate 0 entries for state #0. */ |
| for (i = 0; i < num_full_table_rows; ++i) { |
| mk2data (0); |
| yynxt_data[yynxt_curr++] = 0; |
| } |
| |
| dataflush (); |
| if (gentables) |
| outn (" },\n"); |
| } |
| |
| /* Create the first states. */ |
| |
| num_start_states = lastsc * 2; |
| |
| for (i = 1; i <= num_start_states; ++i) { |
| numstates = 1; |
| |
| /* For each start condition, make one state for the case when |
| * we're at the beginning of the line (the '^' operator) and |
| * one for the case when we're not. |
| */ |
| if (i % 2 == 1) |
| nset[numstates] = scset[(i / 2) + 1]; |
| else |
| nset[numstates] = |
| mkbranch (scbol[i / 2], scset[i / 2]); |
| |
| nset = epsclosure (nset, &numstates, accset, &nacc, |
| &hashval); |
| |
| if (snstods (nset, numstates, accset, nacc, hashval, &ds)) { |
| numas += nacc; |
| totnst += numstates; |
| ++todo_next; |
| |
| if (variable_trailing_context_rules && nacc > 0) |
| check_trailing_context (nset, numstates, |
| accset, nacc); |
| } |
| } |
| |
| if (!fullspd) { |
| if (!snstods (nset, 0, accset, 0, 0, &end_of_buffer_state)) |
| flexfatal (_ |
| ("could not create unique end-of-buffer state")); |
| |
| ++numas; |
| ++num_start_states; |
| ++todo_next; |
| } |
| |
| |
| while (todo_head < todo_next) { |
| targptr = 0; |
| totaltrans = 0; |
| |
| for (i = 1; i <= numecs; ++i) |
| state[i] = 0; |
| |
| ds = ++todo_head; |
| |
| dset = dss[ds]; |
| dsize = dfasiz[ds]; |
| |
| if (trace) |
| fprintf (stderr, _("state # %d:\n"), ds); |
| |
| sympartition (dset, dsize, symlist, duplist); |
| |
| for (sym = 1; sym <= numecs; ++sym) { |
| if (symlist[sym]) { |
| symlist[sym] = 0; |
| |
| if (duplist[sym] == NIL) { |
| /* Symbol has unique out-transitions. */ |
| numstates = |
| symfollowset (dset, dsize, |
| sym, nset); |
| nset = epsclosure (nset, |
| &numstates, |
| accset, &nacc, |
| &hashval); |
| |
| if (snstods |
| (nset, numstates, accset, nacc, |
| hashval, &newds)) { |
| totnst = totnst + |
| numstates; |
| ++todo_next; |
| numas += nacc; |
| |
| if (variable_trailing_context_rules && nacc > 0) |
| check_trailing_context |
| (nset, |
| numstates, |
| accset, |
| nacc); |
| } |
| |
| state[sym] = newds; |
| |
| if (trace) |
| fprintf (stderr, |
| "\t%d\t%d\n", sym, |
| newds); |
| |
| targfreq[++targptr] = 1; |
| targstate[targptr] = newds; |
| ++numuniq; |
| } |
| |
| else { |
| /* sym's equivalence class has the same |
| * transitions as duplist(sym)'s |
| * equivalence class. |
| */ |
| targ = state[duplist[sym]]; |
| state[sym] = targ; |
| |
| if (trace) |
| fprintf (stderr, |
| "\t%d\t%d\n", sym, |
| targ); |
| |
| /* Update frequency count for |
| * destination state. |
| */ |
| |
| i = 0; |
| while (targstate[++i] != targ) ; |
| |
| ++targfreq[i]; |
| ++numdup; |
| } |
| |
| ++totaltrans; |
| duplist[sym] = NIL; |
| } |
| } |
| |
| |
| numsnpairs += totaltrans; |
| |
| if (ds > num_start_states) |
| check_for_backing_up (ds, state); |
| |
| if (nultrans) { |
| nultrans[ds] = state[NUL_ec]; |
| state[NUL_ec] = 0; /* remove transition */ |
| } |
| |
| if (fulltbl) { |
| |
| /* Each time we hit here, it's another td_hilen, so we realloc. */ |
| yynxt_tbl->td_hilen++; |
| yynxt_tbl->td_data = yynxt_data = |
| realloc (yynxt_data, |
| yynxt_tbl->td_hilen * |
| yynxt_tbl->td_lolen * |
| sizeof (flex_int32_t)); |
| |
| |
| if (gentables) |
| outn (" {"); |
| |
| /* Supply array's 0-element. */ |
| if (ds == end_of_buffer_state) { |
| mk2data (-end_of_buffer_state); |
| yynxt_data[yynxt_curr++] = |
| -end_of_buffer_state; |
| } |
| else { |
| mk2data (end_of_buffer_state); |
| yynxt_data[yynxt_curr++] = |
| end_of_buffer_state; |
| } |
| |
| for (i = 1; i < num_full_table_rows; ++i) { |
| /* Jams are marked by negative of state |
| * number. |
| */ |
| mk2data (state[i] ? state[i] : -ds); |
| yynxt_data[yynxt_curr++] = |
| state[i] ? state[i] : -ds; |
| } |
| |
| dataflush (); |
| if (gentables) |
| outn (" },\n"); |
| } |
| |
| else if (fullspd) |
| place_state (state, ds, totaltrans); |
| |
| else if (ds == end_of_buffer_state) |
| /* Special case this state to make sure it does what |
| * it's supposed to, i.e., jam on end-of-buffer. |
| */ |
| stack1 (ds, 0, 0, JAMSTATE); |
| |
| else { /* normal, compressed state */ |
| |
| /* Determine which destination state is the most |
| * common, and how many transitions to it there are. |
| */ |
| |
| comfreq = 0; |
| comstate = 0; |
| |
| for (i = 1; i <= targptr; ++i) |
| if (targfreq[i] > comfreq) { |
| comfreq = targfreq[i]; |
| comstate = targstate[i]; |
| } |
| |
| bldtbl (state, ds, totaltrans, comstate, comfreq); |
| } |
| } |
| |
| if (fulltbl) { |
| dataend (); |
| if (tablesext) { |
| yytbl_data_compress (yynxt_tbl); |
| if (yytbl_data_fwrite (&tableswr, yynxt_tbl) < 0) |
| flexerror (_ |
| ("Could not write yynxt_tbl[][]")); |
| } |
| if (yynxt_tbl) { |
| yytbl_data_destroy (yynxt_tbl); |
| yynxt_tbl = 0; |
| } |
| } |
| |
| else if (!fullspd) { |
| cmptmps (); /* create compressed template entries */ |
| |
| /* Create tables for all the states with only one |
| * out-transition. |
| */ |
| while (onesp > 0) { |
| mk1tbl (onestate[onesp], onesym[onesp], |
| onenext[onesp], onedef[onesp]); |
| --onesp; |
| } |
| |
| mkdeftbl (); |
| } |
| |
| free(accset); |
| free(nset); |
| } |
| |
| |
| /* snstods - converts a set of ndfa states into a dfa state |
| * |
| * synopsis |
| * is_new_state = snstods( int sns[numstates], int numstates, |
| * int accset[num_rules+1], int nacc, |
| * int hashval, int *newds_addr ); |
| * |
| * On return, the dfa state number is in newds. |
| */ |
| |
| int snstods (int sns[], int numstates, int accset[], int nacc, int hashval, int *newds_addr) |
| { |
| int didsort = 0; |
| int i, j; |
| int newds, *oldsns; |
| |
| for (i = 1; i <= lastdfa; ++i) |
| if (hashval == dhash[i]) { |
| if (numstates == dfasiz[i]) { |
| oldsns = dss[i]; |
| |
| if (!didsort) { |
| /* We sort the states in sns so we |
| * can compare it to oldsns quickly. |
| */ |
| qsort (&sns [1], (size_t) numstates, sizeof (sns [1]), intcmp); |
| didsort = 1; |
| } |
| |
| for (j = 1; j <= numstates; ++j) |
| if (sns[j] != oldsns[j]) |
| break; |
| |
| if (j > numstates) { |
| ++dfaeql; |
| *newds_addr = i; |
| return 0; |
| } |
| |
| ++hshcol; |
| } |
| |
| else |
| ++hshsave; |
| } |
| |
| /* Make a new dfa. */ |
| |
| if (++lastdfa >= current_max_dfas) |
| increase_max_dfas (); |
| |
| newds = lastdfa; |
| |
| dss[newds] = allocate_integer_array (numstates + 1); |
| |
| /* If we haven't already sorted the states in sns, we do so now, |
| * so that future comparisons with it can be made quickly. |
| */ |
| |
| if (!didsort) |
| qsort (&sns [1], (size_t) numstates, sizeof (sns [1]), intcmp); |
| |
| for (i = 1; i <= numstates; ++i) |
| dss[newds][i] = sns[i]; |
| |
| dfasiz[newds] = numstates; |
| dhash[newds] = hashval; |
| |
| if (nacc == 0) { |
| if (reject) |
| dfaacc[newds].dfaacc_set = NULL; |
| else |
| dfaacc[newds].dfaacc_state = 0; |
| |
| accsiz[newds] = 0; |
| } |
| |
| else if (reject) { |
| /* We sort the accepting set in increasing order so the |
| * disambiguating rule that the first rule listed is considered |
| * match in the event of ties will work. |
| */ |
| |
| qsort (&accset [1], (size_t) nacc, sizeof (accset [1]), intcmp); |
| |
| dfaacc[newds].dfaacc_set = |
| allocate_integer_array (nacc + 1); |
| |
| /* Save the accepting set for later */ |
| for (i = 1; i <= nacc; ++i) { |
| dfaacc[newds].dfaacc_set[i] = accset[i]; |
| |
| if (accset[i] <= num_rules) |
| /* Who knows, perhaps a REJECT can yield |
| * this rule. |
| */ |
| rule_useful[accset[i]] = true; |
| } |
| |
| accsiz[newds] = nacc; |
| } |
| |
| else { |
| /* Find lowest numbered rule so the disambiguating rule |
| * will work. |
| */ |
| j = num_rules + 1; |
| |
| for (i = 1; i <= nacc; ++i) |
| if (accset[i] < j) |
| j = accset[i]; |
| |
| dfaacc[newds].dfaacc_state = j; |
| |
| if (j <= num_rules) |
| rule_useful[j] = true; |
| } |
| |
| *newds_addr = newds; |
| |
| return 1; |
| } |
| |
| |
| /* symfollowset - follow the symbol transitions one step |
| * |
| * synopsis |
| * numstates = symfollowset( int ds[current_max_dfa_size], int dsize, |
| * int transsym, int nset[current_max_dfa_size] ); |
| */ |
| |
| int symfollowset (int ds[], int dsize, int transsym, int nset[]) |
| { |
| int ns, tsp, sym, i, j, lenccl, ch, numstates, ccllist; |
| |
| numstates = 0; |
| |
| for (i = 1; i <= dsize; ++i) { /* for each nfa state ns in the state set of ds */ |
| ns = ds[i]; |
| sym = transchar[ns]; |
| tsp = trans1[ns]; |
| |
| if (sym < 0) { /* it's a character class */ |
| sym = -sym; |
| ccllist = cclmap[sym]; |
| lenccl = ccllen[sym]; |
| |
| if (cclng[sym]) { |
| for (j = 0; j < lenccl; ++j) { |
| /* Loop through negated character |
| * class. |
| */ |
| ch = ccltbl[ccllist + j]; |
| |
| if (ch == 0) |
| ch = NUL_ec; |
| |
| if (ch > transsym) |
| /* Transsym isn't in negated |
| * ccl. |
| */ |
| break; |
| |
| else if (ch == transsym) |
| /* next 2 */ |
| goto bottom; |
| } |
| |
| /* Didn't find transsym in ccl. */ |
| nset[++numstates] = tsp; |
| } |
| |
| else |
| for (j = 0; j < lenccl; ++j) { |
| ch = ccltbl[ccllist + j]; |
| |
| if (ch == 0) |
| ch = NUL_ec; |
| |
| if (ch > transsym) |
| break; |
| else if (ch == transsym) { |
| nset[++numstates] = tsp; |
| break; |
| } |
| } |
| } |
| |
| else if (sym == SYM_EPSILON) { /* do nothing */ |
| } |
| |
| else if (ABS (ecgroup[sym]) == transsym) |
| nset[++numstates] = tsp; |
| |
| bottom:; |
| } |
| |
| return numstates; |
| } |
| |
| |
| /* sympartition - partition characters with same out-transitions |
| * |
| * synopsis |
| * sympartition( int ds[current_max_dfa_size], int numstates, |
| * int symlist[numecs], int duplist[numecs] ); |
| */ |
| |
| void sympartition (int ds[], int numstates, int symlist[], int duplist[]) |
| { |
| int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich; |
| |
| /* Partitioning is done by creating equivalence classes for those |
| * characters which have out-transitions from the given state. Thus |
| * we are really creating equivalence classes of equivalence classes. |
| */ |
| |
| for (i = 1; i <= numecs; ++i) { /* initialize equivalence class list */ |
| duplist[i] = i - 1; |
| dupfwd[i] = i + 1; |
| } |
| |
| duplist[1] = NIL; |
| dupfwd[numecs] = NIL; |
| |
| for (i = 1; i <= numstates; ++i) { |
| ns = ds[i]; |
| tch = transchar[ns]; |
| |
| if (tch != SYM_EPSILON) { |
| if (tch < -lastccl || tch >= csize) { |
| flexfatal (_ |
| ("bad transition character detected in sympartition()")); |
| } |
| |
| if (tch >= 0) { /* character transition */ |
| int ec = ecgroup[tch]; |
| |
| mkechar (ec, dupfwd, duplist); |
| symlist[ec] = 1; |
| } |
| |
| else { /* character class */ |
| tch = -tch; |
| |
| lenccl = ccllen[tch]; |
| cclp = cclmap[tch]; |
| mkeccl (ccltbl + cclp, lenccl, dupfwd, |
| duplist, numecs, NUL_ec); |
| |
| if (cclng[tch]) { |
| j = 0; |
| |
| for (k = 0; k < lenccl; ++k) { |
| ich = ccltbl[cclp + k]; |
| |
| if (ich == 0) |
| ich = NUL_ec; |
| |
| for (++j; j < ich; ++j) |
| symlist[j] = 1; |
| } |
| |
| for (++j; j <= numecs; ++j) |
| symlist[j] = 1; |
| } |
| |
| else |
| for (k = 0; k < lenccl; ++k) { |
| ich = ccltbl[cclp + k]; |
| |
| if (ich == 0) |
| ich = NUL_ec; |
| |
| symlist[ich] = 1; |
| } |
| } |
| } |
| } |
| } |