LLgen.g 13 KB

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