check.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450
  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. * check.c
  14. * Several routines to perform checks and printouts
  15. */
  16. #include <stdlib.h>
  17. #include <string.h>
  18. # include "types.h"
  19. # include "extern.h"
  20. # include "io.h"
  21. # include "sets.h"
  22. # include "assert.h"
  23. #include "LLgen.h"
  24. static string c_first = "> firstset ";
  25. static string c_contains = "> containset ";
  26. static string c_follow = "> followset ";
  27. static int level;
  28. /* In this file are defined : */
  29. void conflchecks() {
  30. /*
  31. * Check for conflicts, that is,
  32. * in a repeating term, the FIRST and FOLLOW must be disjunct,
  33. * unless there is a disambiguating condition.
  34. * in an alternation, the sets that determine the direction to take,
  35. * must be disjunct.
  36. */
  37. p_nont p;
  38. int s;
  39. p_file x = files;
  40. f_input = x->f_name;
  41. if (verbose >= 3) {
  42. for (p = nonterms; p < maxnt; p++) p->n_flags |= VERBOSE;
  43. }
  44. if (verbose) {
  45. if ((fout = fopen(f_out,"w")) == NULL) fatal(1,e_noopen,f_out, NULL);
  46. }
  47. /*
  48. * Check the rules in the order in which they are declared,
  49. * and input file by input file, to give proper error messages
  50. */
  51. for (; x < maxfiles; x++) {
  52. f_input = x->f_name;
  53. for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  54. p = &nonterms[s];
  55. if (check(p->n_rule)) p->n_flags |= VERBOSE;
  56. }
  57. }
  58. for (x = files; x < maxfiles; x++) {
  59. f_input = x->f_name;
  60. for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  61. p = &nonterms[s];
  62. if (p->n_flags & RECURSIVE) {
  63. error(p->n_lineno,
  64. "Recursion in default for nonterminal %s",
  65. p->n_name, NULL);
  66. }
  67. /*
  68. * If a printout is needed for this rule in
  69. * LL.output, just do it
  70. */
  71. if (verbose && (p->n_flags & VERBOSE)) {
  72. fprintf(fout,"\n%s :\n",p->n_name);
  73. printset(p->n_first,c_first);
  74. printset(p->n_contains,c_contains);
  75. printset(p->n_follow,c_follow);
  76. fprintf(fout,"> rule%s\n\t",
  77. p->n_flags&EMPTY ? "\t(EMPTY producing)" : "");
  78. level = 8;
  79. prrule(p->n_rule);
  80. level = 0;
  81. prline("\n");
  82. }
  83. /*
  84. * Now, the conflicts may be resolved
  85. */
  86. resolve(p->n_rule);
  87. }
  88. }
  89. if (verbose) fclose(fout);
  90. }
  91. STATIC void prline(char *s) {
  92. fputs(s, fout);
  93. spaces();
  94. }
  95. STATIC void printset(p_set p, char *s) {
  96. /*
  97. * Print the elements of a set
  98. */
  99. int i;
  100. int j;
  101. p_token pt;
  102. string name;
  103. int k;
  104. int hulp;
  105. k = strlen(s) + 2 + level;
  106. /*
  107. * k contains relative level of indentation
  108. */
  109. fprintf(fout,"%s{ ",s);
  110. j = k;
  111. /*
  112. * j will gather the total length of the line
  113. */
  114. for (i = 0, pt = tokens; i < ntokens; i++,pt++) {
  115. if (IN(p,i)) {
  116. hulp = strlen(pt->t_string)+1;
  117. if (pt->t_tokno < 0400) hulp += 2;
  118. if ((j += hulp) >= 78) {
  119. /*
  120. * Line becoming too long
  121. */
  122. j = k+hulp;
  123. prline("\n");
  124. fprintf(fout,">%*c",k - level - 1,' ');
  125. }
  126. fprintf(fout, pt->t_tokno<0400 ? "'%s' " : "%s ",pt->t_string);
  127. }
  128. }
  129. if (ntprint) for (i = 0; i < nnonterms; i++) {
  130. /*
  131. * Nonterminals in the set must also be printed
  132. */
  133. if (NTIN(p,i)) {
  134. name = nonterms[i].n_name;
  135. hulp = strlen(name) + 3;
  136. if ((j += hulp) >= 78) {
  137. j = k + hulp;
  138. prline("\n");
  139. fprintf(fout,">%*c",k - level - 1,' ');
  140. }
  141. fprintf(fout,"<%s> ",name);
  142. }
  143. }
  144. prline("}\n");
  145. }
  146. STATIC int check(p_gram p) {
  147. /*
  148. * Search for conflicts in a grammar rule.
  149. */
  150. p_set temp;
  151. int retval;
  152. retval = 0;
  153. for (;;) {
  154. switch (g_gettype(p)) {
  155. case EORULE :
  156. return retval;
  157. case NONTERM : {
  158. p_nont n;
  159. n = &nonterms[g_getcont(p)];
  160. if (g_getnpar(p) != getntparams(n)) {
  161. error(p->g_lineno,
  162. "Call of %s: parameter count mismatch",
  163. n->n_name, NULL);
  164. }
  165. break; }
  166. case TERM : {
  167. p_term q;
  168. q = g_getterm(p);
  169. retval |= check(q->t_rule);
  170. if (r_getkind(q) == FIXED) break;
  171. if (setempty(q->t_first)) {
  172. q->t_flags |= EMPTYFIRST;
  173. retval = 1;
  174. error(p->g_lineno, "No symbols in term", NULL, NULL);
  175. }
  176. if (empty(q->t_rule)) {
  177. q->t_flags |= EMPTYTERM;
  178. retval = 1;
  179. error(p->g_lineno, "Term with variable repetition count produces empty", NULL, NULL);
  180. }
  181. temp = setalloc();
  182. setunion(temp,q->t_first);
  183. if (!setintersect(temp,q->t_follow)) {
  184. /*
  185. * q->t_first * q->t_follow != EMPTY
  186. */
  187. if (!(q->t_flags & RESOLVER)) {
  188. /*
  189. * No conflict resolver
  190. */
  191. error(p->g_lineno,
  192. "Repetition conflict", NULL, NULL);
  193. retval = 1;
  194. moreverbose(temp);
  195. }
  196. }
  197. else {
  198. if (q->t_flags & RESOLVER) {
  199. q->t_flags |= NOCONF;
  200. warning(p->g_lineno,
  201. "%%while without conflict", NULL, NULL);
  202. }
  203. }
  204. free((p_mem) temp);
  205. break; }
  206. case ALTERNATION : {
  207. p_link l;
  208. l = g_getlink(p);
  209. temp = setalloc();
  210. setunion(temp,l->l_symbs);
  211. if(!setintersect(temp,l->l_others)) {
  212. /*
  213. * temp now contains the conflicting
  214. * symbols
  215. */
  216. if (!(l->l_flag & (COND|PREFERING|AVOIDING))) {
  217. error(p->g_lineno, "Alternation conflict", NULL, NULL);
  218. retval = 1;
  219. moreverbose(temp);
  220. }
  221. } else {
  222. if (l->l_flag & (COND|PREFERING|AVOIDING)) {
  223. l->l_flag |= NOCONF;
  224. warning(p->g_lineno, "Conflict resolver without conflict", NULL, NULL);
  225. }
  226. }
  227. free( (p_mem) temp);
  228. if (l->l_flag & PREFERING) propagate(l->l_symbs,p+1);
  229. retval |= check(l->l_rule);
  230. break; }
  231. }
  232. p++;
  233. }
  234. }
  235. STATIC void moreverbose(p_set t) {
  236. /*
  237. * t points to a set containing conflicting symbols and pssibly
  238. * also containing nonterminals.
  239. * Take care that a printout will be prepared for these nonterminals
  240. */
  241. int i;
  242. p_nont p;
  243. if (verbose == 2) for (i = 0, p = nonterms; i < nnonterms; i++, p++) {
  244. if (NTIN(t,i)) p->n_flags |= VERBOSE;
  245. }
  246. }
  247. STATIC void prrule(p_gram p) {
  248. /*
  249. * Create a verbose printout of grammar rule p
  250. */
  251. FILE *f;
  252. int present = 0;
  253. int firstalt = 1;
  254. f = fout;
  255. for (;;) {
  256. switch (g_gettype(p)) {
  257. case EORULE :
  258. fputs("\n",f);
  259. return;
  260. case TERM : {
  261. p_term q;
  262. int c;
  263. q = g_getterm(p);
  264. if (present) prline("\n");
  265. fputs("[ ",f);
  266. level += 4;
  267. if (q->t_flags & RESOLVER) {
  268. prline("%while (..)\n");
  269. }
  270. if (q->t_flags & PERSISTENT) {
  271. prline("%persistent\n");
  272. }
  273. if (r_getkind(q) != FIXED) {
  274. if (!(q->t_flags & PERSISTENT)) {
  275. prline("> continue repetition on the\n");
  276. }
  277. printset(q->t_first, c_first);
  278. if (q->t_flags & PERSISTENT) {
  279. prline("> continue repetition on the\n");
  280. }
  281. printset(q->t_contains, c_contains);
  282. prline("> terminate repetition on the\n");
  283. printset(q->t_follow,c_follow);
  284. if (q->t_flags & EMPTYFIRST) {
  285. prline(">>> empty first\n");
  286. }
  287. if (q->t_flags & EMPTYTERM) {
  288. prline(">>> term produces empty\n");
  289. }
  290. cfcheck(q->t_first,q->t_follow,
  291. q->t_flags & RESOLVER);
  292. }
  293. prrule(q->t_rule);
  294. level -= 4;
  295. spaces();
  296. c = r_getkind(q);
  297. fputs(c == STAR ? "]*" : c == PLUS ? "]+" :
  298. c == OPT ? "]?" : "]", f);
  299. c = r_getnum(q);
  300. if (c) {
  301. fprintf(f,"%d",c);
  302. }
  303. prline("\n");
  304. break; }
  305. case ACTION :
  306. fputs("{..} ",f);
  307. break;
  308. case ALTERNATION : {
  309. p_link l;
  310. l = g_getlink(p);
  311. if (firstalt) {
  312. firstalt = 0;
  313. }
  314. else prline("|\n");
  315. printset(l->l_symbs,"> alternative on ");
  316. cfcheck(l->l_symbs,
  317. l->l_others,
  318. (int)(l->l_flag&(COND|PREFERING|AVOIDING)));
  319. fputs(" ",f);
  320. level += 4;
  321. if (l->l_flag & DEF) {
  322. prline("%default\n");
  323. }
  324. if (l->l_flag & AVOIDING) {
  325. prline("%avoid\n");
  326. }
  327. if (l->l_flag & PREFERING) {
  328. prline("%prefer\n");
  329. }
  330. if (l->l_flag & COND) {
  331. prline("%if ( ... )\n");
  332. }
  333. prrule(l->l_rule);
  334. level -= 4;
  335. if (g_gettype(p+1) == EORULE) {
  336. return;
  337. }
  338. spaces();
  339. p++; continue; }
  340. case LITERAL :
  341. case TERMINAL : {
  342. p_token pt = &tokens[g_getcont(p)];
  343. fprintf(f,pt->t_tokno<0400 ?
  344. "'%s' " : "%s ", pt->t_string);
  345. break; }
  346. case NONTERM :
  347. fprintf(f,"%s ",nonterms[g_getcont(p)].n_name);
  348. break;
  349. }
  350. p++;
  351. present = 1;
  352. }
  353. }
  354. STATIC void cfcheck(p_set s1, p_set s2, int flag) {
  355. /*
  356. * Check if s1 and s2 have elements in common.
  357. * If so, flag must be non-zero, indicating that there is a
  358. * conflict resolver, otherwise, flag must be zero, indicating
  359. * that there is not.
  360. */
  361. p_set temp;
  362. temp = setalloc();
  363. setunion(temp,s1);
  364. if (!setintersect(temp,s2)) {
  365. if (! flag) {
  366. printset(temp,">>> conflict on ");
  367. prline("\n");
  368. }
  369. } else {
  370. if (flag) {
  371. prline(">>> %if/%while, no conflict\n");
  372. }
  373. }
  374. free((p_mem) temp);
  375. }
  376. STATIC void resolve(p_gram p) {
  377. /*
  378. * resolve conflicts, as specified by the user
  379. */
  380. for (;;) {
  381. switch (g_gettype(p)) {
  382. case EORULE :
  383. return;
  384. case TERM :
  385. resolve(g_getterm(p)->t_rule);
  386. break;
  387. case ALTERNATION : {
  388. p_link l;
  389. l = g_getlink(p);
  390. if (l->l_flag & AVOIDING) {
  391. /*
  392. * On conflicting symbols, this rule
  393. * is never chosen
  394. */
  395. setminus(l->l_symbs,l->l_others);
  396. }
  397. if (setempty(l->l_symbs)) {
  398. /*
  399. * This may be caused by the statement above
  400. */
  401. error(p->g_lineno,"Alternative never chosen", NULL, NULL);
  402. }
  403. resolve(l->l_rule);
  404. break; }
  405. }
  406. p++;
  407. }
  408. }
  409. STATIC void propagate(p_set set, p_gram p) {
  410. /*
  411. * Propagate the fact that on the elements of set the grammar rule
  412. * p will not be chosen.
  413. */
  414. while (g_gettype(p) != EORULE) {
  415. setminus(g_getlink(p)->l_symbs,set);
  416. p++;
  417. }
  418. }
  419. STATIC void spaces() {
  420. if (level > 0) fprintf(fout,"%*c",level,' ');
  421. }