summaryrefslogtreecommitdiff
path: root/src/nfa.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/nfa.c')
-rw-r--r--src/nfa.c719
1 files changed, 719 insertions, 0 deletions
diff --git a/src/nfa.c b/src/nfa.c
new file mode 100644
index 0000000..ee06578
--- /dev/null
+++ b/src/nfa.c
@@ -0,0 +1,719 @@
+/* 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 PROTO ((int));
+void mkxtion PROTO ((int, int));
+
+
+/* add_accept - add an accepting state to a machine
+ *
+ * accepting_number becomes mach's accepting number.
+ */
+
+void add_accept (mach, accepting_number)
+ int mach, 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 (singl, num)
+ int singl, 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 (state1)
+ 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 (mach)
+ 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 (mach, variable_trail_rule, headcnt, trailcnt,
+ pcont_act)
+ int mach, variable_trail_rule, headcnt, trailcnt, 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 ((FILE *) 0, 1);
+}
+
+
+/* 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 (first, last)
+ int first, 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 (mach)
+ 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 (first, second)
+ int first, 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 (state)
+ 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 (mach)
+ 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 (first, second)
+ int first, 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 (state)
+ 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 (mach, lb, ub)
+ int mach, lb, 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 (sym)
+ 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 (statefrom, stateto)
+ int statefrom, 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 ()
+{
+ 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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-30 08:26:11 +0000