check.c 9.8 KB

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