| [3031] | 1 | /* nfa - NFA construction routines */
|
|---|
| 2 |
|
|---|
| 3 | /* Copyright (c) 1990 The Regents of the University of California. */
|
|---|
| 4 | /* All rights reserved. */
|
|---|
| 5 |
|
|---|
| 6 | /* This code is derived from software contributed to Berkeley by */
|
|---|
| 7 | /* Vern Paxson. */
|
|---|
| 8 |
|
|---|
| 9 | /* The United States Government has rights in this work pursuant */
|
|---|
| 10 | /* to contract no. DE-AC03-76SF00098 between the United States */
|
|---|
| 11 | /* Department of Energy and the University of California. */
|
|---|
| 12 |
|
|---|
| 13 | /* This file is part of flex. */
|
|---|
| 14 |
|
|---|
| 15 | /* Redistribution and use in source and binary forms, with or without */
|
|---|
| 16 | /* modification, are permitted provided that the following conditions */
|
|---|
| 17 | /* are met: */
|
|---|
| 18 |
|
|---|
| 19 | /* 1. Redistributions of source code must retain the above copyright */
|
|---|
| 20 | /* notice, this list of conditions and the following disclaimer. */
|
|---|
| 21 | /* 2. Redistributions in binary form must reproduce the above copyright */
|
|---|
| 22 | /* notice, this list of conditions and the following disclaimer in the */
|
|---|
| 23 | /* documentation and/or other materials provided with the distribution. */
|
|---|
| 24 |
|
|---|
| 25 | /* Neither the name of the University nor the names of its contributors */
|
|---|
| 26 | /* may be used to endorse or promote products derived from this software */
|
|---|
| 27 | /* without specific prior written permission. */
|
|---|
| 28 |
|
|---|
| 29 | /* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */
|
|---|
| 30 | /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */
|
|---|
| 31 | /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
|
|---|
| 32 | /* PURPOSE. */
|
|---|
| 33 |
|
|---|
| 34 | #include "flexdef.h"
|
|---|
| 35 |
|
|---|
| 36 |
|
|---|
| 37 | /* declare functions that have forward references */
|
|---|
| 38 |
|
|---|
| 39 | int dupmachine PROTO ((int));
|
|---|
| 40 | void mkxtion PROTO ((int, int));
|
|---|
| 41 |
|
|---|
| 42 |
|
|---|
| 43 | /* add_accept - add an accepting state to a machine
|
|---|
| 44 | *
|
|---|
| 45 | * accepting_number becomes mach's accepting number.
|
|---|
| 46 | */
|
|---|
| 47 |
|
|---|
| 48 | void add_accept (mach, accepting_number)
|
|---|
| 49 | int mach, accepting_number;
|
|---|
| 50 | {
|
|---|
| 51 | /* Hang the accepting number off an epsilon state. if it is associated
|
|---|
| 52 | * with a state that has a non-epsilon out-transition, then the state
|
|---|
| 53 | * will accept BEFORE it makes that transition, i.e., one character
|
|---|
| 54 | * too soon.
|
|---|
| 55 | */
|
|---|
| 56 |
|
|---|
| 57 | if (transchar[finalst[mach]] == SYM_EPSILON)
|
|---|
| 58 | accptnum[finalst[mach]] = accepting_number;
|
|---|
| 59 |
|
|---|
| 60 | else {
|
|---|
| 61 | int astate = mkstate (SYM_EPSILON);
|
|---|
| 62 |
|
|---|
| 63 | accptnum[astate] = accepting_number;
|
|---|
| 64 | (void) link_machines (mach, astate);
|
|---|
| 65 | }
|
|---|
| 66 | }
|
|---|
| 67 |
|
|---|
| 68 |
|
|---|
| 69 | /* copysingl - make a given number of copies of a singleton machine
|
|---|
| 70 | *
|
|---|
| 71 | * synopsis
|
|---|
| 72 | *
|
|---|
| 73 | * newsng = copysingl( singl, num );
|
|---|
| 74 | *
|
|---|
| 75 | * newsng - a new singleton composed of num copies of singl
|
|---|
| 76 | * singl - a singleton machine
|
|---|
| 77 | * num - the number of copies of singl to be present in newsng
|
|---|
| 78 | */
|
|---|
| 79 |
|
|---|
| 80 | int copysingl (singl, num)
|
|---|
| 81 | int singl, num;
|
|---|
| 82 | {
|
|---|
| 83 | int copy, i;
|
|---|
| 84 |
|
|---|
| 85 | copy = mkstate (SYM_EPSILON);
|
|---|
| 86 |
|
|---|
| 87 | for (i = 1; i <= num; ++i)
|
|---|
| 88 | copy = link_machines (copy, dupmachine (singl));
|
|---|
| 89 |
|
|---|
| 90 | return copy;
|
|---|
| 91 | }
|
|---|
| 92 |
|
|---|
| 93 |
|
|---|
| 94 | /* dumpnfa - debugging routine to write out an nfa */
|
|---|
| 95 |
|
|---|
| 96 | void dumpnfa (state1)
|
|---|
| 97 | int state1;
|
|---|
| 98 |
|
|---|
| 99 | {
|
|---|
| 100 | int sym, tsp1, tsp2, anum, ns;
|
|---|
| 101 |
|
|---|
| 102 | fprintf (stderr,
|
|---|
| 103 | _
|
|---|
| 104 | ("\n\n********** beginning dump of nfa with start state %d\n"),
|
|---|
| 105 | state1);
|
|---|
| |
|---|
