/* $OpenBSD: nfa.c,v 1.4 2001/06/17 07:30:42 deraadt 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. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that: (1) source distributions * retain this entire copyright notice and comment, and (2) distributions * including binaries display the following acknowledgement: ``This product * includes software developed by the University of California, Berkeley * and its contributors'' in the documentation or other materials provided * with the distribution and in all advertising materials mentioning * features or use of this software. 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. */ /* $Header: /cvs/OpenBSD/src/usr.bin/lex/nfa.c,v 1.4 2001/06/17 07:30:42 deraadt Exp $ */ #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 ) int mach, variable_trail_rule, headcnt, trailcnt; { 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]; sprintf( action_text, "case %d:\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_c_buf_p = yy_cp"; char *scanner_bp = "yy_bp"; add_action( "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" ); if ( headcnt > 0 ) { sprintf( action_text, "%s = %s + %d;\n", scanner_cp, scanner_bp, headcnt ); add_action( action_text ); } else { sprintf( 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 ) register 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 INFINITY 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 == INFINITY ) { 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 ) lerrif( _( "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 ); } if ( num_rules > MAX_RULE ) lerrif( _( "too many rules (> %d)!" ), MAX_RULE ); rule_linenum[num_rules] = linenum; rule_useful[num_rules] = false; }