home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / gnu / flex-2.4.6-src.lha / src / amiga / flex-2.4.6 / nfa.c < prev    next >
C/C++ Source or Header  |  1993-12-07  |  17KB  |  708 lines
  1. /* nfa - NFA construction routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. /* $Header: /home/daffy/u0/vern/flex/RCS/nfa.c,v 2.13 93/12/07 10:18:28 vern Exp $ */
  30.  
  31. #include "flexdef.h"
  32.  
  33.  
  34. /* declare functions that have forward references */
  35.  
  36. int dupmachine PROTO((int));
  37. void mkxtion PROTO((int, int));
  38.  
  39.  
  40. /* add_accept - add an accepting state to a machine
  41.  *
  42.  * accepting_number becomes mach's accepting number.
  43.  */
  44.  
  45. void add_accept( mach, accepting_number )
  46. int mach, accepting_number;
  47.     {
  48.     /* Hang the accepting number off an epsilon state.  if it is associated
  49.      * with a state that has a non-epsilon out-transition, then the state
  50.      * will accept BEFORE it makes that transition, i.e., one character
  51.      * too soon.
  52.      */
  53.  
  54.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  55.         accptnum[finalst[mach]] = accepting_number;
  56.  
  57.     else
  58.         {
  59.         int astate = mkstate( SYM_EPSILON );
  60.         accptnum[astate] = accepting_number;
  61.         (void) link_machines( mach, astate );
  62.         }
  63.     }
  64.  
  65.  
  66. /* copysingl - make a given number of copies of a singleton machine
  67.  *
  68.  * synopsis
  69.  *
  70.  *   newsng = copysingl( singl, num );
  71.  *
  72.  *     newsng - a new singleton composed of num copies of singl
  73.  *     singl  - a singleton machine
  74.  *     num    - the number of copies of singl to be present in newsng
  75.  */
  76.  
  77. int copysingl( singl, num )
  78. int singl, num;
  79.     {
  80.     int copy, i;
  81.  
  82.     copy = mkstate( SYM_EPSILON );
  83.  
  84.     for ( i = 1; i <= num; ++i )
  85.         copy = link_machines( copy, dupmachine( singl ) );
  86.  
  87.     return copy;
  88.     }
  89.  
  90.  
  91. /* dumpnfa - debugging routine to write out an nfa */
  92.  
  93. void dumpnfa( state1 )
  94. int state1;
  95.  
  96.     {
  97.     int sym, tsp1, tsp2, anum, ns;
  98.  
  99.     fprintf( stderr,
  100.         "\n\n********** beginning dump of nfa with start state %d\n",
  101.         state1 );
  102.  
  103.     /* We probably should loop starting at firstst[state1] and going to
  104.      * lastst[state1], but they're not maintained properly when we "or"
  105.      * all of the rules together.  So we use our knowledge that the machine
  106.      * starts at state 1 and ends at lastnfa.
  107.      */
  108.  
  109.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  110.     for ( ns = 1; ns <= lastnfa; ++ns )
  111.         {
  112.         fprintf( stderr, "state # %4d\t", ns );
  113.  
  114.         sym = transchar[ns];
  115.         tsp1 = trans1[ns];
  116.         tsp2 = trans2[ns];
  117.         anum = accptnum[ns];
  118.  
  119.         fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  120.  
  121.         if ( anum != NIL )
  122.             fprintf( stderr, "  [%d]", anum );
  123.  
  124.         fprintf( stderr, "\n" );
  125.         }
  126.  
  127.     fprintf( stderr, "********** end of dump\n" );
  128.     }
  129.  
  130.  
  131. /* dupmachine - make a duplicate of a given machine
  132.  *
  133.  * synopsis
  134.  *
  135.  *   copy = dupmachine( mach );
  136.  *
  137.  *     copy - holds duplicate of mach
  138.  *     mach - machine to be duplicated
  139.  *
  140.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  141.  * transition states values are adjusted so that the copy is self-contained,
  142.  * as the original should have been.
  143.  *
  144.  * also note that the original MUST be contiguous, with its low and high
  145.  * states accessible by the arrays firstst and lastst
  146.  */
  147.  
  148. int dupmachine( mach )
  149. int mach;
  150.     {
  151.     int i, init, state_offset;
  152.     int state = 0;
  153.     int last = lastst[mach];
  154.  
  155.     for ( i = firstst[mach]; i <= last; ++i )
  156.         {
  157.         state = mkstate( transchar[i] );
  158.  
  159.         if ( trans1[i] != NO_TRANSITION )
  160.             {
  161.             mkxtion( finalst[state], trans1[i] + state - i );
  162.  
  163.             if ( transchar[i] == SYM_EPSILON &&
  164.                  trans2[i] != NO_TRANSITION )
  165.                 mkxtion( finalst[state],
  166.                     trans2[i] + state - i );
  167.             }
  168.  
  169.         accptnum[state] = accptnum[i];
  170.         }
  171.  
  172.     if ( state == 0 )
  173.         flexfatal( "empty machine in dupmachine()" );
  174.  
  175.     state_offset = state - i + 1;
  176.  
  177.     init = mach + state_offset;
  178.     firstst[init] = firstst[mach] + state_offset;
  179.     finalst[init] = finalst[mach] + state_offset;
  180.     lastst[init] = lastst[mach] + state_offset;
  181.  
  182.     return init;
  183.     }
  184.  
  185.  
  186. /* finish_rule - finish up the processing for a rule
  187.  *
  188.  * An accepting number is added to the given machine.  If variable_trail_rule
  189.  * is true then the rule has trailing context and both the head and trail
  190.  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  191.  * the machine recognizes a pattern with trailing context and headcnt is
  192.  * the number of characters in the matched part of the pattern, or zero
  193.  * if the matched part has variable length.  trailcnt is the number of
  194.  * trailing context characters in the pattern, or zero if the trailing
  195.  * context has variable length.
  196.  */
  197.  
  198. void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  199. int mach, variable_trail_rule, headcnt, trailcnt;
  200.     {
  201.     char action_text[MAXLINE];
  202.  
  203.     add_accept( mach, num_rules );
  204.  
  205.     /* We did this in new_rule(), but it often gets the wrong
  206.      * number because we do it before we start parsing the current rule.
  207.      */
  208.     rule_linenum[num_rules] = linenum;
  209.  
  210.     /* If this is a continued action, then the line-number has already
  211.      * been updated, giving us the wrong number.
  212.      */
  213.     if ( continued_action )
  214.         --rule_linenum[num_rules];
  215.  
  216.     sprintf( action_text, "case %d:\n", num_rules );
  217.     add_action( action_text );
  218.  
  219.     if ( variable_trail_rule )
  220.         {
  221.         rule_type[num_rules] = RULE_VARIABLE;
  222.  
  223.         if ( performance_report > 0 )
  224.             fprintf( stderr,
  225.                 "Variable trailing context rule at line %d\n",
  226.                 rule_linenum[num_rules] );
  227.  
  228.         variable_trailing_context_rules = true;
  229.         }
  230.  
  231.     else
  232.         {
  233.         rule_type[num_rules] = RULE_NORMAL;
  234.  
  235.         if ( headcnt > 0 || trailcnt > 0 )
  236.             {
  237.             /* Do trailing context magic to not match the trailing
  238.              * characters.
  239.              */
  240.             char *scanner_cp = "yy_c_buf_p = yy_cp";
  241.             char *scanner_bp = "yy_bp";
  242.  
  243.             add_action(
  244.     "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  245.  
  246.             if ( headcnt > 0 )
  247.                 {
  248.                 sprintf( action_text, "%s = %s + %d;\n",
  249.                 scanner_cp, scanner_bp, headcnt );
  250.                 add_action( action_text );
  251.                 }
  252.  
  253.             else
  254.                 {
  255.                 sprintf( action_text, "%s -= %d;\n",
  256.                     scanner_cp, trailcnt );
  257.                 add_action( action_text );
  258.                 }
  259.  
  260.             add_action(
  261.             "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  262.             }
  263.         }
  264.  
  265.     /* Okay, in the action code at this point yytext and yyleng have
  266.      * their proper final values for this rule, so here's the point
  267.      * to do any user action.
  268.      */
  269.     add_action( "YY_USER_ACTION\n" );
  270.  
  271.     line_directive_out( (FILE *) 0 );
  272.     }
  273.  
  274.  
  275. /* link_machines - connect two machines together
  276.  *
  277.  * synopsis
  278.  *
  279.  *   new = link_machines( first, last );
  280.  *
  281.  *     new    - a machine constructed by connecting first to last
  282.  *     first  - the machine whose successor is to be last
  283.  *     last   - the machine whose predecessor is to be first
  284.  *
  285.  * note: this routine concatenates the machine first with the machine
  286.  *  last to produce a machine new which will pattern-match first first
  287.  *  and then last, and will fail if either of the sub-patterns fails.
  288.  *  FIRST is set to new by the operation.  last is unmolested.
  289.  */
  290.  
  291. int link_machines( first, last )
  292. int first, last;
  293.     {
  294.     if ( first == NIL )
  295.         return last;
  296.  
  297.     else if ( last == NIL )
  298.         return first;
  299.  
  300.     else
  301.         {
  302.         mkxtion( finalst[first], last );
  303.         finalst[first] = finalst[last];
  304.         lastst[first] = MAX( lastst[first], lastst[last] );
  305.         firstst[first] = MIN( firstst[first], firstst[last] );
  306.  
  307.         return first;
  308.