gencode.c 29 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289
  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. * gencode.c
  14. * Defines the routine "gencode", which generates the parser
  15. * we wanted so badly.
  16. * This file is a mess, it should be cleaned up some time.
  17. */
  18. #include <stdlib.h>
  19. # include "types.h"
  20. # include "io.h"
  21. # include "extern.h"
  22. # include "sets.h"
  23. # include "assert.h"
  24. # include "cclass.h"
  25. #include "LLgen.h"
  26. /*
  27. * Some codechar *s used more than once
  28. */
  29. static char * c_arrend = "0 };\n";
  30. static char * c_close = "}\n";
  31. static char * c_break = "break;\n";
  32. static char * c_read = "LLread();\n";
  33. /* Some constants used for reading from the action file */
  34. # define ENDDECL 0400
  35. # define IDENT 0401
  36. static int nlabel; /* count for the generation of labels */
  37. static int firsts; /* are there any? */
  38. static int listcount;
  39. /* In this file the following routines are defined: */
  40. # define NOPOP -20000
  41. void doclose(FILE *f)
  42. {
  43. if (ferror(f) != 0) {
  44. fatal(0,"Write error on temporary", NULL, NULL);
  45. }
  46. fclose(f);
  47. }
  48. STATIC int *mk_tokenlist()
  49. {
  50. int i = ntokens;
  51. int *p = (int *)alloc((unsigned)(i * sizeof(int))) + i;
  52. while (i--) *--p = -1;
  53. return p;
  54. }
  55. STATIC void genhdr()
  56. {
  57. if (!firsts) fputs("#define LLNOFIRSTS\n", fpars);
  58. if (ansi_c) fputs("#define LL_ANSI_C 1\n", fpars);
  59. else {
  60. fputs("#if __STDC__ || __cplusplus\n#define LL_ANSI_C 1\n#endif\n", fpars);
  61. }
  62. #ifdef NON_CORRECTING
  63. if (non_corr) fputs("#define LL_NON_CORR 1\n", fpars);
  64. #endif
  65. fprintf(fpars, "#define LL_LEXI %s\n", lexical);
  66. copyfile(incl_file);
  67. }
  68. void gencode(int argc) {
  69. p_file p = files;
  70. /* Set up for code generation */
  71. if ((fact = fopen(f_temp,"r")) == NULL) {
  72. fatal(0,e_noopen,f_temp, NULL);
  73. }
  74. #ifdef NON_CORRECTING
  75. /* The non-correcting error recovery must be generated BEFORE
  76. parser code is generated!!!! In case of conflict resolvers,
  77. the code-generation process will delete conflicting symbols
  78. from first and followsets, making them UNUSABLE for the
  79. non-correcting error recovery code.
  80. */
  81. if (non_corr)
  82. genncrecovery();
  83. #endif
  84. /* For every source file .... */
  85. while (argc--) {
  86. /* Open temporary */
  87. f_input = p->f_name;
  88. opentemp(f_input);
  89. correct_prefix();
  90. /* generate code ... */
  91. generate(p);
  92. getaction(2);
  93. doclose(fpars);
  94. /* And install */
  95. install(genname(p->f_name),p->f_name);
  96. p++;
  97. }
  98. geninclude();
  99. genrecovery();
  100. fclose(fact);
  101. }
  102. STATIC void opentemp(char *str) {
  103. if ((fpars = fopen(f_pars,"w")) == NULL) {
  104. fatal(0,e_noopen,f_pars, NULL);
  105. }
  106. if (!str) str = ".";
  107. fprintf(fpars,LLgenid,str);
  108. }
  109. STATIC void geninclude() {
  110. p_token p;
  111. int maxno = 0;
  112. opentemp((char *) 0);
  113. for (p = tokens; p < maxt; p++) {
  114. if (p->t_tokno > maxno) maxno = p->t_tokno;
  115. if (p->t_tokno >= 0400) {
  116. fprintf(fpars,"#define %s %d\n",
  117. p->t_string,
  118. p->t_tokno);
  119. }
  120. }
  121. fprintf(fpars, "#define %s_MAXTOKNO %d\n", prefix ? prefix : "LL",
  122. maxno);
  123. #ifdef NON_CORRECTING
  124. if (non_corr) {
  125. fprintf(fpars, "#define %sNONCORR\n", prefix ? prefix : "LL");
  126. }
  127. #endif
  128. doclose(fpars);
  129. install(f_include, ".");
  130. }
  131. STATIC void genrecovery() {
  132. FILE *f;
  133. p_token t;
  134. int *q;
  135. p_nont p;
  136. p_set *psetl;
  137. int *index;
  138. int i;
  139. p_start st;
  140. opentemp((char *) 0);
  141. f = fpars;
  142. correct_prefix();
  143. genhdr();
  144. for (st = start; st; st = st->ff_next) {
  145. /* Make sure that every set the parser needs is in the list
  146. * before generating a define of the number of them!
  147. */
  148. p = &nonterms[st->ff_nont];
  149. if (g_gettype(p->n_rule) == ALTERNATION) {
  150. findindex(p->n_contains);
  151. }
  152. }
  153. i = maxptr - setptr;
  154. fprintf(f,
  155. "#define LL_SSIZE %d\n#define LL_NSETS %d\n#define LL_NTERMINALS %d\n",
  156. nbytes,
  157. i > 0 ? i : 1,
  158. ntokens);
  159. if (onerror) fprintf(f,"#define LL_USERHOOK %s\n", onerror);
  160. #ifdef NON_CORRECTING
  161. if (non_corr) {
  162. fputs("static int nc_done = 0;\n", f);
  163. fputs("static int err_seen = 0;\n", f);
  164. }
  165. #endif
  166. /* Now generate the routines that call the startsymbols */
  167. fputs("#if LL_ANSI_C\n", f);
  168. for (st = start; st; st = st->ff_next) {
  169. p = &nonterms[st->ff_nont];
  170. fputs("void ", f);
  171. genextname(st->ff_nont, p->n_name, f);
  172. fputs("(void);\n", f);
  173. }
  174. fputs("#endif\n", f);
  175. for (st = start; st; st = st->ff_next) {
  176. fprintf(f, "#if LL_ANSI_C\nvoid %s(void)\n#else\n%s()\n#endif\n", st->ff_name, st->ff_name);
  177. p = &nonterms[st->ff_nont];
  178. fputs(" {\n\tunsigned int s[LL_NTERMINALS+LL_NSETS+2];", f);
  179. #ifdef NON_CORRECTING
  180. if (non_corr) {
  181. fputs(" \n\tint oldstartsymb;", f);
  182. fputs(" \n\tint oldncflag;", f);
  183. fputs(" \n\toldstartsymb = LLstartsymb;", f);
  184. fputs(" \n\toldncflag = nc_done;", f);
  185. fputs(" \n\tnc_done = 0;", f);
  186. fprintf(f, "\n\tLLstartsymb = %d;", st->ff_nont + assval);
  187. }
  188. #endif
  189. fputs("\n\tLLnewlevel(s);\n\tLLread();\n", f);
  190. if (g_gettype(p->n_rule) == ALTERNATION) {
  191. genpush(findindex(p->n_contains));
  192. }
  193. genextname(st->ff_nont, p->n_name, f);
  194. fputs("();\n", f);
  195. if (getntout(p) == NOSCANDONE) {
  196. fputs("\tLL_NOSCANDONE(EOFILE);\n",f);
  197. }
  198. else fputs("\tLL_SCANDONE(EOFILE);\n",f);
  199. fputs("\tLLoldlevel(s);\n",f);
  200. #ifdef NON_CORRECTING
  201. if (non_corr) {
  202. fputs("\tLLstartsymb = oldstartsymb;\n", f);
  203. fputs("\tif (nc_done == 1) { \n", f);
  204. fputs("\t\terr_seen = 1;\n", f);
  205. fputs("\tnc_done = oldncflag;\n", f);
  206. fputs("\t}\n", f);
  207. }
  208. #endif
  209. fputs("}\n", f);
  210. }
  211. /* Now generate the sets */
  212. fputs("static char LLsets[] = {\n",f);
  213. for (psetl = setptr; psetl < maxptr; psetl++) prset(*psetl);
  214. fputs(c_arrend, f);
  215. index = (int *) alloc((unsigned) (assval * sizeof(int)));
  216. for (q = index; q < &index[assval];) *q++ = -1;
  217. for (t = tokens; t < maxt; t++) {
  218. index[t->t_tokno] = t - tokens;
  219. }
  220. fputs("#define LLindex (LL_index+1)\nstatic short LL_index[] = {0,0,\n",f);
  221. for (q = index+1; q < &index[assval]; q++) {
  222. fprintf(f, "%d,\n", *q);
  223. }
  224. fputs(c_arrend, f);
  225. free((p_mem) index);
  226. if (onerror) {
  227. fputs("static short LLtok[] = {\n", f);
  228. for (t = tokens; t < maxt; t++) {
  229. fprintf(f, t->t_tokno<0400 ? "'%s',\n" : "%s,\n",t->t_string);
  230. }
  231. fputs(c_arrend, f);
  232. }
  233. fputs("#define LL_NEWMESS\n", f);
  234. copyfile(rec_file);
  235. doclose(f);
  236. install(f_rec, ".");
  237. }
  238. #ifdef NON_CORRECTING
  239. STATIC void genncrecovery() {
  240. FILE *f;
  241. p_token t;
  242. int *q;
  243. int *index;
  244. /* Generate the non-correcting error recovery file */
  245. opentemp((char *) 0);
  246. f = fpars;
  247. genhdr();
  248. correct_prefix();
  249. save_grammar(f);
  250. fprintf(f, "#define LLFIRST_NT %d\n", assval);
  251. fprintf(f, "#define LLSETSIZE %d\n", nbytes);
  252. index = (int *) alloc((unsigned) (assval * sizeof(int)));
  253. for (q = index; q < &index[assval];) *q++ = -1;
  254. for (t = tokens; t < maxt; t++) {
  255. index[t->t_tokno] = t - tokens;
  256. }
  257. fputs("#define LLindex (LL_index+1)\nstatic short LL_index[] = {0,0,\n",f);
  258. for (q = index+1; q < &index[assval]; q++) {
  259. fprintf(f, "%d,\n", *q);
  260. }
  261. fputs(c_arrend, f);
  262. free((p_mem) index);
  263. copyfile(nc_incl_file);
  264. copyfile(nc_rec_file);
  265. doclose(f);
  266. install(f_nc, ".");
  267. }
  268. #endif
  269. STATIC void generate(p_file f) {
  270. /*
  271. * Generates a parsing routine for every nonterminal
  272. */
  273. int s;
  274. p_nont p;
  275. int i;
  276. p_first ff;
  277. int mustpop;
  278. int is_first = 1;
  279. fprintf(fpars, "#define LL_LEXI %s\n", lexical);
  280. listcount = 0;
  281. /* Generate first sets */
  282. for (ff = f->f_firsts; ff; ff = ff->ff_next) {
  283. macro(ff->ff_name,&nonterms[ff->ff_nont]);
  284. }
  285. genhdr();
  286. /* For every nonterminal generate a function */
  287. for (s = f->f_nonterminals; s != -1; s = p->n_next) {
  288. p = &nonterms[s];
  289. /* Generate functions in the order in which the nonterminals
  290. * were defined in the grammar. This is important, because
  291. * of synchronisation with the action file
  292. */
  293. while (p->n_count--) getaction(1);
  294. if (g_gettype(p->n_rule) == EORULE &&
  295. getntparams(p) == 0) {
  296. continue;
  297. }
  298. if (is_first) genprototypes(f);
  299. is_first = 0;
  300. if (p->n_flags & GENSTATIC) fputs("static\n", fpars);
  301. fputs("#if LL_ANSI_C\nvoid\n#endif\n", fpars);
  302. genextname(s, p->n_name, fpars);
  303. if (p->n_flags & PARAMS) {
  304. long off = ftell(fact);
  305. fputs("(\n#if LL_ANSI_C\n", fpars);
  306. controlline();
  307. getansiparams(1);
  308. fseek(fact, off, 0);
  309. fputs("#else\n", fpars);
  310. controlline();
  311. getparams();
  312. fputs("#endif\n{\n", fpars);
  313. }
  314. else fputs("(\n#if LL_ANSI_C\nvoid\n#endif\n) {\n", fpars);
  315. if (p->n_flags & LOCALS) getaction(1);
  316. i = getntsafe(p);
  317. mustpop = NOPOP;
  318. if (g_gettype(p->n_rule) == ALTERNATION &&
  319. i > SAFESCANDONE) {
  320. mustpop = findindex(p->n_contains);
  321. if (i == NOSCANDONE) {
  322. fputs(c_read, fpars);
  323. i = SCANDONE;
  324. }
  325. }
  326. nlabel = 1;
  327. rulecode(p->n_rule,
  328. i,
  329. getntout(p) != NOSCANDONE,
  330. mustpop);
  331. fputs(c_close, fpars);
  332. }
  333. }
  334. STATIC void prset(p_set p) {
  335. int k;
  336. unsigned i;
  337. int j;
  338. j = nbytes;
  339. for (;;) {
  340. i = (unsigned) *p++;
  341. for (k = 0; k < sizeof(int); k++) {
  342. fprintf(fpars,"'\\%o',",(int)(i & 0377));
  343. i >>= 8;
  344. if (--j == 0) {
  345. fputs("\n",fpars);
  346. return;
  347. }
  348. }
  349. }
  350. /* NOTREACHED */
  351. }
  352. STATIC void macro(char * s, p_nont n) {
  353. int i;
  354. i = findindex(n->n_first);
  355. if (i < 0) {
  356. fprintf(fpars, "#define %s(x) ((x) == %d)\n",
  357. s,
  358. tokens[-(i+1)].t_tokno);
  359. return;
  360. }
  361. firsts = 1;
  362. fprintf(fpars,"#define %s(x) LLfirst((x), %d)\n", s, i);
  363. }
  364. STATIC void controlline() {
  365. /* Copy a compiler control line */
  366. int l;
  367. FILE *f1,*f2;
  368. f1 = fact; f2 = fpars;
  369. l = getc(f1);
  370. assert(l == '\0');
  371. do {
  372. l = getc(f1);
  373. if (l == EOF) fatal(0, "temp file mangled", NULL, NULL);
  374. putc(l,f2);
  375. } while ( l != '\n' ) ;
  376. }
  377. STATIC void getparams() {
  378. /* getparams is called if a nonterminal has parameters. The names
  379. * of the parameters have to be found, and they should be declared
  380. */
  381. long off;
  382. int l;
  383. long ftell();
  384. char first;
  385. char add_semi = ' ';
  386. first = ' ';
  387. /* save offset in file to be able to copy the declaration later */
  388. off = ftell(fact);
  389. /* First pass through declaration, find the parameter names */
  390. ltext[0] = '\0';
  391. while ((l = gettok()) != ENDDECL) {
  392. if ((l == ';' || l == ',') && ltext[0] != '\0') {
  393. /*
  394. * The last identifier found before a ';' or a ','
  395. * must be a parameter
  396. */
  397. fprintf(fpars,"%c%s", first, ltext);
  398. first = ',';
  399. ltext[0] = '\0';
  400. }
  401. }
  402. if (ltext[0] != '\0') {
  403. fprintf(fpars, "%c%s", first, ltext);
  404. add_semi = ';';
  405. }
  406. fputs(") ",fpars);
  407. /*
  408. * Now copy the declarations
  409. */
  410. l = getc(fact); /* patch: some implementations of fseek
  411. do not work properly after "ungetc"
  412. */
  413. fseek(fact,off,0);
  414. getaction(0);
  415. fprintf(fpars, "%c\n",add_semi);
  416. }
  417. STATIC void genprototypes(p_file f)
  418. {
  419. /*
  420. * Generate prototypes for all nonterminals
  421. */
  422. int i;
  423. p_nont p;
  424. long off = ftell(fact);
  425. fputs("#if LL_ANSI_C\n", fpars);
  426. for (i = 0; i < nnonterms; i++) {
  427. if (! IN(f->f_used, i)) continue;
  428. p = &nonterms[i];
  429. if (g_gettype(p->n_rule) == EORULE &&
  430. getntparams(p) == 0) {
  431. continue;
  432. }
  433. if (p->n_flags & GENSTATIC) fputs("static ", fpars);
  434. fputs("void ", fpars);
  435. genextname(i, p->n_name, fpars);
  436. if (p->n_flags & PARAMS) {
  437. fputs("(\n", fpars);
  438. fseek(fact, p->n_off, 0);
  439. controlline();
  440. getansiparams(0);
  441. }
  442. else fputs("(void);\n", fpars);
  443. }
  444. fseek(fact, off, 0);
  445. fputs("#else\n", fpars);
  446. for (i = 0; i < nnonterms; i++) {
  447. if (! IN(f->f_used, i)) continue;
  448. p = &nonterms[i];
  449. if (!(p->n_flags & GENSTATIC)) continue;
  450. if (g_gettype(p->n_rule) == EORULE &&
  451. getntparams(p) == 0) {
  452. continue;
  453. }
  454. fputs("static ", fpars);
  455. genextname(i, p->n_name, fpars);
  456. fputs("();\n", fpars);
  457. }
  458. fputs("#endif\n", fpars);
  459. }
  460. STATIC void getansiparams(int mkdef) {
  461. /* getansiparams is called if a nonterminal has parameters
  462. * and an ANSI C function definition/declaration has to be produced.
  463. * If a definition has to be produced, "mkdef" is set to 1.
  464. */
  465. int l;
  466. int delayed = 0;
  467. ltext[0] = '\0';
  468. while ((l = gettok()) != ENDDECL) {
  469. if (l > 0177 || c_class[l] != ISSPA) {
  470. if (delayed) {
  471. fputc(',', fpars);
  472. delayed = 0;
  473. }
  474. }
  475. if ((l == ';' || l == ',') && ltext[0] != '\0') {
  476. /*
  477. * The last identifier found before a ';' or a ','
  478. * must be a parameter
  479. */
  480. delayed = 1;
  481. ltext[0] = '\0';
  482. }
  483. else if (l == IDENT) fprintf(fpars, "%s", ltext);
  484. else fputc(l, fpars);
  485. }
  486. fprintf(fpars, ") %c\n", mkdef ? ' ' : ';');
  487. }
  488. STATIC int gettok() {
  489. /* Read from the action file. */
  490. int ch;
  491. char *c;
  492. FILE *f;
  493. f = fact;
  494. ch = getc(f);
  495. switch(ch) {
  496. case '\n':
  497. ch = getc(f);
  498. if (ch != EOF) {
  499. ungetc(ch,f);
  500. if (ch != '\0') return '\n';
  501. }
  502. return ENDDECL;
  503. case '\0':
  504. ungetc(ch,f);
  505. /* Fall through */
  506. case EOF :
  507. return ENDDECL;
  508. default :
  509. if (c_class[ch] == ISLET) {
  510. c = ltext;
  511. do {
  512. *c++ = ch;
  513. if (c-ltext >= LTEXTSZ) --c;
  514. ch = getc(f);
  515. } while (c_class[ch] == ISLET || c_class[ch] == ISDIG);
  516. if (ch != EOF) ungetc(ch,f);
  517. *c = '\0';
  518. return IDENT;
  519. }
  520. return ch;
  521. }
  522. }
  523. STATIC void rulecode(p_gram p, int safety, int mustscan, int mustpop) {
  524. /*
  525. * Code for a production rule.
  526. */
  527. int toplevel = 1;
  528. FILE *f;
  529. int *ppu;
  530. int *pushlist;
  531. int *ppushlist;
  532. /*
  533. * First generate code to push the contains sets of this rule
  534. * on a stack
  535. */
  536. ppushlist = dopush(p,safety,1, &pushlist);
  537. if (mustpop != NOPOP) for (ppu = pushlist; ppu < ppushlist; ppu++) {
  538. if (*ppu == mustpop) {
  539. *ppu = mustpop = NOPOP;
  540. break;
  541. }
  542. }
  543. if (g_gettype(p) != ALTERNATION) {
  544. genpop(mustpop);
  545. mustpop = NOPOP;
  546. }
  547. for (ppu = pushlist; ppu < ppushlist; ppu++) genpush(*ppu);
  548. free((p_mem) pushlist);
  549. f = fpars;
  550. for (;;) {
  551. switch (g_gettype(p)) {
  552. case EORULE :
  553. if (mustscan && safety == NOSCANDONE) {
  554. fputs(c_read,f);
  555. }
  556. return;
  557. case LITERAL :
  558. case TERMINAL : {
  559. p_token t;
  560. char * s;
  561. t = &tokens[g_getcont(p)];
  562. if (toplevel == 0) {
  563. fprintf(f,"LLtdecr(%d);\n", g_getcont(p));
  564. }
  565. if (safety == SAFE) {
  566. fputs("LL_SAFE(",f);
  567. }
  568. else if (safety == SAFESCANDONE) {
  569. fputs("LL_SSCANDONE(",f);
  570. }
  571. else if (safety == SCANDONE) {
  572. fputs("LL_SCANDONE(",f);
  573. }
  574. else /* if (safety == NOSCANDONE) */ {
  575. fputs("LL_NOSCANDONE(", f);
  576. }
  577. if (t->t_tokno < 0400) s = "'%s');\n";
  578. else s = "%s);\n";
  579. fprintf(f,s,t->t_string);
  580. if (safety <= SAFESCANDONE && toplevel > 0) {
  581. safety = NOSCANDONE;
  582. toplevel = -1;
  583. p++;
  584. continue;
  585. }
  586. safety = NOSCANDONE;
  587. break; }
  588. case NONTERM : {
  589. p_nont n = &nonterms[g_getcont(p)];
  590. if (safety == NOSCANDONE &&
  591. getntsafe(n) < NOSCANDONE) {
  592. safety = getntsafe(n);
  593. fputs(c_read, f);
  594. }
  595. if (toplevel == 0 &&
  596. (g_gettype(n->n_rule) != ALTERNATION ||
  597. getntsafe(n) <= SAFESCANDONE)) {
  598. genpop(findindex(n->n_contains));
  599. }
  600. genextname(g_getcont(p), n->n_name, f);
  601. if (g_getnpar(p)) {
  602. fputs("(\n", f);
  603. controlline();
  604. getaction(0);
  605. fputs(");\n",f);
  606. }
  607. else fputs("();\n", f);
  608. safety = getntout(n);
  609. break; }
  610. case TERM :
  611. safety = codeforterm(g_getterm(p),
  612. safety,
  613. toplevel);
  614. break;
  615. case ACTION :
  616. getaction(1);
  617. p++;
  618. continue;
  619. case ALTERNATION :
  620. alternation(p, safety, mustscan, mustpop, 0);
  621. return;
  622. }
  623. p++;
  624. toplevel = 0;
  625. }
  626. }
  627. STATIC void alternation(p_gram pp, int safety, int mustscan, int mustpop, int lb)
  628. {
  629. p_gram p = pp;
  630. FILE *f = fpars;
  631. p_link l;
  632. int hulp, hulp1,hulp2;
  633. int haddefault = 0;
  634. int nsafe;
  635. p_set set;
  636. p_set setalloc();
  637. int *tokenlist = mk_tokenlist();
  638. int casecnt = 0;
  639. int compacted;
  640. int unsafe;
  641. assert(safety < NOSCANDONE);
  642. hulp = nlabel++;
  643. hulp1 = nlabel++;
  644. hulp2 = nlabel++;
  645. if (!lb) lb = hulp1;
  646. unsafe = onerror || safety > SAFESCANDONE;
  647. if (!unsafe) {
  648. genpop(mustpop);
  649. mustpop = NOPOP;
  650. }
  651. if (unsafe && hulp1 == lb) {
  652. fprintf(f,"goto L_%d; /* so that the label is used for certain */\nL_%d: ;\n", hulp1, hulp1);
  653. }
  654. if (safety == SAFE) {
  655. /* check if we can avoid to generate the switch */
  656. for (;;) {
  657. if (g_gettype(p) == EORULE) return;
  658. l = g_getlink(p);
  659. if (l->l_flag & COND) break;
  660. if ((g_gettype(l->l_rule) != TERMINAL &&
  661. g_gettype(l->l_rule) != LITERAL) ||
  662. g_gettype(l->l_rule+1) != EORULE) break;
  663. p++;
  664. }
  665. p = pp;
  666. }
  667. while (g_gettype(p) != EORULE) {
  668. set = 0;
  669. l = g_getlink(p);
  670. if (l->l_flag & COND) {
  671. if (!(l->l_flag & NOCONF)) {
  672. set = setalloc();
  673. setunion(set, l->l_others);
  674. setintersect(set, l->l_symbs);
  675. setminus(l->l_symbs, set);
  676. setminus(l->l_others, set);
  677. add_cases(set, tokenlist, casecnt++);
  678. }
  679. }
  680. if (!unsafe && (l->l_flag & DEF)) {
  681. haddefault = 1;
  682. }
  683. else add_cases(l->l_symbs, tokenlist, casecnt++);
  684. if (l->l_flag & DEF) {
  685. haddefault = 1;
  686. }
  687. if ((l->l_flag & COND) && !(l->l_flag & NOCONF)) {
  688. p++;
  689. if (g_gettype(p+1) == EORULE) {
  690. setminus(g_getlink(p)->l_symbs, set);
  691. free((p_mem) set);
  692. continue;
  693. }
  694. free((p_mem) set);
  695. if (!haddefault) {
  696. }
  697. else {
  698. add_cases(l->l_others, tokenlist, casecnt++);
  699. unsafe = 0;
  700. }
  701. break;
  702. }
  703. p++;
  704. }
  705. unsafe = onerror || safety > SAFESCANDONE;
  706. p = pp;
  707. haddefault = 0;
  708. compacted = analyze_switch(tokenlist);
  709. if (compacted) {
  710. fputs("{", f);
  711. out_list(tokenlist, listcount++, casecnt);
  712. }
  713. else fputs("switch(LLcsymb) {\n", f);
  714. casecnt = 0;
  715. while (g_gettype(p) != EORULE) {
  716. l = g_getlink(p);
  717. if (l->l_flag & COND) {
  718. if (l->l_flag & NOCONF) {
  719. fputs("#ifdef ___NOCONFLICT___\n", f);
  720. }
  721. else gencases(tokenlist, casecnt++, compacted);
  722. controlline();
  723. fputs("if (!",f);
  724. getaction(0);
  725. fprintf(f,") goto L_%d;\n", hulp);
  726. if (l->l_flag & NOCONF) {
  727. fputs("#endif\n", f);
  728. }
  729. }
  730. if (!unsafe && (l->l_flag & DEF)) {
  731. haddefault = 1;
  732. fputs("default:\n", f);
  733. }
  734. else gencases(tokenlist, casecnt++, compacted);
  735. nsafe = SAFE;
  736. if (l->l_flag & DEF) {
  737. if (unsafe) {
  738. fprintf(f,"goto L_%d;\nL_%d: ;\n", hulp2, hulp2);
  739. }
  740. if (safety != SAFE) nsafe = SAFESCANDONE;
  741. }
  742. rulecode(l->l_rule, nsafe, mustscan, mustpop);
  743. fputs(c_break,f);
  744. if (unsafe && (l->l_flag & DEF)) {
  745. haddefault = 1;
  746. fprintf(f,
  747. "default: if (LLskip()) goto L_%d;\ngoto L_%d;\n",
  748. lb, hulp2);
  749. }
  750. if ((l->l_flag & COND) && !(l->l_flag & NOCONF)) {
  751. p++;
  752. fprintf(f,"goto L_%d;\nL_%d : ;\n", hulp, hulp);
  753. if (g_gettype(p+1) == EORULE) {
  754. continue;
  755. }
  756. if (!haddefault) {
  757. fputs("default:\n", f);
  758. }
  759. else {
  760. gencases(tokenlist, casecnt++, compacted);
  761. safety = SAFE;
  762. unsafe = 0;
  763. }
  764. if (! unsafe) {
  765. genpop(mustpop);
  766. mustpop = NOPOP;
  767. }
  768. alternation(p,safety,mustscan,mustpop,lb);
  769. break;
  770. }
  771. p++;
  772. }
  773. if (compacted) fputs(c_close, f);
  774. fputs(c_close, f);
  775. free((p_mem) tokenlist);
  776. }
  777. STATIC int *
  778. dopush(p,safety,toplevel,pp) p_gram p; int **pp; {
  779. /*
  780. * The safety only matters if toplevel != 0
  781. */
  782. unsigned int i = 100;
  783. int *ip = (int *) alloc(100 * sizeof(int));
  784. *pp = ip;
  785. for (;;) {
  786. if (ip - *pp >= i) {
  787. *pp = (int *)
  788. ralloc((p_mem) (*pp), (i + 100) * sizeof(int));
  789. ip = *pp + i;
  790. i += 100;
  791. }
  792. switch(g_gettype(p)) {
  793. case EORULE :
  794. case ALTERNATION :
  795. return ip;
  796. case TERM : {
  797. p_term q;
  798. int rep_kind, rep_count;
  799. q = g_getterm(p);
  800. rep_kind = r_getkind(q);
  801. rep_count = r_getnum(q);
  802. if (!(toplevel > 0 && safety <= SAFESCANDONE &&
  803. (rep_kind == OPT || (rep_kind == FIXED && rep_count == 0)))) {
  804. *ip++ = findindex(q->t_contains);
  805. }
  806. break; }
  807. case LITERAL :
  808. case TERMINAL :
  809. if (toplevel > 0 && safety <= SAFESCANDONE) {
  810. toplevel = -1;
  811. p++;
  812. safety = NOSCANDONE;
  813. continue;
  814. }
  815. if (toplevel == 0) *ip++ = -(g_getcont(p)+1);
  816. break;
  817. case NONTERM : {
  818. p_nont n;
  819. n = &nonterms[g_getcont(p)];
  820. if (toplevel == 0 ||
  821. (g_gettype(n->n_rule) == ALTERNATION &&
  822. getntsafe(n) > SAFESCANDONE)) {
  823. *ip++ = findindex(n->n_contains);
  824. }
  825. break; }
  826. case ACTION :
  827. p++;
  828. continue;
  829. }
  830. toplevel = 0;
  831. safety = NOSCANDONE;
  832. p++;
  833. }
  834. }
  835. # define max(a,b) ((a) < (b) ? (b) : (a))
  836. STATIC void getaction(int flag) {
  837. /* Read an action from the action file.
  838. * flag = 1 if it is an action,
  839. * 0 when reading parameters
  840. */
  841. int ch;
  842. FILE *f;
  843. int mark = 0;
  844. if (flag == 1) {
  845. controlline();
  846. }
  847. f = fpars;
  848. for (;;) {
  849. ch = gettok();
  850. switch(ch) {
  851. case ENDDECL:
  852. if (flag != 2) break;
  853. ch = getc(fact);
  854. assert(ch == '\0');
  855. fputs("\n",f);
  856. if (mark) return;
  857. mark = 1;
  858. continue;
  859. case IDENT :
  860. fputs(ltext,f);
  861. continue;
  862. }
  863. mark = 0;
  864. if (ch == ENDDECL) break;
  865. putc(ch,f);
  866. }
  867. if (flag) fputs("\n",f);
  868. }
  869. STATIC int codeforterm(p_term q, int safety, int toplevel) {
  870. /*
  871. * Generate code for a term
  872. */
  873. FILE *f = fpars;
  874. int rep_count = r_getnum(q);
  875. int rep_kind = r_getkind(q);
  876. int term_is_persistent = (q->t_flags & PERSISTENT);
  877. int ispushed = NOPOP;
  878. if (!(toplevel > 0 &&
  879. (safety == 0 || (!onerror && safety <= SAFESCANDONE)) &&
  880. (rep_kind == OPT || (rep_kind == FIXED && rep_count == 0)))) {
  881. ispushed = findindex(q->t_contains);
  882. }
  883. if (safety == NOSCANDONE && (rep_kind != FIXED || rep_count == 0 ||
  884. gettout(q) != NOSCANDONE)) {
  885. fputs(c_read, f);
  886. safety = SCANDONE;
  887. }
  888. if (rep_kind == PLUS && !term_is_persistent) {
  889. int temp;
  890. temp = findindex(q->t_first);
  891. if (temp != ispushed) {
  892. genpop(ispushed);
  893. ispushed = temp;
  894. genpush(temp);
  895. }
  896. }
  897. if (rep_count) {
  898. /* N > 0, so generate fixed forloop */
  899. fputs("{\nLL_i;\n", f);
  900. assert(ispushed != NOPOP);
  901. fprintf(f, "for (LL_i = %d; LL_i >= 0; LL_i--) {\n", rep_count - 1);
  902. if (rep_kind == FIXED) {
  903. fputs("if (!LL_i) ", f);
  904. genpop(ispushed);
  905. genpush(ispushed);
  906. if (safety == NOSCANDONE) {
  907. assert(gettout(q) == NOSCANDONE);
  908. fputs(c_read, f);
  909. }
  910. }
  911. }
  912. else if (rep_kind != OPT && rep_kind != FIXED) {
  913. /* '+' or '*', so generate infinite loop */
  914. fputs("for (;;) {\n",f);
  915. }
  916. else if (rep_kind == OPT &&
  917. (safety == 0 || (!onerror && safety <= SAFESCANDONE))) {
  918. genpop(ispushed);
  919. ispushed = NOPOP;
  920. }
  921. if (rep_kind == STAR || rep_kind == OPT) {
  922. genswhead(q, rep_kind, rep_count, safety, ispushed);
  923. }
  924. rulecode(q->t_rule,
  925. t_safety(rep_kind,rep_count,term_is_persistent,safety),
  926. gettout(q) != NOSCANDONE,
  927. rep_kind == FIXED ? ispushed : NOPOP);
  928. if (gettout(q) == NOSCANDONE && rep_kind != FIXED) {
  929. fputs(c_read, f);
  930. }
  931. /* in the case of '+', the if is after the code for the rule */
  932. if (rep_kind == PLUS) {
  933. if (rep_count) {
  934. fputs("if (!LL_i) break;\n", f);
  935. }
  936. genswhead(q, rep_kind, rep_count, safety, ispushed);
  937. }
  938. if (rep_kind != OPT && rep_kind != FIXED) fputs("continue;\n", f);
  939. if (rep_kind != FIXED) {
  940. fputs(c_close, f); /* Close switch */
  941. fputs(c_close, f);
  942. if (rep_kind != OPT) {
  943. genpop(ispushed);
  944. fputs(c_break, f);
  945. }
  946. }
  947. if (rep_kind != OPT && (rep_kind != FIXED || rep_count > 0)) {
  948. fputs(c_close, f); /* Close for */
  949. if (rep_count > 0) {
  950. fputs(c_close, f);/* Close ... */
  951. }
  952. }
  953. return t_after(rep_kind, rep_count, gettout(q));
  954. }
  955. STATIC void genswhead(p_term q, int rep_kind, int rep_count, int safety, int ispushed) {
  956. /*
  957. * Generate switch statement for term q
  958. */
  959. FILE *f = fpars;
  960. p_set p1;
  961. p_set setalloc();
  962. int hulp1 = 0, hulp2;
  963. int safeterm;
  964. int termissafe = 0;
  965. int casecnt = 0;
  966. int *tokenlist = mk_tokenlist();
  967. int compacted;
  968. if (rep_kind == PLUS) safeterm = gettout(q);
  969. else if (rep_kind == OPT) safeterm = safety;
  970. else /* if (rep_kind == STAR) */ safeterm = max(safety, gettout(q));
  971. hulp2 = nlabel++;
  972. fprintf(f, "goto L_%d;\nL_%d : ", hulp2, hulp2);
  973. if (q->t_flags & RESOLVER) {
  974. hulp1 = nlabel++;
  975. if (! (q->t_flags & NOCONF)) {
  976. p1 = setalloc();
  977. setunion(p1,q->t_first);
  978. setintersect(p1,q->t_follow);
  979. /*
  980. * p1 now points to a set containing the conflicting
  981. * symbols
  982. */
  983. setminus(q->t_first, p1);
  984. setminus(q->t_follow, p1);
  985. setminus(q->t_contains, p1);
  986. add_cases(p1, tokenlist, casecnt++);
  987. free((p_mem) p1);
  988. }
  989. }
  990. if (safeterm == 0 || (!onerror && safeterm <= SAFESCANDONE)) {
  991. termissafe = 1;
  992. }
  993. else add_cases(q->t_follow, tokenlist, casecnt++);
  994. if (!onerror && (q->t_flags & PERSISTENT) && safeterm != SAFE) {
  995. add_cases(q->t_contains, tokenlist, casecnt);
  996. }
  997. else add_cases(q->t_first, tokenlist, casecnt);
  998. compacted = analyze_switch(tokenlist);
  999. fputs("{", f);
  1000. if (compacted) {
  1001. out_list(tokenlist, listcount++, casecnt);
  1002. }
  1003. else fputs("switch(LLcsymb) {\n", f);
  1004. casecnt = 0;
  1005. if (q->t_flags & RESOLVER) {
  1006. if (q->t_flags & NOCONF) {
  1007. fputs("#ifdef ___NOCONFLICT___\n", f);
  1008. }
  1009. else gencases(tokenlist, casecnt++, compacted);
  1010. controlline();
  1011. fputs("if (", f);
  1012. getaction(0);
  1013. fprintf(f, ") goto L_%d;\n", hulp1);
  1014. if (q->t_flags & NOCONF) {
  1015. fputs("#endif /* ___NOCONFLICT___ */\n", f);
  1016. }
  1017. }
  1018. if (safeterm == 0 || (!onerror && safeterm <= SAFESCANDONE)) {
  1019. fputs("default:\n", f);
  1020. }
  1021. else gencases(tokenlist, casecnt++, compacted);
  1022. if (rep_kind == OPT) genpop(ispushed);
  1023. fputs(c_break, f);
  1024. if (! termissafe) {
  1025. int i;
  1026. static int nvar;
  1027. assert(ispushed != NOPOP);
  1028. if (ispushed >= 0) i = -ispushed;
  1029. else i = tokens[-(ispushed+1)].t_tokno;
  1030. ++nvar;
  1031. fprintf(f,"default:{int LL_%d=LLnext(%d);\n;if (!LL_%d) {\n",
  1032. nvar, i, nvar);
  1033. if (rep_kind == OPT) genpop(ispushed);
  1034. fputs(c_break, f);
  1035. fputs(c_close, f);
  1036. fprintf(f,"else if (LL_%d & 1) goto L_%d;}\n",nvar, hulp2);
  1037. }
  1038. gencases(tokenlist, casecnt, compacted);
  1039. if (q->t_flags & RESOLVER) {
  1040. fprintf(f, "goto L_%d;\nL_%d : ;\n", hulp1, hulp1);
  1041. }
  1042. if (rep_kind == OPT) genpop(ispushed);
  1043. if (rep_count > 0) {
  1044. assert(ispushed != NOPOP);
  1045. fputs(rep_kind == STAR ? "if (!LL_i) " : "if (LL_i == 1) ", f);
  1046. genpop(ispushed);
  1047. }
  1048. free((p_mem) tokenlist);
  1049. }
  1050. STATIC void gencases(int *tokenlist, int caseno, int compacted)
  1051. {
  1052. /*
  1053. * setp points to a bitset indicating which cases must
  1054. * be generated.
  1055. * YECH, the PCC compiler does not accept many cases without
  1056. * statements in between, so after every case label an empty
  1057. * statement is generated.
  1058. * The C-grammar used by PCC is really stupid on this point :
  1059. * it contains the rule
  1060. * statement : label statement
  1061. * which is right-recursive, and as is well known, LALR parsers don't
  1062. * handle these things very well.
  1063. * The grammar should have been written :
  1064. * labeledstatement : labels statement ;
  1065. * labels : labels label | ;
  1066. */
  1067. p_token p;
  1068. int i;
  1069. if (compacted) fprintf(fpars, "case %d :\n", caseno);
  1070. for (i = 0, p = tokens; i < ntokens; i++, p++) {
  1071. if (tokenlist[i] == caseno)
  1072. {
  1073. if (compacted)
  1074. fprintf(fpars, p->t_tokno < 0400 ? "/* case '%s' */\n" :
  1075. "/* case %s */\n",
  1076. p->t_string);
  1077. else
  1078. fprintf(fpars, p->t_tokno<0400 ? "case /* '%s' */ %d : ;\n" :
  1079. "case /* %s */ %d : ;\n",
  1080. p->t_string, i);
  1081. }
  1082. }
  1083. }
  1084. static char namebuf[20];
  1085. STATIC char *genname(char * s) {
  1086. /*
  1087. * Generate a target file name from the
  1088. * source file name s.
  1089. */
  1090. char *c, *d;
  1091. c = namebuf;
  1092. while (*s) {
  1093. if (*s == '/') {
  1094. while (*s == '/') s++;
  1095. if (*s) c = namebuf;
  1096. else break;
  1097. }
  1098. *c++ = *s++;
  1099. }
  1100. for (d = c; --d > namebuf;) if (*d == '.') break;
  1101. if (d == namebuf) d = c;
  1102. if (d >= &namebuf[12]) {
  1103. fatal(0,"%s : filename too long",namebuf, NULL);
  1104. }
  1105. *d++ = '.';
  1106. *d++ = 'c';
  1107. *d = '\0';
  1108. return namebuf;
  1109. }
  1110. STATIC void genpush(int d) {
  1111. genincrdecr("incr", d);
  1112. }
  1113. STATIC void genincrdecr(char *s, int d) {
  1114. if (d == NOPOP) return;
  1115. if (d >= 0) {
  1116. fprintf(fpars, "LLs%s(%d);\n", s, d / nbytes);
  1117. return;
  1118. }
  1119. fprintf(fpars, "LLt%s(%d);\n", s, -(d + 1));
  1120. }
  1121. STATIC void genpop(int d) {
  1122. genincrdecr("decr", d);
  1123. }
  1124. STATIC int analyze_switch(int *tokenlist)
  1125. {
  1126. int i;
  1127. int ncases = 0;
  1128. int percentage;
  1129. int maxcase = 0, mincase = 0;
  1130. if (! jmptable_option) return 0;
  1131. for (i = 0; i < ntokens; i++) {
  1132. if (tokenlist[i] >= 0) {
  1133. ncases++;
  1134. if (! mincase) mincase = i + 1;
  1135. maxcase = i + 1;
  1136. }
  1137. }
  1138. if (ncases < min_cases_for_jmptable) return 0;
  1139. percentage = ncases * 100 / (maxcase - mincase);
  1140. fprintf(fpars, "/* percentage is %d */\n", percentage);
  1141. return percentage >= low_percentage && percentage <= high_percentage;
  1142. }
  1143. STATIC void add_cases(p_set s, int *tokenlist, int caseno)
  1144. {
  1145. int i;
  1146. for (i = 0; i < ntokens; i++) {
  1147. if (IN(s, i)) {
  1148. tokenlist[i] = caseno;
  1149. }
  1150. }
  1151. }
  1152. STATIC void out_list(int *tokenlist, int listno, int casecnt)
  1153. {
  1154. int i;
  1155. FILE *f = fpars;
  1156. fprintf(f, "static %s LL%d_tklist[] = {",
  1157. casecnt <= 127 ? "char" : "short",
  1158. listno);
  1159. for (i = 0; i < ntokens; i++) {
  1160. fprintf(f, "%c%d,", i % 10 == 0 ? '\n': ' ', tokenlist[i]);
  1161. }
  1162. fputs(c_arrend, f);
  1163. fprintf(f, "switch(LL%d_tklist[LLcsymb]) {\n", listno);
  1164. }
  1165. STATIC void genextname(int d, char *s, FILE *f)
  1166. {
  1167. fprintf(f, "%s%d_%s", prefix ? prefix : "LL", d, s);
  1168. }
  1169. STATIC void correct_prefix()
  1170. {
  1171. FILE *f = fpars;
  1172. char *s = prefix;
  1173. if (s) {
  1174. fprintf(f, "#define LLsymb %ssymb\n", s);
  1175. fprintf(f, "#define LLerror %serror\n", s);
  1176. fprintf(f, "#define LLsafeerror %ssafeerror\n", s);
  1177. fprintf(f, "#ifndef LL_FASTER\n#define LLscan %sscan\n#endif\n", s);
  1178. fprintf(f, "#define LLscnt %sscnt\n", s);
  1179. fprintf(f, "#define LLtcnt %stcnt\n", s);
  1180. fprintf(f, "#define LLcsymb %scsymb\n", s);
  1181. fprintf(f, "#define LLread %sread\n", s);
  1182. fprintf(f, "#define LLskip %sskip\n", s);
  1183. fprintf(f, "#define LLnext %snext\n", s);
  1184. fprintf(f, "#define LLfirst %sfirst\n", s);
  1185. fprintf(f, "#define LLnewlevel %snewlevel\n", s);
  1186. fprintf(f, "#define LLoldlevel %soldlevel\n", s);
  1187. fprintf(f, "#define LLmessage %smessage\n", s);
  1188. #ifdef NON_CORRECTING
  1189. fprintf(f, "#define LLnc_recovery %sncrecovery\n", s);
  1190. fprintf(f, "#define LLstartsymb %sstartsymb\n", s);
  1191. #endif
  1192. }
  1193. fprintf(f, "#include \"%s\"\n", f_include);
  1194. }