nfa.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717
  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. * Redistribution and use in source and binary forms are permitted provided
  14. * that: (1) source distributions retain this entire copyright notice and
  15. * comment, and (2) distributions including binaries display the following
  16. * acknowledgement: ``This product includes software developed by the
  17. * University of California, Berkeley and its contributors'' in the
  18. * documentation or other materials provided with the distribution and in
  19. * all advertising materials mentioning features or use of this software.
  20. * Neither the name of the University nor the names of its contributors may
  21. * be used to endorse or promote products derived from this software without
  22. * specific prior written permission.
  23. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  24. * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  25. * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  26. */
  27. #ifndef lint
  28. static char rcsid[] =
  29. "@(#) $Id$ (LBL)";
  30. #endif
  31. #include "flexdef.h"
  32. /* declare functions that have forward references */
  33. int dupmachine PROTO((int));
  34. void mkxtion PROTO((int, int));
  35. /* add_accept - add an accepting state to a machine
  36. *
  37. * synopsis
  38. *
  39. * add_accept( mach, accepting_number );
  40. *
  41. * accepting_number becomes mach's accepting number.
  42. */
  43. void add_accept( mach, accepting_number )
  44. int mach, accepting_number;
  45. {
  46. /* hang the accepting number off an epsilon state. if it is associated
  47. * with a state that has a non-epsilon out-transition, then the state
  48. * will accept BEFORE it makes that transition, i.e., one character
  49. * too soon
  50. */
  51. if ( transchar[finalst[mach]] == SYM_EPSILON )
  52. accptnum[finalst[mach]] = accepting_number;
  53. else
  54. {
  55. int astate = mkstate( SYM_EPSILON );
  56. accptnum[astate] = accepting_number;
  57. mach = link_machines( mach, astate );
  58. }
  59. }
  60. /* copysingl - make a given number of copies of a singleton machine
  61. *
  62. * synopsis
  63. *
  64. * newsng = copysingl( singl, num );
  65. *
  66. * newsng - a new singleton composed of num copies of singl
  67. * singl - a singleton machine
  68. * num - the number of copies of singl to be present in newsng
  69. */
  70. int copysingl( singl, num )
  71. int singl, num;
  72. {
  73. int copy, i;
  74. copy = mkstate( SYM_EPSILON );
  75. for ( i = 1; i <= num; ++i )
  76. copy = link_machines( copy, dupmachine( singl ) );
  77. return ( copy );
  78. }
  79. /* dumpnfa - debugging routine to write out an nfa
  80. *
  81. * synopsis
  82. * int state1;
  83. * dumpnfa( state1 );
  84. */
  85. void dumpnfa( state1 )
  86. int state1;
  87. {
  88. int sym, tsp1, tsp2, anum, ns;
  89. fprintf( stderr, "\n\n********** beginning dump of nfa with start state %d\n",
  90. state1 );
  91. /* we probably should loop starting at firstst[state1] and going to
  92. * lastst[state1], but they're not maintained properly when we "or"
  93. * all of the rules together. So we use our knowledge that the machine
  94. * starts at state 1 and ends at lastnfa.
  95. */
  96. /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  97. for ( ns = 1; ns <= lastnfa; ++ns )
  98. {
  99. fprintf( stderr, "state # %4d\t", ns );
  100. sym = transchar[ns];
  101. tsp1 = trans1[ns];
  102. tsp2 = trans2[ns];
  103. anum = accptnum[ns];
  104. fprintf( stderr, "%3d: %4d, %4d", sym, tsp1, tsp2 );
  105. if ( anum != NIL )
  106. fprintf( stderr, " [%d]", anum );
  107. fprintf( stderr, "\n" );
  108. }
  109. fprintf( stderr, "********** end of dump\n" );
  110. }
  111. /* dupmachine - make a duplicate of a given machine
  112. *
  113. * synopsis
  114. *
  115. * copy = dupmachine( mach );
  116. *
  117. * copy - holds duplicate of mach
  118. * mach - machine to be duplicated
  119. *
  120. * note that the copy of mach is NOT an exact duplicate; rather, all the
  121. * transition states values are adjusted so that the copy is self-contained,
  122. * as the original should have been.
  123. *
  124. * also note that the original MUST be contiguous, with its low and high
  125. * states accessible by the arrays firstst and lastst
  126. */
  127. int dupmachine( mach )
  128. int mach;
  129. {
  130. int i, init, state_offset;
  131. int state = 0;
  132. int last = lastst[mach];
  133. for ( i = firstst[mach]; i <= last; ++i )
  134. {
  135. state = mkstate( transchar[i] );
  136. if ( trans1[i] != NO_TRANSITION )
  137. {
  138. mkxtion( finalst[state], trans1[i] + state - i );
  139. if ( transchar[i] == SYM_EPSILON && trans2[i] != NO_TRANSITION )
  140. mkxtion( finalst[state], trans2[i] + state - i );
  141. }
  142. accptnum[state] = accptnum[i];
  143. }
  144. if ( state == 0 )
  145. flexfatal( "empty machine in dupmachine()" );
  146. state_offset = state - i + 1;
  147. init = mach + state_offset;
  148. firstst[init] = firstst[mach] + state_offset;
  149. finalst[init] = finalst[mach] + state_offset;
  150. lastst[init] = lastst[mach] + state_offset;
  151. return ( init );
  152. }
  153. /* finish_rule - finish up the processing for a rule
  154. *
  155. * synopsis
  156. *
  157. * finish_rule( mach, variable_trail_rule, headcnt, trailcnt );
  158. *
  159. * An accepting number is added to the given machine. If variable_trail_rule
  160. * is true then the rule has trailing context and both the head and trail
  161. * are variable size. Otherwise if headcnt or trailcnt is non-zero then
  162. * the machine recognizes a pattern with trailing context and headcnt is
  163. * the number of characters in the matched part of the pattern, or zero
  164. * if the matched part has variable length. trailcnt is the number of
  165. * trailing context characters in the pattern, or zero if the trailing
  166. * context has variable length.
  167. */
  168. void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  169. int mach, variable_trail_rule, headcnt, trailcnt;
  170. {
  171. add_accept( mach, num_rules );
  172. /* we did this in new_rule(), but it often gets the wrong
  173. * number because we do it before we start parsing the current rule
  174. */
  175. rule_linenum[num_rules] = linenum;
  176. /* if this is a continued action, then the line-number has
  177. * already been updated, giving us the wrong number
  178. */
  179. if ( continued_action )
  180. --rule_linenum[num_rules];
  181. fprintf( temp_action_file, "case %d:\n", num_rules );
  182. if ( variable_trail_rule )
  183. {
  184. rule_type[num_rules] = RULE_VARIABLE;
  185. if ( performance_report )
  186. fprintf( stderr, "Variable trailing context rule at line %d\n",
  187. rule_linenum[num_rules] );
  188. variable_trailing_context_rules = true;
  189. }
  190. else
  191. {
  192. rule_type[num_rules] = RULE_NORMAL;
  193. if ( headcnt > 0 || trailcnt > 0 )
  194. {
  195. /* do trailing context magic to not match the trailing characters */
  196. char *scanner_cp = "yy_c_buf_p = yy_cp";
  197. char *scanner_bp = "yy_bp";
  198. fprintf( temp_action_file,
  199. "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  200. if ( headcnt > 0 )
  201. fprintf( temp_action_file, "%s = %s + %d;\n",
  202. scanner_cp, scanner_bp, headcnt );
  203. else
  204. fprintf( temp_action_file,
  205. "%s -= %d;\n", scanner_cp, trailcnt );
  206. fprintf( temp_action_file,
  207. "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  208. }
  209. }
  210. line_directive_out( temp_action_file );
  211. }
  212. /* link_machines - connect two machines together
  213. *
  214. * synopsis
  215. *
  216. * new = link_machines( first, last );
  217. *
  218. * new - a machine constructed by connecting first to last
  219. * first - the machine whose successor is to be last
  220. * last - the machine whose predecessor is to be first
  221. *
  222. * note: this routine concatenates the machine first with the machine
  223. * last to produce a machine new which will pattern-match first first
  224. * and then last, and will fail if either of the sub-patterns fails.
  225. * FIRST is set to new by the operation. last is unmolested.
  226. */
  227. int link_machines( first, last )
  228. int first, last;
  229. {
  230. if ( first == NIL )
  231. return ( last );
  232. else if ( last == NIL )
  233. return ( first );
  234. else
  235. {
  236. mkxtion( finalst[first], last );
  237. finalst[first] = finalst[last];
  238. lastst[first] = max( lastst[first], lastst[last] );
  239. firstst[first] = min( firstst[first], firstst[last] );
  240. return ( first );
  241. }
  242. }
  243. /* mark_beginning_as_normal - mark each "beginning" state in a machine
  244. * as being a "normal" (i.e., not trailing context-
  245. * associated) states
  246. *
  247. * synopsis
  248. *
  249. * mark_beginning_as_normal( mach )
  250. *
  251. * mach - machine to mark
  252. *
  253. * The "beginning" states are the epsilon closure of the first state
  254. */
  255. void mark_beginning_as_normal( mach )
  256. register int mach;
  257. {
  258. switch ( state_type[mach] )
  259. {
  260. case STATE_NORMAL:
  261. /* oh, we've already visited here */
  262. return;
  263. case STATE_TRAILING_CONTEXT:
  264. state_type[mach] = STATE_NORMAL;
  265. if ( transchar[mach] == SYM_EPSILON )
  266. {
  267. if ( trans1[mach] != NO_TRANSITION )
  268. mark_beginning_as_normal( trans1[mach] );
  269. if ( trans2[mach] != NO_TRANSITION )
  270. mark_beginning_as_normal( trans2[mach] );
  271. }
  272. break;
  273. default:
  274. flexerror( "bad state type in mark_beginning_as_normal()" );
  275. break;
  276. }
  277. }
  278. /* mkbranch - make a machine that branches to two machines
  279. *
  280. * synopsis
  281. *
  282. * branch = mkbranch( first, second );
  283. *
  284. * branch - a machine which matches either first's pattern or second's
  285. * first, second - machines whose patterns are to be or'ed (the | operator)
  286. *
  287. * note that first and second are NEITHER destroyed by the operation. Also,
  288. * the resulting machine CANNOT be used with any other "mk" operation except
  289. * more mkbranch's. Compare with mkor()
  290. */
  291. int mkbranch( first, second )
  292. int first, second;
  293. {
  294. int eps;
  295. if ( first == NO_TRANSITION )
  296. return ( second );
  297. else if ( second == NO_TRANSITION )
  298. return ( first );
  299. eps = mkstate( SYM_EPSILON );
  300. mkxtion( eps, first );
  301. mkxtion( eps, second );
  302. return ( eps );
  303. }
  304. /* mkclos - convert a machine into a closure
  305. *
  306. * synopsis
  307. * new = mkclos( state );
  308. *
  309. * new - a new state which matches the closure of "state"
  310. */
  311. int mkclos( state )
  312. int state;
  313. {
  314. return ( mkopt( mkposcl( state ) ) );
  315. }
  316. /* mkopt - make a machine optional
  317. *
  318. * synopsis
  319. *
  320. * new = mkopt( mach );
  321. *
  322. * new - a machine which optionally matches whatever mach matched
  323. * mach - the machine to make optional
  324. *
  325. * notes:
  326. * 1. mach must be the last machine created
  327. * 2. mach is destroyed by the call
  328. */
  329. int mkopt( mach )
  330. int mach;
  331. {
  332. int eps;
  333. if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
  334. {
  335. eps = mkstate( SYM_EPSILON );
  336. mach = link_machines( mach, eps );
  337. }
  338. /* can't skimp on the following if FREE_EPSILON(mach) is true because
  339. * some state interior to "mach" might point back to the beginning
  340. * for a closure
  341. */
  342. eps = mkstate( SYM_EPSILON );
  343. mach = link_machines( eps, mach );
  344. mkxtion( mach, finalst[mach] );
  345. return ( mach );
  346. }
  347. /* mkor - make a machine that matches either one of two machines
  348. *
  349. * synopsis
  350. *
  351. * new = mkor( first, second );
  352. *
  353. * new - a machine which matches either first's pattern or second's
  354. * first, second - machines whose patterns are to be or'ed (the | operator)
  355. *
  356. * note that first and second are both destroyed by the operation
  357. * the code is rather convoluted because an attempt is made to minimize
  358. * the number of epsilon states needed
  359. */
  360. int mkor( first, second )
  361. int first, second;
  362. {
  363. int eps, orend;
  364. if ( first == NIL )
  365. return ( second );
  366. else if ( second == NIL )
  367. return ( first );
  368. else
  369. {
  370. /* see comment in mkopt() about why we can't use the first state
  371. * of "first" or "second" if they satisfy "FREE_EPSILON"
  372. */
  373. eps = mkstate( SYM_EPSILON );
  374. first = link_machines( eps, first );
  375. mkxtion( first, second );
  376. if ( SUPER_FREE_EPSILON(finalst[first]) &&
  377. accptnum[finalst[first]] == NIL )
  378. {
  379. orend = finalst[first];
  380. mkxtion( finalst[second], orend );
  381. }
  382. else if ( SUPER_FREE_EPSILON(finalst[second]) &&
  383. accptnum[finalst[second]] == NIL )
  384. {
  385. orend = finalst[second];
  386. mkxtion( finalst[first], orend );
  387. }
  388. else
  389. {
  390. eps = mkstate( SYM_EPSILON );
  391. first = link_machines( first, eps );
  392. orend = finalst[first];
  393. mkxtion( finalst[second], orend );
  394. }
  395. }
  396. finalst[first] = orend;
  397. return ( first );
  398. }
  399. /* mkposcl - convert a machine into a positive closure
  400. *
  401. * synopsis
  402. * new = mkposcl( state );
  403. *
  404. * new - a machine matching the positive closure of "state"
  405. */
  406. int mkposcl( state )
  407. int state;
  408. {
  409. int eps;
  410. if ( SUPER_FREE_EPSILON(finalst[state]) )
  411. {
  412. mkxtion( finalst[state], state );
  413. return ( state );
  414. }
  415. else
  416. {
  417. eps = mkstate( SYM_EPSILON );
  418. mkxtion( eps, state );
  419. return ( link_machines( state, eps ) );
  420. }
  421. }
  422. /* mkrep - make a replicated machine
  423. *
  424. * synopsis
  425. * new = mkrep( mach, lb, ub );
  426. *
  427. * new - a machine that matches whatever "mach" matched from "lb"
  428. * number of times to "ub" number of times
  429. *
  430. * note
  431. * if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
  432. */
  433. int mkrep( mach, lb, ub )
  434. int mach, lb, ub;
  435. {
  436. int base_mach, tail, copy, i;
  437. base_mach = copysingl( mach, lb - 1 );
  438. if ( ub == INFINITY )
  439. {
  440. copy = dupmachine( mach );
  441. mach = link_machines( mach,
  442. link_machines( base_mach, mkclos( copy ) ) );
  443. }
  444. else
  445. {
  446. tail = mkstate( SYM_EPSILON );
  447. for ( i = lb; i < ub; ++i )
  448. {
  449. copy = dupmachine( mach );
  450. tail = mkopt( link_machines( copy, tail ) );
  451. }
  452. mach = link_machines( mach, link_machines( base_mach, tail ) );
  453. }
  454. return ( mach );
  455. }
  456. /* mkstate - create a state with a transition on a given symbol
  457. *
  458. * synopsis
  459. *
  460. * state = mkstate( sym );
  461. *
  462. * state - a new state matching sym
  463. * sym - the symbol the new state is to have an out-transition on
  464. *
  465. * note that this routine makes new states in ascending order through the
  466. * state array (and increments LASTNFA accordingly). The routine DUPMACHINE
  467. * relies on machines being made in ascending order and that they are
  468. * CONTIGUOUS. Change it and you will have to rewrite DUPMACHINE (kludge
  469. * that it admittedly is)
  470. */
  471. int mkstate( sym )
  472. int sym;
  473. {
  474. if ( ++lastnfa >= current_mns )
  475. {
  476. if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
  477. lerrif( "input rules are too complicated (>= %d NFA states)",
  478. current_mns );
  479. ++num_reallocs;
  480. firstst = reallocate_integer_array( firstst, current_mns );
  481. lastst = reallocate_integer_array( lastst, current_mns );
  482. finalst = reallocate_integer_array( finalst, current_mns );
  483. transchar = reallocate_integer_array( transchar, current_mns );
  484. trans1 = reallocate_integer_array( trans1, current_mns );
  485. trans2 = reallocate_integer_array( trans2, current_mns );
  486. accptnum = reallocate_integer_array( accptnum, current_mns );
  487. assoc_rule = reallocate_integer_array( assoc_rule, current_mns );
  488. state_type = reallocate_integer_array( state_type, current_mns );
  489. }
  490. firstst[lastnfa] = lastnfa;
  491. finalst[lastnfa] = lastnfa;
  492. lastst[lastnfa] = lastnfa;
  493. transchar[lastnfa] = sym;
  494. trans1[lastnfa] = NO_TRANSITION;
  495. trans2[lastnfa] = NO_TRANSITION;
  496. accptnum[lastnfa] = NIL;
  497. assoc_rule[lastnfa] = num_rules;
  498. state_type[lastnfa] = current_state_type;
  499. /* fix up equivalence classes base on this transition. Note that any
  500. * character which has its own transition gets its own equivalence class.
  501. * Thus only characters which are only in character classes have a chance
  502. * at being in the same equivalence class. E.g. "a|b" puts 'a' and 'b'
  503. * into two different equivalence classes. "[ab]" puts them in the same
  504. * equivalence class (barring other differences elsewhere in the input).
  505. */
  506. if ( sym < 0 )
  507. {
  508. /* we don't have to update the equivalence classes since that was
  509. * already done when the ccl was created for the first time
  510. */
  511. }
  512. else if ( sym == SYM_EPSILON )
  513. ++numeps;
  514. else
  515. {
  516. if ( useecs )
  517. /* map NUL's to csize */
  518. mkechar( sym ? sym : csize, nextecm, ecgroup );
  519. }
  520. return ( lastnfa );
  521. }
  522. /* mkxtion - make a transition from one state to another
  523. *
  524. * synopsis
  525. *
  526. * mkxtion( statefrom, stateto );
  527. *
  528. * statefrom - the state from which the transition is to be made
  529. * stateto - the state to which the transition is to be made
  530. */
  531. void mkxtion( statefrom, stateto )
  532. int statefrom, stateto;
  533. {
  534. if ( trans1[statefrom] == NO_TRANSITION )
  535. trans1[statefrom] = stateto;
  536. else if ( (transchar[statefrom] != SYM_EPSILON) ||
  537. (trans2[statefrom] != NO_TRANSITION) )
  538. flexfatal( "found too many transitions in mkxtion()" );
  539. else
  540. { /* second out-transition for an epsilon state */
  541. ++eps2;
  542. trans2[statefrom] = stateto;
  543. }
  544. }
  545. /* new_rule - initialize for a new rule
  546. *
  547. * synopsis
  548. *
  549. * new_rule();
  550. *
  551. * the global num_rules is incremented and the any corresponding dynamic
  552. * arrays (such as rule_type[]) are grown as needed.
  553. */
  554. void new_rule()
  555. {
  556. if ( ++num_rules >= current_max_rules )
  557. {
  558. ++num_reallocs;
  559. current_max_rules += MAX_RULES_INCREMENT;
  560. rule_type = reallocate_integer_array( rule_type, current_max_rules );
  561. rule_linenum =
  562. reallocate_integer_array( rule_linenum, current_max_rules );
  563. }
  564. if ( num_rules > MAX_RULE )
  565. lerrif( "too many rules (> %d)!", MAX_RULE );
  566. rule_linenum[num_rules] = linenum;
  567. }