compute.c 23 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157
  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. #if 0
  532. static int nc_follow(p_set setp, p_gram p)
  533. {
  534. /*
  535. * setp is the follow set for the rule p.
  536. * Compute the follow sets in the rule p from this set.
  537. * Return 1 if a follow set of a nonterminal changed.
  538. */
  539. int s; /* Will gather return value */
  540. s = 0;
  541. for (;;) {
  542. switch (g_gettype(p)) {
  543. case EORULE :
  544. return s;
  545. case TERM : {
  546. p_term q;
  547. q = g_getterm(p);
  548. if (empty(p+1)) {
  549. /*
  550. * If what follows the term can be empty,
  551. * everything that can follow the whole
  552. * rule can also follow the term
  553. */
  554. s |= setunion(q->t_nc_follow,setp);
  555. }
  556. /*
  557. * Everything that can start the rest of the rule
  558. * can follow the term
  559. */
  560. s |= nc_first(q->t_nc_follow,p+1,1);
  561. if (r_getkind(q) == STAR ||
  562. r_getkind(q) == PLUS ||
  563. r_getnum(q) ) {
  564. /*
  565. * If the term involves a repetition
  566. * of possibly more than one,
  567. * everything that can start the term
  568. * can also follow it.
  569. */
  570. s |= nc_follow(q->t_nc_first,q->t_rule);
  571. }
  572. /*
  573. * Now propagate the set computed sofar
  574. */
  575. s |= nc_follow(q->t_nc_follow, q->t_rule);
  576. break; }
  577. case ALTERNATION :
  578. /*
  579. * Just propagate setp
  580. */
  581. s |= nc_follow(setp,g_getlink(p)->l_rule);
  582. break;
  583. case NONTERM : {
  584. p_nont n;
  585. n = &nonterms[g_getcont(p)];
  586. s |= nc_first(n->n_nc_follow,p+1,1);
  587. if (empty(p+1)) {
  588. /*
  589. * If the rest of p can produce empty,
  590. * everything that follows p can follow
  591. * the nonterminal
  592. */
  593. s |= setunion(n->n_nc_follow,setp);
  594. }
  595. break; }
  596. }
  597. p++;
  598. }
  599. }
  600. #endif
  601. #endif
  602. static void co_dirsymb(p_set setp, p_gram p)
  603. {
  604. /*
  605. * Walk the rule p, doing the work for alternations
  606. */
  607. p_gram s = 0;
  608. for (;;) {
  609. switch (g_gettype(p)) {
  610. case EORULE :
  611. return;
  612. case TERM : {
  613. p_term q;
  614. q = g_getterm(p);
  615. co_dirsymb(q->t_follow,q->t_rule);
  616. break; }
  617. case ALTERNATION : {
  618. p_link l;
  619. /*
  620. * Save first alternative
  621. */
  622. if (!s) s = p;
  623. l = g_getlink(p);
  624. co_dirsymb(setp,l->l_rule);
  625. if (empty(l->l_rule)) {
  626. /*
  627. * If the rule can produce empty, everything
  628. * that follows it can also start it
  629. */
  630. setunion(l->l_symbs,setp);
  631. }
  632. if (g_gettype(p+1) == EORULE) {
  633. /*
  634. * Every alternation is implemented as a
  635. * choice between two alternatives :
  636. * this one or one of the following.
  637. * The l_others set will contain the starters
  638. * of the other alternatives
  639. */
  640. co_others(s);
  641. return;
  642. } }
  643. }
  644. p++;
  645. }
  646. }
  647. static void co_others(p_gram p)
  648. {
  649. /*
  650. * compute the l_others-sets for the list of alternatives
  651. * indicated by p
  652. */
  653. p_link l1,l2;
  654. l1 = g_getlink(p);
  655. p++;
  656. l2 = g_getlink(p);
  657. setunion(l1->l_others,l2->l_symbs);
  658. if (g_gettype(p+1) != EORULE) {
  659. /*
  660. * First compute l2->l_others
  661. */
  662. co_others(p);
  663. /*
  664. * and then l1->l_others
  665. */
  666. setunion(l1->l_others,l2->l_others);
  667. }
  668. }
  669. static p_length length;
  670. # define INFINITY 32767
  671. static int ncomplength(p_nont p)
  672. {
  673. p_length pl = &length[p - nonterms];
  674. int x = pl->cnt;
  675. pl->cnt = -1;
  676. complength(p->n_rule, pl);
  677. return pl->cnt < INFINITY && x == INFINITY;
  678. }
  679. static void do_lengthcomp()
  680. {
  681. /*
  682. * Compute the minimum length of a terminal production for each
  683. * nonterminal.
  684. * This length consists of two fields: the number of terminals,
  685. * and a number that is composed of
  686. * - the number of this alternative
  687. * - a crude measure of the number of terms and nonterminals in the
  688. * production of this shortest string.
  689. */
  690. p_length pl;
  691. p_nont p;
  692. p_mem alloc();
  693. length = (p_length) alloc((unsigned) (nnonterms * sizeof(*length)));
  694. for (pl = &length[nnonterms-1]; pl >= length; pl--) {
  695. pl->val = pl->cnt = INFINITY;
  696. }
  697. co_trans(ncomplength);
  698. pl = length;
  699. for (p = nonterms; p < maxnt; p++, pl++) {
  700. if (pl->cnt == INFINITY) {
  701. p->n_flags |= RECURSIVE;
  702. }
  703. setdefaults(p->n_rule);
  704. }
  705. free ((p_mem) length);
  706. }
  707. static void complength(p_gram p, p_length le)
  708. {
  709. /*
  710. * Walk grammar rule p, computing minimum lengths
  711. */
  712. p_link l;
  713. p_term q;
  714. t_length i;
  715. t_length X;
  716. int cnt = 0;
  717. X.cnt = 0;
  718. X.val = 0;
  719. for (;;) {
  720. switch (g_gettype(p)) {
  721. case LITERAL :
  722. case TERMINAL :
  723. #ifdef NON_CORRECTING
  724. if (g_getcont(p) == g_getcont(illegal_gram)) {
  725. add(&X, INFINITY, 0);
  726. break;
  727. }
  728. #endif
  729. add(&X, 1, 0);
  730. break;
  731. case ALTERNATION :
  732. X.cnt = INFINITY;
  733. X.val = INFINITY;
  734. while (g_gettype(p) != EORULE) {
  735. cnt++;
  736. l = g_getlink(p);
  737. p++;
  738. complength(l->l_rule,&i);
  739. i.val += cnt;
  740. if (l->l_flag & DEF) {
  741. X = i;
  742. break;
  743. }
  744. if (compare(&i, &X) < 0) {
  745. X = i;
  746. }
  747. }
  748. /* Fall through */
  749. case EORULE :
  750. le->cnt = X.cnt;
  751. le->val = X.val;
  752. return;
  753. case TERM : {
  754. int rep;
  755. q = g_getterm(p);
  756. rep = r_getkind(q);
  757. X.val += 1;
  758. if ((q->t_flags&PERSISTENT) ||
  759. rep==FIXED || rep==PLUS) {
  760. complength(q->t_rule,&i);
  761. add(&X, i.cnt, i.val);
  762. if (rep == FIXED && r_getnum(q) > 0) {
  763. for (rep = r_getnum(q) - 1;
  764. rep > 0; rep--) {
  765. add(&X, i.cnt, i.val);
  766. }
  767. }
  768. }
  769. break; }
  770. case NONTERM : {
  771. int nn = g_getcont(p);
  772. p_length pl = &length[nn];
  773. int x = pl->cnt;
  774. if (x == INFINITY) {
  775. pl->cnt = -1;
  776. complength(nonterms[nn].n_rule,pl);
  777. x = pl->cnt;
  778. }
  779. else if (x == -1) x = INFINITY;
  780. add(&X, x, pl->val);
  781. X.val += 1;
  782. }
  783. }
  784. p++;
  785. }
  786. }
  787. static void add(p_length a, int c, int v)
  788. {
  789. if (a->cnt == INFINITY || c == INFINITY) {
  790. a->cnt = INFINITY;
  791. return;
  792. }
  793. a->val += v;
  794. a->cnt += c;
  795. }
  796. static int compare(p_length a, p_length b)
  797. {
  798. if (a->cnt != b->cnt) return a->cnt - b->cnt;
  799. return a->val - b->val;
  800. }
  801. static void setdefaults(p_gram p)
  802. {
  803. for (;;) {
  804. switch(g_gettype(p)) {
  805. case EORULE:
  806. return;
  807. case TERM:
  808. setdefaults(g_getterm(p)->t_rule);
  809. break;
  810. case ALTERNATION: {
  811. p_link l, l1;
  812. int temp = 0, temp1, cnt = 0;
  813. t_length count, i;
  814. count.cnt = INFINITY;
  815. count.val = INFINITY;
  816. l1 = g_getlink(p);
  817. do {
  818. cnt++;
  819. l = g_getlink(p);
  820. p++;
  821. complength(l->l_rule,&i);
  822. i.val += cnt;
  823. if (l->l_flag & DEF) temp = 1;
  824. temp1 = compare(&i, &count);
  825. if (temp1 < 0 ||
  826. (temp1 == 0 && l1->l_flag & AVOIDING)) {
  827. l1 = l;
  828. count = i;
  829. }
  830. setdefaults(l->l_rule);
  831. } while (g_gettype(p) != EORULE);
  832. if (!temp) {
  833. /* No user specified default */
  834. l1->l_flag |= DEF;
  835. }
  836. return; }
  837. }
  838. p++;
  839. }
  840. }
  841. static void do_contains(p_nont n)
  842. {
  843. /*
  844. * Compute the total set of symbols that nonterminal n can
  845. * produce
  846. */
  847. if (n->n_contains == 0) {
  848. n->n_contains = get_set();
  849. contains(n->n_rule,n->n_contains);
  850. /*
  851. * If the rule can produce empty, delete all symbols that
  852. * can follow the rule as well as be in the rule.
  853. * This is needed because the contains-set may only contain
  854. * symbols that are guaranteed to be eaten by the rule!
  855. * Otherwise, the generated parser may loop forever
  856. */
  857. if (n->n_flags & EMPTY) {
  858. setminus(n->n_contains,n->n_follow);
  859. }
  860. /*
  861. * But the symbols that can start the rule are always
  862. * eaten
  863. */
  864. setunion(n->n_contains,n->n_first);
  865. }
  866. }
  867. static void contains(p_gram p, p_set set)
  868. {
  869. /*
  870. * Does the real computation of the contains-sets
  871. */
  872. for (;;) {
  873. switch (g_gettype(p)) {
  874. case EORULE :
  875. return;
  876. case TERM : {
  877. p_term q;
  878. int rep;
  879. q = g_getterm(p);
  880. rep = r_getkind(q);
  881. if ((q->t_flags & PERSISTENT) ||
  882. rep == PLUS || rep == FIXED) {
  883. /*
  884. * In these cases, the term belongs to the
  885. * continuation grammar.
  886. * Otherwise, q->t_contains is just
  887. * q->t_first
  888. */
  889. if (!q->t_contains) {
  890. q->t_contains = get_set();
  891. }
  892. contains(q->t_rule,q->t_contains);
  893. if (rep != FIXED || empty(q->t_rule)) {
  894. setminus(q->t_contains,q->t_follow);
  895. }
  896. setunion(q->t_contains,q->t_first);
  897. } else {
  898. contains(q->t_rule, (p_set) 0);
  899. q->t_contains = q->t_first;
  900. }
  901. if (set) setunion(set,q->t_contains);
  902. break; }
  903. case NONTERM : {
  904. p_nont n;
  905. n = &nonterms[g_getcont(p)];
  906. do_contains(n);
  907. if (set) {
  908. setunion(set, n->n_contains);
  909. if (ntneeded) NTPUTIN(set, g_getcont(p));
  910. }
  911. break; }
  912. case ALTERNATION : {
  913. p_link l;
  914. l = g_getlink(p);
  915. contains(l->l_rule,
  916. (l->l_flag & DEF) ? set : (p_set) 0);
  917. break; }
  918. case LITERAL :
  919. case TERMINAL : {
  920. int hulp;
  921. if (set) {
  922. hulp = g_getcont(p);
  923. assert(hulp < ntokens);
  924. PUTIN(set,hulp);
  925. }}
  926. }
  927. p++;
  928. }
  929. }
  930. static int nsafes(p_nont p)
  931. {
  932. int ch;
  933. int i;
  934. ch = 0;
  935. i = getntsafe(p);
  936. if (i != NOSAFETY) {
  937. i = do_safes(p->n_rule, i, &ch);
  938. if (i < SCANDONE) i = SCANDONE;
  939. /* After a nonterminal, we only know whether a scan was done
  940. or not
  941. */
  942. if (getntout(p) != i) {
  943. ch = 1;
  944. setntout(p,i);
  945. }
  946. }
  947. return ch;
  948. }
  949. static int do_safes(p_gram p, int safe, int *ch)
  950. {
  951. /*
  952. * Walk the grammar rule, doing the computation described in the
  953. * comment of the procedure above this one.
  954. */
  955. int retval;
  956. for (;;) {
  957. switch (g_gettype(p)) {
  958. case ACTION:
  959. p++;
  960. continue;
  961. case LITERAL:
  962. case TERMINAL:
  963. safe = NOSCANDONE;
  964. break;
  965. case TERM : {
  966. p_term q;
  967. int i,rep;
  968. q = g_getterm(p);
  969. i = r_getnum(q);
  970. rep = r_getkind(q);
  971. retval = do_safes(q->t_rule,
  972. t_safety(rep,i,q->t_flags&PERSISTENT,safe),ch);
  973. settout(q, retval);
  974. safe = t_after(rep, i, retval);
  975. break; }
  976. case ALTERNATION : {
  977. p_link l;
  978. int i;
  979. retval = -1;
  980. while (g_gettype(p) == ALTERNATION) {
  981. l = g_getlink(p);
  982. p++;
  983. if (safe > SAFE && (l->l_flag & DEF)) {
  984. i = do_safes(l->l_rule,SAFESCANDONE,ch);
  985. }
  986. else i = do_safes(l->l_rule,SAFE,ch);
  987. if (retval == -1) retval = i;
  988. else if (i != retval) {
  989. if (i == NOSCANDONE ||
  990. retval == NOSCANDONE) {
  991. retval = SCANDONE;
  992. }
  993. else if (i > retval) retval = i;
  994. }
  995. }
  996. return retval; }
  997. case NONTERM : {
  998. p_nont n;
  999. int nsafe, osafe;
  1000. n = &nonterms[g_getcont(p)];
  1001. nsafe = getntsafe(n);
  1002. osafe = safe;
  1003. safe = getntout(n);
  1004. if (safe == NOSAFETY) safe = SCANDONE;
  1005. if (osafe == nsafe) break;
  1006. if (nsafe == NOSAFETY) {
  1007. *ch = 1;
  1008. setntsafe(n, osafe);
  1009. break;
  1010. }
  1011. if (osafe == NOSCANDONE || nsafe == NOSCANDONE) {
  1012. if (nsafe != SCANDONE) {
  1013. *ch = 1;
  1014. setntsafe(n, SCANDONE);
  1015. }
  1016. break;
  1017. }
  1018. if (osafe > nsafe) {
  1019. setntsafe(n, osafe);
  1020. *ch = 1;
  1021. }
  1022. break; }
  1023. case EORULE :
  1024. return safe;
  1025. }
  1026. p++;
  1027. }
  1028. }
  1029. int t_safety(int rep, int count, int persistent, int safety)
  1030. {
  1031. if (safety == NOSCANDONE) safety = SCANDONE;
  1032. switch(rep) {
  1033. default:
  1034. assert(0);
  1035. case OPT:
  1036. if (!persistent || safety < SAFESCANDONE) return SAFE;
  1037. return SAFESCANDONE;
  1038. case STAR:
  1039. if (persistent) return SAFESCANDONE;
  1040. return SAFE;
  1041. case PLUS:
  1042. if (persistent) {
  1043. if (safety > SAFESCANDONE) return safety;
  1044. return SAFESCANDONE;
  1045. }
  1046. return safety;
  1047. case FIXED:
  1048. if (!count) return safety;
  1049. return SCANDONE;
  1050. }
  1051. /* NOTREACHED */
  1052. }
  1053. int t_after(int rep, int count, int outsafety)
  1054. {
  1055. if (count == 0 && (rep == STAR || rep == PLUS)) {
  1056. return SAFESCANDONE;
  1057. }
  1058. if (rep != FIXED) {
  1059. if (outsafety <= SAFESCANDONE) return SAFESCANDONE;
  1060. return SCANDONE;
  1061. }
  1062. return outsafety;
  1063. }