/*	$OpenBSD: nfa.c,v 1.11 2015/11/19 22:52:40 tedu Exp $	*/

/* 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.

	 */

	else {

	}

/* 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;

}

/* dumpnfa - debugging routine to write out an nfa */

void

dumpnfa(state1)

	int state1;

{

	int sym, tsp1, tsp2, anum, ns;

	    _

	    ("\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 ) */

	}

}

/* 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;

			    trans2[i] != NO_TRANSITION)

				    trans2[i] + state - i);

		}

	}

}

/* 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];

	/*

	 * We did this in new_rule(), but it often gets the wrong number

	 * because we do it before we start parsing the current rule.

	 */

	/*

	 * If this is a continued action, then the line-number has already

	 * been updated, giving us the wrong number.

	 */

	/*

	 * If the previous rule was continued action, then we inherit the

	 * previous newline flag, possibly overriding the current one.

	 */

		    num_rules);

	}

			    _

			    ("Variable trailing context rule at line %d\n"),

			    rule_linenum[num_rules]);

	} else {

			/*

			 * Do trailing context magic to not match the

			 * trailing characters.

			 */

			    ("*yy_cp = YY_G(yy_hold_char); /* undo effects of setting up yytext */\n");

					    "YY_LINENO_REWIND_TO(%s + %d);\n", scanner_bp, headcnt);

				}

				    scanner_cp, scanner_bp, headcnt);

			} else {

					    "YY_LINENO_REWIND_TO(yy_cp - %d);\n", trailcnt);

				}

				    scanner_cp, trailcnt);

			}

			    ("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.

	 */

/* 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;

	else {

	}

}

/* 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;

{

	case STATE_NORMAL:

		/* Oh, we've already visited here. */

		return;

	case STATE_TRAILING_CONTEXT:

		}

		break;

	default:

		    ("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;

}

/* 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;

}

/* 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;

	}

	/*

	 * 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.

	 */

}

/* 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;

	else {

		/*

		 * See comment in mkopt() about why we can't use the first

		 * state of "first" or "second" if they satisfy

		 * "FREE_EPSILON".

		 */

		    accptnum[finalst[first]] == NIL) {

		    accptnum[finalst[second]] == NIL) {

		} else {

		}

	}

}

/* 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;

	} else {

	}

}

/* 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;

		    link_machines(base_mach,

			mkclos(copy)));

	} else {

		}

		    link_machines(mach,

		    link_machines(base_mach, tail));

	}

}

/* 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;

			    ("input rules are too complicated (>= %d NFA states)"),

			    current_mns);

		    reallocate_integer_array(transchar, current_mns);

		    reallocate_integer_array(accptnum, current_mns);

		    reallocate_integer_array(assoc_rule, current_mns);

		    reallocate_integer_array(state_type, current_mns);

	}

	/*

	 * 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).

	 */

		/*

		 * We don't have to update the equivalence classes since that

		 * was already done when the ccl was created for the first

		 * time.

		 */

	else {

			/* Map NUL's to csize. */

	}

}

/* 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;

	    (trans2[statefrom] != NO_TRANSITION))

	else {			/* second out-transition for an epsilon state */

	}

/* new_rule - initialize for a new rule */

void

new_rule()

		    current_max_rules);

		    current_max_rules);

		    current_max_rules);

		    current_max_rules);

	}