savegram.c 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385
  1. /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
  2. * All rights reserved.
  3. */
  4. #ifdef NON_CORRECTING
  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. * savegram.c
  14. * Save the input grammar for non-correcting error recovery
  15. *
  16. * Grammar rules are `flattened' by introducing anonymous nonterminals.
  17. * [B]? becomes X; X: B | {empty}
  18. * [B]+ becomes X: B Y; Y: X | {empty}
  19. * [B]* becomes X; X: B X | {empty}
  20. * [B | C] becomes X; X: B | C
  21. * [B | C]* becomes X; X: B X | C X | {empty} etc.
  22. */
  23. # include "types.h"
  24. # include "extern.h"
  25. # include "io.h"
  26. # include "assert.h"
  27. # include "sets.h"
  28. #define LLALT 9999
  29. static int nt_highest;
  30. extern int nbytes;
  31. extern p_mem alloc();
  32. extern p_set start_firsts;
  33. extern p_set setalloc();
  34. extern p_gram search();
  35. STATIC save_rule();
  36. STATIC save_set();
  37. /* t_list will contain terms to be `flattened' */
  38. static struct t_list {
  39. p_term term;
  40. int t_nt_num;
  41. } *t_list;
  42. /* Subparse list will contain symbols in %substart */
  43. static struct subparse_list {
  44. p_gram sub_action;
  45. int sub_nt_num;
  46. } *sub_list;
  47. /* Index in t_list */
  48. static int t_list_index;
  49. /* Index in subparse_list */
  50. static int sub_list_index;
  51. /* File to save grammar to */
  52. static FILE *fgram;
  53. /* Nonterminal number to simulate parsers that get called in actions
  54. used when LLgen called with -n -s options */
  55. int act_nt;
  56. save_grammar(f) FILE *f; {
  57. /*
  58. * Save the grammar
  59. */
  60. register p_nont p;
  61. register p_start st;
  62. register int nt_nr;
  63. fgram = f;
  64. /* Compute highest nonterminal nr. */
  65. nt_highest = nnonterms + assval - 1;
  66. /* Generate some constants in the grammar file */
  67. /* Allocate terms list */
  68. t_list = (struct t_list *) alloc((unsigned) nterms * sizeof(struct t_list));
  69. t_list_index = 0;
  70. sub_list = (struct subparse_list *) alloc(nsubstarts * sizeof(struct subparse_list));
  71. fputs("static ", fgram);
  72. fputs((prefix ? prefix : "LL"), fgram);
  73. fputs("grammar[] = {\n", fgram);
  74. /* Check if -n -s option is on */
  75. if (subpars_sim) {
  76. /* Allocate action simulation nt */
  77. act_nt = ++nt_highest;
  78. /* write simualtion rule */
  79. fprintf(fgram, "/* Simulation rule */\n");
  80. fprintf(fgram, "%d,\n", act_nt);
  81. /* Put a firstset and a fake followset */
  82. /* Followset optimization is not implemented for
  83. -s because it would be hard, and does not
  84. bring enough improvement to jutify the effort
  85. */
  86. save_set(start_firsts);
  87. save_set(start_firsts);
  88. /* Simulation rule procudes empty */
  89. fprintf(fgram, "%d,\n", 1);
  90. for (st = start; st; st = st->ff_next)
  91. {
  92. fprintf(fgram, "%d, %d, %d, \n", st->ff_nont + assval,
  93. act_nt, LLALT);
  94. }
  95. fprintf(fgram, "%d, \n", 0);
  96. }
  97. /* Now process all rules */
  98. for (p = nonterms, nt_nr = assval; p < maxnt; p++, nt_nr++) {
  99. fprintf(fgram, "/* nr. %d %s */\n", nt_nr, p->n_name);
  100. fprintf(fgram, "%d, ",nt_nr);
  101. if (! p->n_rule) { /* undefined */
  102. f_input = p->n_string;
  103. error(p->n_lineno,"Nonterminal %s not defined",
  104. p->n_name);
  105. }
  106. /* Save the first_set and follow set */
  107. save_set(p->n_nc_first);
  108. save_set(p->n_nc_follow);
  109. if (p->n_flags & EMPTY)
  110. fprintf(fgram, "%d,\n", 1);
  111. else
  112. fprintf(fgram, "%d,\n", 0);
  113. save_rule(p->n_rule, 0);
  114. fprintf(fgram, "%d,\n", 0);
  115. }
  116. /* Resolve terms, they are on t_list */
  117. fprintf(fgram, "/* Fresh nonterminals */\n");
  118. { int i;
  119. for (i = 0; i < t_list_index; i++)
  120. {
  121. /* Terms of the form [] without + ? * or number produce
  122. a NIL pointer in the term-list */
  123. if ((t_list + i)->term == (struct term *) 0) {
  124. continue;
  125. }
  126. fprintf(fgram, "%d, ", (t_list + i)->t_nt_num);
  127. /* Save the first and follow sets */
  128. save_set((t_list + i)->term->t_nc_first);
  129. save_set((t_list + i)->term->t_nc_follow);
  130. /* NOTE: A VARIABLE REPETITION COUNT TERMS RULE IS NOT
  131. ALLOWED TO PRODUCE EMPTY IN LLGEN
  132. */
  133. switch(r_getkind((t_list + i)->term)) {
  134. case FIXED:
  135. /* Already done by repeating new nonterminal */
  136. /* FIXED term-rule may produce empty */
  137. if (empty((t_list +i)->term->t_rule))
  138. fprintf(fgram, "%d,\n", 1);
  139. else
  140. fprintf(fgram, "%d,\n", 0);
  141. save_rule((t_list + i)->term->t_rule, 0);
  142. fprintf(fgram, "%d,\n", 0);
  143. break;
  144. case STAR:
  145. /* Save the rule, appending the new lhs for this rule */
  146. /* Star rules always produce empty */
  147. fprintf(fgram, "1,\n");
  148. save_rule((t_list + i)->term->t_rule,
  149. (t_list + i)->t_nt_num);
  150. fprintf(fgram, "%d,\n%d,\n", LLALT, 0);
  151. /* ALT EMPTY*/
  152. break;
  153. case PLUS:
  154. /* Save the rule appending a fresh nonterminal */
  155. fprintf(fgram, "%d,\n", 0);
  156. save_rule((t_list + i)->term->t_rule, ++nt_highest);
  157. fprintf(fgram, "%d,\n", 0); /* EOR */
  158. fprintf(fgram, "%d, ", nt_highest);
  159. /* First set of the extra nonterm is same as
  160. for the term */
  161. /* Except that the new nonterm also produces empty ! */
  162. save_set((t_list + i)->term->t_nc_first);
  163. save_set((t_list + i)->term->t_nc_follow);
  164. fprintf(fgram, "1,\n");
  165. fprintf(fgram, "%d, ", (t_list+i)->t_nt_num);
  166. fprintf(fgram, "%d,\n%d,\n", LLALT, 0); /* ALT EMPTY */
  167. break;
  168. case OPT:
  169. fprintf(fgram, "1,\n");
  170. save_rule((t_list + i)->term->t_rule, 0);
  171. fprintf(fgram, "%d,\n%d,\n", LLALT, 0); /* ALT EMPTY */
  172. break;
  173. }
  174. }
  175. }
  176. /* Resolve %substarts */
  177. if (!subpars_sim) {
  178. int i,s,check;
  179. p_start ff, gg;
  180. p_set temp_set;
  181. for (i = 0; i < sub_list_index; i++) {
  182. fprintf(fgram, "%d, ", (sub_list + i)->sub_nt_num);
  183. /* Compute the first set */
  184. temp_set = setalloc();
  185. for (ff = g_getsubparse((sub_list + i)->sub_action);
  186. ff; ff = ff->ff_next){
  187. s = setunion(temp_set,
  188. (&nonterms[ff->ff_nont])->n_first);
  189. check = 0;
  190. for (gg =start; gg; gg = gg->ff_next)
  191. if (ff->ff_nont == gg->ff_nont)
  192. check = 1;
  193. if (check == 0)
  194. warning((sub_list + i)->sub_action->g_lineno,
  195. "\"%s\" is not a startsymbol",
  196. (&nonterms[ff->ff_nont])->n_name);
  197. }
  198. save_set(temp_set);
  199. save_set(temp_set);
  200. free(temp_set);
  201. /* Produces empty */
  202. fprintf(fgram, "1,\n");
  203. ff = g_getsubparse((sub_list + i)->sub_action);
  204. for (; ff; ff = ff->ff_next)
  205. fprintf(fgram, "%d, %d, %d, \n", ff->ff_nont + assval,
  206. (sub_list + i)->sub_nt_num,
  207. LLALT);
  208. fprintf(fgram, "%d, \n", 0);
  209. }
  210. }
  211. fprintf(fgram, "%d\n};\n", 0);
  212. fprintf(fgram, "#define LLNNONTERMINALS %d\n", nt_highest - assval + 1);
  213. }
  214. STATIC
  215. save_rule(p, tail) register p_gram p; int tail; {
  216. /*
  217. Walk through rule p, saving it. The non-terminal tail is
  218. appended to the rule. It needs to be appended in this function
  219. to process alt-rules correctly. Tail == 0 means don't append.
  220. */
  221. int in_alt;
  222. int illegal_num;
  223. /* Processing an alt needs some special care. When processing the
  224. first alternative, we don't want to write the alt-code;
  225. When appending something to the alt, it needs to be appended to
  226. every alternative and not at the end of the rule.
  227. */
  228. /* Look up the ILLEGAL token number */
  229. illegal_num = tokens[g_getcont(illegal_gram)].t_tokno;
  230. in_alt = 0;
  231. for (;;) {
  232. switch(g_gettype(p)) {
  233. case ALTERNATION :
  234. if (in_alt)
  235. fprintf(fgram, "%d,\n", LLALT);
  236. else
  237. in_alt = 1;
  238. save_rule(g_getlink(p)->l_rule, tail);
  239. break;
  240. case TERM :
  241. /* Make entry in term list */
  242. (t_list + t_list_index)->term = g_getterm(p);
  243. /* Test for [] without specifier */
  244. if (g_getterm(p) == (struct term *) 0) {
  245. t_list_index++;
  246. break;
  247. }
  248. (t_list + t_list_index++)->t_nt_num = ++nt_highest;
  249. fprintf(fgram, "%d, ", nt_highest);
  250. /* Check if repetition, if so handle here */
  251. if (r_getkind(g_getterm(p)) == FIXED)
  252. {
  253. int k;
  254. for (k = 1; k < r_getnum(g_getterm(p)); k++)
  255. fprintf(fgram, "%d, ", nt_highest);
  256. }
  257. break;
  258. case NONTERM :
  259. fprintf(fgram, "%d, ", g_getcont(p) + assval);
  260. break;
  261. case TERMINAL:
  262. if (g_getcont(p) == g_getcont(illegal_gram)) {
  263. /* %illegal. Ignore. */
  264. break;
  265. }
  266. if (p->g_erroneous)
  267. fprintf(fgram, "%d, ", illegal_num);
  268. else
  269. fprintf(fgram, "%d, ",
  270. tokens[g_getcont(p)].t_tokno);
  271. break;
  272. case LITERAL:
  273. if (p->g_erroneous)
  274. fprintf(fgram, "%d, ", illegal_num);
  275. else
  276. fprintf(fgram, "%d, ",
  277. tokens[g_getcont(p)].t_tokno);
  278. break;
  279. case ACTION:
  280. if (subpars_sim) {
  281. fprintf(fgram, "%d, ", act_nt);
  282. }
  283. else if (g_getsubparse(p)) {
  284. /* Allocate nonterminal that will simulate
  285. subparser
  286. */
  287. (sub_list + sub_list_index)->sub_nt_num =
  288. ++nt_highest;
  289. (sub_list + sub_list_index++)->sub_action = p;
  290. fprintf(fgram, "%d, ", nt_highest);
  291. }
  292. break;
  293. case EORULE :
  294. if ((! in_alt) && tail )
  295. /* If this rule is not an alt, append tail now.
  296. If it is an alt, the recursive call of this function
  297. has appended tail to each alternative
  298. */
  299. fprintf(fgram, "%d, ", tail);
  300. return;
  301. }
  302. p++;
  303. }
  304. }
  305. STATIC
  306. save_set(p) p_set p; {
  307. register int k;
  308. register unsigned i;
  309. int j;
  310. j = nbytes;
  311. for (;;) {
  312. i = (unsigned) *p++;
  313. for (k = 0; k < sizeof(int); k++) {
  314. fprintf(fgram,"0%o,",(int)(i & 0377));
  315. i >>= 8;
  316. if (--j == 0) {
  317. fputs("\n",fgram);
  318. return;
  319. }
  320. }
  321. }
  322. /* NOTREACHED */
  323. }
  324. #endif