LLgen.g 14 KB

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