123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450 |
- /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
- * For full copyright and restrictions on use see the file COPYING in the top
- * level of the LLgen tree.
- */
- /*
- * L L G E N
- *
- * An Extended LL(1) Parser Generator
- *
- * Author : Ceriel J.H. Jacobs
- */
- /*
- * check.c
- * Several routines to perform checks and printouts
- */
- #include <stdlib.h>
- #include <string.h>
- # include "types.h"
- # include "extern.h"
- # include "io.h"
- # include "sets.h"
- # include "assert.h"
- #include "LLgen.h"
- static string c_first = "> firstset ";
- static string c_contains = "> containset ";
- static string c_follow = "> followset ";
- static int level;
- /* In this file are defined : */
- void conflchecks() {
- /*
- * Check for conflicts, that is,
- * in a repeating term, the FIRST and FOLLOW must be disjunct,
- * unless there is a disambiguating condition.
- * in an alternation, the sets that determine the direction to take,
- * must be disjunct.
- */
- p_nont p;
- int s;
- p_file x = files;
- f_input = x->f_name;
- if (verbose >= 3) {
- for (p = nonterms; p < maxnt; p++) p->n_flags |= VERBOSE;
- }
- if (verbose) {
- if ((fout = fopen(f_out,"w")) == NULL) fatal(1,e_noopen,f_out, NULL);
- }
- /*
- * Check the rules in the order in which they are declared,
- * and input file by input file, to give proper error messages
- */
- for (; x < maxfiles; x++) {
- f_input = x->f_name;
- for (s = x->f_nonterminals; s != -1; s = p->n_next) {
- p = &nonterms[s];
- if (check(p->n_rule)) p->n_flags |= VERBOSE;
- }
- }
- for (x = files; x < maxfiles; x++) {
- f_input = x->f_name;
- for (s = x->f_nonterminals; s != -1; s = p->n_next) {
- p = &nonterms[s];
- if (p->n_flags & RECURSIVE) {
- error(p->n_lineno,
- "Recursion in default for nonterminal %s",
- p->n_name, NULL);
- }
- /*
- * If a printout is needed for this rule in
- * LL.output, just do it
- */
- if (verbose && (p->n_flags & VERBOSE)) {
- fprintf(fout,"\n%s :\n",p->n_name);
- printset(p->n_first,c_first);
- printset(p->n_contains,c_contains);
- printset(p->n_follow,c_follow);
- fprintf(fout,"> rule%s\n\t",
- p->n_flags&EMPTY ? "\t(EMPTY producing)" : "");
- level = 8;
- prrule(p->n_rule);
- level = 0;
- prline("\n");
- }
- /*
- * Now, the conflicts may be resolved
- */
- resolve(p->n_rule);
- }
- }
- if (verbose) fclose(fout);
- }
- STATIC void prline(char *s) {
- fputs(s, fout);
- spaces();
- }
- STATIC void printset(p_set p, char *s) {
- /*
- * Print the elements of a set
- */
- int i;
- int j;
- p_token pt;
- string name;
- int k;
- int hulp;
- k = strlen(s) + 2 + level;
- /*
- * k contains relative level of indentation
- */
- fprintf(fout,"%s{ ",s);
- j = k;
- /*
- * j will gather the total length of the line
- */
- for (i = 0, pt = tokens; i < ntokens; i++,pt++) {
- if (IN(p,i)) {
- hulp = strlen(pt->t_string)+1;
- if (pt->t_tokno < 0400) hulp += 2;
- if ((j += hulp) >= 78) {
- /*
- * Line becoming too long
- */
- j = k+hulp;
- prline("\n");
- fprintf(fout,">%*c",k - level - 1,' ');
- }
- fprintf(fout, pt->t_tokno<0400 ? "'%s' " : "%s ",pt->t_string);
- }
- }
- if (ntprint) for (i = 0; i < nnonterms; i++) {
- /*
- * Nonterminals in the set must also be printed
- */
- if (NTIN(p,i)) {
- name = nonterms[i].n_name;
- hulp = strlen(name) + 3;
- if ((j += hulp) >= 78) {
- j = k + hulp;
- prline("\n");
- fprintf(fout,">%*c",k - level - 1,' ');
- }
- fprintf(fout,"<%s> ",name);
- }
- }
- prline("}\n");
- }
- STATIC int check(p_gram p) {
- /*
- * Search for conflicts in a grammar rule.
- */
- p_set temp;
- int retval;
- retval = 0;
- for (;;) {
- switch (g_gettype(p)) {
- case EORULE :
- return retval;
- case NONTERM : {
- p_nont n;
- n = &nonterms[g_getcont(p)];
- if (g_getnpar(p) != getntparams(n)) {
- error(p->g_lineno,
- "Call of %s: parameter count mismatch",
- n->n_name, NULL);
- }
- break; }
- case TERM : {
- p_term q;
- q = g_getterm(p);
- retval |= check(q->t_rule);
- if (r_getkind(q) == FIXED) break;
- if (setempty(q->t_first)) {
- q->t_flags |= EMPTYFIRST;
- retval = 1;
- error(p->g_lineno, "No symbols in term", NULL, NULL);
- }
- if (empty(q->t_rule)) {
- q->t_flags |= EMPTYTERM;
- retval = 1;
- error(p->g_lineno, "Term with variable repetition count produces empty", NULL, NULL);
- }
- temp = setalloc();
- setunion(temp,q->t_first);
- if (!setintersect(temp,q->t_follow)) {
- /*
- * q->t_first * q->t_follow != EMPTY
- */
- if (!(q->t_flags & RESOLVER)) {
- /*
- * No conflict resolver
- */
- error(p->g_lineno,
- "Repetition conflict", NULL, NULL);
- retval = 1;
- moreverbose(temp);
- }
- }
- else {
- if (q->t_flags & RESOLVER) {
- q->t_flags |= NOCONF;
- warning(p->g_lineno,
- "%%while without conflict", NULL, NULL);
- }
- }
- free((p_mem) temp);
- break; }
- case ALTERNATION : {
- p_link l;
- l = g_getlink(p);
- temp = setalloc();
- setunion(temp,l->l_symbs);
- if(!setintersect(temp,l->l_others)) {
- /*
- * temp now contains the conflicting
- * symbols
- */
- if (!(l->l_flag & (COND|PREFERING|AVOIDING))) {
- error(p->g_lineno, "Alternation conflict", NULL, NULL);
- retval = 1;
- moreverbose(temp);
- }
- } else {
- if (l->l_flag & (COND|PREFERING|AVOIDING)) {
- l->l_flag |= NOCONF;
- warning(p->g_lineno, "Conflict resolver without conflict", NULL, NULL);
- }
- }
- free( (p_mem) temp);
- if (l->l_flag & PREFERING) propagate(l->l_symbs,p+1);
- retval |= check(l->l_rule);
- break; }
- }
- p++;
- }
- }
- STATIC void moreverbose(p_set t) {
- /*
- * t points to a set containing conflicting symbols and pssibly
- * also containing nonterminals.
- * Take care that a printout will be prepared for these nonterminals
- */
- int i;
- p_nont p;
- if (verbose == 2) for (i = 0, p = nonterms; i < nnonterms; i++, p++) {
- if (NTIN(t,i)) p->n_flags |= VERBOSE;
- }
- }
- STATIC void prrule(p_gram p) {
- /*
- * Create a verbose printout of grammar rule p
- */
- FILE *f;
- int present = 0;
- int firstalt = 1;
- f = fout;
- for (;;) {
- switch (g_gettype(p)) {
- case EORULE :
- fputs("\n",f);
- return;
- case TERM : {
- p_term q;
- int c;
- q = g_getterm(p);
- if (present) prline("\n");
- fputs("[ ",f);
- level += 4;
- if (q->t_flags & RESOLVER) {
- prline("%while (..)\n");
- }
- if (q->t_flags & PERSISTENT) {
- prline("%persistent\n");
- }
- if (r_getkind(q) != FIXED) {
- if (!(q->t_flags & PERSISTENT)) {
- prline("> continue repetition on the\n");
- }
- printset(q->t_first, c_first);
- if (q->t_flags & PERSISTENT) {
- prline("> continue repetition on the\n");
- }
- printset(q->t_contains, c_contains);
- prline("> terminate repetition on the\n");
- printset(q->t_follow,c_follow);
- if (q->t_flags & EMPTYFIRST) {
- prline(">>> empty first\n");
- }
- if (q->t_flags & EMPTYTERM) {
- prline(">>> term produces empty\n");
- }
- cfcheck(q->t_first,q->t_follow,
- q->t_flags & RESOLVER);
- }
- prrule(q->t_rule);
- level -= 4;
- spaces();
- c = r_getkind(q);
- fputs(c == STAR ? "]*" : c == PLUS ? "]+" :
- c == OPT ? "]?" : "]", f);
- c = r_getnum(q);
- if (c) {
- fprintf(f,"%d",c);
- }
- prline("\n");
- break; }
- case ACTION :
- fputs("{..} ",f);
- break;
- case ALTERNATION : {
- p_link l;
- l = g_getlink(p);
- if (firstalt) {
- firstalt = 0;
- }
- else prline("|\n");
- printset(l->l_symbs,"> alternative on ");
- cfcheck(l->l_symbs,
- l->l_others,
- (int)(l->l_flag&(COND|PREFERING|AVOIDING)));
- fputs(" ",f);
- level += 4;
- if (l->l_flag & DEF) {
- prline("%default\n");
- }
- if (l->l_flag & AVOIDING) {
- prline("%avoid\n");
- }
- if (l->l_flag & PREFERING) {
- prline("%prefer\n");
- }
- if (l->l_flag & COND) {
- prline("%if ( ... )\n");
- }
- prrule(l->l_rule);
- level -= 4;
- if (g_gettype(p+1) == EORULE) {
- return;
- }
- spaces();
- p++; continue; }
- case LITERAL :
- case TERMINAL : {
- p_token pt = &tokens[g_getcont(p)];
- fprintf(f,pt->t_tokno<0400 ?
- "'%s' " : "%s ", pt->t_string);
- break; }
- case NONTERM :
- fprintf(f,"%s ",nonterms[g_getcont(p)].n_name);
- break;
- }
- p++;
- present = 1;
- }
- }
- STATIC void cfcheck(p_set s1, p_set s2, int flag) {
- /*
- * Check if s1 and s2 have elements in common.
- * If so, flag must be non-zero, indicating that there is a
- * conflict resolver, otherwise, flag must be zero, indicating
- * that there is not.
- */
- p_set temp;
- temp = setalloc();
- setunion(temp,s1);
- if (!setintersect(temp,s2)) {
- if (! flag) {
- printset(temp,">>> conflict on ");
- prline("\n");
- }
- } else {
- if (flag) {
- prline(">>> %if/%while, no conflict\n");
- }
- }
- free((p_mem) temp);
- }
- STATIC void resolve(p_gram p) {
- /*
- * resolve conflicts, as specified by the user
- */
- for (;;) {
- switch (g_gettype(p)) {
- case EORULE :
- return;
- case TERM :
- resolve(g_getterm(p)->t_rule);
- break;
- case ALTERNATION : {
- p_link l;
- l = g_getlink(p);
- if (l->l_flag & AVOIDING) {
- /*
- * On conflicting symbols, this rule
- * is never chosen
- */
- setminus(l->l_symbs,l->l_others);
- }
- if (setempty(l->l_symbs)) {
- /*
- * This may be caused by the statement above
- */
- error(p->g_lineno,"Alternative never chosen", NULL, NULL);
- }
- resolve(l->l_rule);
- break; }
- }
- p++;
- }
- }
- STATIC void propagate(p_set set, p_gram p) {
- /*
- * Propagate the fact that on the elements of set the grammar rule
- * p will not be chosen.
- */
- while (g_gettype(p) != EORULE) {
- setminus(g_getlink(p)->l_symbs,set);
- p++;
- }
- }
- STATIC void spaces() {
- if (level > 0) fprintf(fout,"%*c",level,' ');
- }
|