compute.c 23 KB

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