From 129ce0f1c9d43c04ed8198ac184bce8d8be0042e Mon Sep 17 00:00:00 2001 From: Terence Parr <> Date: Thu, 5 Oct 1995 19:39:56 -0500 Subject: [PATCH] auto commit for import --- antlr/bits.c | 826 +++++++++++++++ antlr/build.c | 716 +++++++++++++ antlr/err.c | 317 ++++++ antlr/fset.c | 978 +++++++++++++++++ antlr/fset2.c | 1207 +++++++++++++++++++++ antlr/gen.c | 2790 +++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 6834 insertions(+) create mode 100755 antlr/bits.c create mode 100755 antlr/build.c create mode 100755 antlr/err.c create mode 100755 antlr/fset.c create mode 100755 antlr/fset2.c create mode 100755 antlr/gen.c diff --git a/antlr/bits.c b/antlr/bits.c new file mode 100755 index 0000000..ba71f81 --- /dev/null +++ b/antlr/bits.c @@ -0,0 +1,826 @@ +/* + * bits.c -- manage creation and output of bit sets used by the parser. + * + * $Id: bits.c,v 1.3 95/09/26 12:58:38 parrt Exp $ + * $Revision: 1.3 $ + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ +#include +#include +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +/* char is only thing that is pretty much always known == 8 bits + * This allows output of antlr (set stuff, anyway) to be androgynous (portable) + */ +typedef unsigned char SetWordType; +#define BitsPerByte 8 +#define BitsPerWord BitsPerByte*sizeof(SetWordType) + +static SetWordType *setwd = NULL; +int setnum = -1; +int wordnum = 0; + +int esetnum = 0; + +/* Used to convert native wordsize, which ANTLR uses (via set.c) to manipulate sets, + to bytes that are most portable size-wise. + */ +void +#ifdef __STDC__ +DumpIntAsChars( FILE *f, char *format, unsigned wd ) +#else +DumpIntAsChars( f, format, wd ) +FILE *f; +char *format; +unsigned wd; +#endif +{ + int i; + /* uses max of 32 bit unsigned integer for the moment */ + static unsigned long byte_mask[sizeof(unsigned long)] = + { 0xFF, 0xFF00, 0xFF0000, 0xFF000000 }; +/* 0xFF00000000, 0xFF0000000000, 0xFF000000000000, 0xFF00000000000000 };*/ + + /* for each byte in the word */ + for (i=0; i>(i*BitsPerByte)); + if ( itok))); + return empty; + } + r = RulePtr[q->rulenum]; + r->end->halt = TRUE; /* don't let reach fall off end of rule here */ + rk = empty; + REACH(r, 1, &rk, a); + r->end->halt = FALSE; + return a; +} + +/* + * scan the list of tokens/eclasses/nonterminals filling the new eclass + * with the set described by the list. Note that an eclass can be + * quoted to allow spaces etc... However, an eclass must not conflict + * with a reg expr found elsewhere. The reg expr will be taken over + * the eclass name. + */ +static void +#ifdef __STDC__ +doEclass( char *eclass ) +#else +doEclass( eclass ) +char *eclass; +#endif +{ + TermEntry *q; + ECnode *p; + ListNode *e; + unsigned int t; + unsigned deg=0; + set a; + require(eclass!=NULL, "doEclass: NULL eset"); + + p = (ECnode *) eclass; + lexmode(p->lexclass); /* switch to lexclass where errclass is defined */ + p->eset = empty; + for (e = (p->elist)->next; e!=NULL; e=e->next) + { + if ( islower( *((char *)e->elem) ) ) /* is it a rule ref? (alias FIRST request) */ + { + a = Efirst((char *)e->elem, p); + set_orin(&p->eset, a); + deg += set_deg(a); + set_free( a ); + continue; + } + else if ( *((char *)e->elem)=='"' ) + { + t = 0; + q = (TermEntry *) hash_get(Texpr, (char *) e->elem); + if ( q == NULL ) + { + /* if quoted and not an expr look for eclass name */ + q = (TermEntry *) hash_get(Tname, *((char **)&(e->elem))=StripQuotes((char *)e->elem)); + if ( q != NULL ) t = q->token; + } + else t = q->token; + } + else /* labelled token/eclass/tokclass */ + { + q = (TermEntry *) hash_get(Tname, (char *)e->elem); + if ( q != NULL ) + { + if ( strcmp((char *)e->elem, TokenString(p->tok))==0 ) + { + warnNoFL(eMsg1("self-referential error class '%s'; ignored", + (char *)e->elem)); + continue; + } + else + t = q->token; + } + else t=0; + } + if ( t!=0 ) + { + set_orel(t, &p->eset); + deg++; + } + else warnNoFL(eMsg2("undefined token '%s' referenced in errclass '%s'; ignored", + (char *)e->elem, TokenString(p->tok))); + } + p->setdeg = deg; +} + +void +#ifdef __STDC__ +ComputeErrorSets( void ) +#else +ComputeErrorSets( ) +#endif +{ +#ifdef __cplusplus + list_apply(eclasses, (void (*)(void *)) doEclass); +#else +#ifdef __STDC__ + list_apply(eclasses, (void (*)(void *)) doEclass); +#else + list_apply(eclasses, doEclass); +#endif +#endif +} + +void +#ifdef __STDC__ +ComputeTokSets( void ) +#else +ComputeTokSets( ) +#endif +{ + ListNode *t, *e = NULL; + int something_changed; + TCnode *p; + TermEntry *q; + + if ( tclasses == NULL ) return; + + /* turn lists of token/tokclass references into sets */ + for (t = tclasses->next; t!=NULL; t=t->next) + { + p = (TCnode *) t->elem; + + /* if wild card, then won't have entries in tclass, assume all_tokens */ + if ( p->tok == WildCardToken ) + { + p->tset = set_dup(all_tokens); + continue; + } + + lexmode(p->lexclass); /* switch to lexclass where tokclass is defined */ + p->tset = empty; + + /* instantiate all tokens/token_classes into the tset */ + for (e = (p->tlist)->next; e!=NULL; e=e->next) + { + char *tokstr; + tokstr = (char *)e->elem; + if ( *tokstr == '"' ) q = (TermEntry *) hash_get(Texpr, tokstr); + else q = (TermEntry *) hash_get(Tname, tokstr); + require(q!=NULL, "ComputeTokSets: no token def"); + set_orel(q->token, &p->tset); + } + } + + /* Go thru list of tokclasses again looking for tokclasses in sets */ +again: + something_changed = 0; + for (t = tclasses->next; t!=NULL; t=t->next) + { + set tcl; + p = (TCnode *) t->elem; + tcl = set_and(p->tset, tokclasses); + if ( !set_nil(tcl) ) + { + int tk; + /* replace refs to tokclasses with the associated set of tokens */ + something_changed = 1; + while ( !set_nil(tcl) ) + { + tk = set_int(tcl); /* grab one of the tok class refs */ + set_rm(tk, tcl); + if ( p->tok != tk ) /* tokclass ref to yourself? */ + { + q = (TermEntry *) hash_get(Tname, TokenString(tk)); + require(q!=NULL, "#tokclass not in hash table"); + set_orin(&p->tset, q->tclass->tset); + } + set_rm(tk, p->tset); /* remove ref that we replaced */ + } + } + set_free(tcl); + } + if ( something_changed ) goto again; +} + +void +DumpRemainingTokSets() +{ + TCnode *p; + ListNode *t; + + /* Go thru tclasses (for the last time) and dump the sets not dumped + * during code gen; yes, this is a bogus way to do this, but ComputeTokSets() + * can't dump the defs as the error file and tok file has not been created + * yet etc... + */ + if ( tclasses==NULL ) return; + for (t = tclasses->next; t!=NULL; t=t->next) + { + unsigned e; + p = (TCnode *) t->elem; + if ( p->dumped ) continue; + e = DefErrSet(&(p->tset), 0, TokenString(p->tok)); + p->dumped = 1; + p->setnum = e; + } +} + + +/* replace a subset of an error set with an error class name if a subset is found + * repeat process until no replacements made + */ +void +#ifdef __STDC__ +SubstErrorClass( set *f ) +#else +SubstErrorClass( f ) +set *f; +#endif +{ + int max, done = 0; + ListNode *p; + ECnode *ec, *maxclass = NULL; + set a; + require(f!=NULL, "SubstErrorClass: NULL eset"); + + if ( eclasses == NULL ) return; + while ( !done ) + { + max = 0; + maxclass = NULL; + for (p=eclasses->next; p!=NULL; p=p->next) /* chk all error classes */ + { + ec = (ECnode *) p->elem; + if ( ec->setdeg > max ) + { + if ( set_sub(ec->eset, *f) || set_equ(ec->eset, *f) ) + {maxclass = ec; max=ec->setdeg;} + } + } + if ( maxclass != NULL ) /* if subset found, replace with token */ + { + a = set_dif(*f, maxclass->eset); + set_orel((unsigned)maxclass->tok, &a); + set_free(*f); + *f = a; + } + else done = 1; + } +} + +int +#ifdef __STDC__ +DefErrSet( set *f, int subst, char *name ) +#else +DefErrSet( f, subst, name ) +set *f; +int subst; /* should be substitute error classes? */ +char *name; +#endif +{ + if ( GenCC ) return DefErrSetForCC( f, subst, name ); + else return DefErrSetForC( f, subst, name ); +} + +/* Define a new error set. WARNING...set-implementation dependent. + */ +int +#ifdef __STDC__ +DefErrSetForC( set *f, int subst, char *name ) +#else +DefErrSetForC( f, subst, name ) +set *f; +int subst; /* should be substitute error classes? */ +char *name; +#endif +{ + unsigned *p, *endp; + int e=1; + require(!set_nil(*f), "DefErrSet: nil set to dump?"); + + if ( subst ) SubstErrorClass(f); + p = f->setword; + endp = &(f->setword[f->n]); + esetnum++; + if ( name!=NULL ) + fprintf(DefFile, "extern SetWordType %s_set[];\n", name); + else + fprintf(DefFile, "extern SetWordType zzerr%d[];\n", esetnum); + if ( name!=NULL ) { + fprintf(ErrFile, "SetWordType %s_set[%d] = {", + name, + NumWords(TokenNum-1)*sizeof(unsigned)); + } + else { + fprintf(ErrFile, "SetWordType zzerr%d[%d] = {", + esetnum, + NumWords(TokenNum-1)*sizeof(unsigned)); + } + while ( p < endp ) + { + if ( e > 1 ) fprintf(ErrFile, ", "); + DumpIntAsChars(ErrFile, "0x%x", *p++); + if ( e == 3 ) + { + DAWDLE; + if ( p < endp ) fprintf(ErrFile, ","); + fprintf(ErrFile, "\n\t"); + e=1; + } + else e++; + } + fprintf(ErrFile, "};\n"); + + return esetnum; +} + +/* Define a new error set. WARNING...set-implementation dependent; + * Only used when -CC on. + */ +int +#ifdef __STDC__ +DefErrSetForCC( set *f, int subst, char *name ) +#else +DefErrSetForCC( f, subst, name ) +set *f; +int subst; /* should be substitute error classes? */ +char *name; +#endif +{ + unsigned *p, *endp; + int e=1; + require(!set_nil(*f), "DefErrSet: nil set to dump?"); + + if ( subst ) SubstErrorClass(f); + p = f->setword; + endp = &(f->setword[f->n]); + esetnum++; + + if ( name!=NULL ) { + fprintf(Parser_h, "\tstatic SetWordType %s_set[%d];\n", name, + NumWords(TokenNum-1)*sizeof(unsigned)); + fprintf(Parser_c, "SetWordType %s::%s_set[%d] = {", + CurrentClassName, + name, + NumWords(TokenNum-1)*sizeof(unsigned)); + } + else { + fprintf(Parser_c, "SetWordType %s::err%d[%d] = {", + CurrentClassName, + esetnum, + NumWords(TokenNum-1)*sizeof(unsigned)); + fprintf(Parser_h, "\tstatic SetWordType err%d[%d];\n", esetnum, + NumWords(TokenNum-1)*sizeof(unsigned)); + } + + while ( p < endp ) + { + if ( e > 1 ) fprintf(Parser_c, ", "); + DumpIntAsChars(Parser_c, "0x%x", *p++); + if ( e == 3 ) + { + if ( p < endp ) fprintf(Parser_c, ","); + fprintf(Parser_c, "\n\t"); + e=1; + } + else e++; + } + fprintf(Parser_c, "};\n"); + + return esetnum; +} + +void +#ifdef __STDC__ +GenParser_c_Hdr(void) +#else +GenParser_c_Hdr() +#endif +{ + int i,j; + + fprintf(Parser_c, "/*\n"); + fprintf(Parser_c, " * %s: P a r s e r S u p p o r t\n", CurrentClassName); + fprintf(Parser_c, " *\n"); + fprintf(Parser_c, " * Generated from:"); + for (i=0; i\n"); + fprintf(Parser_c, "#define ANTLR_VERSION %s\n", VersionDef); + fprintf(Parser_c, "#define ANTLR_SUPPORT_CODE\n"); + if ( UserTokenDefsFile != NULL ) + fprintf(Parser_c, "#include %s\n", UserTokenDefsFile); + else + fprintf(Parser_c, "#include \"%s\"\n", DefFileName); + + fprintf(Parser_c, "#include \"%s.h\"\n", CurrentClassName); + + /* Dump a Parser::tokens for each automaton */ + fprintf(Parser_c, "\nANTLRChar *%s::_token_tbl[]={\n", CurrentClassName); + fprintf(Parser_c, "\t/* 00 */\t\"Invalid\""); + + for (i=1; i=LastTokenCounted ) + { + fprintf(Parser_c, ",\n\t/* %02d */\t\"invalid\"", i); + continue; + } + if ( TokenString(i) != NULL ) + fprintf(Parser_c, ",\n\t/* %02d */\t\"%s\"", i, TokenString(i)); + else + { + /* look in all lexclasses for the reg expr */ + for (j=0; j=NumLexClasses ) + { + if ( UserDefdTokens ) + { + fprintf(Parser_c, ",\n\t/* %02d */\t\"\"", i); + } + else + fatal_internal(eMsgd("No label or expr for token %d",i)); + } + } + } + fprintf(Parser_c, "\n};\n"); + + /* Build constructors */ + fprintf(Parser_c, "\n%s::", CurrentClassName); + fprintf(Parser_c, "%s(ANTLRTokenBuffer *input) : ANTLRParser(input,%d,%d,%d,%d)\n", + CurrentClassName, + OutputLL_k, + FoundGuessBlk, + DemandLookahead, + NumWords(TokenNum-1)*sizeof(unsigned)); + fprintf(Parser_c, "{\n"); + fprintf(Parser_c, "\ttoken_tbl = _token_tbl;\n"); + fprintf(Parser_c, "}\n\n"); +} + +void +#ifdef __STDC__ +GenParser_h_Hdr(void) +#else +GenParser_h_Hdr() +#endif +{ + int i; + + fprintf(Parser_h, "/*\n"); + fprintf(Parser_h, " * %s: P a r s e r H e a d e r \n", CurrentClassName); + fprintf(Parser_h, " *\n"); + fprintf(Parser_h, " * Generated from:"); + for (i=0; i\n"); + fprintf(ErrFile, "#define ANTLR_VERSION %s\n", VersionDef); + if ( strcmp(ParserName, DefaultParserName)!=0 ) + fprintf(ErrFile, "#define %s %s\n", DefaultParserName, ParserName); + if ( strcmp(ParserName, DefaultParserName)!=0 ) + fprintf(ErrFile, "#include \"%s\"\n", RemapFileName); + if ( HdrAction != NULL ) dumpAction( HdrAction, ErrFile, 0, -1, 0, 1 ); + if ( FoundGuessBlk ) + { + fprintf(ErrFile, "#define ZZCAN_GUESS\n"); + fprintf(ErrFile, "#include \n"); + } + + if ( OutputLL_k > 1 ) fprintf(ErrFile, "#define LL_K %d\n", OutputLL_k); +#ifdef DUM + if ( LexGen ) fprintf(ErrFile, "#define zzEOF_TOKEN %d\n", (TokenInd!=NULL?TokenInd[EofToken]:EofToken)); +#endif + fprintf(ErrFile, "#define zzSET_SIZE %d\n", NumWords(TokenNum-1)*sizeof(unsigned)); + if ( DemandLookahead ) fprintf(ErrFile, "#define DEMAND_LOOK\n"); + fprintf(ErrFile, "#include \"antlr.h\"\n"); + if ( GenAST ) fprintf(ErrFile, "#include \"ast.h\"\n"); + + if ( UserDefdTokens ) fprintf(ErrFile, "#include %s\n", UserTokenDefsFile); + /* still need this one as it has the func prototypes */ + fprintf(ErrFile, "#include \"%s\"\n", DefFileName); + fprintf(ErrFile, "#include \"dlgdef.h\"\n"); + fprintf(ErrFile, "#include \"err.h\"\n\n"); + + /* Dump a zztokens for each automaton */ + if ( strcmp(ParserName, DefaultParserName)!=0 ) + { + fprintf(ErrFile, "ANTLRChar *%s_zztokens[%d]={\n", ParserName, TokenNum-1); + } + else + { + fprintf(ErrFile, "ANTLRChar *zztokens[%d]={\n", TokenNum-1); + } + fprintf(ErrFile, "\t/* 00 */\t\"Invalid\""); + for (i=1; i=LastTokenCounted ) + { + fprintf(ErrFile, ",\n\t/* %02d */\t\"invalid\"", i); + continue; + } + if ( TokenString(i) != NULL ) + fprintf(ErrFile, ",\n\t/* %02d */\t\"%s\"", i, TokenString(i)); + else + { + /* look in all lexclasses for the reg expr */ + for (j=0; j=NumLexClasses ) + { + if ( UserDefdTokens ) + { + fprintf(ErrFile, ",\n\t/* %02d */\t\"\"", i); + } + else + fatal_internal(eMsgd("No label or expr for token %d",i)); + } + } + } + fprintf(ErrFile, "\n};\n"); +} + +void +#ifdef __STDC__ +dumpExpr( FILE *f, char *e ) +#else +dumpExpr( f, e ) +FILE *f; +char *e; +#endif +{ + while ( *e!='\0' ) + { + if ( *e=='\\' && *(e+1)=='\\' ) + {putc('\\', f); putc('\\', f); e+=2;} + else if ( *e=='\\' && *(e+1)=='"' ) + {putc('\\', f); putc('"', f); e+=2;} + else if ( *e=='\\' ) {putc('\\', f); putc('\\', f); e++;} + else {putc(*e, f); e++;} + } +} diff --git a/antlr/build.c b/antlr/build.c new file mode 100755 index 0000000..95e9103 --- /dev/null +++ b/antlr/build.c @@ -0,0 +1,716 @@ +/* + * build.c -- functions associated with building syntax diagrams. + * + * $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $ + * $Revision: 1.3 $ + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ +#include +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +#define SetBlk(g, t, approx) { \ + ((Junction *)g.left)->jtype = t; \ + ((Junction *)g.left)->approx = approx; \ + ((Junction *)g.left)->end = (Junction *) g.right; \ + ((Junction *)g.right)->jtype = EndBlk;} + +/* Add the parameter string 'parm' to the parms field of a block-type junction + * g.left points to the sentinel node on a block. i.e. g.left->p1 points to + * the actual junction with its jtype == some block-type. + */ +void +#ifdef __STDC__ +addParm( Node *p, char *parm ) +#else +addParm( p, parm ) +Node *p; +char *parm; +#endif +{ + char *q = (char *) malloc( strlen(parm) + 1 ); + require(p!=NULL, "addParm: NULL object\n"); + require(q!=NULL, "addParm: unable to alloc parameter\n"); + + strcpy(q, parm); + if ( p->ntype == nRuleRef ) + { + ((RuleRefNode *)p)->parms = q; + } + else if ( p->ntype == nJunction ) + { + ((Junction *)p)->parm = q; /* only one parameter allowed on subrules */ + } + else fatal_internal("addParm: invalid node for adding parm"); +} + +/* + * Build an action node for the syntax diagram + * + * buildAction(ACTION) ::= --o-->ACTION-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildAction( char *action, int file, int line, int is_predicate ) +#else +buildAction( action, file, line, is_predicate ) +char *action; +int file; +int line; +int is_predicate; +#endif +{ + Junction *j1, *j2; + Graph g; + ActionNode *a; + require(action!=NULL, "buildAction: invalid action"); + + j1 = newJunction(); + j2 = newJunction(); + a = newActionNode(); + a->action = (char *) malloc( strlen(action)+1 ); + require(a->action!=NULL, "buildAction: cannot alloc space for action\n"); + strcpy(a->action, action); + j1->p1 = (Node *) a; + a->next = (Node *) j2; + a->is_predicate = is_predicate; + g.left = (Node *) j1; g.right = (Node *) j2; + a->file = file; + a->line = line; + a->rname = "not filled in"; + return g; +} + +/* + * Build a token node for the syntax diagram + * + * buildToken(TOKEN) ::= --o-->TOKEN-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildToken( char *text ) +#else +buildToken( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + TokNode *t; + require(text!=NULL, "buildToken: invalid token name"); + + j1 = newJunction(); + j2 = newJunction(); + t = newTokNode(); + t->altstart = CurAltStart; + if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );} + else {t->label=TRUE; t->token = addTname( text );} + j1->p1 = (Node *) t; + t->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +/* + * Build a wild-card node for the syntax diagram + * + * buildToken(TOKEN) ::= --o-->'.'-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildWildCard( char *text ) +#else +buildWildCard( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + TokNode *t; + TCnode *w; + TermEntry *p; + require(text!=NULL, "buildWildCard: invalid token name"); + + j1 = newJunction(); + j2 = newJunction(); + t = newTokNode(); + + /* If the ref a wild card, make a token class for it */ + if ( Tnum(WildCardString) == 0 ) + { + w = newTCnode; + w->tok = addTname( WildCardString ); + set_orel(w->tok, &imag_tokens); + set_orel(w->tok, &tokclasses); + WildCardToken = w->tok; + require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL, + "hash table mechanism is broken"); + p->classname = 1; /* entry is class name, not token */ + p->tclass = w; /* save ptr to this tclass def */ + list_add(&tclasses, (char *)w); + } + else { + p=(TermEntry *)hash_get(Tname, WildCardString); + require( p!= NULL, "hash table mechanism is broken"); + w = p->tclass; + } + + t->token = w->tok; + t->wild_card = 1; + t->tclass = w; + + t->altstart = CurAltStart; + j1->p1 = (Node *) t; + t->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +void +#ifdef __STDC__ +setUpperRange(TokNode *t, char *text) +#else +setUpperRange(t, text) +TokNode *t; +char *text; +#endif +{ + require(t!=NULL, "setUpperRange: NULL token node"); + require(text!=NULL, "setUpperRange: NULL token string"); + + if ( *text == '"' ) {t->upper_range = addTexpr( text );} + else {t->upper_range = addTname( text );} +} + +/* + * Build a rule reference node of the syntax diagram + * + * buildRuleRef(RULE) ::= --o-->RULE-->o-- + * + * Where o is a junction node. + * + * If rule 'text' has been defined already, don't alloc new space to store string. + * Set r->text to point to old copy in string table. + */ +Graph +#ifdef __STDC__ +buildRuleRef( char *text ) +#else +buildRuleRef( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + RuleRefNode *r; + RuleEntry *p; + require(text!=NULL, "buildRuleRef: invalid rule name"); + + j1 = newJunction(); + j2 = newJunction(); + r = newRNode(); + r->altstart = CurAltStart; + r->assign = NULL; + if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str; + else r->text = mystrdup( text ); + j1->p1 = (Node *) r; + r->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +/* + * Or two subgraphs into one graph via: + * + * Or(G1, G2) ::= --o-G1-o-- + * | ^ + * v | + * o-G2-o + * + * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1. + * If, however, the G1 altnum is 0, make it 1 and then + * make G2 altnum = G1 altnum + 1. + */ +Graph +#ifdef __STDC__ +Or( Graph g1, Graph g2 ) +#else +Or( g1, g2 ) +Graph g1; +Graph g2; +#endif +{ + Graph g; + require(g1.left != NULL, "Or: invalid graph"); + require(g2.left != NULL && g2.right != NULL, "Or: invalid graph"); + + ((Junction *)g1.left)->p2 = g2.left; + ((Junction *)g2.right)->p1 = g1.right; + /* set altnums */ + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1; + g.left = g2.left; + g.right = g1.right; + return g; +} + +/* + * Catenate two subgraphs + * + * Cat(G1, G2) ::= --o-G1-o-->o-G2-o-- + * Cat(NULL,G2)::= --o-G2-o-- + * Cat(G1,NULL)::= --o-G1-o-- + */ +Graph +#ifdef __STDC__ +Cat( Graph g1, Graph g2 ) +#else +Cat( g1, g2 ) +Graph g1; +Graph g2; +#endif +{ + Graph g; + + if ( g1.left == NULL && g1.right == NULL ) return g2; + if ( g2.left == NULL && g2.right == NULL ) return g1; + ((Junction *)g1.right)->p1 = g2.left; + g.left = g1.left; + g.right = g2.right; + return g; +} + +/* + * Make a subgraph an optional block + * + * makeOpt(G) ::= --o-->o-G-o-->o-- + * | ^ + * v | + * o-------o + * + * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found. + * + * The node on the far right is added so that every block owns its own + * EndBlk node. + */ +Graph +#ifdef __STDC__ +makeOpt( Graph g1, int approx ) +#else +makeOpt( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *j1,*j2,*p; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph"); + + j1 = newJunction(); + j2 = newJunction(); + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + g = emptyAlt(); + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1; + for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2) + {;} /* find last alt */ + p->p2 = g.left; /* add optional alternative */ + ((Junction *)g.right)->p1 = (Node *)j2; /* opt alt points to EndBlk */ + g1.right = (Node *)j2; + SetBlk(g1, aOptBlk, approx); + j1->p1 = g1.left; /* add generic node in front */ + g.left = (Node *) j1; + g.right = g1.right; + + return g; +} + +/* + * Make a graph into subblock + * + * makeBlk(G) ::= --o-->o-G-o-->o-- + * + * The node on the far right is added so that every block owns its own + * EndBlk node. + */ +Graph +#ifdef __STDC__ +makeBlk( Graph g1, int approx ) +#else +makeBlk( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *j,*j2; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph"); + + j = newJunction(); + j2 = newJunction(); + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + g1.right = (Node *)j2; + SetBlk(g1, aSubBlk, approx); + j->p1 = g1.left; /* add node in front */ + g.left = (Node *) j; + g.right = g1.right; + + return g; +} + +/* + * Make a subgraph into a loop (closure) block -- (...)* + * + * makeLoop(G) ::= |---| + * v | + * --o-->o-->o-G-o-->o-- + * | ^ + * v | + * o-----------o + * + * After making loop, always place generic node out front. It becomes + * the start of enclosing block. The aLoopBlk is the target of the loop. + * + * Loop blks have TWO EndBlk nodes--the far right and the node that loops back + * to the aLoopBlk node. Node with which we can branch past loop == aLoopBegin and + * one which is loop target == aLoopBlk. + * The branch-past (initial) aLoopBegin node has end + * pointing to the last EndBlk node. The loop-target node has end==NULL. + * + * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node. + */ +Graph +#ifdef __STDC__ +makeLoop( Graph g1, int approx ) +#else +makeLoop( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *back, *front, *begin; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph"); + + back = newJunction(); + front = newJunction(); + begin = newJunction(); + g = emptyAlt(); + ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */ + ((Junction *)g1.right)->p1 = (Node *) back; /* add node to G at end */ + ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */ + ((Junction *)g1.left)->jtype = aLoopBlk; /* mark 2nd aLoopBlk node */ + ((Junction *)g1.left)->end = (Junction *) g1.right; + ((Junction *)g1.left)->lock = makelocks(); + ((Junction *)g1.left)->pred_lock = makelocks(); + g1.right = (Node *) back; + begin->p1 = (Node *) g1.left; + g1.left = (Node *) begin; + begin->p2 = (Node *) g.left; /* make bypass arc */ + ((Junction *)g.right)->p1 = (Node *) back; + SetBlk(g1, aLoopBegin, approx); + front->p1 = g1.left; /* add node to front */ + g1.left = (Node *) front; + + return g1; +} + +/* + * Make a subgraph into a plus block -- (...)+ -- 1 or more times + * + * makePlus(G) ::= |---| + * v | + * --o-->o-G-o-->o-- + * + * After making loop, always place generic node out front. It becomes + * the start of enclosing block. The aPlusBlk is the target of the loop. + * + * Plus blks have TWO EndBlk nodes--the far right and the node that loops back + * to the aPlusBlk node. + * + * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node. + */ +Graph +#ifdef __STDC__ +makePlus( Graph g1, int approx ) +#else +makePlus( g1, approx ) +Graph g1; +int approx; +#endif +{ + int has_empty_alt_already = 0; + Graph g; + Junction *j2, *j3, *first_alt; + Junction *last_alt, *p; + require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph"); + + first_alt = (Junction *)g1.left; + j2 = newJunction(); + j3 = newJunction(); + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */ + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */ + g1.right = (Node *) j2; + SetBlk(g1, aPlusBlk, approx); + ((Junction *)g1.left)->lock = makelocks(); + ((Junction *)g1.left)->pred_lock = makelocks(); + j3->p1 = g1.left; /* add node to front */ + g1.left = (Node *) j3; + + /* add an optional branch which is the "exit" branch of loop */ + /* FIRST, check to ensure that there does not already exist + * an optional path. + */ + /* find last alt */ + for(p=first_alt; p!=NULL; p=(Junction *)p->p2) + { + if ( p->p1->ntype == nJunction && + p->p1!=NULL && + ((Junction *)p->p1)->jtype==Generic && + ((Junction *)p->p1)->p1!=NULL && + ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk ) + { + has_empty_alt_already = 1; + } + last_alt = p; + } + if ( !has_empty_alt_already ) + { + require(last_alt!=NULL, "last_alt==NULL; bad (..)+"); + g = emptyAlt(); + last_alt->p2 = g.left; + ((Junction *)g.right)->p1 = (Node *) j2; + + /* make sure lookahead computation ignores this alt for + * FIRST("(..)+"); but it's still used for computing the FIRST + * of each alternative. + */ + ((Junction *)g.left)->ignore = 1; + } + + return g1; +} + +/* + * Return an optional path: --o-->o-- + */ +Graph +#ifdef __STDC__ +emptyAlt( void ) +#else +emptyAlt( ) +#endif +{ + Junction *j1, *j2; + Graph g; + + j1 = newJunction(); + j2 = newJunction(); + j1->p1 = (Node *) j2; + g.left = (Node *) j1; + g.right = (Node *) j2; + + return g; +} + +/* N o d e A l l o c a t i o n */ + +TokNode * +#ifdef __STDC__ +newTokNode( void ) +#else +newTokNode( ) +#endif +{ + static TokNode *FreeList = NULL; + TokNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new token nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */ + p->next = NULL; /* NULL the ptr we used */ + + p->ntype = nToken; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->altstart = NULL; + + return p; +} + +RuleRefNode * +#ifdef __STDC__ +newRNode( void ) +#else +newRNode( ) +#endif +{ + static RuleRefNode *FreeList = NULL; + RuleRefNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new rref nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */ + p->next = NULL; /* NULL the ptr we used */ + + p->ntype = nRuleRef; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->astnode = ASTinclude; + p->altstart = NULL; + + return p; +} + +Junction * +#ifdef __STDC__ +newJunction( void ) +#else +newJunction( ) +#endif +{ + static Junction *FreeList = NULL; + Junction *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++) + { + p->p1 = (Node *)FreeList; /* add all new Junction nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (Junction *)FreeList->p1;/* remove a Junction node */ + p->p1 = NULL; /* NULL the ptr we used */ + + p->ntype = nJunction; p->visited = 0; + p->jtype = Generic; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->exception_label = NULL; + p->fset = (set *) calloc(CLL_k+1, sizeof(set)); + require(p->fset!=NULL, "cannot allocate fset in newJunction"); + + return p; +} + +ActionNode * +#ifdef __STDC__ +newActionNode( void ) +#else +newActionNode( ) +#endif +{ + static ActionNode *FreeList = NULL; + ActionNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new Action nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (ActionNode *)FreeList->next;/* remove an Action node */ + p->ntype = nAction; + p->next = NULL; /* NULL the ptr we used */ + p->done = 0; + p->pred_fail = NULL; + p->guardpred = NULL; + + return p; +} + +/* + * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion. + * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs. + * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes. + * + * if ( lock[k]==TRUE ) then we have been here before looking for k tokens + * of lookahead. + */ +char * +#ifdef __STDC__ +makelocks( void ) +#else +makelocks( ) +#endif +{ + char *p = (char *) calloc(CLL_k+1, sizeof(char)); + require(p!=NULL, "cannot allocate lock array"); + + return p; +} diff --git a/antlr/err.c b/antlr/err.c new file mode 100755 index 0000000..30788e6 --- /dev/null +++ b/antlr/err.c @@ -0,0 +1,317 @@ +/* + * A n t l r S e t s / E r r o r F i l e H e a d e r + * + * Generated from: antlr.g + * + * Terence Parr, Russell Quong, Will Cohen, and Hank Dietz: 1989-1995 + * Parr Research Corporation + * with Purdue University Electrical Engineering + * With AHPCRC, University of Minnesota + * ANTLR Version 1.32 + */ + +#include +#define ANTLR_VERSION 132 + +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "set.h" +#include +#include "syn.h" +#include "hash.h" +#include "generic.h" +#define zzcr_attr(attr,tok,t) +#define zzSET_SIZE 20 +#include "antlr.h" +#include "tokens.h" +#include "dlgdef.h" +#include "err.h" + +ANTLRChar *zztokens[146]={ + /* 00 */ "Invalid", + /* 01 */ "Eof", + /* 02 */ "QuotedTerm", + /* 03 */ "[\\n\\r]", + /* 04 */ "\\[\\n\\r]", + /* 05 */ "\\~[]", + /* 06 */ "~[\\n\\r\"\\]+", + /* 07 */ "\"", + /* 08 */ "[\\n\\r]", + /* 09 */ "\\[\\n\\r]", + /* 10 */ "\\~[]", + /* 11 */ "~[\\n\\r\"\\]+", + /* 12 */ "'", + /* 13 */ "[\\n\\r]", + /* 14 */ "\\~[]", + /* 15 */ "~[\\n\\r'\\]+", + /* 16 */ "\\*/", + /* 17 */ "\\*", + /* 18 */ "[\\n\\r]", + /* 19 */ "~[\\n\\r\\*]+", + /* 20 */ "\\*/", + /* 21 */ "\\*", + /* 22 */ "[\\n\\r]", + /* 23 */ "~[\\n\\r\\*]+", + /* 24 */ "[\\n\\r]", + /* 25 */ "~[\\n\\r]+", + /* 26 */ "[\\n\\r]", + /* 27 */ "~[\\n\\r]+", + /* 28 */ "[\\n\\r]", + /* 29 */ "~[\\n\\r]+", + /* 30 */ "\\*/", + /* 31 */ "\\*", + /* 32 */ "[\\n\\r]", + /* 33 */ "~[\\n\\r\\*]+", + /* 34 */ "Action", + /* 35 */ "Pred", + /* 36 */ "PassAction", + /* 37 */ "consumeUntil\\( [\\ \\t]* \\{~[\\}]+\\} [\\ \\t]* \\)", + /* 38 */ "consumeUntil\\( ~[\\)]+ \\)", + /* 39 */ "[\\n\\r]", + /* 40 */ "\\>", + /* 41 */ "$", + /* 42 */ "$$", + /* 43 */ "$\\[\\]", + /* 44 */ "$\\[", + /* 45 */ "$[0-9]+", + /* 46 */ "$[0-9]+.", + /* 47 */ "$[0-9]+.[0-9]+", + /* 48 */ "$[_a-zA-Z][_a-zA-Z0-9]*", + /* 49 */ "#0", + /* 50 */ "#\\[\\]", + /* 51 */ "#\\(\\)", + /* 52 */ "#[0-9]+", + /* 53 */ "#[_a-zA-Z][_a-zA-Z0-9]*", + /* 54 */ "#\\[", + /* 55 */ "#\\(", + /* 56 */ "#", + /* 57 */ "\\)", + /* 58 */ "\\[", + /* 59 */ "\\(", + /* 60 */ "\\\\]", + /* 61 */ "\\\\)", + /* 62 */ "\\>", + /* 63 */ "'", + /* 64 */ "\"", + /* 65 */ "\\$", + /* 66 */ "\\#", + /* 67 */ "\\[\\n\\r]", + /* 68 */ "\\~[\\]\\)>$#]", + /* 69 */ "/", + /* 70 */ "/\\*", + /* 71 */ "\\*/", + /* 72 */ "//", + /* 73 */ "~[\\n\\r\\)\\(\\$#\\>\\]\\[\"'/]+", + /* 74 */ "[\\t\\ ]+", + /* 75 */ "[\\n\\r]", + /* 76 */ "\\[", + /* 77 */ "\\<\\<", + /* 78 */ "\"", + /* 79 */ "/\\*", + /* 80 */ "\\*/", + /* 81 */ "//", + /* 82 */ "\\>\\>", + /* 83 */ "WildCard", + /* 84 */ "\\@", + /* 85 */ "LABEL", + /* 86 */ "grammar-element", + /* 87 */ "meta-symbol", + /* 88 */ "#header", + /* 89 */ "#parser", + /* 90 */ "#tokdefs", + /* 91 */ "\\}", + /* 92 */ "class", + /* 93 */ "NonTerminal", + /* 94 */ "TokenTerm", + /* 95 */ "\\{", + /* 96 */ "!", + /* 97 */ "\\<", + /* 98 */ "\\>", + /* 99 */ ":", + /* 100 */ ";", + /* 101 */ "#lexaction", + /* 102 */ "#lexclass", + /* 103 */ "#errclass", + /* 104 */ "#tokclass", + /* 105 */ "#token", + /* 106 */ "=", + /* 107 */ "[0-9]+", + /* 108 */ "\\|", + /* 109 */ "\\~", + /* 110 */ "..", + /* 111 */ "^", + /* 112 */ "#pragma", + /* 113 */ "approx", + /* 114 */ "LL(1)", + /* 115 */ "LL(2)", + /* 116 */ "\\(", + /* 117 */ "\\)", + /* 118 */ "\\*", + /* 119 */ "\\+", + /* 120 */ "?", + /* 121 */ "=>", + /* 122 */ "exception", + /* 123 */ "default", + /* 124 */ "catch", + /* 125 */ "#[A-Za-z0-9_]*", + /* 126 */ "[\\t\\ ]+", + /* 127 */ "[\\n\\r]", + /* 128 */ "//", + /* 129 */ "/\\*", + /* 130 */ "#ifdef", + /* 131 */ "#if", + /* 132 */ "#ifndef", + /* 133 */ "#else", + /* 134 */ "#endif", + /* 135 */ "#undef", + /* 136 */ "#import", + /* 137 */ "ID", + /* 138 */ "#define", + /* 139 */ "INT", + /* 140 */ "enum", + /* 141 */ "\\{", + /* 142 */ "=", + /* 143 */ ",", + /* 144 */ "\\}", + /* 145 */ ";" +}; +SetWordType zzerr1[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x60, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType setwd1[146] = {0x0,0xb0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0xaa,0x0,0x40,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x1,0x1,0x1,0xae,0xae,0xa4,0x0, + 0x0,0x0,0x40,0x0,0x0,0x0,0xaa,0xa6, + 0xae,0xae,0xa6,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x22,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0}; +SetWordType zzerr2[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x40, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr3[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x60, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr4[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x60, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr5[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x40, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType setwd2[146] = {0x0,0x6b,0x14,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x6b,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0xeb,0x6b,0x6f,0x14, + 0x0,0x0,0x0,0x0,0x0,0x80,0x6b,0x6b, + 0x6b,0x6b,0x6b,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x80,0x0, + 0x0,0x0,0x0,0x6b,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0}; +SetWordType zzerr6[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x40, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr7[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0xd0,0x0, + 0x0,0x0,0x0,0x4, 0x0,0x0,0x0,0x0}; +SetWordType zzerr8[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x40, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr9[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0xd0,0x0, + 0x0,0x0,0x0,0x4, 0x0,0x0,0x0,0x0}; +SetWordType zzerr10[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0xc0,0x0, + 0x0,0x0,0x0,0x4, 0x0,0x0,0x0,0x0}; +SetWordType zzerr11[20] = {0x4,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x8,0x60, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType setwd3[146] = {0x0,0x0,0x7d,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x71,0x71,0xf1,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x7d,0x30,0x79,0x0, + 0x0,0x0,0x0,0x0,0x72,0x0,0x7d,0x7d, + 0x71,0x0,0x80,0x71,0x0,0x72,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x72,0x71,0x0, + 0x0,0x71,0x0,0x0,0x0,0x71,0x72,0x71, + 0x71,0x0,0x0,0x72,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0}; +SetWordType zzerr12[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, + 0x0,0x0,0xe,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr13[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x40,0x8, + 0x10,0x30,0x20,0x6, 0x0,0x0,0x0,0x0}; +SetWordType zzerr14[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x40,0x8, + 0x10,0x30,0x20,0x5, 0x0,0x0,0x0,0x0}; +SetWordType zzerr15[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x80, + 0x0,0x0,0x10,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr16[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x40,0x0, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr17[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x60, + 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0}; +SetWordType zzerr18[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0, 0x0,0x14,0x0,0x0}; +SetWordType zzerr19[20] = {0x2,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0, 0x10,0x14,0x0,0x0}; +SetWordType setwd4[146] = {0x0,0x60,0xe,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x7e,0xe,0xe,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0xe,0x0,0xe,0x0, + 0x0,0x0,0x0,0x0,0x7e,0x70,0x7e,0xe, + 0xf,0x0,0x0,0xe,0x0,0x6e,0x70,0x70, + 0x70,0x70,0x70,0x0,0x0,0x6e,0xe,0x0, + 0x0,0xf,0x0,0x0,0x0,0xf,0x6e,0xe, + 0xe,0x0,0x0,0x7e,0x40,0x40,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x80,0x0,0x0, + 0x0,0x0,0x0,0x80,0x0,0x80,0x0,0x0, + 0x0,0x0,0x0}; +SetWordType zzerr20[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0, 0x0,0xc0,0x1,0x0}; +SetWordType zzerr21[20] = {0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, 0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0, 0x0,0xc0,0x1,0x0}; +SetWordType setwd5[146] = {0x0,0x13,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0, + 0x0,0x0,0x0,0x0,0x0,0x10,0x0,0x0, + 0xc,0xc,0x0}; diff --git a/antlr/fset.c b/antlr/fset.c new file mode 100755 index 0000000..71f85ca --- /dev/null +++ b/antlr/fset.c @@ -0,0 +1,978 @@ +/* + * fset.c + * + * $Id: fset.c,v 1.6 95/06/15 18:07:09 parrt Exp $ + * $Revision: 1.6 $ + * + * Compute FIRST and FOLLOW sets. + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ +#include +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +extern char *PRED_AND_LIST; +extern char *PRED_OR_LIST; + +#ifdef __STDC__ +static void ensure_predicates_cover_ambiguous_lookahead_sequences(Junction *, Junction *, char *, Tree *); +#else +static void ensure_predicates_cover_ambiguous_lookahead_sequences(); +#endif + +/* + * What tokens are k tokens away from junction q? + * + * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this + * node. + * We lock the junction according to k--the lookahead. If we have been at this + * junction before looking for the same, k, number of lookahead tokens, we will + * do it again and again...until we blow up the stack. Locks are only used on aLoopBlk, + * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from + * FIRST and FOLLOW calcs. + * + * If p->jtype == EndRule we are going to attempt a FOLLOW. (FOLLOWs are really defined + * in terms of FIRST's, however). To proceed with the FOLLOW, p->halt cannot be + * set. p->halt is set to indicate that a reference to the current rule is in progress + * and the FOLLOW is not desirable. + * + * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule + * junction yields an empty set, replace the empty set with EOF. No FOLLOW means that + * only EOF can follow the current rule. This normally occurs only on the start symbol + * since all other rules are referenced by another rule somewhere. + * + * Normally, both p1 and p2 are followed. However, checking p2 on a RuleBlk node is + * the same as checking the next rule which is clearly incorrect. + * + * Cycles in the FOLLOW sense are possible. e.g. Fo(c) requires Fo(b) which requires + * Fo(c). Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c). Let's say + * Fo(c) is attempted first. It finds all of the FOLLOW symbols and then attempts + * to do Fo(b) which finds of its FOLLOW symbols. So, we have: + * + * Fo(c) + * / \ + * a set Fo(b) + * / \ + * a set Fo(c) .....Hmmmm..... Infinite recursion! + * + * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now + * correctly Fo(c) union Fo(b). We wish to pick up where we left off, so the fact + * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already + * laying around. SOOOOoooo, we track FOLLOW cycles. All FOLLOW computations are + * cached in a hash table. After the sequence of FOLLOWs finish, we reconcile all + * cycles --> correct all Fo(rule) sets in the cache. + * + * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30]. + * TJP 8/93 -- can now read PhD thesis from Purdue. + * + * Also, FIRST sets are cached in the hash table. Keys are (rulename,Fi/Fo,k). + * Only FIRST sets, for which the FOLLOW is not included, are stored. + * + * SPECIAL CASE of (...)+ blocks: + * I added an optional alt so that the alts could see what + * was behind the (...)+ block--thus using enough lookahead + * to branch out rather than just enough to distinguish + * between alts in the (...)+. However, when the FIRST("(...)+") is + * is needed, must not use this last "optional" alt. This routine + * turns off this path by setting a new 'ignore' flag for + * the alt and then resetting it afterwards. + */ +set +#ifdef __STDC__ +rJunc( Junction *p, int k, set *rk ) +#else +rJunc( p, k, rk ) +Junction *p; +int k; +set *rk; +#endif +{ + set a, b; + require(p!=NULL, "rJunc: NULL node"); + require(p->ntype==nJunction, "rJunc: not junction"); + +#ifdef DBG_LL1 + if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k); + else fprintf(stderr, "rJunc: %s in rule %s\n", + decodeJType[p->jtype], ((Junction *)p)->rname); +#endif + /* if this is one of the added optional alts for (...)+ then return */ + if ( p->ignore ) return empty; + + /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */ + if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || + p->jtype==aPlusBlk || p->jtype==EndRule ) + { + require(p->lock!=NULL, "rJunc: lock array is NULL"); + if ( p->lock[k] ) + { + if ( p->jtype == EndRule ) /* FOLLOW cycle? */ + { +#ifdef DBG_LL1 + fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname); +#endif + RegisterCycle(p->rname, k); + } + return empty; + } + if ( p->jtype == RuleBlk && p->end->halt ) /* check for FIRST cache */ + { + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k)); + if ( q != NULL ) + { + set_orin(rk, q->rk); + return set_dup( q->fset ); + } + } + if ( p->jtype == EndRule ) /* FOLLOW set cached already? */ + { + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); + if ( q != NULL ) + { +#ifdef DBG_LL1 + fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k); + s_fprT(stderr, q->fset); + if ( q->incomplete ) fprintf(stderr, " (incomplete)"); + fprintf(stderr, "\n"); +#endif + if ( !q->incomplete ) + { + return set_dup( q->fset ); + } + } + } + p->lock[k] = TRUE; /* This rule is busy */ + } + + a = b = empty; + + if ( p->jtype == EndRule ) + { + if ( p->halt ) /* don't want FOLLOW here? */ + { + p->lock[k] = FALSE; + set_orel(k, rk); /* indicate this k value needed */ + return empty; + } + FoPush(p->rname, k); /* Attempting FOLLOW */ + if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */ +#ifdef DBG_LL1 + fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k); +#endif + } + + if ( p->p1 != NULL ) REACH(p->p1, k, rk, a); + + /* C a c h e R e s u l t s */ + if ( p->jtype == RuleBlk && p->end->halt ) /* can save FIRST set? */ + { + CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) ); + /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/ + hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q); + q->fset = set_dup( a ); + q->rk = set_dup( *rk ); + } + + if ( p->jtype == EndRule ) /* just completed FOLLOW? */ + { + /* Cache Follow set */ + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); + if ( q==NULL ) + { + q = newCacheEntry( Fkey(p->rname,'o',k) ); + hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q); + } + /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/ + if ( set_nil(a) && !q->incomplete ) + { + /* Don't ever save a nil set as complete. + * Turn it into an eof set. + */ + set_orel(EofToken, &a); + } + set_orin(&(q->fset), a); + FoPop( k ); + if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k); +#ifdef DBG_LL1 + fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k); + s_fprT(stderr, q->fset); + if ( q->incomplete ) fprintf(stderr, " (incomplete)"); + fprintf(stderr, "\n"); +#endif + } + + if ( p->jtype != RuleBlk && p->p2 != NULL ) REACH(p->p2, k, rk, b); + if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || + p->jtype==aPlusBlk || p->jtype==EndRule ) + p->lock[k] = FALSE; /* unlock node */ + + set_orin(&a, b); + set_free(b); + return a; +} + +set +#ifdef __STDC__ +rRuleRef( RuleRefNode *p, int k, set *rk_out ) +#else +rRuleRef( p, k, rk_out ) +RuleRefNode *p; +int k; +set *rk_out; +#endif +{ + set rk; + Junction *r; + int k2; + set a, rk2, b; + int save_halt; + RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text); + require(p!=NULL, "rRuleRef: NULL node"); + require(p->ntype==nRuleRef, "rRuleRef: not rule ref"); + +#ifdef DBG_LL1 + fprintf(stderr, "rRuleRef: %s\n", p->text); +#endif + if ( q == NULL ) + { + warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line ); + REACH(p->next, k, rk_out, a); + return a; + } + rk2 = empty; + r = RulePtr[q->rulenum]; + if ( r->lock[k] ) + { + errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s", + r->rname, p->rname) ); + return empty; + } + save_halt = r->end->halt; + r->end->halt = TRUE; /* don't let reach fall off end of rule here */ + rk = empty; + REACH(r, k, &rk, a); + r->end->halt = save_halt; + while ( !set_nil(rk) ) { + k2 = set_int(rk); + set_rm(k2, rk); + REACH(p->next, k2, &rk2, b); + set_orin(&a, b); + set_free(b); + } + set_free(rk); /* this has no members, but free it's memory */ + set_orin(rk_out, rk2); /* remember what we couldn't do */ + set_free(rk2); + return a; +} + +/* + * Return FIRST sub k ( token_node ) + * + * TJP 10/11/93 modified this so that token nodes that are actually + * ranges (T1..T2) work. + */ +set +#ifdef __STDC__ +rToken( TokNode *p, int k, set *rk ) +#else +rToken( p, k, rk ) +TokNode *p; +int k; +set *rk; +#endif +{ + set a; + require(p!=NULL, "rToken: NULL node"); + require(p->ntype==nToken, "rToken: not token node"); + +#ifdef DBG_LL1 + fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token): + ExprString(p->token)); +#endif + if ( k-1 == 0 ) + { + if ( !set_nil(p->tset) ) return set_dup(p->tset); + return set_of(p->token); + } + REACH(p->next, k-1, rk, a); + + return a; +} + +set +#ifdef __STDC__ +rAction( ActionNode *p, int k, set *rk ) +#else +rAction( p, k, rk ) +ActionNode *p; +int k; +set *rk; +#endif +{ + set a; + require(p!=NULL, "rJunc: NULL node"); + require(p->ntype==nAction, "rJunc: not action"); + + REACH(p->next, k, rk, a); /* ignore actions */ + return a; +} + + /* A m b i g u i t y R e s o l u t i o n */ + + +void +#ifdef __STDC__ +dumpAmbigMsg( set *fset, FILE *f, int want_nls ) +#else +dumpAmbigMsg( fset, f, want_nls ) +set *fset; +FILE *f; +int want_nls; +#endif +{ + int i; + + if ( want_nls ) fprintf(f, "\n\t"); + else fprintf(f, " "); + for (i=1; i<=CLL_k; i++) + { + if ( i>1 ) + { + if ( !want_nls ) fprintf(f, ", "); + } + if ( set_deg(fset[i]) > 3 && elevel == 1 ) + { + int e,m; + fprintf(f, "{"); + for (m=1; m<=3; m++) + { + e=set_int(fset[i]); + fprintf(f, " %s", TerminalString(e)); + set_rm(e, fset[i]); + } + fprintf(f, " ... }"); + } + else s_fprT(f, fset[i]); + if ( want_nls ) fprintf(f, "\n\t"); + } + fprintf(f, "\n"); +} + +static void +#ifdef __USE_PROTOS +verify_context(Predicate *predicate) +#else +verify_context(predicate) +Predicate *predicate; +#endif +{ + if ( predicate == NULL ) return; + + if ( predicate->expr == PRED_OR_LIST || + predicate->expr == PRED_AND_LIST ) + { + verify_context(predicate->down); + return; + } + + if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL && + ((predicate->k > 1 && + !is_single_tuple(predicate->tcontext)) || + ( predicate->k == 1 && + set_deg(predicate->scontext[1])>1 )) ) + { + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k); + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " [you may only want one lookahead %d-sequence to apply.\n", predicate->k); + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " Try using a context guard '(...)? =>'.]\n"); + predicate->source->ctxwarned = 1; + } +} + +/* + * If delta is the set of ambiguous lookahead sequences, then make sure that + * the predicate(s) for productions alt1,alt2 cover the sequences in delta. + * + * For example, + * a : <>? (A B|A C) + * | b + * ; + * b : <>? A B + * | A C + * ; + * + * This should give a warning that (A C) predicts both productions and alt2 + * does not have a predicate in the production that generates (A C). + * + * The warning detection is simple. Let delta = LOOK(alt1) intersection LOOK(alt2). + * Now, if ( delta set-difference context(predicates-for-alt1) != empty then + * alt1 does not "cover" all ambiguous sequences. + * + * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset + * info. Actually, sets are used only if k=1 for this grammar. + */ +static void +#ifdef __USE_PROTOS +ensure_predicates_cover_ambiguous_lookahead_sequences( Junction *alt1, Junction *alt2, char *sub, Tree *ambig ) +#else +ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig ) +Junction *alt1; +Junction *alt2; +char *sub; +Tree *ambig; +#endif +{ + if ( !ParseWithPredicates ) return; + + if ( ambig!=NULL ) + { + Tree *non_covered = NULL; + if ( alt1->predicate!=NULL ) + non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset); + if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt1->altnum, sub); + if ( alt1->predicate!=NULL && non_covered!=NULL ) + { + fprintf(stderr, " upon"); + preorder(non_covered); + } + else if ( alt1->predicate==NULL ) + { + fprintf(stderr, " upon"); + preorder(ambig->down); + } + fprintf(stderr, "\n"); + } + Tfree(non_covered); + non_covered = NULL; + if ( alt2->predicate!=NULL ) + non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset); + if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt2->altnum, sub); + if ( alt2->predicate!=NULL && non_covered!=NULL ) + { + fprintf(stderr, " upon"); + preorder(non_covered); + } + else if ( alt2->predicate==NULL ) + { + fprintf(stderr, " upon"); + preorder(ambig->down); + } + fprintf(stderr, "\n"); + } + Tfree(non_covered); + } + else if ( !set_nil(alt1->fset[1]) ) + { + set delta, non_covered; + delta = set_and(alt1->fset[1], alt2->fset[1]); + non_covered = set_dif(delta, covered_set(alt1->predicate)); + if ( set_deg(non_covered)>0 && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt1->altnum, sub); + if ( alt1->predicate!=NULL ) + { + fprintf(stderr, " upon "); + s_fprT(stderr, non_covered); + } + fprintf(stderr, "\n"); + } + set_free( non_covered ); + non_covered = set_dif(delta, covered_set(alt2->predicate)); + if ( set_deg(non_covered)>0 && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt2->altnum, sub); + if ( alt2->predicate!=NULL ) + { + fprintf(stderr, " upon "); + s_fprT(stderr, non_covered); + } + fprintf(stderr, "\n"); + } + set_free( non_covered ); + set_free( delta ); + } + else fatal_internal("productions have no lookahead in predicate checking routine"); +} + +void +#ifdef __STDC__ +HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype ) +#else +HandleAmbiguity( block, alt1, alt2, jtype ) +Junction *block; +Junction *alt1; +Junction *alt2; +int jtype; +#endif +{ + unsigned **ftbl; + set *fset, b; + int i, numAmbig, n, n2; + Tree *ambig=NULL, *t, *u; + char *sub = ""; + require(block!=NULL, "NULL block"); + require(block->ntype==nJunction, "invalid block"); + + /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */ + fset = (set *) calloc(CLL_k+1, sizeof(set)); + require(fset!=NULL, "cannot allocate fset"); + ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *)); + require(ftbl!=NULL, "cannot allocate ftbl"); + /* create constraint table and count number of possible ambiguities (use<=LL_k) */ + for (n=1,i=1; i<=CLL_k; i++) + { + b = set_and(alt1->fset[i], alt2->fset[i]); + n *= set_deg(b); + fset[i] = set_dup(b); + ftbl[i] = set_pdq(b); + set_free(b); + } + + switch ( jtype ) + { + case aSubBlk: sub = "of (..) "; break; + case aOptBlk: sub = "of {..} "; break; + case aLoopBegin: sub = "of (..)* "; break; + case aLoopBlk: sub = "of (..)* "; break; + case aPlusBlk: sub = "of (..)+ "; break; + case RuleBlk: sub = "of the rule itself "; break; + default : sub = ""; break; + } + + /* If the block is marked as a compressed lookahead only block, then + * simply return; ambiguity warning is given only at warning level 2. + */ + if ( block->approx>0 ) + { + if ( ParseWithPredicates ) + { + alt1->predicate = find_predicates((Node *)alt1->p1); + alt2->predicate = find_predicates((Node *)alt2->p1); + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + } + + if ( WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + } + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* if all sets have degree 1 for k=1 permutation; + * don't bother doing full LL(k) analysis. + * (This "if" block handles the LL(1) case) + */ + n2 = 0; + for (i=1; ifset[i])+set_deg(alt2->fset[i]); + if ( n2==2*(LL_k-1) ) + { +/* TJP: added to fix the case where LL(1) and syntactic predicates didn't + * work. It now recognizes syntactic predicates, but does not like combo: + * LL(1)/syn/sem predicates. (10/24/93) + */ + if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL ) + { + if ( WarningLevel==1 ) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + } + + ambig = NULL; + if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset); + if ( ParseWithPredicates ) + { + alt1->predicate = find_predicates((Node *)alt1->p1); + alt2->predicate = find_predicates((Node *)alt2->p1); + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel == 1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + Tfree(ambig); + return; + } + } +/* end TJP (10/24/93) */ + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + if ( elevel == 3 && LL_k>1 ) + { + preorder(ambig); + fprintf(stderr, "\n"); + Tfree(ambig); + return; + } + Tfree(ambig); + dumpAmbigMsg(fset, stderr, 0); + + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* in case tree construction runs out of memory, set info to make good err msg */ + CurAmbigAlt1 = alt1->altnum; + CurAmbigAlt2 = alt2->altnum; + CurAmbigbtype = sub; + CurAmbigfile = alt1->file; + CurAmbigline = alt1->line; + + /* Don't do full LL(n) analysis if (...)? block because the block, + by definition, defies LL(n) analysis. + If guess (...)? block and ambiguous then don't remove anything from + 2nd alt to resolve ambig. + Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block + since it is much cheaper than LL(n). LL sup 1 ( n ) "covers" the LL(n) + lookahead information. + + Note: LL(n) context cannot be computed for semantic predicates when + followed by (..)?. + + If (..)? then we scream "AAAHHHH! No LL(n) analysis will help" + + Is 'ambig' always defined if we enter this if? I hope so + because the 'ensure...()' func references it. TJP Nov 1993. + */ + if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL ) + { + if ( ParseWithPredicates ) + { + alt1->predicate = find_predicates((Node *)alt1->p1); + alt2->predicate = find_predicates((Node *)alt2->p1); + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel==1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + } + + if ( WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + } + + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* Not resolved with (..)? block. Do full LL(n) analysis */ + + /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */ + ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + + /* are all things in intersection really ambigs? */ + if ( numAmbig < n ) + { + Tree *v; + + /* remove ambig permutation from 2nd alternative to resolve ambig; + * We want to compute the set of artificial tuples, arising from + * LL sup 1 (n) compression, that collide with real tuples from the + * 2nd alternative. This is the set of "special case" tuples that + * the LL sup 1 (n) decision template maps incorrectly. + */ + if ( ambig!=NULL ) + { + for (v=ambig->down; v!=NULL; v=v->right) + { + u = trm_perm(u, v); + } +/* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/ + } + Tfree( t ); + alt1->ftree = tappend(alt1->ftree, u); + alt1->ftree = tleft_factor(alt1->ftree); + } + + if ( ambig==NULL ) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + return; + } + + ambig = tleft_factor(ambig); + +/* TJP: + * At this point, we surely have an LL(k) ambiguity. Check for predicates + */ + if ( ParseWithPredicates ) + { + alt1->predicate = find_predicates((Node *)alt1->p1); + alt2->predicate = find_predicates((Node *)alt2->p1); + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel==1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + /* We found at least one pred for at least one of the alts; + * If warnings are low, just return. + */ + Tfree(ambig); + return; + } + /* else we're gonna give a warning */ + } +/* end TJP addition */ + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + if ( elevel == 3 ) + { + preorder(ambig->down); + fprintf(stderr, "\n"); + Tfree(ambig); + return; + } + Tfree(ambig); + dumpAmbigMsg(fset, stderr, 0); + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); +} + +/* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze + * Return the 1st node of the beta block if present else return j. + */ +Junction * +#ifdef __STDC__ +analysis_point( Junction *j ) +#else +analysis_point( j ) +Junction *j; +#endif +{ + Junction *gblock; + + if ( j->ntype!=nJunction ) return j; + gblock = first_item_is_guess_block((Junction *)j); + + if ( gblock!=NULL ) + { + Junction *past = gblock->end; + Junction *p; + require(past!=NULL, "analysis_point: no end block on (...)? block"); + + for (p=(Junction *)past->p1; p!=NULL; ) + { + if ( p->ntype==nAction ) + { + p=(Junction *)((ActionNode *)p)->next; + continue; + } + if ( p->ntype!=nJunction ) + { + return (Junction *)past->p1; + } + if ( p->jtype==EndBlk || p->jtype==EndRule ) + { + return j; + } + p=(Junction *)p->p1; + } + } + return j; +} + +set +#ifdef __STDC__ +First( Junction *j, int k, int jtype, int *max_k ) +#else +First( j, k, jtype, max_k ) +Junction *j; +int k; +int jtype; +int *max_k; +#endif +{ + Junction *alt1, *alt2; + set a, rk, fCurBlk; + int savek; + int p1, p2; + require(j->ntype==nJunction, "First: non junction passed"); + + /* C o m p u t e F I R S T s e t w i t h k l o o k a h e a d */ + fCurBlk = rk = empty; + for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2) + { + Junction *p = analysis_point((Junction *)alt1->p1); + REACH(p, k, &rk, alt1->fset[k]); + require(set_nil(rk), "rk != nil"); + set_free(rk); + set_orin(&fCurBlk, alt1->fset[k]); + } + + /* D e t e c t A m b i g u i t i e s */ + *max_k = 1; + for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++) + { + for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++) + { + savek = k; + a = set_and(alt1->fset[k], alt2->fset[k]); + while ( !set_nil(a) ) + { + /* if we have hit the max k requested, just give warning */ + if ( j->approx==k ) { + } + + if ( k==CLL_k ) + { +#ifdef NOT_USED + int save_LL_k = LL_k; + int save_CLL_k = CLL_k; + /* Get new LL_k from interactive feature if enabled */ + if ( AImode ) + AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k); +#endif + *max_k = CLL_k; + HandleAmbiguity(j, alt1, alt2, jtype); + break; + } + else + { + Junction *p = analysis_point((Junction *)alt1->p1); + Junction *q = analysis_point((Junction *)alt2->p1); + k++; /* attempt ambig alts again with more lookahead */ + REACH(p, k, &rk, alt1->fset[k]); + require(set_nil(rk), "rk != nil"); + REACH(q, k, &rk, alt2->fset[k]); + require(set_nil(rk), "rk != nil"); + set_free(a); + a = set_and(alt1->fset[k], alt2->fset[k]); + if ( k > *max_k ) *max_k = k; + } + } + set_free(a); + k = savek; + } + } + + return fCurBlk; +} diff --git a/antlr/fset2.c b/antlr/fset2.c new file mode 100755 index 0000000..5491791 --- /dev/null +++ b/antlr/fset2.c @@ -0,0 +1,1207 @@ +/* + * fset2.c + * + * $Id: fset2.c,v 1.7 95/10/05 11:57:01 parrt Exp $ + * $Revision: 1.7 $ + * + * Compute FIRST sets for full LL(k) + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ +#include +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#ifdef __STDC__ +#include +#else +#include +#endif +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +extern char tokens[]; + +extern char *PRED_AND_LIST; +extern char *PRED_OR_LIST; + +/* ick! globals. Used by permute() to track which elements of a set have been used */ +static int *findex; +static set *fset; +static unsigned **ftbl; +static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */ +int ConstrainSearch; +static int maxk; /* set to initial k upon tree construction request */ +static Tree *FreeList = NULL; + +#ifdef __STDC__ +static int tmember_of_context(Tree *, Predicate *); +#else +static int tmember_of_context(); +#endif + +/* Do root + * Then each sibling + */ +void +#ifdef __STDC__ +preorder( Tree *tree ) +#else +preorder( tree ) +Tree *tree; +#endif +{ + if ( tree == NULL ) return; + if ( tree->down != NULL ) fprintf(stderr, " ("); + if ( tree->token == ALT ) fprintf(stderr, " J"); + else fprintf(stderr, " %s", TerminalString(tree->token)); + if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk); + preorder(tree->down); + if ( tree->down != NULL ) fprintf(stderr, " )"); + preorder(tree->right); +} + +/* check the depth of each primary sibling to see that it is exactly + * k deep. e.g.; + * + * ALT + * | + * A ------- B + * | | + * C -- D E + * + * Remove all branches <= k deep. + * + * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work. + */ +Tree * +#ifdef __STDC__ +prune( Tree *t, int k ) +#else +prune( t, k ) +Tree *t; +int k; +#endif +{ + if ( t == NULL ) return NULL; + if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree"); + if ( t->right!=NULL ) t->right = prune(t->right, k); + if ( k>1 ) + { + if ( t->down!=NULL ) t->down = prune(t->down, k-1); + if ( t->down == NULL ) + { + Tree *r = t->right; + t->right = NULL; + Tfree(t); + return r; + } + } + return t; +} + +/* build a tree (root child1 child2 ... NULL) */ +#ifdef __STDC__ +Tree *tmake(Tree *root, ...) +#else +Tree *tmake(va_alist) +va_dcl +#endif +{ + Tree *w; + va_list ap; + Tree *child, *sibling=NULL, *tail; +#ifndef __STDC__ + Tree *root; +#endif + +#ifdef __STDC__ + va_start(ap, root); +#else + va_start(ap); + root = va_arg(ap, Tree *); +#endif + child = va_arg(ap, Tree *); + while ( child != NULL ) + { +#ifdef DUM + /* added "find end of child" thing TJP March 1994 */ + for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */ +#else + w = child; +#endif + + if ( sibling == NULL ) {sibling = child; tail = w;} + else {tail->right = child; tail = w;} + child = va_arg(ap, Tree *); + } + + /* was "root->down = sibling;" */ + if ( root==NULL ) root = sibling; + else root->down = sibling; + + va_end(ap); + return root; +} + +Tree * +#ifdef __STDC__ +tnode( int tok ) +#else +tnode( tok ) +int tok; +#endif +{ + Tree *p, *newblk; + static int n=0; + + if ( FreeList == NULL ) + { + /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/ + if ( TreeResourceLimit > 0 ) + { + if ( (n+TreeBlockAllocSize) >= TreeResourceLimit ) + { + fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); + fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n", + CurAmbigAlt1, + CurAmbigAlt2, + CurAmbigbtype); + exit(PCCTS_EXIT_FAILURE); + } + } + newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree)); + if ( newblk == NULL ) + { + fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); + fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n", + CurAmbigAlt1, + CurAmbigAlt2, + CurAmbigbtype); + exit(PCCTS_EXIT_FAILURE); + } + n += TreeBlockAllocSize; + for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++) + { + p->right = FreeList; /* add all new Tree nodes to Free List */ + FreeList = p; + } + } + p = FreeList; + FreeList = FreeList->right; /* remove a tree node */ + p->right = NULL; /* zero out ptrs */ + p->down = NULL; + p->token = tok; +#ifdef TREE_DEBUG + require(!p->in_use, "tnode: node in use!"); + p->in_use = 1; +#endif + return p; +} + +static Tree * +#ifdef __STDC__ +eofnode( int k ) +#else +eofnode( k ) +int k; +#endif +{ + Tree *t=NULL; + int i; + + for (i=1; i<=k; i++) + { + t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL); + } + return t; +} + + + +void +#ifdef __STDC__ +_Tfree( Tree *t ) +#else +_Tfree( t ) +Tree *t; +#endif +{ + if ( t!=NULL ) + { +#ifdef TREE_DEBUG + require(t->in_use, "_Tfree: node not in use!"); + t->in_use = 0; +#endif + t->right = FreeList; + FreeList = t; + } +} + +/* tree duplicate */ +Tree * +#ifdef __STDC__ +tdup( Tree *t ) +#else +tdup( t ) +Tree *t; +#endif +{ + Tree *u; + + if ( t == NULL ) return NULL; + u = tnode(t->token); + u->v.rk = t->v.rk; + u->right = tdup(t->right); + u->down = tdup(t->down); + return u; +} + +/* tree duplicate (assume tree is a chain downwards) */ +Tree * +#ifdef __STDC__ +tdup_chain( Tree *t ) +#else +tdup_chain( t ) +Tree *t; +#endif +{ + Tree *u; + + if ( t == NULL ) return NULL; + u = tnode(t->token); + u->v.rk = t->v.rk; + u->down = tdup(t->down); + return u; +} + +Tree * +#ifdef __STDC__ +tappend( Tree *t, Tree *u ) +#else +tappend( t, u ) +Tree *t; +Tree *u; +#endif +{ + Tree *w; + + /*fprintf(stderr, "tappend("); + preorder(t); fprintf(stderr, ","); + preorder(u); fprintf(stderr, " )\n");*/ + if ( t == NULL ) return u; + if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u); + for (w=t; w->right!=NULL; w=w->right) {;} + w->right = u; + return t; +} + +/* dealloc all nodes in a tree */ +void +#ifdef __STDC__ +Tfree( Tree *t ) +#else +Tfree( t ) +Tree *t; +#endif +{ + if ( t == NULL ) return; + Tfree( t->down ); + Tfree( t->right ); + _Tfree( t ); +} + +/* find all children (alts) of t that require remaining_k nodes to be LL_k + * tokens long. + * + * t-->o + * | + * a1--a2--...--an <-- LL(1) tokens + * | | | + * b1 b2 ... bn <-- LL(2) tokens + * | | | + * . . . + * . . . + * z1 z2 ... zn <-- LL(LL_k) tokens + * + * We look for all [Ep] needing remaining_k nodes and replace with u. + * u is not destroyed or actually used by the tree (a copy is made). + */ +Tree * +#ifdef __STDC__ +tlink( Tree *t, Tree *u, int remaining_k ) +#else +tlink( t, u, remaining_k ) +Tree *t; +Tree *u; +int remaining_k; +#endif +{ + Tree *p; + require(remaining_k!=0, "tlink: bad tree"); + + if ( t==NULL ) return NULL; + /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/ + if ( t->token == EpToken && t->v.rk == remaining_k ) + { + require(t->down==NULL, "tlink: invalid tree"); + if ( u == NULL ) return t->right; + p = tdup( u ); + p->right = t->right; + _Tfree( t ); + return p; + } + t->down = tlink(t->down, u, remaining_k); + t->right = tlink(t->right, u, remaining_k); + return t; +} + +/* remove as many ALT nodes as possible while still maintaining semantics */ +Tree * +#ifdef __STDC__ +tshrink( Tree *t ) +#else +tshrink( t ) +Tree *t; +#endif +{ + if ( t == NULL ) return NULL; + t->down = tshrink( t->down ); + t->right = tshrink( t->right ); + if ( t->down == NULL ) + { + if ( t->token == ALT ) + { + Tree *u = t->right; + _Tfree(t); + return u; /* remove useless alts */ + } + return t; + } + + /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */ + if ( t->token == ALT && t->down->right == NULL) + { + Tree *u = t->down; + u->right = t->right; + _Tfree( t ); + return u; + } + /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */ + if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL ) + { + Tree *u = t->down->down; + _Tfree( t->down ); + t->down = u; + return t; + } + return t; +} + +Tree * +#ifdef __STDC__ +tflatten( Tree *t ) +#else +tflatten( t ) +Tree *t; +#endif +{ + if ( t == NULL ) return NULL; + t->down = tflatten( t->down ); + t->right = tflatten( t->right ); + if ( t->down == NULL ) return t; + + if ( t->token == ALT ) + { + Tree *u; + /* find tail of children */ + for (u=t->down; u->right!=NULL; u=u->right) {;} + u->right = t->right; + u = t->down; + _Tfree( t ); + return u; + } + return t; +} + +Tree * +#ifdef __STDC__ +tJunc( Junction *p, int k, set *rk ) +#else +tJunc( p, k, rk ) +Junction *p; +int k; +set *rk; +#endif +{ + Tree *t=NULL, *u=NULL; + Junction *alt; + Tree *tail, *r; + +#ifdef DBG_TRAV + fprintf(stderr, "tJunc(%d): %s in rule %s\n", k, + decodeJType[p->jtype], ((Junction *)p)->rname); +#endif + if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || + p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk ) + { + if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) { + require(p->lock!=NULL, "rJunc: lock array is NULL"); + if ( p->lock[k] ) return NULL; + p->lock[k] = TRUE; + } + TRAV(p->p1, k, rk, tail); + if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;} + r = tmake(tnode(ALT), tail, NULL); + for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2) + { + /* if this is one of the added optional alts for (...)+ then break */ + if ( alt->ignore ) break; + + if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;} + else + { + TRAV(alt->p1, k, rk, tail->right); + if ( tail->right != NULL ) tail = tail->right; + } + } + if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE; +#ifdef DBG_TREES + fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n"); +#endif + if ( r->down == NULL ) {_Tfree(r); return NULL;} + return r; + } + + if ( p->jtype==EndRule ) + { + if ( p->halt ) /* don't want FOLLOW here? */ + { +/* if ( ContextGuardTRAV ) return NULL;*/ + set_orel(k, rk); /* indicate this k value needed */ + t = tnode(EpToken); + t->v.rk = k; + return t; + } + require(p->lock!=NULL, "rJunc: lock array is NULL"); + if ( p->lock[k] ) return NULL; + /* if no FOLLOW assume k EOF's */ + if ( p->p1 == NULL ) return eofnode(k); + p->lock[k] = TRUE; + } + + if ( p->p2 == NULL ) + { + TRAV(p->p1, k, rk,t); + if ( p->jtype==EndRule ) p->lock[k]=FALSE; + return t; + } + TRAV(p->p1, k, rk, t); + if ( p->jtype!=RuleBlk ) TRAV(p->p2, k, rk, u); + if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */ + + if ( t==NULL ) return tmake(tnode(ALT), u, NULL); + return tmake(tnode(ALT), t, u, NULL); +} + +Tree * +#ifdef __STDC__ +tRuleRef( RuleRefNode *p, int k, set *rk_out ) +#else +tRuleRef( p, k, rk_out ) +RuleRefNode *p; +int k; +set *rk_out; +#endif +{ + int k2; + Tree *t, *u; + Junction *r; + set rk, rk2; + int save_halt; + RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text); + +#ifdef DBG_TRAV + fprintf(stderr, "tRuleRef: %s\n", p->text); +#endif + if ( q == NULL ) + { + TRAV(p->next, k, rk_out, t);/* ignore undefined rules */ + return t; + } + rk = rk2 = empty; + r = RulePtr[q->rulenum]; + if ( r->lock[k] ) return NULL; + save_halt = r->end->halt; + r->end->halt = TRUE; /* don't let reach fall off end of rule here */ + TRAV(r, k, &rk, t); + r->end->halt = save_halt; +#ifdef DBG_TREES + fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n"); +#endif + t = tshrink( t ); + while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */ + k2 = set_int(rk); + set_rm(k2, rk); + TRAV(p->next, k2, &rk2, u); + t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */ + } + set_free(rk); /* rk is empty, but free it's memory */ + set_orin(rk_out, rk2); /* remember what we couldn't do */ + set_free(rk2); + return t; +} + +Tree * +#ifdef __STDC__ +tToken( TokNode *p, int k, set *rk ) +#else +tToken( p, k, rk ) +TokNode *p; +int k; +set *rk; +#endif +{ + Tree *t, *tset=NULL, *u; + + if ( ConstrainSearch ) + { + require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set"); + constrain = &fset[maxk-k+1]; + } + +#ifdef DBG_TRAV + fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token)); + if ( ConstrainSearch ) { + fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n"); + } +#endif + /* is it a meta token (set of tokens)? */ + if ( !set_nil(p->tset) ) + { + unsigned e=0; + set a; + Tree *n, *tail = NULL; + + if ( ConstrainSearch ) a = set_and(p->tset, *constrain); + else a = set_dup(p->tset); +#ifdef DUM + if ( ConstrainSearch ) a = set_dif(p->tset, *constrain); + else a = set_dup(p->tset); +#endif + for (; !set_nil(a); set_rm(e, a)) + { + e = set_int(a); + n = tnode(e); + if ( tset==NULL ) { tset = n; tail = n; } + else { tail->right = n; tail = n; } + } + set_free( a ); + } + else if ( ConstrainSearch && !set_el(p->token, *constrain) ) + { +/* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token), + k);*/ + return NULL; + } + else tset = tnode( p->token ); + + if ( k == 1 ) return tset; + + TRAV(p->next, k-1, rk, t); + /* here, we are positive that, at least, this tree will not contribute + * to the LL(2) tree since it will be too shallow, IF t==NULL. + * If doing a context guard walk, then don't prune. + */ + if ( t == NULL && !ContextGuardTRAV ) /* tree will be too shallow */ + { + if ( tset!=NULL ) Tfree( tset ); + return NULL; + } +#ifdef DBG_TREES + fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n"); +#endif + + /* if single token root, then just make new tree and return */ + if ( set_nil(p->tset) ) return tmake(tnode(p->token), t, NULL); + + /* here we must make a copy of t as a child of each element of the tset; + * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) ) + */ + for (u=tset; u!=NULL; u=u->right) + { + /* make a copy of t and hook it onto bottom of u */ + u->down = tdup(t); + } + Tfree( t ); +#ifdef DBG_TREES + fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n"); +#endif + return tset; +} + +Tree * +#ifdef __STDC__ +tAction( ActionNode *p, int k, set *rk ) +#else +tAction( p, k, rk ) +ActionNode *p; +int k; +set *rk; +#endif +{ + Tree *t; + + /*fprintf(stderr, "tAction\n");*/ + TRAV(p->next, k, rk, t); + return t; +} + +/* see if e exists in s as a possible input permutation (e is always a chain) */ +int +#ifdef __STDC__ +tmember( Tree *e, Tree *s ) +#else +tmember( e, s ) +Tree *e; +Tree *s; +#endif +{ + if ( e==NULL||s==NULL ) return 0; + /*fprintf(stderr, "tmember("); + preorder(e); fprintf(stderr, ","); + preorder(s); fprintf(stderr, " )\n");*/ + if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down); + if ( e->token!=s->token ) + { + if ( s->right==NULL ) return 0; + return tmember(e, s->right); + } + if ( e->down==NULL && s->down == NULL ) return 1; + if ( tmember(e->down, s->down) ) return 1; + if ( s->right==NULL ) return 0; + return tmember(e, s->right); +} + +/* see if e exists in s as a possible input permutation (e is always a chain); + * Only check s to the depth of e. In other words, 'e' can be a shorter + * sequence than s. + */ +int +#ifdef __STDC__ +tmember_constrained( Tree *e, Tree *s) +#else +tmember_constrained( e, s ) +Tree *e; +Tree *s; +#endif +{ + if ( e==NULL||s==NULL ) return 0; +/* fprintf(stderr, "tmember_constrained("); + preorder(e); fprintf(stderr, ","); + preorder(s); fprintf(stderr, " )\n");*/ + if ( s->token == ALT && s->right == NULL ) + return tmember_constrained(e, s->down); + if ( e->token!=s->token ) + { + if ( s->right==NULL ) return 0; + return tmember_constrained(e, s->right); + } + if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */ + if ( tmember_constrained(e->down, s->down) ) return 1; + if ( s->right==NULL ) return 0; + return tmember_constrained(e, s->right); +} + +/* combine (? (A t) ... (A u) ...) into (? (A t u)) */ +Tree * +#ifdef __STDC__ +tleft_factor( Tree *t ) +#else +tleft_factor( t ) +Tree *t; +#endif +{ + Tree *u, *v, *trail, *w; + + /* left-factor what is at this level */ + if ( t == NULL ) return NULL; + for (u=t; u!=NULL; u=u->right) + { + trail = u; + v=u->right; + while ( v!=NULL ) + { + if ( u->token == v->token ) + { + if ( u->down!=NULL ) + { + for (w=u->down; w->right!=NULL; w=w->right) {;} + w->right = v->down; /* link children together */ + } + else u->down = v->down; + trail->right = v->right; /* unlink factored node */ + _Tfree( v ); + v = trail->right; + } + else {trail = v; v=v->right;} + } + } + /* left-factor what is below */ + for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down ); + return t; +} + +/* remove the permutation p from t if present */ +Tree * +#ifdef __STDC__ +trm_perm( Tree *t, Tree *p ) +#else +trm_perm( t, p ) +Tree *t; +Tree *p; +#endif +{ + /* + fprintf(stderr, "trm_perm("); + preorder(t); fprintf(stderr, ","); + preorder(p); fprintf(stderr, " )\n"); + */ + if ( t == NULL || p == NULL ) return NULL; + if ( t->token == ALT ) + { + t->down = trm_perm(t->down, p); + if ( t->down == NULL ) /* nothing left below, rm cur node */ + { + Tree *u = t->right; + _Tfree( t ); + return trm_perm(u, p); + } + t->right = trm_perm(t->right, p); /* look for more instances of p */ + return t; + } + if ( p->token != t->token ) /* not found, try a sibling */ + { + t->right = trm_perm(t->right, p); + return t; + } + t->down = trm_perm(t->down, p->down); + if ( t->down == NULL ) /* nothing left below, rm cur node */ + { + Tree *u = t->right; + _Tfree( t ); + return trm_perm(u, p); + } + t->right = trm_perm(t->right, p); /* look for more instances of p */ + return t; +} + +/* add the permutation 'perm' to the LL_k sets in 'fset' */ +void +#ifdef __STDC__ +tcvt( set *fset, Tree *perm ) +#else +tcvt( fset, perm ) +set *fset; +Tree *perm; +#endif +{ + if ( perm==NULL ) return; + set_orel(perm->token, fset); + tcvt(fset+1, perm->down); +} + +/* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1]) + * as a child. + */ +Tree * +#ifdef __STDC__ +permute( int k, int max_k ) +#else +permute( k, max_k ) +int k, max_k; +#endif +{ + Tree *t, *u; + + if ( k>max_k ) return NULL; + if ( ftbl[k][findex[k]] == nil ) return NULL; + t = permute(k+1, max_k); + if ( t==NULL&&k maxk will have to change. + */ +Tree * +#ifdef __STDC__ +VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig ) +#else +VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig ) +Junction *alt1; +Junction *alt2; +unsigned **ft; +set *fs; +Tree **t; +Tree **u; +int *numAmbig; +#endif +{ + set rk; + Tree *perm, *ambig=NULL; + Junction *p; + int k; + + maxk = LL_k; /* NOTE: for now, we look for LL_k */ + ftbl = ft; + fset = fs; + constrain = &(fset[1]); + findex = (int *) calloc(LL_k+1, sizeof(int)); + if ( findex == NULL ) + { + fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); + fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n", + CurAmbigAlt1, + CurAmbigAlt2, + CurAmbigbtype); + exit(PCCTS_EXIT_FAILURE); + } + for (k=1; k<=LL_k; k++) findex[k] = 0; + + rk = empty; + ConstrainSearch = 1; /* consider only tokens in ambig sets */ + + p = analysis_point((Junction *)alt1->p1); + TRAV(p, LL_k, &rk, *t); + *t = tshrink( *t ); + *t = tflatten( *t ); + *t = prune(*t, LL_k); + *t = tleft_factor( *t ); +/* fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/ + if ( *t == NULL ) + { +/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/ + Tfree( *t ); /* kill if impossible to have ambig */ + *t = NULL; + } + + p = analysis_point((Junction *)alt2->p1); + TRAV(p, LL_k, &rk, *u); + *u = tshrink( *u ); + *u = tflatten( *u ); + *u = prune(*u, LL_k); + *u = tleft_factor( *u ); +/* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/ + if ( *u == NULL ) + { +/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/ + Tfree( *u ); + *u = NULL; + } + + for (k=1; k<=LL_k; k++) set_clr( fs[k] ); + + ambig = tnode(ALT); + k = 0; + if ( *t!=NULL && *u!=NULL ) + { + while ( (perm=permute(1,LL_k))!=NULL ) + { +/* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/ + if ( tmember(perm, *t) && tmember(perm, *u) ) + { +/* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/ + k++; + perm->right = ambig->down; + ambig->down = perm; + tcvt(&(fs[1]), perm); + } + else Tfree( perm ); + } + } + + *numAmbig = k; + if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;} + free( (char *)findex ); +/* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/ + return ambig; +} + +static Tree * +#ifdef __STDC__ +bottom_of_chain( Tree *t ) +#else +bottom_of_chain( t ) +Tree *t; +#endif +{ + if ( t==NULL ) return NULL; + for (; t->down != NULL; t=t->down) {;} + return t; +} + +/* + * Make a tree from k sets where the degree of the first k-1 sets is 1. + */ +Tree * +#ifdef __STDC__ +make_tree_from_sets( set *fset1, set *fset2 ) +#else +make_tree_from_sets( fset1, fset2 ) +set *fset1; +set *fset2; +#endif +{ + set inter; + int i; + Tree *t=NULL, *n, *u; + unsigned *p,*q; + require(LL_k>1, "make_tree_from_sets: LL_k must be > 1"); + + /* do the degree 1 sets first */ + for (i=1; i<=LL_k-1; i++) + { + inter = set_and(fset1[i], fset2[i]); + require(set_deg(inter)==1, "invalid set to tree conversion"); + n = tnode(set_int(inter)); + if (t==NULL) t=n; else tmake(t, n, NULL); + set_free(inter); + } + + /* now add the chain of tokens at depth k */ + u = bottom_of_chain(t); + inter = set_and(fset1[LL_k], fset2[LL_k]); + if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq"); + /* first one is linked to bottom, then others are sibling linked */ + n = tnode(*p++); + u->down = n; + u = u->down; + while ( *p != nil ) + { + n = tnode(*p); + u->right = n; + u = u->right; + p++; + } + free((char *)q); + + return t; +} + +/* create and return the tree of lookahead k-sequences that are in t, but not + * in the context of predicates in predicate list p. + */ +Tree * +#ifdef __STDC__ +tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 ) +#else +tdif( ambig_tuples, p, fset1, fset2 ) +Tree *ambig_tuples; +Predicate *p; +set *fset1; +set *fset2; +#endif +{ + unsigned **ft; + Tree *dif=NULL; + Tree *perm; + set b; + int i,k; + + if ( p == NULL ) return tdup(ambig_tuples); + + ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *)); + require(ft!=NULL, "cannot allocate ft"); + for (i=1; i<=CLL_k; i++) + { + b = set_and(fset1[i], fset2[i]); + ft[i] = set_pdq(b); + set_free(b); + } + findex = (int *) calloc(LL_k+1, sizeof(int)); + if ( findex == NULL ) + { + fatal_internal("out of memory in tdif while checking predicates"); + } + for (k=1; k<=LL_k; k++) findex[k] = 0; + +#ifdef DBG_TRAV + fprintf(stderr, "tdif_%d[", p->k); + preorder(ambig_tuples); + fprintf(stderr, ","); + preorder(p->tcontext); + fprintf(stderr, "] ="); +#endif + + ftbl = ft; + while ( (perm=permute(1,p->k))!=NULL ) + { +#ifdef DBG_TRAV + fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n"); +#endif + if ( tmember_constrained(perm, ambig_tuples) && + !tmember_of_context(perm, p) ) + { +#ifdef DBG_TRAV + fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n"); +#endif + k++; + if ( dif==NULL ) dif = perm; + else + { + perm->right = dif; + dif = perm; + } + } + else Tfree( perm ); + } + +#ifdef DBG_TRAV + preorder(dif); + fprintf(stderr, "\n"); +#endif + + for (i=1; i<=CLL_k; i++) free( (char *)ft[i] ); + free((char *)ft); + free((char *)findex); + + return dif; +} + +/* is lookahead sequence t a member of any context tree for any + * predicate in p? + */ +static int +#ifdef __STDC__ +tmember_of_context( Tree *t, Predicate *p ) +#else +tmember_of_context( t, p ) +Tree *t; +Predicate *p; +#endif +{ + for (; p!=NULL; p=p->right) + { + if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST ) + return tmember_of_context(t, p->down); + if ( tmember_constrained(t, p->tcontext) ) return 1; + if ( tmember_of_context(t, p->down) ) return 1; + } + return 0; +} + +int +#ifdef __STDC__ +is_single_tuple( Tree *t ) +#else +is_single_tuple( t ) +Tree *t; +#endif +{ + if ( t == NULL ) return 0; + if ( t->right != NULL ) return 0; + if ( t->down == NULL ) return 1; + return is_single_tuple(t->down); +} + +/* + * Look at a (...)? generalized-predicate context-guard and compute + * either a lookahead set (k==1) or a lookahead tree for k>1. The + * k level is determined by the guard itself rather than the LL_k + * variable. For example, ( A B )? is an LL(2) guard and ( ID )? + * is an LL(1) guard. For the moment, you can only have a single + * tuple in the guard. Physically, the block must look like this + * --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o-- + * An error is printed for any other type. + */ +Predicate * +#ifdef __STDC__ +computePredicateFromContextGuard(Graph blk) +#else +computePredicateFromContextGuard(blk) +Graph blk; +#endif +{ + Junction *junc = (Junction *)blk.left, *p; + Tree *t; + Predicate *pred = NULL; + set scontext, rk; + require(junc!=NULL && junc->ntype == nJunction, "bad context guard"); + + rk = empty; + p = junc; + pred = new_pred(); + pred->k = LL_k; + if ( LL_k > 1 ) + { + ConstrainSearch = 0; + ContextGuardTRAV = 1; + TRAV(p, LL_k, &rk, t); + ContextGuardTRAV = 0; + set_free(rk); + t = tshrink( t ); + t = tflatten( t ); + t = tleft_factor( t ); +/* + fprintf(stderr, "ctx guard:"); + preorder(t); + fprintf(stderr, "\n"); +*/ + pred->tcontext = t; + } + else + { + REACH(p, 1, &rk, scontext); + require(set_nil(rk), "rk != nil"); + set_free(rk); +/* + fprintf(stderr, "LL(1) ctx guard is:"); + s_fprT(stderr, scontext); + fprintf(stderr, "\n"); +*/ + pred->scontext[1] = scontext; + } + + return pred; +} diff --git a/antlr/gen.c b/antlr/gen.c new file mode 100755 index 0000000..0b2de9a --- /dev/null +++ b/antlr/gen.c @@ -0,0 +1,2790 @@ +/* + * gen.c + * + * $Id: gen.c,v 1.7 95/09/26 12:58:40 parrt Exp $ + * $Revision: 1.7 $ + * + * Generate C code (ANSI, K&R, C++) + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ +#include +#include +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +#define NumExprPerLine 4 +static int on1line=0; +static set tokensRefdInBlock; + +extern char *PRED_AND_LIST; +extern char *PRED_OR_LIST; + + + /* T r a n s l a t i o n T a b l e s */ + +/* C_Trans[node type] == pointer to function that knows how to translate that node. */ +#ifdef __cplusplus +void (*C_Trans[NumNodeTypes+1])(...) = { + NULL, + NULL, /* See next table. +Junctions have many types */ + (void (*)(...)) genRuleRef, + (void (*)(...)) genToken, + (void (*)(...)) genAction +}; +#else +void (*C_Trans[NumNodeTypes+1])() = { + NULL, + NULL, /* See next table. +Junctions have many types */ + genRuleRef, + genToken, + genAction +}; +#endif + +/* C_JTrans[Junction type] == pointer to function that knows how to translate that + * kind of junction node. + */ +#ifdef __cplusplus +void (*C_JTrans[NumJuncTypes+1])(...) = { + NULL, + (void (*)(...)) genSubBlk, + (void (*)(...)) genOptBlk, + (void (*)(...)) genLoopBlk, + (void (*)(...)) genEndBlk, + (void (*)(...)) genRule, + (void (*)(...)) genJunction, + (void (*)(...)) genEndRule, + (void (*)(...)) genPlusBlk, + (void (*)(...)) genLoopBegin +}; +#else +void (*C_JTrans[NumJuncTypes+1])() = { + NULL, + genSubBlk, + genOptBlk, + genLoopBlk, + genEndBlk, + genRule, + genJunction, + genEndRule, + genPlusBlk, + genLoopBegin +}; +#endif + +#define PastWhiteSpace(s) while (*(s) == ' ' || *(s) == '\t') {s++;} + +static int tabs = 0; +#define TAB { int i; for (i=0; i>? predicates"); +} + +void +#ifdef __USE_PROTOS +freeBlkFsets( Junction *q ) +#else +freeBlkFsets( q ) +Junction *q; +#endif +{ + int i; + Junction *alt; + require(q!=NULL, "freeBlkFsets: invalid node"); + + for (alt=q; alt != NULL; alt= (Junction *) alt->p2 ) + { + for (i=1; i<=CLL_k; i++) set_free(alt->fset[i]); + } +} + +/* + * Generate a local variable allocation for each token references + * in this block. + */ +static void +#ifdef __USE_PROTOS +genTokenPointers( Junction *q ) +#else +genTokenPointers( q ) +Junction *q; +#endif +{ + /* Rule refs are counted and can be referenced, but their + * value is not set to anything useful ever. + * + * The ptrs are to be named _tij where i is the current level + * and j is the element number within an alternative. + */ + int first=1, t=0; + set a; + tokensRefdInBlock = q->tokrefs; + + if ( set_deg(q->tokrefs) == 0 ) return; + a = set_dup(q->tokrefs); + gen("ANTLRTokenPtr "); + for (; !set_nil(a); set_rm(t, a)) + { + t = set_int(a); + if ( first ) first = 0; + else _gen(","); + if ( !DontCopyTokens ) _gen2("_tv%d%d,", BlkLevel, t); + _gen2("_t%d%d", BlkLevel, t); + if ( !DontCopyTokens ) {_gen2("= &_tv%d%d", BlkLevel, t);} + else _gen("=NULL"); + } + _gen(";\n"); + set_free(a); +} + +static int +#ifdef __USE_PROTOS +hasDefaultException(ExceptionGroup *eg) +#else +hasDefaultException(eg) +ExceptionGroup *eg; +#endif +{ + ListNode *q; + + for (q = eg->handlers->next; q!=NULL; q=q->next) + { + ExceptionHandler *eh = (ExceptionHandler *)q->elem; + if ( strcmp("default", eh->signalname)==0 ) { + return 1; + } + } + return 0; +} + +static void +#ifdef __USE_PROTOS +dumpException(ExceptionGroup *eg, int no_default_case) +#else +dumpException(eg, no_default_case) +ExceptionGroup *eg; +int no_default_case; +#endif +{ + gen1("switch ( _signal ) {\n", eg->label==NULL?"":eg->label); + { + ListNode *q; + for (q = eg->handlers->next; q!=NULL; q=q->next) + { + ExceptionHandler *eh = (ExceptionHandler *)q->elem; + if ( strcmp("default", eh->signalname)==0 ) { + gen("default :\n"); + tabs++; + dumpAction(eh->action, output, tabs, -1, 1, 1); + gen("_signal = NoSignal;\n"); + tabs--; + gen("}\n"); + return; + } + gen1("case %s :\n", eh->signalname); + tabs++; + if ( eh->action != NULL ) + { + dumpAction(eh->action, output, tabs, -1, 1, 1); + gen("_signal = NoSignal;\n"); + gen("break;\n"); + } + tabs--; + } + } + if ( no_default_case ) return; + + gen("default :\n"); + tabs++; +/* gen("*_retsignal = _signal;\n");*/ + gen("goto _handler;\n"); + tabs--; + gen("}\n"); +} + +static void +#ifdef __USE_PROTOS +dumpExceptions(ListNode *list) +#else +dumpExceptions(list) +ListNode *list; +#endif +{ + ListNode *p; + + for (p = list->next; p!=NULL; p=p->next) + { + ExceptionGroup *eg = (ExceptionGroup *) p->elem; + _gen2("%s%s_handler:\n", + eg->label==NULL?"":eg->label, + eg->altID==NULL?"":eg->altID); + if ( eg->altID!=NULL ) dumpException(eg, 0); + else { + /* This must be the rule exception handler */ + dumpException(eg, 1); + if ( !hasDefaultException(eg) ) + { + gen("default :\n"); + tabs++; + gen("zzdflthandlers(_signal,_retsignal);\n"); + tabs--; + gen("}\n"); + } + } + } +} + +/* For each element label that is found in a rule, generate a unique + * Attribute (and AST pointer if GenAST) variable. + */ +void +#ifdef __USE_PROTOS +genElementLabels(ListNode *list) +#else +genElementLabels(list) +ListNode *list; +#endif +{ + int first=1; + ListNode *p; + + if ( GenCC ) {gen("ANTLRTokenPtr");} + else {gen("Attrib");} + for (p = list->next; p!=NULL; p=p->next) + { + char *ep = (char *)p->elem; + if ( first ) first = 0; + else _gen(","); + if ( GenCC ) {_gen1(" %s=NULL",ep);} + else {_gen1(" %s",ep);} + } + _gen(";\n"); + + if ( !GenAST ) return; + + first = 1; + gen("AST"); + for (p = list->next; p!=NULL; p=p->next) + { + char *ep = (char *)p->elem; + if ( first ) first = 0; + else _gen(","); + _gen1(" *%s_ast=NULL",ep); + } + _gen(";\n"); +} + +/* + * Generate a local variable allocation for each token or rule reference + * in this block. + */ +static void +#ifdef __USE_PROTOS +genASTPointers( Junction *q ) +#else +genASTPointers( q ) +Junction *q; +#endif +{ + int first=1, t; + set a; + + a = set_or(q->tokrefs, q->rulerefs); + if ( set_deg(a) > 0 ) + { + gen("AST "); + for (; !set_nil(a); set_rm(t, a)) + { + t = set_int(a); + if ( first ) first = 0; + else _gen(","); + _gen2("*_ast%d%d=NULL", BlkLevel, t); + } + set_free(a); + } + _gen(";\n"); +} + +static void +#ifdef __USE_PROTOS +BLOCK_Head( void ) +#else +BLOCK_Head( ) +#endif +{ + gen("{\n"); + tabs++; + if ( !GenCC ) gen1("zzBLOCK(zztasp%d);\n", BlkLevel); +} + +static void +#ifdef __USE_PROTOS +BLOCK_Tail( void ) +#else +BLOCK_Tail( ) +#endif +{ + if ( !GenCC ) gen1("zzEXIT(zztasp%d);\n", BlkLevel); + if ( !GenCC ) gen("}\n"); + tabs--; + gen("}\n"); +} + +static void +#ifdef __USE_PROTOS +BLOCK_Preamble( Junction *q ) +#else +BLOCK_Preamble( q ) +Junction *q; +#endif +{ + ActionNode *a; + Junction *begin; + + BLOCK_Head(); + if ( GenCC ) genTokenPointers(q); + if ( GenCC&&GenAST ) genASTPointers(q); + if ( q->jtype == aPlusBlk ) gen("int zzcnt=1;\n"); + if ( q->parm != NULL && !q->predparm ) gen1("zzaPush(%s);\n", q->parm) + else if ( !GenCC ) gen("zzMake0;\n"); + if ( !GenCC ) gen("{\n"); + if ( q->jtype == aLoopBegin ) begin = (Junction *) ((Junction *)q->p1); + else begin = q; + if ( has_guess_block_as_first_item(begin) ) + { + gen("zzGUESS_BLOCK\n"); + } + if ( q->jtype == aLoopBegin ) + a = findImmedAction( ((Junction *)q->p1)->p1 ); /* look at aLoopBlk */ + else + a = findImmedAction( q->p1 ); + if ( a!=NULL && !a->is_predicate ) { + dumpAction(a->action, output, tabs, a->file, a->line, 1); + a->done = 1; /* remove action. We have already handled it */ + } +} + +void +#ifdef __USE_PROTOS +genCombinedPredTreeContext( Predicate *p ) +#else +genCombinedPredTreeContext( p ) +Predicate *p; +#endif +{ + static set *ctx=NULL; /* genExprSets() is destructive, make copy*/ + require(p!=NULL, "can't make context tree for NULL pred tree"); + +#ifdef DBG_PRED + fprintf(stderr, "enter genCombinedPredTreeContext(%s,0x%x) with sets:\n", p->expr, p); + s_fprT(stderr, p->scontext[1]); + fprintf(stderr, "\n"); +#endif + if ( p->down == NULL ) + { +/* if ( p->k>1 && p->tcontext!=NULL ) */ + if ( p->tcontext!=NULL ) + { + _gen("("); + genExprTree(p->tcontext, 1); + _gen(")"); + } +/* else if ( p->k==1 && set_deg(p->scontext[1])>0 )*/ + else if ( set_deg(p->scontext[1])>0 ) + { + if ( ctx==NULL ) ctx = (set *)calloc(CLL_k+1, sizeof(set)); + require(ctx!=NULL, "ctx cannot allocate"); + ctx[0]=empty; + ctx[1]=set_dup(p->scontext[1]); + _gen("("); + genExprSets(&(ctx[0]), p->k); + _gen(")"); + set_free(ctx[1]); + } + else if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST ) { + fatal_internal("pred tree is orphan OR or AND list"); + } + else { + fatal_internal("pred tree context is empty"); + } + return; + } + + if ( p->expr == PRED_AND_LIST ) + { + require(p->down!=NULL && p->down->right!=NULL, "pred tree is wacked"); + genCombinedPredTreeContext(p->down); + _gen("||"); + genCombinedPredTreeContext(p->down->right); + return; + } + + if ( p->expr == PRED_OR_LIST ) + { + Predicate *list = p->down; + for (; list!=NULL; list=list->right) + { + genCombinedPredTreeContext(list); + if ( list->right!=NULL ) _gen("||"); + } + return; + } + + fatal("pred tree is really wacked"); +} + +void +#ifdef __USE_PROTOS +genPredTreeGate( Predicate *p, int in_and_expr ) +#else +genPredTreeGate( p, in_and_expr ) +Predicate *p; +int in_and_expr; +#endif +{ + if ( in_and_expr ) + { + _gen("!("); + genCombinedPredTreeContext(p); + _gen(")||"); + if ( p->down!=NULL ) _gen("\n"); + } + else + { + _gen("("); + genCombinedPredTreeContext(p); + _gen(")&&"); + if ( p->down!=NULL ) _gen("\n"); + } +} + +void +#ifdef __USE_PROTOS +genPred(Predicate *p, Node *j) +#else +genPred(p,j) +Predicate *p; +Node *j; +#endif +{ + if ( FoundException ) {_gen("(_sva=(");} + else {_gen("(");} + if ( GenLineInfo && j->file != -1 ) _gen("\n"); + dumpAction(p->expr, output, 0, -1 /*indicates no line info*/, j->line, 0); + if ( FoundException ) {_gen("))");} + else {_gen(")");} +} + +void +#ifdef __USE_PROTOS +genPredTree( Predicate *p, Node *j, int in_and_expr ) +#else +genPredTree( p, j, in_and_expr ) +Predicate *p; +Node *j; +int in_and_expr; +#endif +{ + if ( HoistPredicateContext ) + { + _gen("("); + genPredTreeGate(p, in_and_expr); + } + + /* if leaf node, just gen predicate */ + if ( p->down==NULL ) + { + genPred(p,j); + if ( HoistPredicateContext ) _gen(")"); + return; + } + + /* if AND list, do both preds (only two possible) */ + if ( p->expr == PRED_AND_LIST ) + { + _gen("("); + genPredTree(p->down, j, 1); + _gen("&&"); + genPredTree(p->down->right, j, 1); + _gen(")"); + if ( HoistPredicateContext ) _gen(")"); + return; + } + + if ( p->expr == PRED_OR_LIST ) + { + Predicate *list; + _gen("("); + list = p->down; + for (; list!=NULL; list=list->right) + { + genPredTree(list, j, 0); + if ( list->right!=NULL ) _gen("||"); + } + _gen(")"); + if ( HoistPredicateContext ) _gen(")"); + return; + } + + fatal_internal("predicate tree is wacked"); +} + +void +#ifdef __USE_PROTOS +genPredTreeMain( Predicate *p, Node *j ) +#else +genPredTreeMain( p, j ) +Predicate *p; +Node *j; +#endif +{ + genPredTree(p,j,1); +} + +static void +#ifdef __USE_PROTOS +genExprTree( Tree *t, int k ) +#else +genExprTree( t, k ) +Tree *t; +int k; +#endif +{ + require(t!=NULL, "genExprTree: NULL tree"); + + if ( t->token == ALT ) + { + _gen("("); genExprTree(t->down, k); _gen(")"); + if ( t->right!=NULL ) + { + _gen("||"); + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + _gen("("); genExprTree(t->right, k); _gen(")"); + } + return; + } + if ( t->down!=NULL ) _gen("("); + _gen1("LA(%d)==",k); + if ( TokenString(t->token) == NULL ) _gen1("%d", t->token) + else _gen1("%s", TokenString(t->token)); + if ( t->down!=NULL ) + { + _gen("&&"); + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + _gen("("); genExprTree(t->down, k+1); _gen(")"); + } + if ( t->down!=NULL ) _gen(")"); + if ( t->right!=NULL ) + { + _gen("||"); + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + _gen("("); genExprTree(t->right, k); _gen(")"); + } +} + +/* + * Generate LL(k) type expressions of the form: + * + * (LA(1) == T1 || LA(1) == T2 || ... || LA(1) == Tn) && + * (LA(2) == T1 || LA(2) == T2 || ... || LA(2) == Tn) && + * ..... + * (LA(k) == T1 || LA(k) == T2 || ... || LA(k) == Tn) + * + * If GenExprSets generate: + * + * (setwdi[LA(1)]&(1<= 1. + * + * This routine is visible only to this file and cannot answer a TRANS message. + * + */ +static int +#ifdef __USE_PROTOS +genExpr( Junction *j ) +#else +genExpr( j ) +Junction *j; +#endif +{ + int max_k; + + /* if full LL(k) is sufficient, then don't use approximate (-ck) lookahead + * from CLL_k..LL_k + */ + { + int limit; + if ( j->ftree!=NULL ) limit = LL_k; + else limit = CLL_k; + max_k = genExprSets(j->fset, limit); + } + + /* Do tests for real tuples from other productions that conflict with + * artificial tuples generated by compression (using sets of tokens + * rather than k-trees). + */ + if ( j->ftree != NULL ) + { + _gen(" && !("); genExprTree(j->ftree, 1); _gen(")"); + } + + if ( ParseWithPredicates && j->predicate!=NULL ) + { + Predicate *p = j->predicate; + warn_about_using_gk_option(); + _gen("&&"); + genPredTreeMain(p, (Node *)j); + } + + return max_k; +} + +static int +#ifdef __USE_PROTOS +genExprSets( set *fset, int limit ) +#else +genExprSets( fset, limit ) +set *fset; +int limit; +#endif +{ + int k = 1; + int max_k = 0; + unsigned *e, *g, firstTime=1; + + if ( GenExprSets ) + { + while ( !set_nil(fset[k]) && k<=limit ) + { + if ( set_deg(fset[k])==1 ) /* too simple for a set? */ + { + int e; + _gen1("(LA(%d)==",k); + e = set_int(fset[k]); + if ( TokenString(e) == NULL ) _gen1("%d)", e) + else _gen1("%s)", TokenString(e)); + } + else + { + NewSet(); + FillSet( fset[k] ); + _gen3("(setwd%d[LA(%d)]&0x%x)", wordnum, k, 1<max_k ) max_k = k; + if ( k == CLL_k ) break; + k++; + if ( !set_nil(fset[k]) && k<=limit ) _gen(" && "); + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + } + return max_k; + } + + while ( !set_nil(fset[k]) && k<=limit ) + { + if ( (e=g=set_pdq(fset[k])) == NULL ) fatal_internal("genExpr: cannot allocate IF expr pdq set"); + for (; *e!=nil; e++) + { + if ( !firstTime ) _gen(" || ") else { _gen("("); firstTime = 0; } + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + _gen1("LA(%d)==",k); + if ( TokenString(*e) == NULL ) _gen1("%d", *e) + else _gen1("%s", TokenString(*e)); + } + free( (char *)g ); + _gen(")"); + if ( k>max_k ) max_k = k; + if ( k == CLL_k ) break; + k++; + if ( !set_nil(fset[k]) && k<=limit ) { firstTime=1; _gen(" && "); } + on1line++; + if ( on1line > NumExprPerLine ) { on1line=0; _gen("\n"); } + } + return max_k; +} + +/* + * Generate code for any type of block. If the last alternative in the block is + * empty (not even an action) don't bother doing it. This permits us to handle + * optional and loop blocks as well. + * + * Only do this block, return after completing the block. + * This routine is visible only to this file and cannot answer a TRANS message. + */ +static set +#ifdef __USE_PROTOS +genBlk( Junction *q, int jtype, int *max_k, int *need_right_curly ) +#else +genBlk( q, jtype, max_k, need_right_curly ) +Junction *q; +int jtype; +int *max_k; +int *need_right_curly; +#endif +{ + set f; + Junction *alt; + int a_guess_in_block = 0; + require(q!=NULL, "genBlk: invalid node"); + require(q->ntype == nJunction, "genBlk: not junction"); + + *need_right_curly=0; + if ( q->p2 == NULL ) /* only one alternative? Then don't need if */ + { + if ( first_item_is_guess_block((Junction *)q->p1)!=NULL ) + { + warnFL("(...)? as only alternative of block is unnecessary", FileStr[q->file], q->line); + gen("zzGUESS\n"); /* guess anyway to make output code consistent */ + gen("if ( !zzrv )\n"); + } + TRANS(q->p1); + return empty; /* no decision to be made-->no error set */ + } + + f = First(q, 1, jtype, max_k); + for (alt=q; alt != NULL; alt= (Junction *) alt->p2 ) + { + if ( alt->p2 == NULL ) /* chk for empty alt */ + { + Node *p = alt->p1; + if ( p->ntype == nJunction ) + { + /* we have empty alt */ + if ( ((Junction *)p)->p1 == (Node *)q->end ) + { + break; /* don't do this one, quit */ + } + } + } + if ( alt != q ) gen("else ") + else + { + if ( DemandLookahead ) + if ( !GenCC ) {gen1("LOOK(%d);\n", *max_k);} + else gen1("look(%d);\n", *max_k); + } + if ( alt!=q ) + { + _gen("{\n"); + tabs++; + (*need_right_curly)++; + /* code to restore state if a prev alt didn't follow guess */ + if ( a_guess_in_block ) + if ( !GenCC ) {gen("if ( zzguessing ) zzGUESS_DONE;\n");} + else gen("if ( !zzrv ) zzGUESS_DONE;\n"); + } + if ( first_item_is_guess_block((Junction *)alt->p1)!=NULL ) + { + a_guess_in_block = 1; + gen("zzGUESS\n"); + } + gen("if ( "); + if ( first_item_is_guess_block((Junction *)alt->p1)!=NULL ) _gen("!zzrv && "); + genExpr(alt); + _gen(" ) "); + _gen("{\n"); + tabs++; + TRANS(alt->p1); + --tabs; + gen("}\n"); + } + return f; +} + +static int +#ifdef __USE_PROTOS +has_guess_block_as_first_item( Junction *q ) +#else +has_guess_block_as_first_item( q ) +Junction *q; +#endif +{ + Junction *alt; + + for (alt=q; alt != NULL; alt= (Junction *) alt->p2 ) + { + if ( first_item_is_guess_block((Junction *)alt->p1)!=NULL ) return 1; + } + return 0; +} + +/* return NULL if 1st item of alt is (...)? block; else return ptr +to aSubBlk node + * of (...)?; This function ignores actions and predicates. + */ +Junction * +#ifdef __USE_PROTOS +first_item_is_guess_block( Junction *q ) +#else +first_item_is_guess_block( q ) +Junction *q; +#endif +{ + while ( q!=NULL && ((q->ntype==nJunction && q->jtype==Generic) || q->ntype==nAction) ) + { + if ( q->ntype==nJunction ) q = (Junction *)q->p1; + else q = (Junction *) ((ActionNode *)q)->next; + } + + if ( q==NULL ) return NULL; + if ( q->ntype!=nJunction ) return NULL; + if ( q->jtype!=aSubBlk ) return NULL; + if ( !q->guess ) return NULL; + return q; +} + +/* Generate an action. Don't if action is NULL which means that it was already + * handled as an init action. + */ +void +#ifdef __USE_PROTOS +genAction( ActionNode *p ) +#else +genAction( p ) +ActionNode *p; +#endif +{ + require(p!=NULL, "genAction: invalid node and/or rule"); + require(p->ntype==nAction, "genAction: not action"); + + if ( !p->done ) + { + if ( p->is_predicate ) + { + if ( p->guardpred!=NULL ) + { + gen("if (!"); + genPredTreeMain(p->guardpred, (Node *)p); + } + else + { + gen("if (!("); + /* make sure that '#line n' is on front of line */ + if ( GenLineInfo && p->file != -1 ) _gen("\n"); + dumpAction(p->action, output, 0, p->file, p->line, 0); + _gen(")"); + } + if ( p->pred_fail != NULL ) + { + _gen(")\n"); + tabs++; + gen1("%s;\n", p->pred_fail); + tabs--; + } + else _gen1(") {zzfailed_pred(\"%s\");}\n",p->action); + } + else + { + if ( FoundGuessBlk ) + if ( GenCC ) {gen("if ( !guessing ) {\n");} + else gen("zzNON_GUESS_MODE {\n"); + dumpAction(p->action, output, tabs, p->file, p->line, 1); + if ( FoundGuessBlk ) gen("}\n"); + } + } + TRANS(p->next) +} + +/* + * if invoking rule has !noAST pass zzSTR to rule ref and zzlink it in + * else pass addr of temp root ptr (&_ast) (don't zzlink it in). + * + * if ! modifies rule-ref, then never link it in and never pass zzSTR. + * Always pass address of temp root ptr. + */ +void +#ifdef __USE_PROTOS +genRuleRef( RuleRefNode *p ) +#else +genRuleRef( p ) +RuleRefNode *p; +#endif +{ + Junction *q; + char *handler_id = ""; + RuleEntry *r, *r2; + char *parm = "", *exsig = ""; + require(p!=NULL, "genRuleRef: invalid node and/or rule"); + require(p->ntype==nRuleRef, "genRuleRef: not rule reference"); + + if ( p->altstart!=NULL && p->altstart->exception_label!=NULL ) + handler_id = p->altstart->exception_label; + + r = (RuleEntry *) hash_get(Rname, p->text); + if ( r == NULL ) + { + warnFL( eMsg1("rule %s not defined", + p->text), FileStr[p->file], p->line ); + return; + } + r2 = (RuleEntry *) hash_get(Rname, p->rname); + if ( r2 == NULL ) {warnNoFL("Rule hash table is screwed up beyond belief"); return;} + + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, p->line, FileStr[p->file]); + + if ( GenCC && GenAST ) { + gen("_ast = NULL;\n"); + } + + if ( FoundGuessBlk && p->assign!=NULL ) + if ( GenCC ) {gen("if ( !guessing ) {\n");} + else gen("zzNON_GUESS_MODE {\n"); + + if ( FoundException ) exsig = "&_signal"; + + tab(); + if ( GenAST ) + { + if ( GenCC ) { +/* if ( r2->noAST || p->astnode==ASTexclude ) +*/ + { +/* _gen("_ast = NULL;\n");*/ + parm = "&_ast"; + } +/* we always want to set just a pointer now, then set correct +pointer after + + else { + _gen("_astp = +(_tail==NULL)?(&_sibling):(&(_tail->_right));\n"); + parm = "_astp"; + } +*/ + } + else { + if ( r2->noAST || p->astnode==ASTexclude ) + { + _gen("_ast = NULL; "); + parm = "&_ast"; + } + else parm = "zzSTR"; + } + if ( p->assign!=NULL ) + { + if ( !HasComma(p->assign) ) {_gen1("%s = ",p->assign);} + else _gen1("{ struct _rv%d _trv; _trv = ", r->rulenum); + } + if ( FoundException ) { + _gen5("%s%s(%s,&_signal%s%s); ", + RulePrefix, + p->text, + parm, + (p->parms!=NULL)?",":"", + (p->parms!=NULL)?p->parms:""); + if ( p->ex_group!=NULL ) { + _gen("\n"); + gen("if (_signal) {\n"); + tabs++; + dumpException(p->ex_group, 0); + tabs--; + gen("}"); + } + else { + _gen1("if (_signal) goto %s_handler;", handler_id); + } + } + else { + _gen5("%s%s(%s%s%s);", + RulePrefix, + p->text, + parm, + (p->parms!=NULL)?",":"", + (p->parms!=NULL)?p->parms:""); + } + if ( GenCC && (r2->noAST || p->astnode==ASTexclude) ) + { + /* rule has a ! or element does */ + /* still need to assign to #i so we can play with it */ + _gen("\n"); + gen2("_ast%d%d = (AST *)_ast;", BlkLevel-1, p->elnum); + } + else if ( !r2->noAST && p->astnode == ASTinclude ) + { + /* rule doesn't have a ! and neither does element */ + if ( GenCC ) { + _gen("\n"); + gen("if ( _tail==NULL ) _sibling = _ast; else _tail->setRight(_ast);\n"); + gen2("_ast%d%d = (AST *)_ast;\n", BlkLevel-1, p->elnum); + tab(); + } + else _gen(" "); + if ( GenCC ) {_gen("ASTBase::");} else _gen("zz"); + _gen("link(_root, &_sibling, &_tail);"); + } + } + else + { + if ( p->assign!=NULL ) + { + if ( !HasComma(p->assign) ) {_gen1("%s = ",p->assign);} + else _gen1("{ struct _rv%d _trv; _trv = ", r->rulenum); + } + if ( FoundException ) { + _gen4("%s%s(&_signal%s%s); ", + RulePrefix, + p->text, + (p->parms!=NULL)?",":"", + (p->parms!=NULL)?p->parms:""); + if ( p->ex_group!=NULL ) { + _gen("\n"); + gen("if (_signal) {\n"); + tabs++; + dumpException(p->ex_group, 0); + tabs--; + gen("}"); + } + else { + _gen1("if (_signal) goto %s_handler;", handler_id); + } + } + else { + _gen3("%s%s(%s);", + RulePrefix, + p->text, + (p->parms!=NULL)?p->parms:""); + } + if ( p->assign!=NULL ) _gen("\n"); + } + q = RulePtr[r->rulenum]; /* find definition of ref'd rule */ + if ( p->assign!=NULL ) { + if ( HasComma(p->assign) ) + { + _gen("\n"); + dumpRetValAssign(p->assign, q->ret); + _gen("}"); + } + } + _gen("\n"); + + /* Handle element labels now */ + if ( p->el_label!=NULL ) + { + if ( GenAST ) + { + if ( GenCC ) { + gen3("%s_ast = _ast%d%d;\n", p->el_label, BlkLevel-1, p->elnum); + } + else {gen1("%s_ast = zzastCur;\n", p->el_label);} + } + else if (!GenCC ) { + gen1("%s = zzaCur;\n", p->el_label); + } + } + + if ( FoundGuessBlk && p->assign!=NULL ) { + /* in guessing mode, don't branch to handler upon error */ + gen("} else {\n"); + if ( FoundException ) { + gen6("%s%s(%s%s&_signal%s%s);\n", + RulePrefix, + p->text, + parm, + (*parm!='\0')?",":"", + (p->parms!=NULL)?",":"", + (p->parms!=NULL)?p->parms:""); + } + else { + gen5("%s%s(%s%s%s);\n", + RulePrefix, + p->text, + parm, + (p->parms!=NULL && *parm!='\0')?",":"", + (p->parms!=NULL)?p->parms:""); + } + gen("}\n"); + } + TRANS(p->next) +} + +/* + * Generate code to match a token. + * + * Getting the next token is tricky. We want to ensure that any action + * following a token is executed before the next GetToken(); + */ +void +#ifdef __USE_PROTOS +genToken( TokNode *p ) +#else +genToken( p ) +TokNode *p; +#endif +{ + RuleEntry *r; + char *handler_id = ""; + ActionNode *a; + char *set_name; + require(p!=NULL, "genToken: invalid node and/or rule"); + require(p->ntype==nToken, "genToken: not token"); + + if ( p->altstart!=NULL && p->altstart->exception_label!=NULL ) + handler_id = p->altstart->exception_label; + + r = (RuleEntry *) hash_get(Rname, p->rname); + if ( r == NULL ) {warnNoFL("Rule hash table is screwed up beyond belief"); return;} + + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, p->line, FileStr[p->file]); + + if ( !set_nil(p->tset) ) /* implies '.', ~Tok, or tokenclass */ + { + unsigned e; + set b; + b = set_dup(p->tset); + if ( p->tclass!=NULL ) /* token class? */ + { + static char buf[MaxRuleName+1]; + if ( p->tclass->dumped ) + e = p->tclass->setnum; + else { + e = DefErrSet(&b, 0, TokenString(p->token)); + p->tclass->dumped = 1; /* indicate set has been created */ + p->tclass->setnum = e; + } + sprintf(buf, "%s_set", TokenString(p->token)); + set_name = buf; + } + else { /* wild card to ~ operator */ + static char buf[sizeof("zzerr")+10]; + int n = DefErrSet( &b, 0, NULL ); + if ( GenCC ) sprintf(buf, "err%d", n); + else sprintf(buf, "zzerr%d", n); + set_name = buf; + } + + if ( !FoundException ) + {gen1("zzsetmatch(%s);", set_name);} + else if ( p->ex_group==NULL ) { + if ( p->use_def_MT_handler ) + gen3("zzsetmatch_wdfltsig(%s,(ANTLRTokenType)%d,%s);", + set_name, + p->token, + tokenFollowSet(p)) + else + gen2("zzsetmatch_wsig(%s, %s_handler);", + set_name, + handler_id); + } + else + { + gen1("if ( !_setmatch_wsig(%s) ) {\n", set_name); + tabs++; + gen("if ( guessing ) goto fail;\n"); + gen("_signal=MismatchedToken;\n"); + dumpException(p->ex_group, 0); + tabs--; + gen("}\n"); + } + set_free(b); + } + else if ( TokenString(p->token)!=NULL ) + { + if ( FoundException ) { + if ( p->use_def_MT_handler ) + gen2("zzmatch_wdfltsig(%s,%s);",TokenString(p->token),tokenFollowSet(p)) + else if ( p->ex_group==NULL ) + { + gen2("zzmatch_wsig(%s, %s_handler);", + TokenString(p->token), + handler_id); + } + else + { + gen1("if ( !_match_wsig(%s) ) {\n", TokenString(p->token)); + tabs++; + gen("if ( guessing ) goto fail;\n"); + gen("_signal=MismatchedToken;\n"); + dumpException(p->ex_group, 0); + tabs--; + gen("}\n"); + } + } + else gen1("zzmatch(%s);", TokenString(p->token)); + } + else { + if ( FoundException ) { + if ( p->use_def_MT_handler ) + gen2("zzmatch_wdfltsig((ANTLRTokenType)%d,%s);", + p->token,tokenFollowSet(p)) + else + gen2("zzmatch_wsig(%d,%s_handler);",p->token,handler_id); + } + else {gen1("zzmatch(%d);", p->token);} + } + + a = findImmedAction( p->next ); + /* generate the token labels */ + if ( GenCC && p->elnum>0 ) + { + /* If building trees in C++, always gen the LT() assigns */ + if ( set_el(p->elnum, tokensRefdInBlock) || GenAST ) + { + if ( FoundGuessBlk ) + { + gen("\n"); + if ( GenCC ) {gen("if ( !guessing ) {\n"); tab();} + else {gen("zzNON_GUESS_MODE {\n"); tab();} + } + _gen2(" _t%d%d = (ANTLRTokenPtr)LT(1);\n", BlkLevel-1, p->elnum); + if ( FoundGuessBlk ) {gen("}\n");} + } + if ( LL_k>1 ) + if ( !DemandLookahead ) _gen(" labase++;"); + _gen("\n"); + tab(); + } + if ( GenAST ) + { + if ( FoundGuessBlk && !(p->astnode == ASTexclude || r->noAST) ) + { + if ( GenCC ) {_gen("if ( !guessing ) {\n"); tab();} + else {_gen("zzNON_GUESS_MODE {\n"); tab();} + } + if ( !r->noAST ) + { + if ( GenCC && !(p->astnode == ASTexclude || r->noAST) ) { + _gen("\n"); + gen4("_ast%d%d = new AST(_t%d%d);\n", BlkLevel-1, p->elnum, BlkLevel-1, p->elnum); + tab(); + } + if ( GenCC && !(p->astnode == ASTexclude || r->noAST) ) + {_gen2("_ast%d%d->", BlkLevel-1, p->elnum);} + else _gen(" "); + if ( p->astnode==ASTchild ) { + if ( !GenCC ) _gen("zz"); + _gen("subchild(_root, &_sibling, &_tail);"); + } + else if ( p->astnode==ASTroot ) { + if ( !GenCC ) _gen("zz"); + _gen("subroot(_root, &_sibling, &_tail);"); + } + if ( GenCC && !(p->astnode == ASTexclude || r->noAST) ) { + _gen("\n"); + tab(); + } + } + else if ( !GenCC ) _gen(" zzastDPush;"); + if ( FoundGuessBlk && !(p->astnode == ASTexclude || r->noAST) ) + {_gen("}\n"); tab();} + } + + /* Handle element labels now */ + if ( p->el_label!=NULL ) + { + _gen("\n"); + if ( FoundGuessBlk ) + { + if ( GenCC ) {gen("if ( !guessing ) {\n"); tab();} + else {gen("zzNON_GUESS_MODE {\n"); tab();} + } + /* Do Attrib / Token ptr */ + if ( GenCC ) { + if ( set_el(p->elnum, tokensRefdInBlock) || GenAST ) + {gen3("%s = _t%d%d;\n", p->el_label, BlkLevel-1, p->elnum);} + else + { + gen1("%s = (ANTLRTokenPtr)LT(1);\n", p->el_label); + } + } + else {gen1("%s = zzaCur;\n", p->el_label);} + /* Do AST ptr */ + if ( GenAST && !(p->astnode == ASTexclude || r->noAST) ) + { + if ( GenCC ) { + gen3("%s_ast = _ast%d%d;\n", p->el_label, BlkLevel-1, p->elnum); + } + else {gen1("%s_ast = zzastCur;\n", p->el_label);} + } + + if ( FoundGuessBlk ) {_gen("}\n"); tab();} + } + + /* Handle any actions immediately following action */ + if ( a != NULL ) + { + /* delay next token fetch until after action */ + _gen("\n"); + if ( a->is_predicate ) + { + gen("if (!("); + dumpAction(a->action, output, 0, a->file, a->line, 0); + if ( a->pred_fail != NULL ) + { + _gen(")) {\n"); +/* if ( FoundGuessBlk ) +gen("zzNON_GUESS_MODE {\n");*/ + tabs++; + gen1("%s;\n", a->pred_fail); + tabs--; + gen("}\n"); +/* if ( FoundGuessBlk ) gen("}\n");*/ + } + else _gen1(")) {zzfailed_pred(\"%s\");}\n",a->action); + } + else + { + if ( FoundGuessBlk ) + if ( GenCC ) {gen("if ( !guessing ) {\n");} + else gen("zzNON_GUESS_MODE {\n"); + dumpAction(a->action, output, tabs, a->file, a->line, 1); + if ( FoundGuessBlk ) gen("}\n"); + } + a->done = 1; + if ( !DemandLookahead ) { + if ( GenCC ) { + if ( FoundException && p->use_def_MT_handler ) gen("if (!_signal)"); + _gen(" consume();") + if ( FoundException && p->use_def_MT_handler ) + _gen(" _signal=NoSignal;"); + _gen("\n"); + } + else { + if ( FoundException && p->use_def_MT_handler ) _gen("if (!_signal)"); + _gen(" zzCONSUME;\n"); + if ( FoundException && p->use_def_MT_handler ) _gen(" _signal=NoSignal;"); + _gen("\n"); + } + } + else gen("\n"); + TRANS( a->next ); + } + else + { + if ( !DemandLookahead ) { + if ( GenCC ) { + if (FoundException && p->use_def_MT_handler) _gen("if (!_signal)"); + _gen(" consume();") + if (FoundException&&p->use_def_MT_handler) _gen(" _signal=NoSignal;"); + _gen("\n"); + } + else { + if (FoundException && p->use_def_MT_handler) _gen("if (!_signal)"); + _gen(" zzCONSUME;"); + if ( FoundException && p->use_def_MT_handler ) _gen(" _signal=NoSignal;"); + _gen("\n"); + } + } + else _gen("\n"); + TRANS(p->next); + } +} + +void +#ifdef __USE_PROTOS +genOptBlk( Junction *q ) +#else +genOptBlk( q ) +Junction *q; +#endif +{ + int max_k; + set f; + int need_right_curly; + set savetkref; + savetkref = tokensRefdInBlock; + require(q!=NULL, "genOptBlk: invalid node and/or rule"); + require(q->ntype == nJunction, "genOptBlk: not junction"); + require(q->jtype == aOptBlk, "genOptBlk: not optional block"); + + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + BLOCK_Preamble(q); + BlkLevel++; + f = genBlk(q, aOptBlk, &max_k, &need_right_curly); + set_free(f); + freeBlkFsets(q); + BlkLevel--; + if ( first_item_is_guess_block((Junction *)q->p1)!=NULL ) + { + if ( !GenCC ) {gen("else if ( zzguessing ) zzGUESS_DONE;\n");} + else gen("else if ( !zzrv ) zzGUESS_DONE;\n"); + } + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + BLOCK_Tail(); + tokensRefdInBlock = savetkref; + if (q->end->p1 != NULL) TRANS(q->end->p1); +} + +/* + * Generate code for a loop blk of form: + * + * |---| + * v | + * --o-G-o-->o-- + */ +void +#ifdef __USE_PROTOS +genLoopBlk( Junction *begin, Junction *q, Junction *start, int max_k ) +#else +genLoopBlk( begin, q, start, max_k ) +Junction *begin; +Junction *q; +Junction *start; /* where to start generating code from */ +int max_k; +#endif +{ + set f; + int need_right_curly; + set savetkref; + savetkref = tokensRefdInBlock; + require(q->ntype == nJunction, "genLoopBlk: not junction"); + require(q->jtype == aLoopBlk, "genLoopBlk: not loop block"); + + if ( q->visited ) return; + q->visited = TRUE; + if ( q->p2 == NULL ) /* only one alternative? */ + { + if ( DemandLookahead ) + if ( !GenCC ) {gen1("LOOK(%d);\n", max_k);} + else gen1("look(%d);\n", max_k); + gen("while ( "); + if ( begin!=NULL ) genExpr(begin); + else genExpr(q); + /* if no predicates have been hoisted for this single alt (..)* + * do so now + */ + if ( ParseWithPredicates && begin->predicate==NULL ) + { + Predicate *a = find_predicates((Node *)q->p1); + if ( a!=NULL ) + { + _gen("&&"); + genPredTreeMain(a, (Node *)q); + } + } + _gen(" ) {\n"); + tabs++; + TRANS(q->p1); + if ( !GenCC ) gen1("zzLOOP(zztasp%d);\n", BlkLevel-1); + if ( DemandLookahead ) + if ( !GenCC ) {gen1("LOOK(%d);\n", max_k);} + else gen1("look(%d);\n", max_k); + --tabs; + gen("}\n"); + freeBlkFsets(q); + q->visited = FALSE; + tokensRefdInBlock = savetkref; + return; + } + gen("while ( 1 ) {\n"); + tabs++; + if ( begin!=NULL ) + { + if ( DemandLookahead ) + { + if ( !GenCC ) {gen1("LOOK(%d);\n", max_k);} + else gen1("look(%d);\n", max_k); + } + /* The bypass arc of the (...)* predicts what to do when you fail, but + * ONLY after having tested the loop start expression. To avoid this, + * we simply break out of the (...)* loop when we find something that + * is not in the prediction of the loop (all alts thereof). + */ + gen("if ( !("); + +/* TJP says: It used to use the prediction expression for the bypass arc + of the (...)*. HOWEVER, if a non LL^1(k) decision was found, this + thing would miss the ftree stored in the aLoopBegin node and generate + an LL^1(k) decision anyway. + + genExpr((Junction *)begin->p2); + */ + + genExpr((Junction *)begin); + _gen(")) break;\n"); + } + f = genBlk(q, aLoopBlk, &max_k, &need_right_curly); + set_free(f); + freeBlkFsets(q); + + /* generate code for terminating loop (this is optional branch) */ + if ( begin==NULL ) gen("else break;\n"); /* code for exiting loop "for sure" */ + + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + if ( !GenCC ) gen1("zzLOOP(zztasp%d);\n", BlkLevel-1); + --tabs; + gen("}\n"); + q->visited = FALSE; + tokensRefdInBlock = savetkref; +} + +/* + * Generate code for a loop blk of form: + * + * |---| + * v | + * --o-->o-->o-G-o-->o-- + * | ^ + * v | + * o-----------o + * + * q->end points to the last node (far right) in the blk. Note +that q->end->jtype + * must be 'EndBlk'. + * + * Generate code roughly of the following form: + * + * do { + * ... code for alternatives ... + * } while ( First Set of aLoopBlk ); + * + * OR if > 1 alternative + * + * do { + * ... code for alternatives ... + * else break; + * } while ( 1 ); + */ +void +#ifdef __USE_PROTOS +genLoopBegin( Junction *q ) +#else +genLoopBegin( q ) +Junction *q; +#endif +{ + set f; + int i; + int max_k; + set savetkref; + savetkref = tokensRefdInBlock; + require(q!=NULL, "genLoopBegin: invalid node and/or rule"); + require(q->ntype == nJunction, "genLoopBegin: not junction"); + require(q->jtype == aLoopBegin, "genLoopBegin: not loop block"); + require(q->p2!=NULL, "genLoopBegin: invalid Loop Graph"); + + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + + BLOCK_Preamble(q); + BlkLevel++; + f = First(q, 1, aLoopBegin, &max_k); + /* If not simple LL(1), must specify to start at LoopBegin, not LoopBlk */ + if ( LL_k>1 && !set_nil(q->fset[2]) ) + genLoopBlk( q, (Junction *)q->p1, q, max_k ); + else genLoopBlk( q, (Junction *)q->p1, NULL, max_k ); + + for (i=1; i<=CLL_k; i++) set_free(q->fset[i]); + for (i=1; i<=CLL_k; i++) set_free(((Junction *)q->p2)->fset[i]); + --BlkLevel; + BLOCK_Tail(); + set_free(f); + tokensRefdInBlock = savetkref; + if (q->end->p1 != NULL) TRANS(q->end->p1); +} + +/* + * Generate code for a loop blk of form: + * + * |---| + * v | + * --o-G-o-->o-- + * + * q->end points to the last node (far right) in the blk. + * Note that q->end->jtype must be 'EndBlk'. + * + * Generate code roughly of the following form: + * + * do { + * ... code for alternatives ... + * } while ( First Set of aPlusBlk ); + * + * OR if > 1 alternative + * + * do { + * ... code for alternatives ... + * else if not 1st time through, break; + * } while ( 1 ); + */ +void +#ifdef __USE_PROTOS +genPlusBlk( Junction *q ) +#else +genPlusBlk( q ) +Junction *q; +#endif +{ + int max_k; + set f; + int need_right_curly; + set savetkref; + savetkref = tokensRefdInBlock; + require(q!=NULL, "genPlusBlk: invalid node and/or rule"); + require(q->ntype == nJunction, "genPlusBlk: not junction"); + require(q->jtype == aPlusBlk, "genPlusBlk: not Plus block"); + require(q->p2 != NULL, "genPlusBlk: not a valid Plus block"); + + if ( q->visited ) return; + q->visited = TRUE; + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + BLOCK_Preamble(q); + BlkLevel++; + /* if the ignore flag is set on the 2nd alt and that alt is empty, + * then it is the implied optional alternative that we added for (...)+ + * and, hence, only 1 alt. + */ + if ( ((Junction *)q->p2)->p2 == NULL && + ((Junction *)q->p2)->ignore ) /* only one alternative? */ + { + Predicate *a=NULL; + /* if the only alt has a semantic predicate, hoist it; must test before + * entering loop. + */ + if ( ParseWithPredicates ) + { + a = find_predicates((Node *)q); + if ( a!=NULL ) { + gen("if ("); + genPredTreeMain(a, (Node *)q); + _gen(") {\n"); + } + } + gen("do {\n"); + tabs++; + TRANS(q->p1); + if ( !GenCC ) gen1("zzLOOP(zztasp%d);\n", BlkLevel-1); + f = First(q, 1, aPlusBlk, &max_k); + if ( DemandLookahead ) + if ( !GenCC ) {gen1("LOOK(%d);\n", max_k);} + else gen1("look(%d);\n", max_k); + --tabs; + gen("} while ( "); + if ( q->parm!=NULL && q->predparm ) _gen1("(%s) && ", q->parm); + genExpr(q); + if ( ParseWithPredicates && a!=NULL ) + { + _gen("&&"); + genPredTreeMain(a, (Node *)q); + } + _gen(" );\n"); + if ( ParseWithPredicates && a!=NULL ) gen("}\n"); + --BlkLevel; + BLOCK_Tail(); + q->visited = FALSE; + freeBlkFsets(q); + set_free(f); + tokensRefdInBlock = savetkref; + if (q->end->p1 != NULL) TRANS(q->end->p1); + return; + } + gen("do {\n"); + tabs++; + f = genBlk(q, aPlusBlk, &max_k, &need_right_curly); + gen("else if ( zzcnt>1 ) break; /* implied exit branch */\n");/* code for exiting loop */ + tab(); + makeErrorClause(q,f,max_k); + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + freeBlkFsets(q); + gen("zzcnt++;"); + if ( !GenCC ) _gen1(" zzLOOP(zztasp%d);", BlkLevel-1); + _gen("\n"); + if ( DemandLookahead ) + if ( !GenCC ) {gen1("LOOK(%d);\n", max_k);} + else gen1("look(%d);\n", max_k); + --tabs; + if ( q->parm!=NULL && q->predparm ) {gen1("} while (%s);\n", q->parm);} + else gen("} while ( 1 );\n"); + --BlkLevel; + BLOCK_Tail(); + q->visited = FALSE; + tokensRefdInBlock = savetkref; + if (q->end->p1 != NULL) TRANS(q->end->p1); +} + +/* + * Generate code for a sub blk of alternatives of form: + * + * --o-G1--o-- + * | ^ + * v /| + * o-G2-o| + * | ^ + * v | + * .......... + * | ^ + * v / + * o-Gn-o + * + * q points to the 1st junction of blk (upper-left). + * q->end points to the last node (far right) in the blk. + * Note that q->end->jtype must be 'EndBlk'. + * The last node in every alt points to q->end. + * + * Generate code of the following form: + * if ( First(G1) ) { + * ...code for G1... + * } + * else if ( First(G2) ) { + * ...code for G2... + * } + * ... + * else { + * ...code for Gn... + * } + */ +void +#ifdef __USE_PROTOS +genSubBlk( Junction *q ) +#else +genSubBlk( q ) +Junction *q; +#endif +{ + int max_k; + set f; + int need_right_curly; + set savetkref; + savetkref = tokensRefdInBlock; + require(q->ntype == nJunction, "genSubBlk: not junction"); + require(q->jtype == aSubBlk, "genSubBlk: not subblock"); + + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + BLOCK_Preamble(q); + BlkLevel++; + f = genBlk(q, aSubBlk, &max_k, &need_right_curly); + if ( q->p2 != NULL ) {tab(); makeErrorClause(q,f,max_k);} + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + freeBlkFsets(q); + --BlkLevel; + BLOCK_Tail(); + + if ( q->guess ) + { + gen("zzGUESS_DONE\n"); + } + + /* must duplicate if (alpha)?; one guesses (validates), the + * second pass matches */ + if ( q->guess && analysis_point(q)==q ) + { + if ( GenLineInfo ) fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + BLOCK_Preamble(q); + BlkLevel++; + f = genBlk(q, aSubBlk, &max_k, &need_right_curly); + if ( q->p2 != NULL ) {tab(); makeErrorClause(q,f,max_k);} + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + freeBlkFsets(q); + --BlkLevel; + BLOCK_Tail(); + } + + tokensRefdInBlock = savetkref; + if (q->end->p1 != NULL) TRANS(q->end->p1); +} + +/* + * Generate code for a rule. + * + * rule--> o-->o-Alternatives-o-->o + * Or, + * rule--> o-->o-Alternative-o-->o + * + * The 1st junction is a RuleBlk. The second can be a SubBlk or just a junction + * (one alternative--no block), the last is EndRule. + * The second to last is EndBlk if more than one alternative exists in the rule. + * + * To get to the init-action for a rule, we must bypass the RuleBlk, + * and possible SubBlk. + * Mark any init-action as generated so genBlk() does not regenerate it. + */ +void +#ifdef __USE_PROTOS +genRule( Junction *q ) +#else +genRule( q ) +Junction *q; +#endif +{ + int max_k; + set follow, rk, f; + ActionNode *a; + RuleEntry *r; + static int file = -1; + int need_right_curly; + require(q->ntype == nJunction, "genRule: not junction"); + require(q->jtype == RuleBlk, "genRule: not rule"); + + r = (RuleEntry *) hash_get(Rname, q->rname); + if ( r == NULL ) warnNoFL("Rule hash table is screwed up beyond belief"); + if ( q->file != file ) /* open new output file if need to */ + { + if ( output != NULL ) fclose( output ); + output = fopen(OutMetaName(outname(FileStr[q->file])), "w"); + require(output != NULL, "genRule: can't open output file"); + + special_fopen_actions(OutMetaName(outname(FileStr[q->file]))); + + if ( file == -1 ) genHdr1(q->file); + else genHdr(q->file); + file = q->file; + } + DumpFuncHeader(q,r); + tabs++; + if ( q->ret!=NULL ) + { + /* Declare the return value - and PURIFY it -ATG 6/5/95 */ + if ( HasComma(q->ret) ) + { + gen1("struct _rv%d _retv;\n",r->rulenum); + gen1("PURIFY(_retv,sizeof(struct _rv%d))\n",r->rulenum); + } + else + { + tab(); + DumpType(q->ret, output); + gen(" _retv;\n"); + gen("PURIFY(_retv,sizeof("); + DumpType(q->ret, output); + gen("))\n"); + } + } + + if ( GenLineInfo ) + { + fprintf(output, LineInfoFormatStr, q->line, FileStr[q->file]); + } + + gen("zzRULE;\n"); + if ( FoundException ) + { + gen("int _sva=1;\n"); + } + if ( GenCC && GenAST ) + gen("ASTBase **_astp, *_ast = NULL, *_sibling = NULL, *_tail = NULL;\n"); + if ( GenCC ) genTokenPointers(q); + if ( GenCC&&GenAST ) genASTPointers(q); + if ( q->el_labels!=NULL ) genElementLabels(q->el_labels); + if ( FoundException ) gen("int _signal=NoSignal;\n"); + if ( !GenCC ) gen1("zzBLOCK(zztasp%d);\n", BlkLevel); + if ( !GenCC ) gen("zzMake0;\n"); + if ( FoundException ) gen("*_retsignal = NoSignal;\n"); + if ( !GenCC ) gen("{\n"); + + if ( has_guess_block_as_first_item((Junction *)q->p1) ) + { + gen("zzGUESS_BLOCK\n"); + } + + /* L o o k F o r I n i t A c t i o n */ + if ( ((Junction *)q->p1)->jtype == aSubBlk ) + a = findImmedAction( ((Junction *)q->p1)->p1 ); + else + a = findImmedAction( q->p1 ); /* only one alternative in rule */ + if ( a!=NULL && !a->is_predicate ) + { + dumpAction(a->action, output, tabs, a->file, a->line, 1); + a->done = 1; /* ignore action. We have already handled it */ + } + if ( TraceGen ) + if ( GenCC ) {gen1("tracein(\"%s\");\n", q->rname);} + else gen1("zzTRACEIN((ANTLRChar *)\"%s\");\n", q->rname); + + BlkLevel++; + q->visited = TRUE; /* mark RULE as visited for FIRST/FOLLOW */ + f = genBlk((Junction *)q->p1, RuleBlk, &max_k, &need_right_curly); + if ( q->p1 != NULL ) + if ( ((Junction *)q->p1)->p2 != NULL ) + {tab(); makeErrorClause((Junction *)q->p1,f,max_k);} + { int i; for (i=1; i<=need_right_curly; i++) {tabs--; gen("}\n");} } + freeBlkFsets((Junction *)q->p1); + q->visited = FALSE; + --BlkLevel; + if ( !GenCC ) gen1("zzEXIT(zztasp%d);\n", BlkLevel); + + if ( TraceGen ) + if ( GenCC ) {gen1("traceout(\"%s\");\n", q->rname);} + else gen1("zzTRACEOUT((ANTLRChar *)\"%s\");\n", q->rname); + + if ( q->ret!=NULL ) gen("return _retv;\n") else gen("return;\n"); + /* E r r o r R e c o v e r y */ + NewSet(); + rk = empty; + REACH(q->end, 1, &rk, follow); + FillSet( follow ); + set_free( follow ); + + _gen("fail:\n"); + if ( !GenCC ) gen("zzEXIT(zztasp1);\n"); + if ( FoundGuessBlk ) + if ( !GenCC ) {gen("if ( zzguessing ) zzGUESS_FAIL;\n");} + else gen("if ( guessing ) zzGUESS_FAIL;\n"); + if ( q->erraction!=NULL ) + dumpAction(q->erraction, output, tabs, q->file, q->line, 1); + if ( GenCC ) + { + gen1("syn(zzBadTok, %s, zzMissSet, zzMissTok, zzErrk);\n", + r->egroup==NULL?"(ANTLRChar *)\"\"":r->egroup); + } + else + { + gen1("zzsyn(zzMissText, zzBadTok, %s, zzMissSet, zzMissTok, zzErrk, zzBadText);\n", + r->egroup==NULL?"(ANTLRChar *)\"\"":r->egroup); + } + gen3("%sresynch(setwd%d, 0x%x);\n", GenCC?"":"zz", wordnum, 1<rname);} + else gen1("zzTRACEOUT((ANTLRChar *)\"%s\");\n", q->rname); + + if ( q->ret!=NULL ) {gen("return _retv;\n");} + else if ( q->exceptions!=NULL ) gen("return;\n"); + if ( !GenCC ) gen("}\n"); + + /* Gen code for exception handlers */ + if ( q->exceptions!=NULL ) + { + gen("/* exception handlers */\n"); + dumpExceptions(q->exceptions); + if ( !r->has_rule_exception ) + { + _gen("_handler:\n"); + gen("zzdflthandlers(_signal,_retsignal);\n"); + } + _gen("_adios:\n"); + if ( q->ret!=NULL ) {gen("return _retv;\n");} + else {gen("return;\n");} + } + else if ( FoundException ) + { + _gen("_handler:\n"); + gen("zzdflthandlers(_signal,_retsignal);\n"); + } + + tabs--; + gen("}\n"); + + if ( q->p2 != NULL ) {TRANS(q->p2);} /* generate code for next rule too */ + else dumpAfterActions( output ); +} + +static void +#ifdef __USE_PROTOS +DumpFuncHeader( Junction *q, RuleEntry *r ) +#else +DumpFuncHeader( q, r ) +Junction *q; +RuleEntry *r; +#endif +{ + /* A N S I */ + _gen("\n"); + if ( q->ret!=NULL ) + { + if ( HasComma(q->ret) ) + { + if (GenCC) gen2("%s::_rv%d\n", CurrentClassName, r->rulenum) + else gen1("struct _rv%d\n",r->rulenum); + } + else + { + DumpType(q->ret, output); + gen("\n"); + } + } + else + { + _gen("void\n"); + } + if ( !GenCC ) _gen("#ifdef __STDC__\n"); + if ( !GenCC ) gen2("%s%s(", RulePrefix, q->rname) + else gen2("%s::%s(", CurrentClassName, q->rname); + DumpANSIFunctionArgDef(output,q); + _gen("\n"); + + if ( GenCC ) {gen("{\n"); return;} + + /* K & R */ + gen("#else\n"); + gen2("%s%s(", RulePrefix, q->rname); + if ( GenAST ) + { + _gen("_root"); + if ( q->pdecl!=NULL ) _gen(","); + } + if ( FoundException ) + { + if ( GenAST ) _gen(","); + _gen("_retsignal"); + if ( q->pdecl!=NULL ) _gen(","); + } + + DumpListOfParmNames( q->pdecl, output ); + gen(")\n"); + if ( GenAST ) gen("AST **_root;\n"); + if ( FoundException ) gen("int *_retsignal;\n"); + DumpOldStyleParms( q->pdecl, output ); + gen("#endif\n"); + gen("{\n"); +} + +void +#ifdef __USE_PROTOS +DumpANSIFunctionArgDef(FILE *f, Junction *q) +#else +DumpANSIFunctionArgDef(f,q) +FILE *f; +Junction *q; +#endif +{ + if ( GenAST ) + { + if ( GenCC ) {fprintf(f,"ASTBase **_root");} + else fprintf(f,"AST**_root"); + if ( !FoundException && q->pdecl!=NULL ) fprintf(f,","); + } + if ( FoundException ) + { + if ( GenAST ) fprintf(f,","); + fprintf(f,"int *_retsignal"); + if ( q->pdecl!=NULL ) fprintf(f,","); + } + if ( q->pdecl!=NULL ) {fprintf(f,"%s", q->pdecl);} + else if ( !GenAST && !FoundException ) fprintf(f,"void"); + fprintf(f,")"); +} + +void +#ifdef __USE_PROTOS +genJunction( Junction *q ) +#else +genJunction( q ) +Junction *q; +#endif +{ + require(q->ntype == nJunction, "genJunction: not junction"); + require(q->jtype == Generic, "genJunction: not generic junction"); + + if ( q->p1 != NULL ) TRANS(q->p1); + if ( q->p2 != NULL ) TRANS(q->p2); +} + +void +#ifdef __USE_PROTOS +genEndBlk( Junction *q ) +#else +genEndBlk( q ) +Junction *q; +#endif +{ +} + +void +#ifdef __USE_PROTOS +genEndRule( Junction *q ) +#else +genEndRule( q ) +Junction *q; +#endif +{ +} + +void +#ifdef __USE_PROTOS +genHdr( int file ) +#else +genHdr( file ) +int file; +#endif +{ + _gen("/*\n"); + _gen(" * A n t l r T r a n s l a t i o n H e a d e r\n"); + _gen(" *\n"); + _gen(" * Terence Parr, Will Cohen, and Hank Dietz: 1989-1994\n"); + _gen(" * Purdue University Electrical Engineering\n"); + _gen(" * With AHPCRC, University of Minnesota\n"); + _gen1(" * ANTLR Version %s\n", Version); + _gen(" */\n"); + _gen("#include \n"); + _gen1("#define ANTLR_VERSION %s\n", VersionDef); + if ( strcmp(ParserName, DefaultParserName)!=0 ) + _gen2("#define %s %s\n", DefaultParserName, ParserName); + if ( strcmp(ParserName, DefaultParserName)!=0 ) + {_gen1("#include \"%s\"\n", RemapFileName);} + if ( GenLineInfo ) _gen2(LineInfoFormatStr, 1, FileStr[file]); + if ( GenCC ) { + if ( UserTokenDefsFile != NULL ) + fprintf(output, "#include %s\n", UserTokenDefsFile); + else + fprintf(output, "#include \"%s\"\n", DefFileName); + } + + if ( HdrAction != NULL ) dumpAction( HdrAction, output, 0, -1, 0, 1); + if ( !GenCC && FoundGuessBlk ) + { + _gen("#define ZZCAN_GUESS\n"); + _gen("#include \n"); + } + if ( FoundException ) + { + _gen("#define EXCEPTION_HANDLING\n"); + _gen1("#define NUM_SIGNALS %d\n", NumSignals); + } + if ( !GenCC && OutputLL_k > 1 ) _gen1("#define LL_K %d\n", OutputLL_k); + if ( GenAST&&!GenCC ) _gen("#define GENAST\n\n"); + if ( GenAST ) { + if ( GenCC ) {_gen1("#include \"%s\"\n\n", ASTBASE_H);} + else _gen("#include \"ast.h\"\n\n"); + } + if ( !GenCC && DemandLookahead ) _gen("#define DEMAND_LOOK\n\n"); +#ifdef DUM + if ( !GenCC && LexGen ) { + _gen1("#define zzEOF_TOKEN %d\n", (TokenInd!=NULL?TokenInd[EofToken]:EofToken)); + } +#endif + /* ###WARNING: This will have to change when SetWordSize changes */ + if ( !GenCC ) _gen1("#define zzSET_SIZE %d\n", NumWords(TokenNum-1)*sizeof(unsigned)); + if ( !GenCC ) {_gen("#include \"antlr.h\"\n");} + else { + _gen1("#include \"%s\"\n", APARSER_H); + _gen1("#include \"%s.h\"\n", CurrentClassName); + } + if ( !GenCC ) { + if ( UserDefdTokens ) + {_gen1("#include %s\n", UserTokenDefsFile);} + /* still need this one as it has the func prototypes */ + _gen1("#include \"%s\"\n", DefFileName); + } + /* still need this one as it defines the DLG interface */ + if ( !GenCC ) _gen("#include \"dlgdef.h\"\n"); + if ( LexGen && GenCC ) _gen1("#include \"%s\"\n", DLEXERBASE_H); + if ( GenCC ) _gen1("#include \"%s\"\n", ATOKPTR_H); + if ( !GenCC && LexGen ) _gen1("#include \"%s\"\n", ModeFileName); + _gen("#ifndef PURIFY\n#define PURIFY(r,s)\n#endif\n"); +} + +void +#ifdef __USE_PROTOS +genHdr1( int file ) +#else +genHdr1( file ) +int file; +#endif +{ + ListNode *p; + + genHdr(file); + if ( GenAST ) + { + if ( !GenCC ) { + _gen("#include \"ast.c\"\n"); + _gen("zzASTgvars\n\n"); + } + } + if ( !GenCC ) _gen("ANTLR_INFO\n"); + if ( BeforeActions != NULL ) + { + for (p = BeforeActions->next; p!=NULL; p=p->next) + { + UserAction *ua = (UserAction *)p->elem; + dumpAction( ua->action, output, 0, ua->file, ua->line, 1); + } + } + + if ( !FoundException ) return; + + if ( GenCC ) + { + _gen1("\nvoid %s::\n", CurrentClassName); + _gen("zzdflthandlers( int _signal, int *_retsignal )\n"); + _gen("{\n"); + } + else + { + _gen("\nvoid\n"); + _gen("#ifdef __STDC__\n"); + _gen("zzdflthandlers( int _signal, int *_retsignal )\n"); + _gen("#else\n"); + _gen("zzdflthandlers( _signal, _retsignal )\n"); + _gen("int _signal;\n"); + _gen("int *_retsignal;\n"); + _gen("#endif\n"); + _gen("{\n"); + } + tabs++; + if ( DefaultExGroup!=NULL ) + { + dumpException(DefaultExGroup, 1); + if ( !hasDefaultException(DefaultExGroup) ) + { + gen("default :\n"); + tabs++; + gen("*_retsignal = _signal;\n"); + tabs--; + gen("}\n"); + } + } + else { + gen("*_retsignal = _signal;\n"); + } + + tabs--; + _gen("}\n\n"); +} + +void +#ifdef __USE_PROTOS +genStdPCCTSIncludeFile( FILE *f ) +#else +genStdPCCTSIncludeFile( f ) +FILE *f; +#endif +{ + fprintf(f,"#ifndef STDPCCTS_H\n"); + fprintf(f,"#define STDPCCTS_H\n"); + fprintf(f,"/*\n"); + fprintf(f," * %s -- P C C T S I n c l u d e\n", stdpccts); + fprintf(f," *\n"); + fprintf(f," * Terence Parr, Will Cohen, and Hank Dietz: 1989-1994\n"); + fprintf(f," * Purdue University Electrical Engineering\n"); + fprintf(f," * With AHPCRC, University of Minnesota\n"); + fprintf(f," * ANTLR Version %s\n", Version); + fprintf(f," */\n"); + fprintf(f,"#include \n"); + fprintf(f,"#define ANTLR_VERSION %s\n", VersionDef); + if ( GenCC ) + { + if ( UserDefdTokens ) + fprintf(f, "#include %s\n", UserTokenDefsFile); + else { + fprintf(f, "#include \"%s\"\n", DefFileName); + } + + fprintf(f, "#include \"%s\"\n", ATOKEN_H); + + if ( HdrAction != NULL ) dumpAction( HdrAction, f, 0, -1, 0, 1); + + fprintf(f, "#include \"%s\"\n", ATOKENBUFFER_H); + + if ( OutputLL_k > 1 ) fprintf(f,"static const unsigned LL_K=%d;\n", OutputLL_k); + if ( GenAST ) { + fprintf(f, "#include \"%s\"\n", ASTBASE_H); + } + fprintf(f,"#include \"%s\"\n", APARSER_H); + fprintf(f,"#include \"%s.h\"\n", CurrentClassName); + if ( LexGen ) fprintf(f,"#include \"%s\"\n", DLEXERBASE_H); + fprintf(f, "#endif\n"); + return; + } + + if ( strcmp(ParserName, DefaultParserName)!=0 ) + fprintf(f, "#define %s %s\n", DefaultParserName, ParserName); + if ( strcmp(ParserName, DefaultParserName)!=0 ) + fprintf(f, "#include \"%s\"\n", RemapFileName); + if ( UserTokenDefsFile != NULL ) + fprintf(f, "#include %s\n", UserTokenDefsFile); + if ( HdrAction != NULL ) dumpAction( HdrAction, f, 0, -1, 0, 1); + if ( FoundGuessBlk ) + { + fprintf(f,"#define ZZCAN_GUESS\n"); + fprintf(f,"#include \n"); + } + if ( OutputLL_k > 1 ) fprintf(f,"#define LL_K %d\n", OutputLL_k); + if ( GenAST ) fprintf(f,"#define GENAST\n"); + if ( FoundException ) + { + _gen("#define EXCEPTION_HANDLING\n"); + _gen1("#define NUM_SIGNALS %d\n", NumSignals); + } + if ( DemandLookahead ) fprintf(f,"#define DEMAND_LOOK\n"); +#ifdef DUM + if ( LexGen ) fprintf(f, "#define zzEOF_TOKEN %d\n", (TokenInd!=NULL?TokenInd[EofToken]:EofToken)); +#endif + /* ###WARNING: This will have to change when SetWordSize changes */ + fprintf(f, "#define zzSET_SIZE %d\n", NumWords(TokenNum-1)*sizeof(unsigned)); + fprintf(f,"#include \"antlr.h\"\n"); + if ( GenAST ) fprintf(f,"#include \"ast.h\"\n"); + if ( UserDefdTokens ) + fprintf(f, "#include %s\n", UserTokenDefsFile); + /* still need this one as it has the func prototypes */ + fprintf(f, "#include \"%s\"\n", DefFileName); + /* still need this one as it defines the DLG interface */ + fprintf(f,"#include \"dlgdef.h\"\n"); + /* don't need this one unless DLG is used */ + if ( LexGen ) fprintf(f,"#include \"%s\"\n", ModeFileName); + fprintf(f,"#endif\n"); +} + +/* dump action 's' to file 'output' starting at "local" tab 'tabs' + Dump line information in front of action if GenLineInfo is set + If file == -1 then GenLineInfo is ignored. + The user may redefine the LineInfoFormatStr to his/her liking + most compilers will like the default, however. + + June '93; changed so that empty lines are left alone so that + line information is correct for the compiler/debuggers. +*/ +void +#ifdef __USE_PROTOS +dumpAction( char *s, FILE *output, int tabs, int file, int line, +int final_newline ) +#else +dumpAction( s, output, tabs, file, line, final_newline ) +char *s; +FILE *output; +int tabs; +int file; +int line; +int final_newline; +#endif +{ + int inDQuote, inSQuote; + require(s!=NULL, "dumpAction: NULL action"); + require(output!=NULL, eMsg1("dumpAction: output FILE is NULL for %s",s)); + + if ( GenLineInfo && file != -1 ) + { + fprintf(output, LineInfoFormatStr, line, FileStr[file]); + } + PastWhiteSpace( s ); + /* don't print a tab if first non-white char is a # (preprocessor command) */ + if ( *s!='#' ) {TAB;} + inDQuote = inSQuote = FALSE; + while ( *s != '\0' ) + { + if ( *s == '\\' ) + { + fputc( *s++, output ); /* Avoid '"' Case */ + if ( *s == '\0' ) return; + if ( *s == '\'' ) fputc( *s++, output ); + if ( *s == '\"' ) fputc( *s++, output ); + } + if ( *s == '\'' ) + { + if ( !inDQuote ) inSQuote = !inSQuote; + } + if ( *s == '"' ) + { + if ( !inSQuote ) inDQuote = !inDQuote; + } + if ( *s == '\n' ) + { + fputc('\n', output); + s++; + PastWhiteSpace( s ); + if ( *s == '}' ) + { + --tabs; + TAB; + fputc( *s++, output ); + continue; + } + if ( *s == '\0' ) return; + if ( *s != '#' ) /* #define, #endif etc.. start at col 1 */ + { + TAB; + } + } + if ( *s == '}' && !(inSQuote || inDQuote) ) + { + --tabs; /* Indent one fewer */ + } + if ( *s == '{' && !(inSQuote || inDQuote) ) + { + tabs++; /* Indent one more */ + } + fputc( *s, output ); + s++; + } + if ( final_newline ) fputc('\n', output); +} + +static void +#ifdef __USE_PROTOS +dumpAfterActions( FILE *output ) +#else +dumpAfterActions( output ) +FILE *output; +#endif +{ + ListNode *p; + require(output!=NULL, "dumpAfterActions: output file was NULL for some reason"); + if ( AfterActions != NULL ) + { + for (p = AfterActions->next; p!=NULL; p=p->next) + { + UserAction *ua = (UserAction *)p->elem; + dumpAction( ua->action, output, 0, ua->file, ua->line, 1); + } + } + fclose( output ); +} + +/* + * Find the next action in the stream of execution. Do not pass + * junctions with more than one path leaving them. + * Only pass generic junctions. + * + * Scan forward while (generic junction with p2==NULL) + * If we stop on an action, return ptr to the action + * else return NULL; + */ +static ActionNode * +#ifdef __USE_PROTOS +findImmedAction( Node *q ) +#else +findImmedAction( q ) +Node *q; +#endif +{ + Junction *j; + require(q!=NULL, "findImmedAction: NULL node"); + require(q->ntype>=1 && q->ntype<=NumNodeTypes, "findImmedAction: invalid node"); + + while ( q->ntype == nJunction ) + { + j = (Junction *)q; + if ( j->jtype != Generic || j->p2 != NULL ) return NULL; + q = j->p1; + if ( q == NULL ) return NULL; + } + if ( q->ntype == nAction ) return (ActionNode *)q; + return NULL; +} + +static void +#ifdef __USE_PROTOS +dumpRetValAssign( char *retval, char *ret_def ) +#else +dumpRetValAssign( retval, ret_def ) +char *retval; +char *ret_def; +#endif +{ + char *q = ret_def; + + tab(); + while ( *retval != '\0' ) + { + while ( isspace((*retval)) ) retval++; + while ( *retval!=',' && *retval!='\0' ) fputc(*retval++, output); + fprintf(output, " = _trv."); + + DumpNextNameInDef(&q, output); + fputc(';', output); fputc(' ', output); + if ( *retval == ',' ) retval++; + } +} + +/* This function computes the set of tokens that can possibly be seen k + * tokens in the future from point j + */ +static set +#ifdef __USE_PROTOS +ComputeErrorSet( Junction *j, int k ) +#else +ComputeErrorSet( j, k ) +Junction *j; +int k; +#endif +{ + Junction *alt1; + set a, rk, f; + require(j->ntype==nJunction, "ComputeErrorSet: non junction passed"); + + f = rk = empty; + for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2) + { + REACH(alt1->p1, k, &rk, a); + require(set_nil(rk), "ComputeErrorSet: rk != nil"); + set_free(rk); + set_orin(&f, a); + set_free(a); + } + return f; +} + +static char * +#ifdef __USE_PROTOS +tokenFollowSet(TokNode *p) +#else +tokenFollowSet(p) +TokNode *p; +#endif +{ + static char buf[100]; + set rk, a; + int n; + rk = empty; + + REACH(p->next, 1, &rk, a); + require(set_nil(rk), "rk != nil"); + set_free(rk); + n = DefErrSet( &a, 0, NULL ); + set_free(a); + if ( GenCC ) + sprintf(buf, "err%d", n); + else + sprintf(buf, "zzerr%d", n); + return buf; +} + +static void +#ifdef __USE_PROTOS +makeErrorClause( Junction *q, set f, int max_k ) +#else +makeErrorClause( q, f, max_k ) +Junction *q; +set f; +int max_k; +#endif +{ + if ( FoundException ) + { + _gen("else {\n"); + tabs++; + if ( FoundGuessBlk ) + { + if ( GenCC ) {gen("if ( guessing ) goto fail;\n");} + else gen("if ( zzguessing ) goto fail;\n"); + } + gen("if (_sva) _signal=NoViableAlt;\n"); + gen("else _signal=NoSemViableAlt;\n"); + gen("goto _handler;\n"); + tabs--; + gen("}\n"); + return; + } + + if ( max_k == 1 ) + { + if ( GenCC ) {_gen1("else {FAIL(1,err%d", DefErrSet(&f,1,NULL));} + else _gen1("else {zzFAIL(1,zzerr%d", DefErrSet(&f,1,NULL)) + set_free(f); + } + else + { + int i; + set_free(f); + if ( GenCC ) {_gen1("else {FAIL(%d", max_k);} + else _gen1("else {zzFAIL(%d", max_k); + for (i=1; i<=max_k; i++) + { + f = ComputeErrorSet(q, i); + if ( GenCC ) {_gen1(",err%d", DefErrSet( &f, 1, NULL ));} + else _gen1(",zzerr%d", DefErrSet( &f, 1, NULL )); + + set_free(f); + } + } + _gen(",&zzMissSet,&zzMissText,&zzBadTok,&zzBadText,&zzErrk); goto fail;}\n"); +} + + + + + +/* If predicates are allowed in parsing expressions: + * + * ( production 1 + * | production 2 + * ... + * | production n + * ) + * + * where production 1 yields visible predicates: <>? <>? + * + * generates (if -prc on): + * + * if ( (production 1 prediction) && + * (((context_of_pred ? pred : 1) && + * (context_of_pred2 ? pred2 : 1))||!(ctx_pred||ctx_pred2))) ) { + * ... + * } + * else if ( production 2 prediction ) { + * ... + * } + * ... + * + * A predicate tree of + * + * p1 + * | + * p2--p3 + * + * results in + * + * if ( (production 1 prediction) && + * (((context_of_p1 ? p1 : 1) && + * ((context_of_p2 ? p2 : 0)|| + * (context_of_p3 ? p3 : 0))) || !(ctx_p1||ctx_p2||ctx_p3)) + * ) { + * ... + * } + * + * If no context, then just test predicate expression. + */ +#ifdef DUM +void +#ifdef __USE_PROTOS +genPredTree( Predicate *p, Junction *j ) +#else +genPredTree( p, j ) +Predicate *p; +Junction *j; +#endif +{ + int context_was_present = 0; + Predicate *start_of_OR_list = NULL; + + _gen("("); + start_of_OR_list = p; + if ( HoistPredicateContext ) _gen("("); + + for (; p!=NULL; p=p->right) + { + if ( HoistPredicateContext ) + { + context_was_present = 0; + if ( LL_k>1 && p->tcontext!=NULL ) + { + context_was_present = 1; + _gen("(("); + genExprTree(p->tcontext, 1); + _gen(")"); + } + else if ( LL_k==1 && set_deg(p->scontext[1])>0 ) + { + context_was_present = 1; + _gen("(("); + genExprSets(&(p->scontext[0]), CLL_k); + _gen(")"); + } + /* &&'s must use ?: still; only leaves with no parent can avoid ?: */ + if ( p->down!=NULL || p->up!=NULL ) {_gen(" ? ");} + else {_gen(" && ");} + } + + if ( FoundException ) {_gen("(_sva=(");} + else {_gen("(");} + dumpAction(p->expr, output, 0, -1 /*indicates no line info*/, j->line, 0); + if ( FoundException ) {_gen("))");} + else {_gen(")");} + + if ( HoistPredicateContext && context_was_present ) + { + if ( p->down!=NULL || p->up!=NULL ) { /* &&'s must use ?: still */ + _gen(" : "); + genPredTermEliminator(p); + } + _gen(")"); + } + + if ( p->down!=NULL ) + { + _gen("&&"); + if ( HoistPredicateContext && context_was_present ) _gen("("); + genPredTree(p->down, j); + if ( HoistPredicateContext && context_was_present && ) + { + _gen(") || !("); + genCombinedPredTreeContext(start_of_OR_list); + _gen(")"); + } + } + + if ( p->right!=NULL ) _gen("||"); + } + + if ( HoistPredicateContext ) + { + _gen(")) || !("); + genCombinedPredTreeContext(start_of_OR_list); + _gen(")"); + } + _gen(")"); +} +#endif -- 2.40.0