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