LLgen.g 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665
  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. * LLgen.g
  14. * Defines the grammar of LLgen.
  15. * Some routines that build the internal structure are also included
  16. */
  17. {
  18. # include <stdlib.h>
  19. # include <string.h>
  20. # include "types.h"
  21. # include "io.h"
  22. # include "extern.h"
  23. # include "assert.h"
  24. # include "cclass.h"
  25. # ifndef NORCSID
  26. static string rcsid = "$Id$";
  27. # endif
  28. p_mem alloc(), ralloc();
  29. string store();
  30. p_gram search();
  31. long ftell();
  32. static int acount; /* count #of global actions */
  33. static p_term t_list;
  34. static int t_cnt;
  35. static p_gram alt_table;
  36. static int n_alts;
  37. static int max_alts;
  38. #define ALTINCR 32
  39. static p_gram rule_table;
  40. static int n_rules;
  41. static int max_rules;
  42. #define RULEINCR 32
  43. /* Here are defined : */
  44. STATIC newnorder();
  45. STATIC newtorder();
  46. STATIC mkalt();
  47. STATIC mkterm();
  48. STATIC p_gram copyrule();
  49. /* and of course LLparse() */
  50. STATIC
  51. newnorder(index) {
  52. static int porder;
  53. if (norder != -1) {
  54. nonterms[porder].n_next = index;
  55. }
  56. else norder = index;
  57. porder = index;
  58. nonterms[porder].n_next = -1;
  59. }
  60. STATIC
  61. newtorder(index) {
  62. static int porder;
  63. if (torder != -1) {
  64. tokens[porder].t_next = index;
  65. }
  66. else torder = index;
  67. porder = index;
  68. tokens[porder].t_next = -1;
  69. }
  70. p_init()
  71. {
  72. alt_table = (p_gram )alloc(ALTINCR*sizeof(t_gram));
  73. n_alts = 0;
  74. max_alts = ALTINCR;
  75. rule_table = (p_gram )alloc(RULEINCR*sizeof(t_gram));
  76. n_rules = 0;
  77. max_rules = RULEINCR;
  78. }
  79. }
  80. %start LLparse, spec;
  81. spec : { acount = 0; p_init(); }
  82. [ %persistent def ]*
  83. { /*
  84. * Put an endmarker in temporary file
  85. */
  86. putc('\0', fact);
  87. putc('\0', fact);
  88. free((p_mem) rule_table);
  89. free((p_mem) alt_table);
  90. }
  91. ;
  92. def { register string p; }
  93. : rule
  94. /*
  95. * A grammar rule
  96. */
  97. | C_TOKEN listel [ ',' listel ]* ';'
  98. /*
  99. * A token declaration
  100. */
  101. | C_START C_IDENT
  102. { p = store(lextoken.t_string); }
  103. ',' C_IDENT
  104. /*
  105. * A start symbol declaration
  106. */
  107. { /*
  108. * Put the declaration in the list
  109. * of start symbols
  110. */
  111. register p_gram temp;
  112. register p_start ff;
  113. temp = search(NONTERM,lextoken.t_string,BOTH);
  114. ff = (p_start) alloc(sizeof(t_start));
  115. ff->ff_nont = g_getcont(temp);
  116. ff->ff_name = p;
  117. ff->ff_next = start;
  118. start = ff;
  119. while (ff = ff->ff_next) {
  120. if (! strcmp(p, ff->ff_name)) {
  121. error(linecount, "\"%s\" already used in a %%start", p);
  122. break;
  123. }
  124. }
  125. }
  126. ';'
  127. | C_LEXICAL C_IDENT
  128. /*
  129. * Declaration of a name for the lexical analyser.
  130. * May appear only once
  131. */
  132. { if (!lexical) {
  133. lexical = store(lextoken.t_string);
  134. }
  135. else error(linecount,"Duplicate %%lexical");
  136. }
  137. ';'
  138. | C_PREFIX C_IDENT
  139. /*
  140. * Prefix of external names (default: LL)
  141. */
  142. { if (!prefix) {
  143. prefix = store(lextoken.t_string);
  144. if (strlen(prefix) > 6) {
  145. error(linecount,
  146. "%%prefix too long");
  147. prefix[6] = 0;
  148. }
  149. }
  150. else error(linecount,"Duplicate %%prefix");
  151. }
  152. ';'
  153. | C_ONERROR C_IDENT
  154. {
  155. #ifdef NON_CORRECTING
  156. if (non_corr) {
  157. warning(linecount, "%%onerror conflicts with -n option");
  158. }
  159. else
  160. #endif
  161. if (! onerror) {
  162. onerror = store(lextoken.t_string);
  163. }
  164. else error(linecount,"Duplicate %%onerror");
  165. }
  166. ';'
  167. | C_ACTION { acount++; }
  168. /*
  169. * A global C-declaration
  170. */
  171. | firsts
  172. /*
  173. * declarations for macros
  174. */
  175. ;
  176. listel : C_IDENT { p_gram temp = search(TERMINAL,lextoken.t_string,ENTERING);
  177. newtorder(g_getcont(temp));
  178. tokens[g_getcont(temp)].t_lineno = linecount;
  179. }
  180. ;
  181. rule { register p_nont p;
  182. p_gram rr;
  183. register p_gram temp;
  184. }
  185. : /*
  186. * grammar for a production rule
  187. */
  188. C_IDENT { temp = search(NONTERM,lextoken.t_string,BOTH);
  189. p = &nonterms[g_getcont(temp)];
  190. if (p->n_rule) {
  191. error(linecount,
  192. "Nonterminal %s already defined", lextoken.t_string);
  193. }
  194. /*
  195. * Remember the order in which the nonterminals
  196. * were defined. Code must be generated in that
  197. * order to keep track with the actions on the
  198. * temporary file
  199. */
  200. newnorder(p - nonterms);
  201. p->n_count = acount;
  202. acount = 0;
  203. p->n_lineno = linecount;
  204. p->n_off = ftell(fact);
  205. }
  206. [ C_PARAMS { if (lextoken.t_num > 0) {
  207. p->n_flags |= PARAMS;
  208. if (lextoken.t_num > 15) {
  209. error(linecount,"Too many parameters");
  210. }
  211. else setntparams(p,lextoken.t_num);
  212. }
  213. }
  214. ]?
  215. [ C_ACTION { p->n_flags |= LOCALS; }
  216. ]?
  217. ':' { in_production = 1; }
  218. productions(&rr) ';'
  219. { in_production = 0; }
  220. /*
  221. * Do not use p->n_rule now! The nonterms array
  222. * might have been re-allocated.
  223. */
  224. { nonterms[g_getcont(temp)].n_rule = rr;}
  225. ;
  226. productions(p_gram *p;)
  227. /*
  228. * One or more alternatives
  229. */
  230. { p_gram prod;
  231. int conflres = 0;
  232. int t = 0;
  233. int haddefault = 0;
  234. int altcnt = 0;
  235. int o_lc, n_lc;
  236. } :
  237. { o_lc = linecount; }
  238. simpleproduction(p,&conflres)
  239. { if (conflres & DEF) haddefault = 1; }
  240. [
  241. [ '|' { n_lc = linecount; }
  242. simpleproduction(&prod,&t)
  243. { if (n_alts >= max_alts-2) {
  244. alt_table = (p_gram ) ralloc(
  245. (p_mem) alt_table,
  246. (unsigned)(max_alts+=ALTINCR)*sizeof(t_gram));
  247. }
  248. if (t & DEF) {
  249. if (haddefault) {
  250. error(n_lc,
  251. "More than one %%default in alternation");
  252. }
  253. haddefault = 1;
  254. }
  255. mkalt(*p,conflres,o_lc,&alt_table[n_alts++]);
  256. altcnt++;
  257. o_lc = n_lc;
  258. conflres = t;
  259. t = 0;
  260. *p = prod;
  261. }
  262. ]+ { if (conflres & (COND|PREFERING|AVOIDING)) {
  263. error(n_lc,
  264. "Resolver on last alternative not allowed");
  265. }
  266. mkalt(*p,conflres,n_lc,&alt_table[n_alts++]);
  267. altcnt++;
  268. g_settype((&alt_table[n_alts]),EORULE);
  269. *p = copyrule(&alt_table[n_alts-altcnt],altcnt+1);
  270. }
  271. |
  272. { if (conflres & (COND|PREFERING|AVOIDING)) {
  273. error(o_lc,
  274. "No alternation conflict resolver allowed here");
  275. }
  276. /*
  277. if (conflres & DEF) {
  278. error(o_lc,
  279. "No %%default allowed here");
  280. }
  281. */
  282. }
  283. ]
  284. { n_alts -= altcnt; }
  285. ;
  286. {
  287. STATIC
  288. mkalt(prod,condition,lc,res) p_gram prod; register p_gram res; {
  289. /*
  290. * Create an alternation and initialise it.
  291. */
  292. register p_link l;
  293. static p_link list;
  294. static int cnt;
  295. if (! cnt) {
  296. cnt = 50;
  297. list = (p_link) alloc(50 * sizeof(t_link));
  298. }
  299. cnt--;
  300. l = list++;
  301. l->l_rule = prod;
  302. l->l_flag = condition;
  303. g_setlink(res,l);
  304. g_settype(res,ALTERNATION);
  305. res->g_lineno = lc;
  306. nalts++;
  307. }
  308. }
  309. simpleproduction(p_gram *p; register int *conflres;)
  310. { t_gram elem;
  311. int elmcnt = 0;
  312. int cnt, kind;
  313. int termdeleted = 0;
  314. } :
  315. [ C_DEFAULT { *conflres |= DEF; }
  316. ]?
  317. [
  318. /*
  319. * Optional conflict reslover
  320. */
  321. C_IF C_EXPR { *conflres |= COND; }
  322. | C_PREFER { *conflres |= PREFERING; }
  323. | C_AVOID { *conflres |= AVOIDING; }
  324. ]?
  325. [ C_ILLEGAL {
  326. #ifdef NON_CORRECTING
  327. if (n_rules >= max_rules-2) {
  328. rule_table = (p_gram) ralloc(
  329. (p_mem) rule_table,
  330. (unsigned)(max_rules+=RULEINCR)*sizeof(t_gram));
  331. }
  332. elmcnt++;
  333. rule_table[n_rules++] =
  334. *search(TERMINAL, "LLILLEGAL", BOTH);
  335. if (*conflres & DEF) {
  336. error(linecount, "%%illegal not allowed in %%default rule");
  337. }
  338. #endif
  339. }
  340. ]?
  341. [ %persistent elem(&elem)
  342. { if (n_rules >= max_rules-2) {
  343. rule_table = (p_gram) ralloc(
  344. (p_mem) rule_table,
  345. (unsigned)(max_rules+=RULEINCR)*sizeof(t_gram));
  346. }
  347. kind = FIXED;
  348. cnt = 0;
  349. }
  350. [ repeats(&kind, &cnt)
  351. { if (g_gettype(&elem) != TERM) {
  352. rule_table[n_rules] = elem;
  353. g_settype((&rule_table[n_rules+1]),EORULE);
  354. mkterm(copyrule(&rule_table[n_rules],2),
  355. 0,
  356. elem.g_lineno,
  357. &elem);
  358. }
  359. }
  360. |
  361. { if (g_gettype(&elem) == TERM) {
  362. register p_term q = g_getterm(&elem);
  363. if (! (q->t_flags & RESOLVER) &&
  364. g_gettype(q->t_rule) != ALTERNATION &&
  365. g_gettype(q->t_rule) != EORULE) {
  366. while (g_gettype(q->t_rule) != EORULE) {
  367. rule_table[n_rules++] = *q->t_rule++;
  368. elmcnt++;
  369. if (n_rules >= max_rules-2) {
  370. rule_table = (p_gram) ralloc(
  371. (p_mem) rule_table,
  372. (unsigned)(max_rules+=RULEINCR)*sizeof(t_gram));
  373. }
  374. }
  375. elem = *--(q->t_rule);
  376. n_rules--;
  377. elmcnt--;
  378. if (q == t_list - 1) {
  379. t_list--;
  380. nterms--;
  381. t_cnt++;
  382. }
  383. termdeleted = 1;
  384. }
  385. }
  386. }
  387. ] { if (!termdeleted && g_gettype(&elem) == TERM) {
  388. register p_term q;
  389. q = g_getterm(&elem);
  390. r_setkind(q,kind);
  391. r_setnum(q,cnt);
  392. if ((q->t_flags & RESOLVER) &&
  393. (kind == PLUS || kind == FIXED)) {
  394. error(linecount,
  395. "%%while not allowed in this term");
  396. }
  397. /*
  398. * A persistent fixed term is the same
  399. * as a non-persistent fixed term.
  400. * Should we complain?
  401. if ((q->t_flags & PERSISTENT) &&
  402. kind == FIXED) {
  403. error(linecount,
  404. "Illegal %%persistent");
  405. }
  406. */
  407. }
  408. termdeleted = 0;
  409. elmcnt++;
  410. rule_table[n_rules++] = elem;
  411. }
  412. ]* { register p_term q;
  413. g_settype((&rule_table[n_rules]),EORULE);
  414. *p = 0;
  415. n_rules -= elmcnt;
  416. if (g_gettype(&rule_table[n_rules]) == TERM &&
  417. elmcnt == 1) {
  418. q = g_getterm(&rule_table[n_rules]);
  419. if (r_getkind(q) == FIXED &&
  420. r_getnum(q) == 0) {
  421. *p = q->t_rule;
  422. }
  423. }
  424. if (!*p) *p = copyrule(&rule_table[n_rules],
  425. elmcnt+1);
  426. }
  427. ;
  428. {
  429. STATIC
  430. mkterm(prod,flags,lc,result) p_gram prod; register p_gram result; {
  431. /*
  432. * Create a term, initialise it and return
  433. * a grammar element containing it
  434. */
  435. register p_term q;
  436. if (! t_cnt) {
  437. t_cnt = 50;
  438. t_list = (p_term) alloc(50 * sizeof(t_term));
  439. }
  440. t_cnt--;
  441. q = t_list++;
  442. q->t_rule = prod;
  443. q->t_contains = 0;
  444. q->t_flags = flags;
  445. g_settype(result,TERM);
  446. g_setterm(result,q);
  447. result->g_lineno = lc;
  448. nterms++;
  449. }
  450. }
  451. elem (register p_gram pres;)
  452. { register int t = 0;
  453. p_gram p1;
  454. int ln;
  455. p_gram pe;
  456. #ifdef NON_CORRECTING
  457. int erroneous = 0;
  458. #endif
  459. } :
  460. '[' { ln = linecount; }
  461. [ C_WHILE C_EXPR { t |= RESOLVER; }
  462. ]?
  463. [ C_PERSISTENT { t |= PERSISTENT; }
  464. ]?
  465. productions(&p1)
  466. ']' {
  467. mkterm(p1,t,ln,pres);
  468. }
  469. |
  470. [ C_ERRONEOUS {
  471. #ifdef NON_CORRECTING
  472. erroneous = 1;
  473. #endif
  474. }
  475. ]?
  476. [
  477. C_IDENT { pe = search(UNKNOWN,lextoken.t_string,BOTH);
  478. *pres = *pe;
  479. #ifdef NON_CORRECTING
  480. if (erroneous) {
  481. if (g_gettype(pres) != TERMINAL){
  482. warning(linecount,
  483. "Erroneous only allowed on terminal");
  484. erroneous = 0;
  485. }
  486. else
  487. pres->g_erroneous = 1;
  488. }
  489. #endif
  490. }
  491. [ C_PARAMS { if (lextoken.t_num > 15) {
  492. error(linecount,"Too many parameters");
  493. } else g_setnpar(pres,lextoken.t_num);
  494. if (g_gettype(pres) == TERMINAL) {
  495. error(linecount,
  496. "Terminal with parameters");
  497. }
  498. }
  499. ]?
  500. | C_LITERAL { pe = search(LITERAL,lextoken.t_string,BOTH);
  501. *pres = *pe;
  502. #ifdef NON_CORRECTING
  503. if (erroneous)
  504. pres->g_erroneous = 1;
  505. #endif
  506. }
  507. ]
  508. | { g_settype(pres,ACTION);
  509. pres->g_lineno = linecount;
  510. #ifdef NON_CORRECTING
  511. g_setsubparse(pres, (p_start) 0);
  512. #endif
  513. }
  514. [ C_SUBSTART
  515. {
  516. #ifdef NON_CORRECTING
  517. nsubstarts++;
  518. #endif
  519. }
  520. C_IDENT
  521. {
  522. #ifdef NON_CORRECTING
  523. register p_gram temp;
  524. register p_start subp;
  525. temp = search(NONTERM,lextoken.t_string,BOTH);
  526. subp = (p_start) alloc (sizeof(t_start));
  527. subp->ff_nont = g_getcont(temp);
  528. subp->ff_name = (string) 0;
  529. subp->ff_next = (p_start) 0;
  530. g_setsubparse(pres, subp);
  531. #endif
  532. }
  533. [ ',' C_IDENT
  534. {
  535. #ifdef NON_CORRECTING
  536. register p_gram temp;
  537. register p_start ff;
  538. temp = search(NONTERM,lextoken.t_string,BOTH);
  539. ff = g_getsubparse(pres);
  540. while (ff) {
  541. if (ff->ff_nont == g_getcont(temp)) {
  542. warning(linecount, "\"%s\" used twice in %%substart", lextoken.t_string);
  543. break;
  544. }
  545. ff = ff->ff_next;
  546. }
  547. ff = (p_start) alloc(sizeof(t_start));
  548. ff->ff_nont = g_getcont(temp);
  549. ff->ff_name = (string) 0;
  550. ff->ff_next = g_getsubparse(pres);
  551. g_setsubparse(pres, ff);
  552. #endif
  553. }
  554. ]* ';'
  555. ]?
  556. C_ACTION
  557. ;
  558. repeats(int *kind; int *cnt;) { int t1 = 0; } :
  559. [
  560. '?' { *kind = OPT; }
  561. | [ '*' { *kind = STAR; }
  562. | '+' { *kind = PLUS; }
  563. ]
  564. number(&t1)?
  565. { if (t1 == 1) {
  566. t1 = 0;
  567. if (*kind == STAR) *kind = OPT;
  568. if (*kind == PLUS) *kind = FIXED;
  569. }
  570. }
  571. | number(&t1)
  572. ] { *cnt = t1; }
  573. ;
  574. number(int *t;)
  575. : C_NUMBER
  576. { *t = lextoken.t_num;
  577. if (*t <= 0 || *t >= 8192) {
  578. error(linecount,"Illegal number");
  579. }
  580. }
  581. ;
  582. firsts { register string p; }
  583. : C_FIRST C_IDENT
  584. { p = store(lextoken.t_string); }
  585. ',' C_IDENT ';'
  586. { /*
  587. * Store this %first in the list belonging
  588. * to this input file
  589. */
  590. p_gram temp;
  591. register p_first ff;
  592. temp = search(NONTERM,lextoken.t_string,BOTH);
  593. ff = (p_first) alloc(sizeof(t_first));
  594. ff->ff_nont = g_getcont(temp);
  595. ff->ff_name = p;
  596. ff->ff_next = pfile->f_firsts;
  597. pfile->f_firsts = ff;
  598. }
  599. ;
  600. {
  601. STATIC p_gram
  602. copyrule(p,length) register p_gram p; {
  603. /*
  604. * Returns a pointer to a grammar rule that was created in
  605. * p. The space pointed to by p can now be reused
  606. */
  607. register p_gram t;
  608. p_gram rule;
  609. t = (p_gram) alloc((unsigned) length * sizeof(t_gram));
  610. rule = t;
  611. while (length--) {
  612. *t++ = *p++;
  613. }
  614. return rule;
  615. }
  616. }