gencode.c 28 KB

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