compute.c 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155
  1. /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
  2. * For full copyright and restrictions on use see the file COPYING in the top
  3. * level of the LLgen tree.
  4. */
  5. /*
  6. * L L G E N
  7. *
  8. * An Extended LL(1) Parser Generator
  9. *
  10. * Author : Ceriel J.H. Jacobs
  11. */
  12. /*
  13. * compute.c
  14. * Defines routines to compute FIRST, FOLLOW etc.
  15. * Also checks the continuation grammar from the specified grammar.
  16. */
  17. #include <stdlib.h>
  18. # include "types.h"
  19. # include "extern.h"
  20. # include "sets.h"
  21. # include "assert.h"
  22. # include "io.h"
  23. #include "LLgen.h"
  24. static void createsets(void);
  25. static void walk(p_set u, p_gram p);
  26. static void co_trans(int (*fc)(p_nont));
  27. static int nempty(p_nont p);
  28. static int nfirst(p_nont p);
  29. static int nc_nfirst(p_nont p);
  30. static int first(p_set setp, p_gram p, int flag);
  31. static int nc_nfollow(p_nont p);
  32. static int nc_first(p_set setp, p_gram p, int flag);
  33. static int nfollow(p_nont p);
  34. static int follow(p_set setp, p_gram p);
  35. static void co_dirsymb(p_set setp, p_gram p);
  36. static void co_others(p_gram p);
  37. static int ncomplength(p_nont p);
  38. static void do_lengthcomp(void);
  39. static void complength(p_gram p, p_length le);
  40. static void add(p_length a, int c, int v);
  41. static int compare(p_length a, p_length b);
  42. static void setdefaults(p_gram p);
  43. static void do_contains(p_nont n);
  44. static void contains(p_gram p, p_set set);
  45. static int nsafes(p_nont p);
  46. static int do_safes(p_gram p, int safe, int *ch);
  47. /* Defined in this file : */
  48. void do_compute(void)
  49. {
  50. /*
  51. * Does all the work, by calling other routines (divide and conquer)
  52. */
  53. p_nont p;
  54. p_start st;
  55. createsets();
  56. co_trans(nempty); /* Which nonterminals produce empty? */
  57. co_trans(nfirst); /* Computes first sets */
  58. /*
  59. * Compute FOLLOW sets.
  60. * First put EOFILE in the follow set of the start nonterminals.
  61. */
  62. for (st = start; st; st = st->ff_next) {
  63. p = &nonterms[st->ff_nont];
  64. PUTIN(p->n_follow,0);
  65. }
  66. co_trans(nfollow);
  67. /*
  68. * Compute the sets which determine which alternative to choose
  69. * in case of a choice
  70. */
  71. for (p = nonterms; p < maxnt; p++) {
  72. co_dirsymb(p->n_follow,p->n_rule);
  73. }
  74. /*
  75. * Compute the minimum length of productions of nonterminals,
  76. * and then determine the default choices
  77. */
  78. do_lengthcomp();
  79. /*
  80. * Compute the contains sets
  81. */
  82. for (p = nonterms; p < maxnt; p++) do_contains(p);
  83. for (p = nonterms; p < maxnt; p++) contains(p->n_rule, (p_set) 0);
  84. /*
  85. * Compute the safety of each nonterminal and term.
  86. * The safety gives an answer to the question whether a scan is done,
  87. * and how it should be handled.
  88. */
  89. for (p = nonterms; p < maxnt; p++) {
  90. /*
  91. * Don't know anything yet
  92. */
  93. setntsafe(p, NOSAFETY);
  94. setntout(p, NOSAFETY);
  95. }
  96. for (st = start; st; st = st->ff_next) {
  97. /*
  98. * But start symbols are called with lookahead done
  99. */
  100. p = &nonterms[st->ff_nont];
  101. setntsafe(p,SCANDONE);
  102. }
  103. co_trans(nsafes);
  104. #ifdef NON_CORRECTING
  105. if (subpars_sim) {
  106. int s;
  107. /* compute the union of the first sets of all start symbols
  108. Used to compute the nc-first-sets when -s option is given */
  109. start_firsts = get_set();
  110. for (st = start; st; st = st->ff_next) {
  111. s = setunion(start_firsts, (&nonterms[st->ff_nont])->n_first);
  112. }
  113. }
  114. if (non_corr) {
  115. /* compute the non_corr first sets for all nonterminals and terms */
  116. co_trans(nc_nfirst);
  117. for (st = start; st; st = st->ff_next) {
  118. p = &nonterms[st->ff_nont];
  119. PUTIN(p->n_nc_follow,0);
  120. }
  121. co_trans(nc_nfollow);
  122. }
  123. #endif
  124. # ifndef NDEBUG
  125. if (debug) {
  126. fputs("Safeties:\n", stderr);
  127. for (p = nonterms; p < maxnt; p++) {
  128. fprintf(stderr, "%s\t%d\t%d\n",
  129. p->n_name,
  130. getntsafe(p),
  131. getntout(p));
  132. }
  133. }
  134. # endif
  135. }
  136. static void createsets()
  137. {
  138. /*
  139. * Allocate space for the sets. Also determine which files use
  140. * which nonterminals, and determine which nonterminals can be
  141. * made static.
  142. */
  143. p_nont p;
  144. p_file f;
  145. p_start st;
  146. int i;
  147. int n = NINTS(NBYTES(nnonterms));
  148. p_mem alloc();
  149. for (f = files; f < maxfiles; f++) {
  150. p_set s;
  151. f->f_used = s = (p_set) alloc((unsigned)n*sizeof(*(f->f_used)));
  152. for (i = n; i; i--) *s++ = 0;
  153. for (i = f->f_nonterminals; i != -1; i = p->n_next) {
  154. p = &nonterms[i];
  155. p->n_flags |= GENSTATIC;
  156. p->n_first = get_set();
  157. #ifdef NON_CORRECTING
  158. p->n_nc_first = get_set();
  159. p->n_nc_follow = get_set();
  160. #endif
  161. p->n_follow = get_set();
  162. walk(f->f_used, p->n_rule);
  163. }
  164. }
  165. for (f = files; f < maxfiles; f++) {
  166. for (i = f->f_nonterminals; i != -1; i = p->n_next) {
  167. p_file f2;
  168. p = &nonterms[i];
  169. for (f2 = files; f2 < maxfiles; f2++) {
  170. if (f2 != f && IN(f2->f_used, i)) {
  171. p->n_flags &= ~GENSTATIC;
  172. }
  173. }
  174. }
  175. }
  176. for (st = start; st; st = st->ff_next) {
  177. nonterms[st->ff_nont].n_flags &= ~GENSTATIC;
  178. }
  179. }
  180. static void walk(p_set u, p_gram p)
  181. {
  182. /*
  183. * Walk through the grammar rule p, allocating sets
  184. */
  185. for (;;) {
  186. switch (g_gettype(p)) {
  187. case TERM : {
  188. p_term q;
  189. q = g_getterm(p);
  190. q->t_first = get_set();
  191. #ifdef NON_CORRECTING
  192. q->t_nc_first = get_set();
  193. q->t_nc_follow = get_set();
  194. #endif
  195. q->t_follow = get_set();
  196. walk(u, q->t_rule);
  197. break; }
  198. case ALTERNATION : {
  199. p_link l;
  200. l = g_getlink(p);
  201. l->l_symbs = get_set();
  202. #ifdef NON_CORRECTING
  203. l->l_nc_symbs = get_set();
  204. #endif
  205. l->l_others = get_set();
  206. walk(u, l->l_rule);
  207. break; }
  208. case NONTERM : {
  209. int i = g_getcont(p);
  210. PUTIN(u, i);
  211. break; }
  212. case EORULE :
  213. return;
  214. }
  215. p++;
  216. }
  217. }
  218. static void co_trans(int (*fc)(p_nont))
  219. {
  220. p_nont p;
  221. int change;
  222. do {
  223. change = 0;
  224. for (p = nonterms; p < maxnt; p++) {
  225. if ((*fc)(p)) change = 1;
  226. }
  227. } while (change);
  228. }
  229. static int nempty(p_nont p)
  230. {
  231. if (!(p->n_flags & EMPTY) && empty(p->n_rule)) {
  232. p->n_flags |= EMPTY;
  233. return 1;
  234. }
  235. return 0;
  236. }
  237. int empty(p_gram p)
  238. {
  239. /*
  240. * Does the rule pointed to by p produce empty ?
  241. */
  242. for (;;) {
  243. switch (g_gettype(p)) {
  244. case EORULE :
  245. return 1;
  246. case TERM : {
  247. p_term q;
  248. q = g_getterm(p);
  249. if (r_getkind(q) == STAR
  250. || r_getkind(q) == OPT
  251. || empty(q->t_rule) ) break;
  252. return 0; }
  253. case ALTERNATION :
  254. if (empty(g_getlink(p)->l_rule)) {
  255. return 1;
  256. }
  257. if (g_gettype(p+1) == EORULE) return 0;
  258. break;
  259. case NONTERM :
  260. if (nonterms[g_getcont(p)].n_flags & EMPTY) {
  261. break;
  262. }
  263. /* Fall through */
  264. case LITERAL :
  265. case TERMINAL :
  266. return 0;
  267. }
  268. p++;
  269. }
  270. }
  271. static int nfirst(p_nont p)
  272. {
  273. return first(p->n_first, p->n_rule, 0);
  274. }
  275. #ifdef NON_CORRECTING
  276. static int nc_nfirst(p_nont p)
  277. {
  278. return nc_first(p->n_nc_first, p->n_rule, 0);
  279. }
  280. #endif
  281. static int first(p_set setp, p_gram p, int flag)
  282. {
  283. /*
  284. * Compute the FIRST set of rule p.
  285. * If flag = 0, also the first sets for terms and alternations in
  286. * the rule p are computed.
  287. * The FIRST set is put in setp.
  288. * return 1 if the set refered to by "setp" changed
  289. */
  290. int s; /* Will gather return value */
  291. int noenter;/* when set, unables entering of elements into
  292. * setp. This is necessary to walk through the
  293. * rest of rule p.
  294. */
  295. s = 0;
  296. noenter = 0;
  297. for (;;) {
  298. switch (g_gettype(p)) {
  299. case EORULE :
  300. return s;
  301. case TERM : {
  302. p_term q;
  303. q = g_getterm(p);
  304. if (flag == 0) {
  305. first(q->t_first,q->t_rule,0);
  306. }
  307. if (!noenter) s |= setunion(setp,q->t_first);
  308. p++;
  309. if (r_getkind(q) == STAR ||
  310. r_getkind(q) == OPT ||
  311. empty(q->t_rule)) continue;
  312. break; }
  313. case ALTERNATION : {
  314. p_link l;
  315. l = g_getlink(p);
  316. if (flag == 0) {
  317. first(l->l_symbs,l->l_rule,0);
  318. }
  319. if (noenter == 0) {
  320. s |= setunion(setp,l->l_symbs);
  321. }
  322. if (g_gettype(p+1) == EORULE) return s;
  323. }
  324. /* Fall Through */
  325. case ACTION :
  326. p++;
  327. continue;
  328. case LITERAL :
  329. case TERMINAL :
  330. if ((noenter == 0) && !IN(setp,g_getcont(p))) {
  331. s = 1;
  332. PUTIN(setp,g_getcont(p));
  333. }
  334. p++;
  335. break;
  336. case NONTERM : {
  337. p_nont n;
  338. n = &nonterms[g_getcont(p)];
  339. if (noenter == 0) {
  340. s |= setunion(setp,n->n_first);
  341. if (ntneeded) NTPUTIN(setp,g_getcont(p));
  342. }
  343. p++;
  344. if (n->n_flags & EMPTY) continue;
  345. break; }
  346. }
  347. if (flag == 0) {
  348. noenter = 1;
  349. continue;
  350. }
  351. return s;
  352. }
  353. }
  354. #ifdef NON_CORRECTING
  355. static int nc_first(p_set setp, p_gram p, int flag)
  356. {
  357. /*
  358. * Compute the non_corr FIRST set of rule p.
  359. * If flag = 0, also the non_corr first sets for terms and
  360. * alternations in the rule p are computed.
  361. * The non_corr FIRST set is put in setp.
  362. * return 1 if the set refered to by "setp" changed
  363. * If the -s flag was given, the union of the first-sets of all
  364. * start symbols is used whenever an action occurs. Else, only the
  365. * first-sets of startsynbols in the %substart are used
  366. */
  367. int s; /* Will gather return value */
  368. int noenter;/* when set, unables entering of elements into
  369. * setp. This is necessary to walk through the
  370. * rest of rule p.
  371. */
  372. s = 0;
  373. noenter = 0;
  374. for (;;) {
  375. switch (g_gettype(p)) {
  376. case EORULE :
  377. return s;
  378. case TERM : {
  379. p_term q;
  380. q = g_getterm(p);
  381. if (flag == 0) {
  382. nc_first(q->t_nc_first,q->t_rule,0);
  383. }
  384. if (!noenter) s |= setunion(setp,q->t_nc_first);
  385. p++;
  386. if (r_getkind(q) == STAR ||
  387. r_getkind(q) == OPT ||
  388. empty(q->t_rule)) continue;
  389. break; }
  390. case ALTERNATION : {
  391. p_link l;
  392. l = g_getlink(p);
  393. if (flag == 0) {
  394. nc_first(l->l_nc_symbs,l->l_rule,0);
  395. }
  396. if (noenter == 0) {
  397. s |= setunion(setp,l->l_nc_symbs);
  398. }
  399. if (g_gettype(p+1) == EORULE) return s;
  400. }
  401. p++;
  402. continue;
  403. case ACTION : {
  404. p_start subp;
  405. if (!noenter)
  406. {
  407. if (subpars_sim)
  408. {
  409. s |= setunion(setp, start_firsts);
  410. }
  411. else
  412. {
  413. for (subp = g_getsubparse(p); subp; subp = subp->ff_next)
  414. {
  415. s |= setunion(setp, (&nonterms[subp->ff_nont])->n_nc_first);
  416. }
  417. }
  418. }
  419. p++;
  420. continue;
  421. }
  422. case LITERAL :
  423. case TERMINAL :
  424. if (g_getcont(p) == g_getcont(illegal_gram)) {
  425. /* Ignore for this set. */
  426. p++;
  427. continue;
  428. }
  429. if ((noenter == 0) && !IN(setp,g_getcont(p))) {
  430. s = 1;
  431. PUTIN(setp,g_getcont(p));
  432. }
  433. p++;
  434. break;
  435. case NONTERM : {
  436. p_nont n;
  437. n = &nonterms[g_getcont(p)];
  438. if (noenter == 0) {
  439. s |= setunion(setp,n->n_nc_first);
  440. if (ntneeded) NTPUTIN(setp,g_getcont(p));
  441. }
  442. p++;
  443. if (n->n_flags & EMPTY) continue;
  444. break; }
  445. }
  446. if (flag == 0) {
  447. noenter = 1;
  448. continue;
  449. }
  450. return s;
  451. }
  452. }
  453. #endif
  454. static int nfollow(p_nont p)
  455. {
  456. return follow(p->n_follow, p->n_rule);
  457. }
  458. static int follow(p_set setp, p_gram p)
  459. {
  460. /*
  461. * setp is the follow set for the rule p.
  462. * Compute the follow sets in the rule p from this set.
  463. * Return 1 if a follow set of a nonterminal changed.
  464. */
  465. int s; /* Will gather return value */
  466. s = 0;
  467. for (;;) {
  468. switch (g_gettype(p)) {
  469. case EORULE :
  470. return s;
  471. case TERM : {
  472. p_term q;
  473. q = g_getterm(p);
  474. if (empty(p+1)) {
  475. /*
  476. * If what follows the term can be empty,
  477. * everything that can follow the whole
  478. * rule can also follow the term
  479. */
  480. s |= setunion(q->t_follow,setp);
  481. }
  482. /*
  483. * Everything that can start the rest of the rule
  484. * can follow the term
  485. */
  486. s |= first(q->t_follow,p+1,1);
  487. if (r_getkind(q) == STAR ||
  488. r_getkind(q) == PLUS ||
  489. r_getnum(q) ) {
  490. /*
  491. * If the term involves a repetition
  492. * of possibly more than one,
  493. * everything that can start the term
  494. * can also follow it.
  495. */
  496. s |= follow(q->t_first,q->t_rule);
  497. }
  498. /*
  499. * Now propagate the set computed sofar
  500. */
  501. s |= follow(q->t_follow, q->t_rule);
  502. break; }
  503. case ALTERNATION :
  504. /*
  505. * Just propagate setp
  506. */
  507. s |= follow(setp,g_getlink(p)->l_rule);
  508. break;
  509. case NONTERM : {
  510. p_nont n;
  511. n = &nonterms[g_getcont(p)];
  512. s |= first(n->n_follow,p+1,1);
  513. if (empty(p+1)) {
  514. /*
  515. * If the rest of p can produce empty,
  516. * everything that follows p can follow
  517. * the nonterminal
  518. */
  519. s |= setunion(n->n_follow,setp);
  520. }
  521. break; }
  522. }
  523. p++;
  524. }
  525. }
  526. #ifdef NON_CORRECTING
  527. static int nc_nfollow(p_nont p)
  528. {
  529. return follow(p->n_nc_follow, p->n_rule);
  530. }
  531. static int nc_follow(p_set setp, p_gram p)
  532. {
  533. /*
  534. * setp is the follow set for the rule p.
  535. * Compute the follow sets in the rule p from this set.
  536. * Return 1 if a follow set of a nonterminal changed.
  537. */
  538. int s; /* Will gather return value */
  539. s = 0;
  540. for (;;) {
  541. switch (g_gettype(p)) {
  542. case EORULE :
  543. return s;
  544. case TERM : {
  545. p_term q;
  546. q = g_getterm(p);
  547. if (empty(p+1)) {
  548. /*
  549. * If what follows the term can be empty,
  550. * everything that can follow the whole
  551. * rule can also follow the term
  552. */
  553. s |= setunion(q->t_nc_follow,setp);
  554. }
  555. /*
  556. * Everything that can start the rest of the rule
  557. * can follow the term
  558. */
  559. s |= nc_first(q->t_nc_follow,p+1,1);
  560. if (r_getkind(q) == STAR ||
  561. r_getkind(q) == PLUS ||
  562. r_getnum(q) ) {
  563. /*
  564. * If the term involves a repetition
  565. * of possibly more than one,
  566. * everything that can start the term
  567. * can also follow it.
  568. */
  569. s |= nc_follow(q->t_nc_first,q->t_rule);
  570. }
  571. /*
  572. * Now propagate the set computed sofar
  573. */
  574. s |= nc_follow(q->t_nc_follow, q->t_rule);
  575. break; }
  576. case ALTERNATION :
  577. /*
  578. * Just propagate setp
  579. */
  580. s |= nc_follow(setp,g_getlink(p)->l_rule);
  581. break;
  582. case NONTERM : {
  583. p_nont n;
  584. n = &nonterms[g_getcont(p)];
  585. s |= nc_first(n->n_nc_follow,p+1,1);
  586. if (empty(p+1)) {
  587. /*
  588. * If the rest of p can produce empty,
  589. * everything that follows p can follow
  590. * the nonterminal
  591. */
  592. s |= setunion(n->n_nc_follow,setp);
  593. }
  594. break; }
  595. }
  596. p++;
  597. }
  598. }
  599. #endif
  600. static void co_dirsymb(p_set setp, p_gram p)
  601. {
  602. /*
  603. * Walk the rule p, doing the work for alternations
  604. */
  605. p_gram s = 0;
  606. for (;;) {
  607. switch (g_gettype(p)) {
  608. case EORULE :
  609. return;
  610. case TERM : {
  611. p_term q;
  612. q = g_getterm(p);
  613. co_dirsymb(q->t_follow,q->t_rule);
  614. break; }
  615. case ALTERNATION : {
  616. p_link l;
  617. /*
  618. * Save first alternative
  619. */
  620. if (!s) s = p;
  621. l = g_getlink(p);
  622. co_dirsymb(setp,l->l_rule);
  623. if (empty(l->l_rule)) {
  624. /*
  625. * If the rule can produce empty, everything
  626. * that follows it can also start it
  627. */
  628. setunion(l->l_symbs,setp);
  629. }
  630. if (g_gettype(p+1) == EORULE) {
  631. /*
  632. * Every alternation is implemented as a
  633. * choice between two alternatives :
  634. * this one or one of the following.
  635. * The l_others set will contain the starters
  636. * of the other alternatives
  637. */
  638. co_others(s);
  639. return;
  640. } }
  641. }
  642. p++;
  643. }
  644. }
  645. static void co_others(p_gram p)
  646. {
  647. /*
  648. * compute the l_others-sets for the list of alternatives
  649. * indicated by p
  650. */
  651. p_link l1,l2;
  652. l1 = g_getlink(p);
  653. p++;
  654. l2 = g_getlink(p);
  655. setunion(l1->l_others,l2->l_symbs);
  656. if (g_gettype(p+1) != EORULE) {
  657. /*
  658. * First compute l2->l_others
  659. */
  660. co_others(p);
  661. /*
  662. * and then l1->l_others
  663. */
  664. setunion(l1->l_others,l2->l_others);
  665. }
  666. }
  667. static p_length length;
  668. # define INFINITY 32767
  669. static int ncomplength(p_nont p)
  670. {
  671. p_length pl = &length[p - nonterms];
  672. int x = pl->cnt;
  673. pl->cnt = -1;
  674. complength(p->n_rule, pl);
  675. return pl->cnt < INFINITY && x == INFINITY;
  676. }
  677. static void do_lengthcomp()
  678. {
  679. /*
  680. * Compute the minimum length of a terminal production for each
  681. * nonterminal.
  682. * This length consists of two fields: the number of terminals,
  683. * and a number that is composed of
  684. * - the number of this alternative
  685. * - a crude measure of the number of terms and nonterminals in the
  686. * production of this shortest string.
  687. */
  688. p_length pl;
  689. p_nont p;
  690. p_mem alloc();
  691. length = (p_length) alloc((unsigned) (nnonterms * sizeof(*length)));
  692. for (pl = &length[nnonterms-1]; pl >= length; pl--) {
  693. pl->val = pl->cnt = INFINITY;
  694. }
  695. co_trans(ncomplength);
  696. pl = length;
  697. for (p = nonterms; p < maxnt; p++, pl++) {
  698. if (pl->cnt == INFINITY) {
  699. p->n_flags |= RECURSIVE;
  700. }
  701. setdefaults(p->n_rule);
  702. }
  703. free ((p_mem) length);
  704. }
  705. static void complength(p_gram p, p_length le)
  706. {
  707. /*
  708. * Walk grammar rule p, computing minimum lengths
  709. */
  710. p_link l;
  711. p_term q;
  712. t_length i;
  713. t_length X;
  714. int cnt = 0;
  715. X.cnt = 0;
  716. X.val = 0;
  717. for (;;) {
  718. switch (g_gettype(p)) {
  719. case LITERAL :
  720. case TERMINAL :
  721. #ifdef NON_CORRECTING
  722. if (g_getcont(p) == g_getcont(illegal_gram)) {
  723. add(&X, INFINITY, 0);
  724. break;
  725. }
  726. #endif
  727. add(&X, 1, 0);
  728. break;
  729. case ALTERNATION :
  730. X.cnt = INFINITY;
  731. X.val = INFINITY;
  732. while (g_gettype(p) != EORULE) {
  733. cnt++;
  734. l = g_getlink(p);
  735. p++;
  736. complength(l->l_rule,&i);
  737. i.val += cnt;
  738. if (l->l_flag & DEF) {
  739. X = i;
  740. break;
  741. }
  742. if (compare(&i, &X) < 0) {
  743. X = i;
  744. }
  745. }
  746. /* Fall through */
  747. case EORULE :
  748. le->cnt = X.cnt;
  749. le->val = X.val;
  750. return;
  751. case TERM : {
  752. int rep;
  753. q = g_getterm(p);
  754. rep = r_getkind(q);
  755. X.val += 1;
  756. if ((q->t_flags&PERSISTENT) ||
  757. rep==FIXED || rep==PLUS) {
  758. complength(q->t_rule,&i);
  759. add(&X, i.cnt, i.val);
  760. if (rep == FIXED && r_getnum(q) > 0) {
  761. for (rep = r_getnum(q) - 1;
  762. rep > 0; rep--) {
  763. add(&X, i.cnt, i.val);
  764. }
  765. }
  766. }
  767. break; }
  768. case NONTERM : {
  769. int nn = g_getcont(p);
  770. p_length pl = &length[nn];
  771. int x = pl->cnt;
  772. if (x == INFINITY) {
  773. pl->cnt = -1;
  774. complength(nonterms[nn].n_rule,pl);
  775. x = pl->cnt;
  776. }
  777. else if (x == -1) x = INFINITY;
  778. add(&X, x, pl->val);
  779. X.val += 1;
  780. }
  781. }
  782. p++;
  783. }
  784. }
  785. static void add(p_length a, int c, int v)
  786. {
  787. if (a->cnt == INFINITY || c == INFINITY) {
  788. a->cnt = INFINITY;
  789. return;
  790. }
  791. a->val += v;
  792. a->cnt += c;
  793. }
  794. static int compare(p_length a, p_length b)
  795. {
  796. if (a->cnt != b->cnt) return a->cnt - b->cnt;
  797. return a->val - b->val;
  798. }
  799. static void setdefaults(p_gram p)
  800. {
  801. for (;;) {
  802. switch(g_gettype(p)) {
  803. case EORULE:
  804. return;
  805. case TERM:
  806. setdefaults(g_getterm(p)->t_rule);
  807. break;
  808. case ALTERNATION: {
  809. p_link l, l1;
  810. int temp = 0, temp1, cnt = 0;
  811. t_length count, i;
  812. count.cnt = INFINITY;
  813. count.val = INFINITY;
  814. l1 = g_getlink(p);
  815. do {
  816. cnt++;
  817. l = g_getlink(p);
  818. p++;
  819. complength(l->l_rule,&i);
  820. i.val += cnt;
  821. if (l->l_flag & DEF) temp = 1;
  822. temp1 = compare(&i, &count);
  823. if (temp1 < 0 ||
  824. (temp1 == 0 && l1->l_flag & AVOIDING)) {
  825. l1 = l;
  826. count = i;
  827. }
  828. setdefaults(l->l_rule);
  829. } while (g_gettype(p) != EORULE);
  830. if (!temp) {
  831. /* No user specified default */
  832. l1->l_flag |= DEF;
  833. }
  834. return; }
  835. }
  836. p++;
  837. }
  838. }
  839. static void do_contains(p_nont n)
  840. {
  841. /*
  842. * Compute the total set of symbols that nonterminal n can
  843. * produce
  844. */
  845. if (n->n_contains == 0) {
  846. n->n_contains = get_set();
  847. contains(n->n_rule,n->n_contains);
  848. /*
  849. * If the rule can produce empty, delete all symbols that
  850. * can follow the rule as well as be in the rule.
  851. * This is needed because the contains-set may only contain
  852. * symbols that are guaranteed to be eaten by the rule!
  853. * Otherwise, the generated parser may loop forever
  854. */
  855. if (n->n_flags & EMPTY) {
  856. setminus(n->n_contains,n->n_follow);
  857. }
  858. /*
  859. * But the symbols that can start the rule are always
  860. * eaten
  861. */
  862. setunion(n->n_contains,n->n_first);
  863. }
  864. }
  865. static void contains(p_gram p, p_set set)
  866. {
  867. /*
  868. * Does the real computation of the contains-sets
  869. */
  870. for (;;) {
  871. switch (g_gettype(p)) {
  872. case EORULE :
  873. return;
  874. case TERM : {
  875. p_term q;
  876. int rep;
  877. q = g_getterm(p);
  878. rep = r_getkind(q);
  879. if ((q->t_flags & PERSISTENT) ||
  880. rep == PLUS || rep == FIXED) {
  881. /*
  882. * In these cases, the term belongs to the
  883. * continuation grammar.
  884. * Otherwise, q->t_contains is just
  885. * q->t_first
  886. */
  887. if (!q->t_contains) {
  888. q->t_contains = get_set();
  889. }
  890. contains(q->t_rule,q->t_contains);
  891. if (rep != FIXED || empty(q->t_rule)) {
  892. setminus(q->t_contains,q->t_follow);
  893. }
  894. setunion(q->t_contains,q->t_first);
  895. } else {
  896. contains(q->t_rule, (p_set) 0);
  897. q->t_contains = q->t_first;
  898. }
  899. if (set) setunion(set,q->t_contains);
  900. break; }
  901. case NONTERM : {
  902. p_nont n;
  903. n = &nonterms[g_getcont(p)];
  904. do_contains(n);
  905. if (set) {
  906. setunion(set, n->n_contains);
  907. if (ntneeded) NTPUTIN(set, g_getcont(p));
  908. }
  909. break; }
  910. case ALTERNATION : {
  911. p_link l;
  912. l = g_getlink(p);
  913. contains(l->l_rule,
  914. (l->l_flag & DEF) ? set : (p_set) 0);
  915. break; }
  916. case LITERAL :
  917. case TERMINAL : {
  918. int hulp;
  919. if (set) {
  920. hulp = g_getcont(p);
  921. assert(hulp < ntokens);
  922. PUTIN(set,hulp);
  923. }}
  924. }
  925. p++;
  926. }
  927. }
  928. static int nsafes(p_nont p)
  929. {
  930. int ch;
  931. int i;
  932. ch = 0;
  933. i = getntsafe(p);
  934. if (i != NOSAFETY) {
  935. i = do_safes(p->n_rule, i, &ch);
  936. if (i < SCANDONE) i = SCANDONE;
  937. /* After a nonterminal, we only know whether a scan was done
  938. or not
  939. */
  940. if (getntout(p) != i) {
  941. ch = 1;
  942. setntout(p,i);
  943. }
  944. }
  945. return ch;
  946. }
  947. static int do_safes(p_gram p, int safe, int *ch)
  948. {
  949. /*
  950. * Walk the grammar rule, doing the computation described in the
  951. * comment of the procedure above this one.
  952. */
  953. int retval;
  954. for (;;) {
  955. switch (g_gettype(p)) {
  956. case ACTION:
  957. p++;
  958. continue;
  959. case LITERAL:
  960. case TERMINAL:
  961. safe = NOSCANDONE;
  962. break;
  963. case TERM : {
  964. p_term q;
  965. int i,rep;
  966. q = g_getterm(p);
  967. i = r_getnum(q);
  968. rep = r_getkind(q);
  969. retval = do_safes(q->t_rule,
  970. t_safety(rep,i,q->t_flags&PERSISTENT,safe),ch);
  971. settout(q, retval);
  972. safe = t_after(rep, i, retval);
  973. break; }
  974. case ALTERNATION : {
  975. p_link l;
  976. int i;
  977. retval = -1;
  978. while (g_gettype(p) == ALTERNATION) {
  979. l = g_getlink(p);
  980. p++;
  981. if (safe > SAFE && (l->l_flag & DEF)) {
  982. i = do_safes(l->l_rule,SAFESCANDONE,ch);
  983. }
  984. else i = do_safes(l->l_rule,SAFE,ch);
  985. if (retval == -1) retval = i;
  986. else if (i != retval) {
  987. if (i == NOSCANDONE ||
  988. retval == NOSCANDONE) {
  989. retval = SCANDONE;
  990. }
  991. else if (i > retval) retval = i;
  992. }
  993. }
  994. return retval; }
  995. case NONTERM : {
  996. p_nont n;
  997. int nsafe, osafe;
  998. n = &nonterms[g_getcont(p)];
  999. nsafe = getntsafe(n);
  1000. osafe = safe;
  1001. safe = getntout(n);
  1002. if (safe == NOSAFETY) safe = SCANDONE;
  1003. if (osafe == nsafe) break;
  1004. if (nsafe == NOSAFETY) {
  1005. *ch = 1;
  1006. setntsafe(n, osafe);
  1007. break;
  1008. }
  1009. if (osafe == NOSCANDONE || nsafe == NOSCANDONE) {
  1010. if (nsafe != SCANDONE) {
  1011. *ch = 1;
  1012. setntsafe(n, SCANDONE);
  1013. }
  1014. break;
  1015. }
  1016. if (osafe > nsafe) {
  1017. setntsafe(n, osafe);
  1018. *ch = 1;
  1019. }
  1020. break; }
  1021. case EORULE :
  1022. return safe;
  1023. }
  1024. p++;
  1025. }
  1026. }
  1027. int t_safety(int rep, int count, int persistent, int safety)
  1028. {
  1029. if (safety == NOSCANDONE) safety = SCANDONE;
  1030. switch(rep) {
  1031. default:
  1032. assert(0);
  1033. case OPT:
  1034. if (!persistent || safety < SAFESCANDONE) return SAFE;
  1035. return SAFESCANDONE;
  1036. case STAR:
  1037. if (persistent) return SAFESCANDONE;
  1038. return SAFE;
  1039. case PLUS:
  1040. if (persistent) {
  1041. if (safety > SAFESCANDONE) return safety;
  1042. return SAFESCANDONE;
  1043. }
  1044. return safety;
  1045. case FIXED:
  1046. if (!count) return safety;
  1047. return SCANDONE;
  1048. }
  1049. /* NOTREACHED */
  1050. }
  1051. int t_after(int rep, int count, int outsafety)
  1052. {
  1053. if (count == 0 && (rep == STAR || rep == PLUS)) {
  1054. return SAFESCANDONE;
  1055. }
  1056. if (rep != FIXED) {
  1057. if (outsafety <= SAFESCANDONE) return SAFESCANDONE;
  1058. return SCANDONE;
  1059. }
  1060. return outsafety;
  1061. }