| /* nfa - NFA 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. */ |
| |
| /* This file is part of flex. */ |
| |
| /* 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" |
| |
| |
| /* declare functions that have forward references */ |
| |
| int dupmachine(int); |
| void mkxtion(int, int); |
| |
| |
| /* add_accept - add an accepting state to a machine |
| * |
| * accepting_number becomes mach's accepting number. |
| */ |
| |
| void add_accept (int mach, int accepting_number) |
| { |
| /* Hang the accepting number off an epsilon state. if it is associated |
| * with a state that has a non-epsilon out-transition, then the state |
| * will accept BEFORE it makes that transition, i.e., one character |
| * too soon. |
| */ |
| |
| if (transchar[finalst[mach]] == SYM_EPSILON) |
| accptnum[finalst[mach]] = accepting_number; |
| |
| else { |
| int astate = mkstate (SYM_EPSILON); |
| |
| accptnum[astate] = accepting_number; |
| (void) link_machines (mach, astate); |
| } |
| } |
| |
| |
| /* copysingl - make a given number of copies of a singleton machine |
| * |
| * synopsis |
| * |
| * newsng = copysingl( singl, num ); |
| * |
| * newsng - a new singleton composed of num copies of singl |
| * singl - a singleton machine |
| * num - the number of copies of singl to be present in newsng |
| */ |
| |
| int copysingl (int singl, int num) |
| { |
| int copy, i; |
| |
| copy = mkstate (SYM_EPSILON); |
| |
| for (i = 1; i <= num; ++i) |
| copy = link_machines (copy, dupmachine (singl)); |
| |
| return copy; |
| } |
| |
| |
| /* dumpnfa - debugging routine to write out an nfa */ |
| |
| void dumpnfa (int state1) |
| { |
| int sym, tsp1, tsp2, anum, ns; |
| |
| fprintf (stderr, |
| _ |
| ("\n\n********** beginning dump of nfa with start state %d\n"), |
| state1); |
| |
| /* We probably should loop starting at firstst[state1] and going to |
| * lastst[state1], but they're not maintained properly when we "or" |
| * all of the rules together. So we use our knowledge that the machine |
| * starts at state 1 and ends at lastnfa. |
| */ |
| |
| /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */ |
| for (ns = 1; ns <= lastnfa; ++ns) { |
| fprintf (stderr, _("state # %4d\t"), ns); |
| |
| sym = transchar[ns]; |
| tsp1 = trans1[ns]; |
| tsp2 = trans2[ns]; |
| anum = accptnum[ns]; |
| |
| fprintf (stderr, "%3d: %4d, %4d", sym, tsp1, tsp2); |
| |
| if (anum != NIL) |
| fprintf (stderr, " [%d]", anum); |
| |
| fprintf (stderr, "\n"); |
| } |
| |
| fprintf (stderr, _("********** end of dump\n")); |
| } |
| |
| |
| /* dupmachine - make a duplicate of a given machine |
| * |
| * synopsis |
| * |
| * copy = dupmachine( mach ); |
| * |
| * copy - holds duplicate of mach |
| * mach - machine to be duplicated |
| * |
| * note that the copy of mach is NOT an exact duplicate; rather, all the |
| * transition states values are adjusted so that the copy is self-contained, |
| * as the original should have been. |
| * |
| * also note that the original MUST be contiguous, with its low and high |
| * states accessible by the arrays firstst and lastst |
| */ |
| |
| int dupmachine (int mach) |
| { |
| int i, init, state_offset; |
| int state = 0; |
| int last = lastst[mach]; |
| |
| for (i = firstst[mach]; i <= last; ++i) { |
| state = mkstate (transchar[i]); |
| |
| if (trans1[i] != NO_TRANSITION) { |
| mkxtion (finalst[state], trans1[i] + state - i); |
| |
| if (transchar[i] == SYM_EPSILON && |
| trans2[i] != NO_TRANSITION) |
| mkxtion (finalst[state], |
| trans2[i] + state - i); |
| } |
| |
| accptnum[state] = accptnum[i]; |
| } |
| |
| if (state == 0) |
| flexfatal (_("empty machine in dupmachine()")); |
| |
| state_offset = state - i + 1; |
| |
| init = mach + state_offset; |
| firstst[init] = firstst[mach] + state_offset; |
| finalst[init] = finalst[mach] + state_offset; |
| lastst[init] = lastst[mach] + state_offset; |
| |
| return init; |
| } |
| |
| |
| /* finish_rule - finish up the processing for a rule |
| * |
| * An accepting number is added to the given machine. If variable_trail_rule |
| * is true then the rule has trailing context and both the head and trail |
| * are variable size. Otherwise if headcnt or trailcnt is non-zero then |
| * the machine recognizes a pattern with trailing context and headcnt is |
| * the number of characters in the matched part of the pattern, or zero |
| * if the matched part has variable length. trailcnt is the number of |
| * trailing context characters in the pattern, or zero if the trailing |
| * context has variable length. |
| */ |
| |
| void finish_rule (int mach, int variable_trail_rule, int headcnt, int trailcnt, |
| int pcont_act) |
| { |
| char action_text[MAXLINE]; |
| |
| add_accept (mach, num_rules); |
| |
| /* We did this in new_rule(), but it often gets the wrong |
| * number because we do it before we start parsing the current rule. |
| */ |
| rule_linenum[num_rules] = linenum; |
| |
| /* If this is a continued action, then the line-number has already |
| * been updated, giving us the wrong number. |
| */ |
| if (continued_action) |
| --rule_linenum[num_rules]; |
| |
| |
| /* If the previous rule was continued action, then we inherit the |
| * previous newline flag, possibly overriding the current one. |
| */ |
| if (pcont_act && rule_has_nl[num_rules - 1]) |
| rule_has_nl[num_rules] = true; |
| |
| snprintf (action_text, sizeof(action_text), "case %d:\n", num_rules); |
| add_action (action_text); |
| if (rule_has_nl[num_rules]) { |
| snprintf (action_text, sizeof(action_text), "/* rule %d can match eol */\n", |
| num_rules); |
| add_action (action_text); |
| } |
| |
| |
| if (variable_trail_rule) { |
| rule_type[num_rules] = RULE_VARIABLE; |
| |
| if (performance_report > 0) |
| fprintf (stderr, |
| _ |
| ("Variable trailing context rule at line %d\n"), |
| rule_linenum[num_rules]); |
| |
| variable_trailing_context_rules = true; |
| } |
| |
| else { |
| rule_type[num_rules] = RULE_NORMAL; |
| |
| if (headcnt > 0 || trailcnt > 0) { |
| /* Do trailing context magic to not match the trailing |
| * characters. |
| */ |
| char *scanner_cp = "YY_G(yy_c_buf_p) = yy_cp"; |
| char *scanner_bp = "yy_bp"; |
| |
| add_action |
| ("*yy_cp = YY_G(yy_hold_char); /* undo effects of setting up yytext */\n"); |
| |
| if (headcnt > 0) { |
| if (rule_has_nl[num_rules]) { |
| snprintf (action_text, sizeof(action_text), |
| "YY_LINENO_REWIND_TO(%s + %d);\n", scanner_bp, headcnt); |
| add_action (action_text); |
| } |
| snprintf (action_text, sizeof(action_text), "%s = %s + %d;\n", |
| scanner_cp, scanner_bp, headcnt); |
| add_action (action_text); |
| } |
| |
| else { |
| if (rule_has_nl[num_rules]) { |
| snprintf (action_text, sizeof(action_text), |
| "YY_LINENO_REWIND_TO(yy_cp - %d);\n", trailcnt); |
| add_action (action_text); |
| } |
| |
| snprintf (action_text, sizeof(action_text), "%s -= %d;\n", |
| scanner_cp, trailcnt); |
| add_action (action_text); |
| } |
| |
| add_action |
| ("YY_DO_BEFORE_ACTION; /* set up yytext again */\n"); |
| } |
| } |
| |
| /* Okay, in the action code at this point yytext and yyleng have |
| * their proper final values for this rule, so here's the point |
| * to do any user action. But don't do it for continued actions, |
| * as that'll result in multiple YY_RULE_SETUP's. |
| */ |
| if (!continued_action) |
| add_action ("YY_RULE_SETUP\n"); |
| |
| line_directive_out(NULL, 1); |
| add_action("[["); |
| } |
| |
| |
| /* link_machines - connect two machines together |
| * |
| * synopsis |
| * |
| * new = link_machines( first, last ); |
| * |
| * new - a machine constructed by connecting first to last |
| * first - the machine whose successor is to be last |
| * last - the machine whose predecessor is to be first |
| * |
| * note: this routine concatenates the machine first with the machine |
| * last to produce a machine new which will pattern-match first first |
| * and then last, and will fail if either of the sub-patterns fails. |
| * FIRST is set to new by the operation. last is unmolested. |
| */ |
| |
| int link_machines (int first, int last) |
| { |
| if (first == NIL) |
| return last; |
| |
| else if (last == NIL) |
| return first; |
| |
| else { |
| mkxtion (finalst[first], last); |
| finalst[first] = finalst[last]; |
| lastst[first] = MAX (lastst[first], lastst[last]); |
| firstst[first] = MIN (firstst[first], firstst[last]); |
| |
| return first; |
| } |
| } |
| |
| |
| /* mark_beginning_as_normal - mark each "beginning" state in a machine |
| * as being a "normal" (i.e., not trailing context- |
| * associated) states |
| * |
| * The "beginning" states are the epsilon closure of the first state |
| */ |
| |
| void mark_beginning_as_normal (int mach) |
| { |
| switch (state_type[mach]) { |
| case STATE_NORMAL: |
| /* Oh, we've already visited here. */ |
| return; |
| |
| case STATE_TRAILING_CONTEXT: |
| state_type[mach] = STATE_NORMAL; |
| |
| if (transchar[mach] == SYM_EPSILON) { |
| if (trans1[mach] != NO_TRANSITION) |
| mark_beginning_as_normal (trans1[mach]); |
| |
| if (trans2[mach] != NO_TRANSITION) |
| mark_beginning_as_normal (trans2[mach]); |
| } |
| break; |
| |
| default: |
| flexerror (_ |
| ("bad state type in mark_beginning_as_normal()")); |
| break; |
| } |
| } |
| |
| |
| /* mkbranch - make a machine that branches to two machines |
| * |
| * synopsis |
| * |
| * branch = mkbranch( first, second ); |
| * |
| * branch - a machine which matches either first's pattern or second's |
| * first, second - machines whose patterns are to be or'ed (the | operator) |
| * |
| * Note that first and second are NEITHER destroyed by the operation. Also, |
| * the resulting machine CANNOT be used with any other "mk" operation except |
| * more mkbranch's. Compare with mkor() |
| */ |
| |
| int mkbranch (int first, int second) |
| { |
| int eps; |
| |
| if (first == NO_TRANSITION) |
| return second; |
| |
| else if (second == NO_TRANSITION) |
| return first; |
| |
| eps = mkstate (SYM_EPSILON); |
| |
| mkxtion (eps, first); |
| mkxtion (eps, second); |
| |
| return eps; |
| } |
| |
| |
| /* mkclos - convert a machine into a closure |
| * |
| * synopsis |
| * new = mkclos( state ); |
| * |
| * new - a new state which matches the closure of "state" |
| */ |
| |
| int mkclos (int state) |
| { |
| return mkopt (mkposcl (state)); |
| } |
| |
| |
| /* mkopt - make a machine optional |
| * |
| * synopsis |
| * |
| * new = mkopt( mach ); |
| * |
| * new - a machine which optionally matches whatever mach matched |
| * mach - the machine to make optional |
| * |
| * notes: |
| * 1. mach must be the last machine created |
| * 2. mach is destroyed by the call |
| */ |
| |
| int mkopt (int mach) |
| { |
| int eps; |
| |
| if (!SUPER_FREE_EPSILON (finalst[mach])) { |
| eps = mkstate (SYM_EPSILON); |
| mach = link_machines (mach, eps); |
| } |
| |
| /* Can't skimp on the following if FREE_EPSILON(mach) is true because |
| * some state interior to "mach" might point back to the beginning |
| * for a closure. |
| */ |
| eps = mkstate (SYM_EPSILON); |
| mach = link_machines (eps, mach); |
| |
| mkxtion (mach, finalst[mach]); |
| |
| return mach; |
| } |
| |
| |
| /* mkor - make a machine that matches either one of two machines |
| * |
| * synopsis |
| * |
| * new = mkor( first, second ); |
| * |
| * new - a machine which matches either first's pattern or second's |
| * first, second - machines whose patterns are to be or'ed (the | operator) |
| * |
| * note that first and second are both destroyed by the operation |
| * the code is rather convoluted because an attempt is made to minimize |
| * the number of epsilon states needed |
| */ |
| |
| int mkor (int first, int second) |
| { |
| int eps, orend; |
| |
| if (first == NIL) |
| return second; |
| |
| else if (second == NIL) |
| return first; |
| |
| else { |
| /* See comment in mkopt() about why we can't use the first |
| * state of "first" or "second" if they satisfy "FREE_EPSILON". |
| */ |
| eps = mkstate (SYM_EPSILON); |
| |
| first = link_machines (eps, first); |
| |
| mkxtion (first, second); |
| |
| if (SUPER_FREE_EPSILON (finalst[first]) && |
| accptnum[finalst[first]] == NIL) { |
| orend = finalst[first]; |
| mkxtion (finalst[second], orend); |
| } |
| |
| else if (SUPER_FREE_EPSILON (finalst[second]) && |
| accptnum[finalst[second]] == NIL) { |
| orend = finalst[second]; |
| mkxtion (finalst[first], orend); |
| } |
| |
| else { |
| eps = mkstate (SYM_EPSILON); |
| |
| first = link_machines (first, eps); |
| orend = finalst[first]; |
| |
| mkxtion (finalst[second], orend); |
| } |
| } |
| |
| finalst[first] = orend; |
| return first; |
| } |
| |
| |
| /* mkposcl - convert a machine into a positive closure |
| * |
| * synopsis |
| * new = mkposcl( state ); |
| * |
| * new - a machine matching the positive closure of "state" |
| */ |
| |
| int mkposcl (int state) |
| { |
| int eps; |
| |
| if (SUPER_FREE_EPSILON (finalst[state])) { |
| mkxtion (finalst[state], state); |
| return state; |
| } |
| |
| else { |
| eps = mkstate (SYM_EPSILON); |
| mkxtion (eps, state); |
| return link_machines (state, eps); |
| } |
| } |
| |
| |
| /* mkrep - make a replicated machine |
| * |
| * synopsis |
| * new = mkrep( mach, lb, ub ); |
| * |
| * new - a machine that matches whatever "mach" matched from "lb" |
| * number of times to "ub" number of times |
| * |
| * note |
| * if "ub" is INFINITE_REPEAT then "new" matches "lb" or more occurrences of "mach" |
| */ |
| |
| int mkrep (int mach, int lb, int ub) |
| { |
| int base_mach, tail, copy, i; |
| |
| base_mach = copysingl (mach, lb - 1); |
| |
| if (ub == INFINITE_REPEAT) { |
| copy = dupmachine (mach); |
| mach = link_machines (mach, |
| link_machines (base_mach, |
| mkclos (copy))); |
| } |
| |
| else { |
| tail = mkstate (SYM_EPSILON); |
| |
| for (i = lb; i < ub; ++i) { |
| copy = dupmachine (mach); |
| tail = mkopt (link_machines (copy, tail)); |
| } |
| |
| mach = |
| link_machines (mach, |
| link_machines (base_mach, tail)); |
| } |
| |
| return mach; |
| } |
| |
| |
| /* mkstate - create a state with a transition on a given symbol |
| * |
| * synopsis |
| * |
| * state = mkstate( sym ); |
| * |
| * state - a new state matching sym |
| * sym - the symbol the new state is to have an out-transition on |
| * |
| * note that this routine makes new states in ascending order through the |
| * state array (and increments LASTNFA accordingly). The routine DUPMACHINE |
| * relies on machines being made in ascending order and that they are |
| * CONTIGUOUS. Change it and you will have to rewrite DUPMACHINE (kludge |
| * that it admittedly is) |
| */ |
| |
| int mkstate (int sym) |
| { |
| if (++lastnfa >= current_mns) { |
| if ((current_mns += MNS_INCREMENT) >= maximum_mns) |
| lerr(_ |
| ("input rules are too complicated (>= %d NFA states)"), |
| current_mns); |
| |
| ++num_reallocs; |
| |
| firstst = reallocate_integer_array (firstst, current_mns); |
| lastst = reallocate_integer_array (lastst, current_mns); |
| finalst = reallocate_integer_array (finalst, current_mns); |
| transchar = |
| reallocate_integer_array (transchar, current_mns); |
| trans1 = reallocate_integer_array (trans1, current_mns); |
| trans2 = reallocate_integer_array (trans2, current_mns); |
| accptnum = |
| reallocate_integer_array (accptnum, current_mns); |
| assoc_rule = |
| reallocate_integer_array (assoc_rule, current_mns); |
| state_type = |
| reallocate_integer_array (state_type, current_mns); |
| } |
| |
| firstst[lastnfa] = lastnfa; |
| finalst[lastnfa] = lastnfa; |
| lastst[lastnfa] = lastnfa; |
| transchar[lastnfa] = sym; |
| trans1[lastnfa] = NO_TRANSITION; |
| trans2[lastnfa] = NO_TRANSITION; |
| accptnum[lastnfa] = NIL; |
| assoc_rule[lastnfa] = num_rules; |
| state_type[lastnfa] = current_state_type; |
| |
| /* Fix up equivalence classes base on this transition. Note that any |
| * character which has its own transition gets its own equivalence |
| * class. Thus only characters which are only in character classes |
| * have a chance at being in the same equivalence class. E.g. "a|b" |
| * puts 'a' and 'b' into two different equivalence classes. "[ab]" |
| * puts them in the same equivalence class (barring other differences |
| * elsewhere in the input). |
| */ |
| |
| if (sym < 0) { |
| /* We don't have to update the equivalence classes since |
| * that was already done when the ccl was created for the |
| * first time. |
| */ |
| } |
| |
| else if (sym == SYM_EPSILON) |
| ++numeps; |
| |
| else { |
| check_char (sym); |
| |
| if (useecs) |
| /* Map NUL's to csize. */ |
| mkechar (sym ? sym : csize, nextecm, ecgroup); |
| } |
| |
| return lastnfa; |
| } |
| |
| |
| /* mkxtion - make a transition from one state to another |
| * |
| * synopsis |
| * |
| * mkxtion( statefrom, stateto ); |
| * |
| * statefrom - the state from which the transition is to be made |
| * stateto - the state to which the transition is to be made |
| */ |
| |
| void mkxtion (int statefrom, int stateto) |
| { |
| if (trans1[statefrom] == NO_TRANSITION) |
| trans1[statefrom] = stateto; |
| |
| else if ((transchar[statefrom] != SYM_EPSILON) || |
| (trans2[statefrom] != NO_TRANSITION)) |
| flexfatal (_("found too many transitions in mkxtion()")); |
| |
| else { /* second out-transition for an epsilon state */ |
| ++eps2; |
| trans2[statefrom] = stateto; |
| } |
| } |
| |
| /* new_rule - initialize for a new rule */ |
| |
| void new_rule (void) |
| { |
| if (++num_rules >= current_max_rules) { |
| ++num_reallocs; |
| current_max_rules += MAX_RULES_INCREMENT; |
| rule_type = reallocate_integer_array (rule_type, |
| current_max_rules); |
| rule_linenum = reallocate_integer_array (rule_linenum, |
| current_max_rules); |
| rule_useful = reallocate_integer_array (rule_useful, |
| current_max_rules); |
| rule_has_nl = reallocate_bool_array (rule_has_nl, |
| current_max_rules); |
| } |
| |
| if (num_rules > MAX_RULE) |
| lerr (_("too many rules (> %d)!"), MAX_RULE); |
| |
| rule_linenum[num_rules] = linenum; |
| rule_useful[num_rules] = false; |
| rule_has_nl[num_rules] = false; |
| } |