check.c 9.8 KB

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