dfa.c 26 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075
  1. /* dfa - DFA 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. void dump_associated_rules PROTO((FILE*, int));
  34. void dump_transitions PROTO((FILE*, int[]));
  35. void sympartition PROTO((int[], int, int[], int[]));
  36. int symfollowset PROTO((int[], int, int, int[]));
  37. /* check_for_backtracking - check a DFA state for backtracking
  38. *
  39. * synopsis
  40. * int ds, state[numecs];
  41. * check_for_backtracking( ds, state );
  42. *
  43. * ds is the number of the state to check and state[] is its out-transitions,
  44. * indexed by equivalence class, and state_rules[] is the set of rules
  45. * associated with this state
  46. */
  47. void check_for_backtracking( ds, state )
  48. int ds;
  49. int state[];
  50. {
  51. if ( (reject && ! dfaacc[ds].dfaacc_set) || ! dfaacc[ds].dfaacc_state )
  52. { /* state is non-accepting */
  53. ++num_backtracking;
  54. if ( backtrack_report )
  55. {
  56. fprintf( backtrack_file, "State #%d is non-accepting -\n", ds );
  57. /* identify the state */
  58. dump_associated_rules( backtrack_file, ds );
  59. /* now identify it further using the out- and jam-transitions */
  60. dump_transitions( backtrack_file, state );
  61. putc( '\n', backtrack_file );
  62. }
  63. }
  64. }
  65. /* check_trailing_context - check to see if NFA state set constitutes
  66. * "dangerous" trailing context
  67. *
  68. * synopsis
  69. * int nfa_states[num_states+1], num_states;
  70. * int accset[nacc+1], nacc;
  71. * check_trailing_context( nfa_states, num_states, accset, nacc );
  72. *
  73. * NOTES
  74. * Trailing context is "dangerous" if both the head and the trailing
  75. * part are of variable size \and/ there's a DFA state which contains
  76. * both an accepting state for the head part of the rule and NFA states
  77. * which occur after the beginning of the trailing context.
  78. * When such a rule is matched, it's impossible to tell if having been
  79. * in the DFA state indicates the beginning of the trailing context
  80. * or further-along scanning of the pattern. In these cases, a warning
  81. * message is issued.
  82. *
  83. * nfa_states[1 .. num_states] is the list of NFA states in the DFA.
  84. * accset[1 .. nacc] is the list of accepting numbers for the DFA state.
  85. */
  86. void check_trailing_context( nfa_states, num_states, accset, nacc )
  87. int *nfa_states, num_states;
  88. int *accset;
  89. register int nacc;
  90. {
  91. register int i, j;
  92. for ( i = 1; i <= num_states; ++i )
  93. {
  94. int ns = nfa_states[i];
  95. register int type = state_type[ns];
  96. register int ar = assoc_rule[ns];
  97. if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE )
  98. { /* do nothing */
  99. }
  100. else if ( type == STATE_TRAILING_CONTEXT )
  101. {
  102. /* potential trouble. Scan set of accepting numbers for
  103. * the one marking the end of the "head". We assume that
  104. * this looping will be fairly cheap since it's rare that
  105. * an accepting number set is large.
  106. */
  107. for ( j = 1; j <= nacc; ++j )
  108. if ( accset[j] & YY_TRAILING_HEAD_MASK )
  109. {
  110. fprintf( stderr,
  111. "%s: Dangerous trailing context in rule at line %d\n",
  112. program_name, rule_linenum[ar] );
  113. return;
  114. }
  115. }
  116. }
  117. }
  118. /* dump_associated_rules - list the rules associated with a DFA state
  119. *
  120. * synopisis
  121. * int ds;
  122. * FILE *file;
  123. * dump_associated_rules( file, ds );
  124. *
  125. * goes through the set of NFA states associated with the DFA and
  126. * extracts the first MAX_ASSOC_RULES unique rules, sorts them,
  127. * and writes a report to the given file
  128. */
  129. void dump_associated_rules( file, ds )
  130. FILE *file;
  131. int ds;
  132. {
  133. register int i, j;
  134. register int num_associated_rules = 0;
  135. int rule_set[MAX_ASSOC_RULES + 1];
  136. int *dset = dss[ds];
  137. int size = dfasiz[ds];
  138. for ( i = 1; i <= size; ++i )
  139. {
  140. register rule_num = rule_linenum[assoc_rule[dset[i]]];
  141. for ( j = 1; j <= num_associated_rules; ++j )
  142. if ( rule_num == rule_set[j] )
  143. break;
  144. if ( j > num_associated_rules )
  145. { /* new rule */
  146. if ( num_associated_rules < MAX_ASSOC_RULES )
  147. rule_set[++num_associated_rules] = rule_num;
  148. }
  149. }
  150. bubble( rule_set, num_associated_rules );
  151. fprintf( file, " associated rule line numbers:" );
  152. for ( i = 1; i <= num_associated_rules; ++i )
  153. {
  154. if ( i % 8 == 1 )
  155. putc( '\n', file );
  156. fprintf( file, "\t%d", rule_set[i] );
  157. }
  158. putc( '\n', file );
  159. }
  160. /* dump_transitions - list the transitions associated with a DFA state
  161. *
  162. * synopisis
  163. * int state[numecs];
  164. * FILE *file;
  165. * dump_transitions( file, state );
  166. *
  167. * goes through the set of out-transitions and lists them in human-readable
  168. * form (i.e., not as equivalence classes); also lists jam transitions
  169. * (i.e., all those which are not out-transitions, plus EOF). The dump
  170. * is done to the given file.
  171. */
  172. void dump_transitions( file, state )
  173. FILE *file;
  174. int state[];
  175. {
  176. register int i, ec;
  177. int out_char_set[CSIZE];
  178. for ( i = 0; i < csize; ++i )
  179. {
  180. ec = abs( ecgroup[i] );
  181. out_char_set[i] = state[ec];
  182. }
  183. fprintf( file, " out-transitions: " );
  184. list_character_set( file, out_char_set );
  185. /* now invert the members of the set to get the jam transitions */
  186. for ( i = 0; i < csize; ++i )
  187. out_char_set[i] = ! out_char_set[i];
  188. fprintf( file, "\n jam-transitions: EOF " );
  189. list_character_set( file, out_char_set );
  190. putc( '\n', file );
  191. }
  192. /* epsclosure - construct the epsilon closure of a set of ndfa states
  193. *
  194. * synopsis
  195. * int t[current_max_dfa_size], numstates, accset[num_rules + 1], nacc;
  196. * int hashval;
  197. * int *epsclosure();
  198. * t = epsclosure( t, &numstates, accset, &nacc, &hashval );
  199. *
  200. * NOTES
  201. * the epsilon closure is the set of all states reachable by an arbitrary
  202. * number of epsilon transitions which themselves do not have epsilon
  203. * transitions going out, unioned with the set of states which have non-null
  204. * accepting numbers. t is an array of size numstates of nfa state numbers.
  205. * Upon return, t holds the epsilon closure and numstates is updated. accset
  206. * holds a list of the accepting numbers, and the size of accset is given
  207. * by nacc. t may be subjected to reallocation if it is not large enough
  208. * to hold the epsilon closure.
  209. *
  210. * hashval is the hash value for the dfa corresponding to the state set
  211. */
  212. int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
  213. int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
  214. {
  215. register int stkpos, ns, tsp;
  216. int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
  217. int stkend, nstate;
  218. static int did_stk_init = false, *stk;
  219. #define MARK_STATE(state) \
  220. trans1[state] = trans1[state] - MARKER_DIFFERENCE;
  221. #define IS_MARKED(state) (trans1[state] < 0)
  222. #define UNMARK_STATE(state) \
  223. trans1[state] = trans1[state] + MARKER_DIFFERENCE;
  224. #define CHECK_ACCEPT(state) \
  225. { \
  226. nfaccnum = accptnum[state]; \
  227. if ( nfaccnum != NIL ) \
  228. accset[++nacc] = nfaccnum; \
  229. }
  230. #define DO_REALLOCATION \
  231. { \
  232. current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
  233. ++num_reallocs; \
  234. t = reallocate_integer_array( t, current_max_dfa_size ); \
  235. stk = reallocate_integer_array( stk, current_max_dfa_size ); \
  236. } \
  237. #define PUT_ON_STACK(state) \
  238. { \
  239. if ( ++stkend >= current_max_dfa_size ) \
  240. DO_REALLOCATION \
  241. stk[stkend] = state; \
  242. MARK_STATE(state) \
  243. }
  244. #define ADD_STATE(state) \
  245. { \
  246. if ( ++numstates >= current_max_dfa_size ) \
  247. DO_REALLOCATION \
  248. t[numstates] = state; \
  249. hashval = hashval + state; \
  250. }
  251. #define STACK_STATE(state) \
  252. { \
  253. PUT_ON_STACK(state) \
  254. CHECK_ACCEPT(state) \
  255. if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
  256. ADD_STATE(state) \
  257. }
  258. if ( ! did_stk_init )
  259. {
  260. stk = allocate_integer_array( current_max_dfa_size );
  261. did_stk_init = true;
  262. }
  263. nacc = stkend = hashval = 0;
  264. for ( nstate = 1; nstate <= numstates; ++nstate )
  265. {
  266. ns = t[nstate];
  267. /* the state could be marked if we've already pushed it onto
  268. * the stack
  269. */
  270. if ( ! IS_MARKED(ns) )
  271. PUT_ON_STACK(ns)
  272. CHECK_ACCEPT(ns)
  273. hashval = hashval + ns;
  274. }
  275. for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  276. {
  277. ns = stk[stkpos];
  278. transsym = transchar[ns];
  279. if ( transsym == SYM_EPSILON )
  280. {
  281. tsp = trans1[ns] + MARKER_DIFFERENCE;
  282. if ( tsp != NO_TRANSITION )
  283. {
  284. if ( ! IS_MARKED(tsp) )
  285. STACK_STATE(tsp)
  286. tsp = trans2[ns];
  287. if ( tsp != NO_TRANSITION )
  288. if ( ! IS_MARKED(tsp) )
  289. STACK_STATE(tsp)
  290. }
  291. }
  292. }
  293. /* clear out "visit" markers */
  294. for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  295. {
  296. if ( IS_MARKED(stk[stkpos]) )
  297. {
  298. UNMARK_STATE(stk[stkpos])
  299. }
  300. else
  301. flexfatal( "consistency check failed in epsclosure()" );
  302. }
  303. *ns_addr = numstates;
  304. *hv_addr = hashval;
  305. *nacc_addr = nacc;
  306. return ( t );
  307. }
  308. /* increase_max_dfas - increase the maximum number of DFAs */
  309. void increase_max_dfas()
  310. {
  311. current_max_dfas += MAX_DFAS_INCREMENT;
  312. ++num_reallocs;
  313. base = reallocate_integer_array( base, current_max_dfas );
  314. def = reallocate_integer_array( def, current_max_dfas );
  315. dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
  316. accsiz = reallocate_integer_array( accsiz, current_max_dfas );
  317. dhash = reallocate_integer_array( dhash, current_max_dfas );
  318. dss = reallocate_int_ptr_array( dss, current_max_dfas );
  319. dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
  320. if ( nultrans )
  321. nultrans = reallocate_integer_array( nultrans, current_max_dfas );
  322. }
  323. /* ntod - convert an ndfa to a dfa
  324. *
  325. * synopsis
  326. * ntod();
  327. *
  328. * creates the dfa corresponding to the ndfa we've constructed. the
  329. * dfa starts out in state #1.
  330. */
  331. void ntod()
  332. {
  333. int *accset, ds, nacc, newds;
  334. int sym, hashval, numstates, dsize;
  335. int num_full_table_rows; /* used only for -f */
  336. int *nset, *dset;
  337. int targptr, totaltrans, i, comstate, comfreq, targ;
  338. int *epsclosure(), snstods(), symlist[CSIZE + 1];
  339. int num_start_states;
  340. int todo_head, todo_next;
  341. /* note that the following are indexed by *equivalence classes*
  342. * and not by characters. Since equivalence classes are indexed
  343. * beginning with 1, even if the scanner accepts NUL's, this
  344. * means that (since every character is potentially in its own
  345. * equivalence class) these arrays must have room for indices
  346. * from 1 to CSIZE, so their size must be CSIZE + 1.
  347. */
  348. int duplist[CSIZE + 1], state[CSIZE + 1];
  349. int targfreq[CSIZE + 1], targstate[CSIZE + 1];
  350. /* this is so find_table_space(...) will know where to start looking in
  351. * chk/nxt for unused records for space to put in the state
  352. */
  353. if ( fullspd )
  354. firstfree = 0;
  355. accset = allocate_integer_array( num_rules + 1 );
  356. nset = allocate_integer_array( current_max_dfa_size );
  357. /* the "todo" queue is represented by the head, which is the DFA
  358. * state currently being processed, and the "next", which is the
  359. * next DFA state number available (not in use). We depend on the
  360. * fact that snstods() returns DFA's \in increasing order/, and thus
  361. * need only know the bounds of the dfas to be processed.
  362. */
  363. todo_head = todo_next = 0;
  364. for ( i = 0; i <= csize; ++i )
  365. {
  366. duplist[i] = NIL;
  367. symlist[i] = false;
  368. }
  369. for ( i = 0; i <= num_rules; ++i )
  370. accset[i] = NIL;
  371. if ( trace )
  372. {
  373. dumpnfa( scset[1] );
  374. fputs( "\n\nDFA Dump:\n\n", stderr );
  375. }
  376. inittbl();
  377. /* check to see whether we should build a separate table for transitions
  378. * on NUL characters. We don't do this for full-speed (-F) scanners,
  379. * since for them we don't have a simple state number lying around with
  380. * which to index the table. We also don't bother doing it for scanners
  381. * unless (1) NUL is in its own equivalence class (indicated by a
  382. * positive value of ecgroup[NUL]), (2) NUL's equilvalence class is
  383. * the last equivalence class, and (3) the number of equivalence classes
  384. * is the same as the number of characters. This latter case comes about
  385. * when useecs is false or when its true but every character still
  386. * manages to land in its own class (unlikely, but it's cheap to check
  387. * for). If all these things are true then the character code needed
  388. * to represent NUL's equivalence class for indexing the tables is
  389. * going to take one more bit than the number of characters, and therefore
  390. * we won't be assured of being able to fit it into a YY_CHAR variable.
  391. * This rules out storing the transitions in a compressed table, since
  392. * the code for interpreting them uses a YY_CHAR variable (perhaps it
  393. * should just use an integer, though; this is worth pondering ... ###).
  394. *
  395. * Finally, for full tables, we want the number of entries in the
  396. * table to be a power of two so the array references go fast (it
  397. * will just take a shift to compute the major index). If encoding
  398. * NUL's transitions in the table will spoil this, we give it its
  399. * own table (note that this will be the case if we're not using
  400. * equivalence classes).
  401. */
  402. /* note that the test for ecgroup[0] == numecs below accomplishes
  403. * both (1) and (2) above
  404. */
  405. if ( ! fullspd && ecgroup[0] == numecs )
  406. { /* NUL is alone in its equivalence class, which is the last one */
  407. int use_NUL_table = (numecs == csize);
  408. if ( fulltbl && ! use_NUL_table )
  409. { /* we still may want to use the table if numecs is a power of 2 */
  410. int power_of_two;
  411. for ( power_of_two = 1; power_of_two <= csize; power_of_two *= 2 )
  412. if ( numecs == power_of_two )
  413. {
  414. use_NUL_table = true;
  415. break;
  416. }
  417. }
  418. if ( use_NUL_table )
  419. nultrans = allocate_integer_array( current_max_dfas );
  420. /* from now on, nultrans != nil indicates that we're
  421. * saving null transitions for later, separate encoding
  422. */
  423. }
  424. if ( fullspd )
  425. {
  426. for ( i = 0; i <= numecs; ++i )
  427. state[i] = 0;
  428. place_state( state, 0, 0 );
  429. }
  430. else if ( fulltbl )
  431. {
  432. if ( nultrans )
  433. /* we won't be including NUL's transitions in the table,
  434. * so build it for entries from 0 .. numecs - 1
  435. */
  436. num_full_table_rows = numecs;
  437. else
  438. /* take into account the fact that we'll be including
  439. * the NUL entries in the transition table. Build it
  440. * from 0 .. numecs.
  441. */
  442. num_full_table_rows = numecs + 1;
  443. /* declare it "short" because it's a real long-shot that that
  444. * won't be large enough.
  445. */
  446. printf( "static short int yy_nxt[][%d] =\n {\n",
  447. /* '}' so vi doesn't get too confused */
  448. num_full_table_rows );
  449. /* generate 0 entries for state #0 */
  450. for ( i = 0; i < num_full_table_rows; ++i )
  451. mk2data( 0 );
  452. /* force ',' and dataflush() next call to mk2data */
  453. datapos = NUMDATAITEMS;
  454. /* force extra blank line next dataflush() */
  455. dataline = NUMDATALINES;
  456. }
  457. /* create the first states */
  458. num_start_states = lastsc * 2;
  459. for ( i = 1; i <= num_start_states; ++i )
  460. {
  461. numstates = 1;
  462. /* for each start condition, make one state for the case when
  463. * we're at the beginning of the line (the '%' operator) and
  464. * one for the case when we're not
  465. */
  466. if ( i % 2 == 1 )
  467. nset[numstates] = scset[(i / 2) + 1];
  468. else
  469. nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] );
  470. nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
  471. if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
  472. {
  473. numas += nacc;
  474. totnst += numstates;
  475. ++todo_next;
  476. if ( variable_trailing_context_rules && nacc > 0 )
  477. check_trailing_context( nset, numstates, accset, nacc );
  478. }
  479. }
  480. if ( ! fullspd )
  481. {
  482. if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
  483. flexfatal( "could not create unique end-of-buffer state" );
  484. ++numas;
  485. ++num_start_states;
  486. ++todo_next;
  487. }
  488. while ( todo_head < todo_next )
  489. {
  490. targptr = 0;
  491. totaltrans = 0;
  492. for ( i = 1; i <= numecs; ++i )
  493. state[i] = 0;
  494. ds = ++todo_head;
  495. dset = dss[ds];
  496. dsize = dfasiz[ds];
  497. if ( trace )
  498. fprintf( stderr, "state # %d:\n", ds );
  499. sympartition( dset, dsize, symlist, duplist );
  500. for ( sym = 1; sym <= numecs; ++sym )
  501. {
  502. if ( symlist[sym] )
  503. {
  504. symlist[sym] = 0;
  505. if ( duplist[sym] == NIL )
  506. { /* symbol has unique out-transitions */
  507. numstates = symfollowset( dset, dsize, sym, nset );
  508. nset = epsclosure( nset, &numstates, accset,
  509. &nacc, &hashval );
  510. if ( snstods( nset, numstates, accset,
  511. nacc, hashval, &newds ) )
  512. {
  513. totnst = totnst + numstates;
  514. ++todo_next;
  515. numas += nacc;
  516. if ( variable_trailing_context_rules && nacc > 0 )
  517. check_trailing_context( nset, numstates,
  518. accset, nacc );
  519. }
  520. state[sym] = newds;
  521. if ( trace )
  522. fprintf( stderr, "\t%d\t%d\n", sym, newds );
  523. targfreq[++targptr] = 1;
  524. targstate[targptr] = newds;
  525. ++numuniq;
  526. }
  527. else
  528. {
  529. /* sym's equivalence class has the same transitions
  530. * as duplist(sym)'s equivalence class
  531. */
  532. targ = state[duplist[sym]];
  533. state[sym] = targ;
  534. if ( trace )
  535. fprintf( stderr, "\t%d\t%d\n", sym, targ );
  536. /* update frequency count for destination state */
  537. i = 0;
  538. while ( targstate[++i] != targ )
  539. ;
  540. ++targfreq[i];
  541. ++numdup;
  542. }
  543. ++totaltrans;
  544. duplist[sym] = NIL;
  545. }
  546. }
  547. numsnpairs = numsnpairs + totaltrans;
  548. if ( caseins && ! useecs )
  549. {
  550. register int j;
  551. for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
  552. state[i] = state[j];
  553. }
  554. if ( ds > num_start_states )
  555. check_for_backtracking( ds, state );
  556. if ( nultrans )
  557. {
  558. nultrans[ds] = state[NUL_ec];
  559. state[NUL_ec] = 0; /* remove transition */
  560. }
  561. if ( fulltbl )
  562. {
  563. /* supply array's 0-element */
  564. if ( ds == end_of_buffer_state )
  565. mk2data( -end_of_buffer_state );
  566. else
  567. mk2data( end_of_buffer_state );
  568. for ( i = 1; i < num_full_table_rows; ++i )
  569. /* jams are marked by negative of state number */
  570. mk2data( state[i] ? state[i] : -ds );
  571. /* force ',' and dataflush() next call to mk2data */
  572. datapos = NUMDATAITEMS;
  573. /* force extra blank line next dataflush() */
  574. dataline = NUMDATALINES;
  575. }
  576. else if ( fullspd )
  577. place_state( state, ds, totaltrans );
  578. else if ( ds == end_of_buffer_state )
  579. /* special case this state to make sure it does what it's
  580. * supposed to, i.e., jam on end-of-buffer
  581. */
  582. stack1( ds, 0, 0, JAMSTATE );
  583. else /* normal, compressed state */
  584. {
  585. /* determine which destination state is the most common, and
  586. * how many transitions to it there are
  587. */
  588. comfreq = 0;
  589. comstate = 0;
  590. for ( i = 1; i <= targptr; ++i )
  591. if ( targfreq[i] > comfreq )
  592. {
  593. comfreq = targfreq[i];
  594. comstate = targstate[i];
  595. }
  596. bldtbl( state, ds, totaltrans, comstate, comfreq );
  597. }
  598. }
  599. if ( fulltbl )
  600. dataend();
  601. else if ( ! fullspd )
  602. {
  603. cmptmps(); /* create compressed template entries */
  604. /* create tables for all the states with only one out-transition */
  605. while ( onesp > 0 )
  606. {
  607. mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
  608. onedef[onesp] );
  609. --onesp;
  610. }
  611. mkdeftbl();
  612. }
  613. }
  614. /* snstods - converts a set of ndfa states into a dfa state
  615. *
  616. * synopsis
  617. * int sns[numstates], numstates, newds, accset[num_rules + 1], nacc, hashval;
  618. * int snstods();
  619. * is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
  620. *
  621. * on return, the dfa state number is in newds.
  622. */
  623. int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
  624. int sns[], numstates, accset[], nacc, hashval, *newds_addr;
  625. {
  626. int didsort = 0;
  627. register int i, j;
  628. int newds, *oldsns;
  629. for ( i = 1; i <= lastdfa; ++i )
  630. if ( hashval == dhash[i] )
  631. {
  632. if ( numstates == dfasiz[i] )
  633. {
  634. oldsns = dss[i];
  635. if ( ! didsort )
  636. {
  637. /* we sort the states in sns so we can compare it to
  638. * oldsns quickly. we use bubble because there probably
  639. * aren't very many states
  640. */
  641. bubble( sns, numstates );
  642. didsort = 1;
  643. }
  644. for ( j = 1; j <= numstates; ++j )
  645. if ( sns[j] != oldsns[j] )
  646. break;
  647. if ( j > numstates )
  648. {
  649. ++dfaeql;
  650. *newds_addr = i;
  651. return ( 0 );
  652. }
  653. ++hshcol;
  654. }
  655. else
  656. ++hshsave;
  657. }
  658. /* make a new dfa */
  659. if ( ++lastdfa >= current_max_dfas )
  660. increase_max_dfas();
  661. newds = lastdfa;
  662. dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) );
  663. if ( ! dss[newds] )
  664. flexfatal( "dynamic memory failure in snstods()" );
  665. /* if we haven't already sorted the states in sns, we do so now, so that
  666. * future comparisons with it can be made quickly
  667. */
  668. if ( ! didsort )
  669. bubble( sns, numstates );
  670. for ( i = 1; i <= numstates; ++i )
  671. dss[newds][i] = sns[i];
  672. dfasiz[newds] = numstates;
  673. dhash[newds] = hashval;
  674. if ( nacc == 0 )
  675. {
  676. if ( reject )
  677. dfaacc[newds].dfaacc_set = (int *) 0;
  678. else
  679. dfaacc[newds].dfaacc_state = 0;
  680. accsiz[newds] = 0;
  681. }
  682. else if ( reject )
  683. {
  684. /* we sort the accepting set in increasing order so the disambiguating
  685. * rule that the first rule listed is considered match in the event of
  686. * ties will work. We use a bubble sort since the list is probably
  687. * quite small.
  688. */
  689. bubble( accset, nacc );
  690. dfaacc[newds].dfaacc_set =
  691. (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );
  692. if ( ! dfaacc[newds].dfaacc_set )
  693. flexfatal( "dynamic memory failure in snstods()" );
  694. /* save the accepting set for later */
  695. for ( i = 1; i <= nacc; ++i )
  696. dfaacc[newds].dfaacc_set[i] = accset[i];
  697. accsiz[newds] = nacc;
  698. }
  699. else
  700. { /* find lowest numbered rule so the disambiguating rule will work */
  701. j = num_rules + 1;
  702. for ( i = 1; i <= nacc; ++i )
  703. if ( accset[i] < j )
  704. j = accset[i];
  705. dfaacc[newds].dfaacc_state = j;
  706. }
  707. *newds_addr = newds;
  708. return ( 1 );
  709. }
  710. /* symfollowset - follow the symbol transitions one step
  711. *
  712. * synopsis
  713. * int ds[current_max_dfa_size], dsize, transsym;
  714. * int nset[current_max_dfa_size], numstates;
  715. * numstates = symfollowset( ds, dsize, transsym, nset );
  716. */
  717. int symfollowset( ds, dsize, transsym, nset )
  718. int ds[], dsize, transsym, nset[];
  719. {
  720. int ns, tsp, sym, i, j, lenccl, ch, numstates;
  721. int ccllist;
  722. numstates = 0;
  723. for ( i = 1; i <= dsize; ++i )
  724. { /* for each nfa state ns in the state set of ds */
  725. ns = ds[i];
  726. sym = transchar[ns];
  727. tsp = trans1[ns];
  728. if ( sym < 0 )
  729. { /* it's a character class */
  730. sym = -sym;
  731. ccllist = cclmap[sym];
  732. lenccl = ccllen[sym];
  733. if ( cclng[sym] )
  734. {
  735. for ( j = 0; j < lenccl; ++j )
  736. { /* loop through negated character class */
  737. ch = ccltbl[ccllist + j];
  738. if ( ch == 0 )
  739. ch = NUL_ec;
  740. if ( ch > transsym )
  741. break; /* transsym isn't in negated ccl */
  742. else if ( ch == transsym )
  743. /* next 2 */ goto bottom;
  744. }
  745. /* didn't find transsym in ccl */
  746. nset[++numstates] = tsp;
  747. }
  748. else
  749. for ( j = 0; j < lenccl; ++j )
  750. {
  751. ch = ccltbl[ccllist + j];
  752. if ( ch == 0 )
  753. ch = NUL_ec;
  754. if ( ch > transsym )
  755. break;
  756. else if ( ch == transsym )
  757. {
  758. nset[++numstates] = tsp;
  759. break;
  760. }
  761. }
  762. }
  763. else if ( sym >= 'A' && sym <= 'Z' && caseins )
  764. flexfatal( "consistency check failed in symfollowset" );
  765. else if ( sym == SYM_EPSILON )
  766. { /* do nothing */
  767. }
  768. else if ( abs( ecgroup[sym] ) == transsym )
  769. nset[++numstates] = tsp;
  770. bottom:
  771. ;
  772. }
  773. return ( numstates );
  774. }
  775. /* sympartition - partition characters with same out-transitions
  776. *
  777. * synopsis
  778. * integer ds[current_max_dfa_size], numstates, duplist[numecs];
  779. * symlist[numecs];
  780. * sympartition( ds, numstates, symlist, duplist );
  781. */
  782. void sympartition( ds, numstates, symlist, duplist )
  783. int ds[], numstates, duplist[];
  784. int symlist[];
  785. {
  786. int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
  787. /* partitioning is done by creating equivalence classes for those
  788. * characters which have out-transitions from the given state. Thus
  789. * we are really creating equivalence classes of equivalence classes.
  790. */
  791. for ( i = 1; i <= numecs; ++i )
  792. { /* initialize equivalence class list */
  793. duplist[i] = i - 1;
  794. dupfwd[i] = i + 1;
  795. }
  796. duplist[1] = NIL;
  797. dupfwd[numecs] = NIL;
  798. for ( i = 1; i <= numstates; ++i )
  799. {
  800. ns = ds[i];
  801. tch = transchar[ns];
  802. if ( tch != SYM_EPSILON )
  803. {
  804. if ( tch < -lastccl || tch > csize )
  805. {
  806. if ( tch > csize && tch <= CSIZE )
  807. flexerror( "scanner requires -8 flag" );
  808. else
  809. flexfatal(
  810. "bad transition character detected in sympartition()" );
  811. }
  812. if ( tch >= 0 )
  813. { /* character transition */
  814. /* abs() needed for fake %t ec's */
  815. int ec = abs( ecgroup[tch] );
  816. mkechar( ec, dupfwd, duplist );
  817. symlist[ec] = 1;
  818. }
  819. else
  820. { /* character class */
  821. tch = -tch;
  822. lenccl = ccllen[tch];
  823. cclp = cclmap[tch];
  824. mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs,
  825. NUL_ec );
  826. if ( cclng[tch] )
  827. {
  828. j = 0;
  829. for ( k = 0; k < lenccl; ++k )
  830. {
  831. ich = ccltbl[cclp + k];
  832. if ( ich == 0 )
  833. ich = NUL_ec;
  834. for ( ++j; j < ich; ++j )
  835. symlist[j] = 1;
  836. }
  837. for ( ++j; j <= numecs; ++j )
  838. symlist[j] = 1;
  839. }
  840. else
  841. for ( k = 0; k < lenccl; ++k )
  842. {
  843. ich = ccltbl[cclp + k];
  844. if ( ich == 0 )
  845. ich = NUL_ec;
  846. symlist[ich] = 1;
  847. }
  848. }
  849. }
  850. }
  851. }