compute.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922
  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. do_compute() {
  57. /*
  58. * Does all the work, by calling other routines (divide and conquer)
  59. */
  60. register p_nont p;
  61. register p_start st;
  62. createsets();
  63. co_trans(nempty); /* Which nonterminals produce empty? */
  64. co_trans(nfirst); /* Computes first sets */
  65. /*
  66. * Compute FOLLOW sets.
  67. * First put EOFILE in the follow set of the start nonterminals.
  68. */
  69. for (st = start; st; st = st->ff_next) {
  70. p = &nonterms[st->ff_nont];
  71. PUTIN(p->n_follow,0);
  72. }
  73. co_trans(nfollow);
  74. /*
  75. * Compute the sets which determine which alternative to choose
  76. * in case of a choice
  77. */
  78. for (p = nonterms; p < maxnt; p++) {
  79. co_dirsymb(p->n_follow,p->n_rule);
  80. }
  81. /*
  82. * Compute the minimum length of productions of nonterminals,
  83. * and then determine the default choices
  84. */
  85. do_lengthcomp();
  86. /*
  87. * Compute the contains sets
  88. */
  89. for (p = nonterms; p < maxnt; p++) do_contains(p);
  90. for (p = nonterms; p < maxnt; p++) contains(p->n_rule, (p_set) 0);
  91. /*
  92. * Compute the safety of each nonterminal and term.
  93. * The safety gives an answer to the question whether a scan is done,
  94. * and how it should be handled.
  95. */
  96. for (p = nonterms; p < maxnt; p++) {
  97. /*
  98. * Don't know anything yet
  99. */
  100. setntsafe(p, NOSAFETY);
  101. setntout(p, NOSAFETY);
  102. }
  103. for (st = start; st; st = st->ff_next) {
  104. /*
  105. * But start symbols are called with lookahead done
  106. */
  107. p = &nonterms[st->ff_nont];
  108. setntsafe(p,SCANDONE);
  109. }
  110. co_trans(nsafes);
  111. # ifndef NDEBUG
  112. if (debug) {
  113. fputs("Safeties:\n", stderr);
  114. for (p = nonterms; p < maxnt; p++) {
  115. fprintf(stderr, "%s\t%d\t%d\n",
  116. p->n_name,
  117. getntsafe(p),
  118. getntout(p));
  119. }
  120. }
  121. # endif
  122. }
  123. STATIC
  124. createsets() {
  125. /*
  126. * Allocate space for the sets. Also determine which files use
  127. * which nonterminals, and determine which nonterminals can be
  128. * made static.
  129. */
  130. register p_nont p;
  131. register p_file f;
  132. register p_start st;
  133. register int i;
  134. int n = NINTS(NBYTES(nnonterms));
  135. p_mem alloc();
  136. for (f = files; f < maxfiles; f++) {
  137. register p_set s;
  138. f->f_used = s = (p_set) alloc((unsigned)n*sizeof(*(f->f_used)));
  139. for (i = n; i; i--) *s++ = 0;
  140. for (i = f->f_nonterminals; i != -1; i = p->n_next) {
  141. p = &nonterms[i];
  142. p->n_flags |= GENSTATIC;
  143. p->n_first = get_set();
  144. p->n_follow = get_set();
  145. walk(f->f_used, p->n_rule);
  146. }
  147. }
  148. for (f = files; f < maxfiles; f++) {
  149. for (i = f->f_nonterminals; i != -1; i = p->n_next) {
  150. register p_file f2;
  151. p = &nonterms[i];
  152. for (f2 = files; f2 < maxfiles; f2++) {
  153. if (f2 != f && IN(f2->f_used, i)) {
  154. p->n_flags &= ~GENSTATIC;
  155. }
  156. }
  157. }
  158. }
  159. for (st = start; st; st = st->ff_next) {
  160. nonterms[st->ff_nont].n_flags &= ~GENSTATIC;
  161. }
  162. }
  163. STATIC
  164. walk(u, p) p_set u; register p_gram p; {
  165. /*
  166. * Walk through the grammar rule p, allocating sets
  167. */
  168. for (;;) {
  169. switch (g_gettype(p)) {
  170. case TERM : {
  171. register p_term q;
  172. q = g_getterm(p);
  173. q->t_first = get_set();
  174. q->t_follow = get_set();
  175. walk(u, q->t_rule);
  176. break; }
  177. case ALTERNATION : {
  178. register p_link l;
  179. l = g_getlink(p);
  180. l->l_symbs = get_set();
  181. l->l_others = get_set();
  182. walk(u, l->l_rule);
  183. break; }
  184. case NONTERM : {
  185. register int i = g_getcont(p);
  186. PUTIN(u, i);
  187. break; }
  188. case EORULE :
  189. return;
  190. }
  191. p++;
  192. }
  193. }
  194. STATIC
  195. co_trans(fc) int (*fc)(); {
  196. register p_nont p;
  197. register int change;
  198. do {
  199. change = 0;
  200. for (p = nonterms; p < maxnt; p++) {
  201. if ((*fc)(p)) change = 1;
  202. }
  203. } while (change);
  204. }
  205. STATIC int
  206. nempty(p) register p_nont p; {
  207. if (!(p->n_flags & EMPTY) && empty(p->n_rule)) {
  208. p->n_flags |= EMPTY;
  209. return 1;
  210. }
  211. return 0;
  212. }
  213. empty(p) register p_gram p; {
  214. /*
  215. * Does the rule pointed to by p produce empty ?
  216. */
  217. for (;;) {
  218. switch (g_gettype(p)) {
  219. case EORULE :
  220. return 1;
  221. case TERM : {
  222. register p_term q;
  223. q = g_getterm(p);
  224. if (r_getkind(q) == STAR
  225. || r_getkind(q) == OPT
  226. || empty(q->t_rule) ) break;
  227. return 0; }
  228. case ALTERNATION :
  229. if (empty(g_getlink(p)->l_rule)) {
  230. return 1;
  231. }
  232. if (g_gettype(p+1) == EORULE) return 0;
  233. break;
  234. case NONTERM :
  235. if (nonterms[g_getcont(p)].n_flags & EMPTY) {
  236. break;
  237. }
  238. /* Fall through */
  239. case LITERAL :
  240. case TERMINAL :
  241. return 0;
  242. }
  243. p++;
  244. }
  245. }
  246. STATIC int
  247. nfirst(p) register p_nont p; {
  248. return first(p->n_first, p->n_rule, 0);
  249. }
  250. STATIC
  251. first(setp,p,flag) p_set setp; register p_gram p; {
  252. /*
  253. * Compute the FIRST set of rule p.
  254. * If flag = 0, also the first sets for terms and alternations in
  255. * the rule p are computed.
  256. * The FIRST set is put in setp.
  257. * return 1 if the set refered to by "setp" changed
  258. */
  259. register s; /* Will gather return value */
  260. int noenter;/* when set, unables entering of elements into
  261. * setp. This is necessary to walk through the
  262. * rest of rule p.
  263. */
  264. s = 0;
  265. noenter = 0;
  266. for (;;) {
  267. switch (g_gettype(p)) {
  268. case EORULE :
  269. return s;
  270. case TERM : {
  271. register p_term q;
  272. q = g_getterm(p);
  273. if (flag == 0) {
  274. if (first(q->t_first,q->t_rule,0))/*nothing*/;
  275. }
  276. if (!noenter) s |= setunion(setp,q->t_first);
  277. p++;
  278. if (r_getkind(q) == STAR ||
  279. r_getkind(q) == OPT ||
  280. empty(q->t_rule)) continue;
  281. break; }
  282. case ALTERNATION : {
  283. register p_link l;
  284. l = g_getlink(p);
  285. if (flag == 0) {
  286. if (first(l->l_symbs,l->l_rule,0))/*nothing*/;
  287. }
  288. if (noenter == 0) {
  289. s |= setunion(setp,l->l_symbs);
  290. }
  291. if (g_gettype(p+1) == EORULE) return s;
  292. }
  293. /* Fall Through */
  294. case ACTION :
  295. p++;
  296. continue;
  297. case LITERAL :
  298. case TERMINAL :
  299. if ((noenter == 0) && !IN(setp,g_getcont(p))) {
  300. s = 1;
  301. PUTIN(setp,g_getcont(p));
  302. }
  303. p++;
  304. break;
  305. case NONTERM : {
  306. register p_nont n;
  307. n = &nonterms[g_getcont(p)];
  308. if (noenter == 0) {
  309. s |= setunion(setp,n->n_first);
  310. if (ntneeded) NTPUTIN(setp,g_getcont(p));
  311. }
  312. p++;
  313. if (n->n_flags & EMPTY) continue;
  314. break; }
  315. }
  316. if (flag == 0) {
  317. noenter = 1;
  318. continue;
  319. }
  320. return s;
  321. }
  322. }
  323. STATIC int
  324. nfollow(p) register p_nont p; {
  325. return follow(p->n_follow, p->n_rule);
  326. }
  327. STATIC
  328. follow(setp,p) p_set setp; register p_gram p; {
  329. /*
  330. * setp is the follow set for the rule p.
  331. * Compute the follow sets in the rule p from this set.
  332. * Return 1 if a follow set of a nonterminal changed.
  333. */
  334. register s; /* Will gather return value */
  335. s = 0;
  336. for (;;) {
  337. switch (g_gettype(p)) {
  338. case EORULE :
  339. return s;
  340. case TERM : {
  341. register p_term q;
  342. q = g_getterm(p);
  343. if (empty(p+1)) {
  344. /*
  345. * If what follows the term can be empty,
  346. * everything that can follow the whole
  347. * rule can also follow the term
  348. */
  349. s |= setunion(q->t_follow,setp);
  350. }
  351. /*
  352. * Everything that can start the rest of the rule
  353. * can follow the term
  354. */
  355. s |= first(q->t_follow,p+1,1);
  356. if (r_getkind(q) == STAR ||
  357. r_getkind(q) == PLUS ||
  358. r_getnum(q) ) {
  359. /*
  360. * If the term involves a repetition
  361. * of possibly more than one,
  362. * everything that can start the term
  363. * can also follow it.
  364. */
  365. s |= follow(q->t_first,q->t_rule);
  366. }
  367. /*
  368. * Now propagate the set computed sofar
  369. */
  370. s |= follow(q->t_follow, q->t_rule);
  371. break; }
  372. case ALTERNATION :
  373. /*
  374. * Just propagate setp
  375. */
  376. s |= follow(setp,g_getlink(p)->l_rule);
  377. break;
  378. case NONTERM : {
  379. register p_nont n;
  380. n = &nonterms[g_getcont(p)];
  381. s |= first(n->n_follow,p+1,1);
  382. if (empty(p+1)) {
  383. /*
  384. * If the rest of p can produce empty,
  385. * everything that follows p can follow
  386. * the nonterminal
  387. */
  388. s |= setunion(n->n_follow,setp);
  389. }
  390. break; }
  391. }
  392. p++;
  393. }
  394. }
  395. STATIC
  396. co_dirsymb(setp,p) p_set setp; register p_gram p; {
  397. /*
  398. * Walk the rule p, doing the work for alternations
  399. */
  400. register p_gram s = 0;
  401. for (;;) {
  402. switch (g_gettype(p)) {
  403. case EORULE :
  404. return;
  405. case TERM : {
  406. register p_term q;
  407. q = g_getterm(p);
  408. co_dirsymb(q->t_follow,q->t_rule);
  409. break; }
  410. case ALTERNATION : {
  411. register p_link l;
  412. /*
  413. * Save first alternative
  414. */
  415. if (!s) s = p;
  416. l = g_getlink(p);
  417. co_dirsymb(setp,l->l_rule);
  418. if (empty(l->l_rule)) {
  419. /*
  420. * If the rule can produce empty, everything
  421. * that follows it can also start it
  422. */
  423. setunion(l->l_symbs,setp);
  424. }
  425. if (g_gettype(p+1) == EORULE) {
  426. /*
  427. * Every alternation is implemented as a
  428. * choice between two alternatives :
  429. * this one or one of the following.
  430. * The l_others set will contain the starters
  431. * of the other alternatives
  432. */
  433. co_others(s);
  434. return;
  435. } }
  436. }
  437. p++;
  438. }
  439. }
  440. STATIC
  441. co_others(p) register p_gram p; {
  442. /*
  443. * compute the l_others-sets for the list of alternatives
  444. * indicated by p
  445. */
  446. register p_link l1,l2;
  447. l1 = g_getlink(p);
  448. p++;
  449. l2 = g_getlink(p);
  450. setunion(l1->l_others,l2->l_symbs);
  451. if (g_gettype(p+1) != EORULE) {
  452. /*
  453. * First compute l2->l_others
  454. */
  455. co_others(p);
  456. /*
  457. * and then l1->l_others
  458. */
  459. setunion(l1->l_others,l2->l_others);
  460. }
  461. }
  462. static p_length length;
  463. # define INFINITY 32767
  464. STATIC
  465. ncomplength(p)
  466. register p_nont p;
  467. {
  468. register p_length pl = &length[p - nonterms];
  469. int x = pl->cnt;
  470. pl->cnt = -1;
  471. complength(p->n_rule, pl);
  472. return pl->cnt < INFINITY && x == INFINITY;
  473. }
  474. STATIC
  475. do_lengthcomp() {
  476. /*
  477. * Compute the minimum length of a terminal production for each
  478. * nonterminal.
  479. * This length consists of two fields: the number of terminals,
  480. * and a number that is composed of
  481. * - the number of this alternative
  482. * - a crude measure of the number of terms and nonterminals in the
  483. * production of this shortest string.
  484. */
  485. register p_length pl;
  486. register p_nont p;
  487. p_mem alloc();
  488. length = (p_length) alloc((unsigned) (nnonterms * sizeof(*length)));
  489. for (pl = &length[nnonterms-1]; pl >= length; pl--) {
  490. pl->val = pl->cnt = INFINITY;
  491. }
  492. co_trans(ncomplength);
  493. pl = length;
  494. for (p = nonterms; p < maxnt; p++, pl++) {
  495. if (pl->cnt == INFINITY) {
  496. p->n_flags |= RECURSIVE;
  497. }
  498. setdefaults(p->n_rule);
  499. }
  500. free ((p_mem) length);
  501. }
  502. STATIC
  503. complength(p,le) register p_gram p; p_length le; {
  504. /*
  505. * Walk grammar rule p, computing minimum lengths
  506. */
  507. register p_link l;
  508. register p_term q;
  509. t_length i;
  510. t_length X;
  511. int cnt = 0;
  512. X.cnt = 0;
  513. X.val = 0;
  514. for (;;) {
  515. switch (g_gettype(p)) {
  516. case LITERAL :
  517. case TERMINAL :
  518. add(&X, 1, 0);
  519. break;
  520. case ALTERNATION :
  521. X.cnt = INFINITY;
  522. X.val = INFINITY;
  523. while (g_gettype(p) != EORULE) {
  524. cnt++;
  525. l = g_getlink(p);
  526. complength(l->l_rule,&i);
  527. i.val += cnt;
  528. if (l->l_flag & DEF) {
  529. X = i;
  530. break;
  531. }
  532. if (compare(&i, &X) < 0) {
  533. X = i;
  534. }
  535. p++;
  536. }
  537. /* Fall through */
  538. case EORULE :
  539. le->cnt = X.cnt;
  540. le->val = X.val;
  541. return;
  542. case TERM : {
  543. register int rep;
  544. q = g_getterm(p);
  545. rep = r_getkind(q);
  546. X.val += 1;
  547. if ((q->t_flags&PERSISTENT) ||
  548. rep==FIXED || rep==PLUS) {
  549. complength(q->t_rule,&i);
  550. add(&X, i.cnt, i.val);
  551. if (rep == FIXED && r_getnum(q) > 0) {
  552. for (rep = r_getnum(q) - 1;
  553. rep > 0; rep--) {
  554. add(&X, i.cnt, i.val);
  555. }
  556. }
  557. }
  558. break; }
  559. case NONTERM : {
  560. int nn = g_getcont(p);
  561. register p_length pl = &length[nn];
  562. int x = pl->cnt;
  563. if (x == INFINITY) {
  564. pl->cnt = -1;
  565. complength(nonterms[nn].n_rule,pl);
  566. x = pl->cnt;
  567. }
  568. else if (x == -1) x = INFINITY;
  569. add(&X, x, pl->val);
  570. X.val += 1;
  571. }
  572. }
  573. p++;
  574. }
  575. }
  576. STATIC
  577. add(a, c, v) register p_length a; {
  578. if (a->cnt == INFINITY || c == INFINITY) {
  579. a->cnt = INFINITY;
  580. return;
  581. }
  582. a->val += v;
  583. a->cnt += c;
  584. }
  585. STATIC int
  586. compare(a, b) register p_length a, b; {
  587. if (a->cnt != b->cnt) return a->cnt - b->cnt;
  588. return a->val - b->val;
  589. }
  590. STATIC
  591. setdefaults(p) register p_gram p; {
  592. for (;;) {
  593. switch(g_gettype(p)) {
  594. case EORULE:
  595. return;
  596. case TERM:
  597. setdefaults(g_getterm(p)->t_rule);
  598. break;
  599. case ALTERNATION: {
  600. register p_link l, l1;
  601. int temp = 0, temp1, cnt = 0;
  602. t_length count, i;
  603. count.cnt = INFINITY;
  604. count.val = INFINITY;
  605. l1 = g_getlink(p);
  606. do {
  607. cnt++;
  608. l = g_getlink(p);
  609. complength(l->l_rule,&i);
  610. i.val += cnt;
  611. if (l->l_flag & DEF) temp = 1;
  612. temp1 = compare(&i, &count);
  613. if (temp1 < 0 ||
  614. (temp1 == 0 && l1->l_flag & AVOIDING)) {
  615. l1 = l;
  616. count = i;
  617. }
  618. setdefaults(l->l_rule);
  619. p++;
  620. } while (g_gettype(p) != EORULE);
  621. if (!temp) {
  622. /* No user specified default */
  623. l1->l_flag |= DEF;
  624. }
  625. return; }
  626. }
  627. p++;
  628. }
  629. }
  630. STATIC
  631. do_contains(n) register p_nont n; {
  632. /*
  633. * Compute the total set of symbols that nonterminal n can
  634. * produce
  635. */
  636. if (n->n_contains == 0) {
  637. n->n_contains = get_set();
  638. contains(n->n_rule,n->n_contains);
  639. /*
  640. * If the rule can produce empty, delete all symbols that
  641. * can follow the rule as well as be in the rule.
  642. * This is needed because the contains-set may only contain
  643. * symbols that are guaranteed to be eaten by the rule!
  644. * Otherwise, the generated parser may loop forever
  645. */
  646. if (n->n_flags & EMPTY) {
  647. setminus(n->n_contains,n->n_follow);
  648. }
  649. /*
  650. * But the symbols that can start the rule are always
  651. * eaten
  652. */
  653. setunion(n->n_contains,n->n_first);
  654. }
  655. }
  656. STATIC
  657. contains(p,set) register p_gram p; register p_set set; {
  658. /*
  659. * Does the real computation of the contains-sets
  660. */
  661. for (;;) {
  662. switch (g_gettype(p)) {
  663. case EORULE :
  664. return;
  665. case TERM : {
  666. register p_term q;
  667. int rep;
  668. q = g_getterm(p);
  669. rep = r_getkind(q);
  670. if ((q->t_flags & PERSISTENT) ||
  671. rep == PLUS || rep == FIXED) {
  672. /*
  673. * In these cases, the term belongs to the
  674. * continuation grammar.
  675. * Otherwise, q->t_contains is just
  676. * q->t_first
  677. */
  678. if (!q->t_contains) {
  679. q->t_contains = get_set();
  680. }
  681. contains(q->t_rule,q->t_contains);
  682. if (rep != FIXED || empty(q->t_rule)) {
  683. setminus(q->t_contains,q->t_follow);
  684. }
  685. setunion(q->t_contains,q->t_first);
  686. } else {
  687. contains(q->t_rule, (p_set) 0);
  688. q->t_contains = q->t_first;
  689. }
  690. if (set) setunion(set,q->t_contains);
  691. break; }
  692. case NONTERM : {
  693. register p_nont n;
  694. n = &nonterms[g_getcont(p)];
  695. do_contains(n);
  696. if (set) {
  697. setunion(set, n->n_contains);
  698. if (ntneeded) NTPUTIN(set, g_getcont(p));
  699. }
  700. break; }
  701. case ALTERNATION : {
  702. register p_link l;
  703. l = g_getlink(p);
  704. contains(l->l_rule,
  705. (l->l_flag & DEF) ? set : (p_set) 0);
  706. break; }
  707. case LITERAL :
  708. case TERMINAL : {
  709. register hulp;
  710. if (set) {
  711. hulp = g_getcont(p);
  712. assert(hulp < ntokens);
  713. PUTIN(set,hulp);
  714. }}
  715. }
  716. p++;
  717. }
  718. }
  719. STATIC int nsafes(p) register p_nont p; {
  720. int ch;
  721. register int i;
  722. ch = 0;
  723. i = getntsafe(p);
  724. if (i != NOSAFETY) {
  725. i = do_safes(p->n_rule, i, &ch);
  726. if (i < SCANDONE) i = SCANDONE;
  727. /* After a nonterminal, we only know whether a scan was done
  728. or not
  729. */
  730. if (getntout(p) != i) {
  731. ch = 1;
  732. setntout(p,i);
  733. }
  734. }
  735. return ch;
  736. }
  737. STATIC int
  738. do_safes(p,safe,ch) register p_gram p; register int *ch; {
  739. /*
  740. * Walk the grammar rule, doing the computation described in the
  741. * comment of the procedure above this one.
  742. */
  743. int retval;
  744. for (;;) {
  745. switch (g_gettype(p)) {
  746. case ACTION:
  747. p++;
  748. continue;
  749. case LITERAL:
  750. case TERMINAL:
  751. safe = NOSCANDONE;
  752. break;
  753. case TERM : {
  754. register p_term q;
  755. int i,rep;
  756. q = g_getterm(p);
  757. i = r_getnum(q);
  758. rep = r_getkind(q);
  759. retval = do_safes(q->t_rule,
  760. t_safety(rep,i,q->t_flags&PERSISTENT,safe),ch);
  761. settout(q, retval);
  762. safe = t_after(rep, i, retval);
  763. break; }
  764. case ALTERNATION : {
  765. register p_link l;
  766. register int i;
  767. retval = -1;
  768. while (g_gettype(p) == ALTERNATION) {
  769. l = g_getlink(p);
  770. if (safe > SAFE && (l->l_flag & DEF)) {
  771. i = do_safes(l->l_rule,SAFESCANDONE,ch);
  772. }
  773. else i = do_safes(l->l_rule,SAFE,ch);
  774. if (retval == -1) retval = i;
  775. else if (i != retval) {
  776. if (i == NOSCANDONE ||
  777. retval == NOSCANDONE) {
  778. retval = SCANDONE;
  779. }
  780. else if (i > retval) retval = i;
  781. }
  782. p++;
  783. }
  784. return retval; }
  785. case NONTERM : {
  786. register p_nont n;
  787. register int nsafe, osafe;
  788. n = &nonterms[g_getcont(p)];
  789. nsafe = getntsafe(n);
  790. osafe = safe;
  791. safe = getntout(n);
  792. if (safe == NOSAFETY) safe = SCANDONE;
  793. if (osafe == nsafe) break;
  794. if (nsafe == NOSAFETY) {
  795. *ch = 1;
  796. setntsafe(n, osafe);
  797. break;
  798. }
  799. if (osafe == NOSCANDONE || nsafe == NOSCANDONE) {
  800. if (nsafe != SCANDONE) {
  801. *ch = 1;
  802. setntsafe(n, SCANDONE);
  803. }
  804. break;
  805. }
  806. if (osafe > nsafe) {
  807. setntsafe(n, osafe);
  808. *ch = 1;
  809. }
  810. break; }
  811. case EORULE :
  812. return safe;
  813. }
  814. p++;
  815. }
  816. }
  817. t_safety(rep, count, persistent, safety) {
  818. if (safety == NOSCANDONE) safety = SCANDONE;
  819. switch(rep) {
  820. default:
  821. assert(0);
  822. case OPT:
  823. if (!persistent || safety < SAFESCANDONE) return SAFE;
  824. return SAFESCANDONE;
  825. case STAR:
  826. if (persistent) return SAFESCANDONE;
  827. return SAFE;
  828. case PLUS:
  829. if (persistent) {
  830. if (safety > SAFESCANDONE) return safety;
  831. return SAFESCANDONE;
  832. }
  833. return safety;
  834. case FIXED:
  835. if (!count) return safety;
  836. return SCANDONE;
  837. }
  838. /* NOTREACHED */
  839. }
  840. t_after(rep, count, outsafety) {
  841. if (count == 0 && (rep == STAR || rep == PLUS)) {
  842. return SAFESCANDONE;
  843. }
  844. if (rep != FIXED) {
  845. if (outsafety <= SAFESCANDONE) return SAFESCANDONE;
  846. return SCANDONE;
  847. }
  848. return outsafety;
  849. }