/*

** This file contains all sources (including headers) to the LEMON

** LALR(1) parser generator. The sources have been combined into a

** single file to make it easy to include LEMON in the source tree

** and Makefile of another program.

**

** The author of this program disclaims copyright.

*/

#include <stdio.h>

#include <stdarg.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

#include <assert.h>

#ifndef __WIN32__

# if defined(_WIN32) || defined(WIN32)

# define __WIN32__

# endif

#endif

#ifdef __WIN32__

extern int access();

#else

#include <unistd.h>

#endif

/* #define PRIVATE static */

#define PRIVATE

#ifdef TEST

#define MAXRHS 5 /* Set low to exercise exception code */

#else

#define MAXRHS 1000

#endif

static char *msort(char*,char**,int(*)(const char*,const char*));

static struct action *Action_new(void);

static struct action *Action_sort(struct action *);

/********** From the file "build.h" ************************************/

void FindRulePrecedences();

void FindFirstSets();

void FindStates();

void FindLinks();

void FindFollowSets();

void FindActions();

/********* From the file "configlist.h" *********************************/

void Configlist_init(/* void */);

struct config *Configlist_add(/* struct rule *, int */);

struct config *Configlist_addbasis(/* struct rule *, int */);

void Configlist_closure(/* void */);

void Configlist_sort(/* void */);

void Configlist_sortbasis(/* void */);

struct config *Configlist_return(/* void */);

struct config *Configlist_basis(/* void */);

void Configlist_eat(/* struct config * */);

void Configlist_reset(/* void */);

/********* From the file "error.h" ***************************************/

void ErrorMsg(const char *, int,const char *, ...);

/****** From the file "option.h" ******************************************/

struct s_options {

enum { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,

OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;

char *label;

char *arg;

char *message;

};

int OptInit(/* char**,struct s_options*,FILE* */);

int OptNArgs(/* void */);

char *OptArg(/* int */);

void OptErr(/* int */);

void OptPrint(/* void */);

/******** From the file "parse.h" *****************************************/

void Parse(/* struct lemon *lemp */);

/********* From the file "plink.h" ***************************************/

struct plink *Plink_new(/* void */);

void Plink_add(/* struct plink **, struct config * */);

void Plink_copy(/* struct plink **, struct plink * */);

void Plink_delete(/* struct plink * */);

/********** From the file "report.h" *************************************/

void Reprint(/* struct lemon * */);

void ReportOutput(/* struct lemon * */);

void ReportTable(/* struct lemon * */);

void ReportHeader(/* struct lemon * */);

void CompressTables(/* struct lemon * */);

void ResortStates(/* struct lemon * */);

/********** From the file "set.h" ****************************************/

void SetSize(/* int N */); /* All sets will be of size N */

char *SetNew(/* void */); /* A new set for element 0..N */

void SetFree(/* char* */); /* Deallocate a set */

int SetAdd(/* char*,int */); /* Add element to a set */

int SetUnion(/* char *A,char *B */); /* A <- A U B, thru element N */

#define SetFind(X,Y) (X[Y]) /* True if Y is in set X */

/********** From the file "struct.h" *************************************/

/*

** Principal data structures for the LEMON parser generator.

*/

typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;

/* Symbols (terminals and nonterminals) of the grammar are stored

** in the following: */

struct symbol {

char *name; /* Name of the symbol */

int index; /* Index number for this symbol */

enum {

TERMINAL,

NONTERMINAL,

MULTITERMINAL

} type; /* Symbols are all either TERMINALS or NTs */

struct rule *rule; /* Linked list of rules of this (if an NT) */

struct symbol *fallback; /* fallback token in case this token doesn't parse */

int prec; /* Precedence if defined (-1 otherwise) */

enum e_assoc {

LEFT,

RIGHT,

NONE,

UNK

} assoc; /* Associativity if precedence is defined */

char *firstset; /* First-set for all rules of this symbol */

Boolean lambda; /* True if NT and can generate an empty string */

int useCnt; /* Number of times used */

char *destructor; /* Code which executes whenever this symbol is

** popped from the stack during error processing */

int destLineno; /* Line number for start of destructor */

char *datatype; /* The data type of information held by this

** object. Only used if type==NONTERMINAL */

int dtnum; /* The data type number. In the parser, the value

** stack is a union. The .yy%d element of this

** union is the correct data type for this object */

/* The following fields are used by MULTITERMINALs only */

int nsubsym; /* Number of constituent symbols in the MULTI */

struct symbol **subsym; /* Array of constituent symbols */

};

/* Each production rule in the grammar is stored in the following

** structure. */

struct rule {

struct symbol *lhs; /* Left-hand side of the rule */

char *lhsalias; /* Alias for the LHS (NULL if none) */

int lhsStart; /* True if left-hand side is the start symbol */

int ruleline; /* Line number for the rule */

int nrhs; /* Number of RHS symbols */

struct symbol **rhs; /* The RHS symbols */

char **rhsalias; /* An alias for each RHS symbol (NULL if none) */

int line; /* Line number at which code begins */

char *code; /* The code executed when this rule is reduced */

struct symbol *precsym; /* Precedence symbol for this rule */

int index; /* An index number for this rule */

Boolean canReduce; /* True if this rule is ever reduced */

struct rule *nextlhs; /* Next rule with the same LHS */

struct rule *next; /* Next rule in the global list */

};

/* A configuration is a production rule of the grammar together with

** a mark (dot) showing how much of that rule has been processed so far.

** Configurations also contain a follow-set which is a list of terminal

** symbols which are allowed to immediately follow the end of the rule.

** Every configuration is recorded as an instance of the following: */

struct config {

struct rule *rp; /* The rule upon which the configuration is based */

int dot; /* The parse point */

char *fws; /* Follow-set for this configuration only */

struct plink *fplp; /* Follow-set forward propagation links */

struct plink *bplp; /* Follow-set backwards propagation links */

struct state *stp; /* Pointer to state which contains this */

enum {

COMPLETE, /* The status is used during followset and */

INCOMPLETE /* shift computations */

} status;

struct config *next; /* Next configuration in the state */

struct config *bp; /* The next basis configuration */

};

/* Every shift or reduce operation is stored as one of the following */

struct action {

struct symbol *sp; /* The look-ahead symbol */

enum e_action {

SHIFT,

ACCEPT,

REDUCE,

ERROR,

SSCONFLICT, /* A shift/shift conflict */

SRCONFLICT, /* Was a reduce, but part of a conflict */

RRCONFLICT, /* Was a reduce, but part of a conflict */

SH_RESOLVED, /* Was a shift. Precedence resolved conflict */

RD_RESOLVED, /* Was reduce. Precedence resolved conflict */

NOT_USED /* Deleted by compression */

} type;

union {

struct state *stp; /* The new state, if a shift */

struct rule *rp; /* The rule, if a reduce */

} x;

struct action *next; /* Next action for this state */

struct action *collide; /* Next action with the same hash */

};

/* Each state of the generated parser's finite state machine

** is encoded as an instance of the following structure. */

struct state {

struct config *bp; /* The basis configurations for this state */

struct config *cfp; /* All configurations in this set */

int statenum; /* Sequential number for this state */

struct action *ap; /* Array of actions for this state */

int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */

int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */

int iDflt; /* Default action */

};

#define NO_OFFSET (-2147483647)

/* A followset propagation link indicates that the contents of one

** configuration followset should be propagated to another whenever

** the first changes. */

struct plink {

struct config *cfp; /* The configuration to which linked */

struct plink *next; /* The next propagate link */

};

/* The state vector for the entire parser generator is recorded as

** follows. (LEMON uses no global variables and makes little use of

** static variables. Fields in the following structure can be thought

** of as begin global variables in the program.) */

struct lemon {

struct state **sorted; /* Table of states sorted by state number */

struct rule *rule; /* List of all rules */

int nstate; /* Number of states */

int nrule; /* Number of rules */

int nsymbol; /* Number of terminal and nonterminal symbols */

int nterminal; /* Number of terminal symbols */

struct symbol **symbols; /* Sorted array of pointers to symbols */

int errorcnt; /* Number of errors */

struct symbol *errsym; /* The error symbol */

struct symbol *wildcard; /* Token that matches anything */

char *name; /* Name of the generated parser */

char *arg; /* Declaration of the 3th argument to parser */

char *tokentype; /* Type of terminal symbols in the parser stack */

char *vartype; /* The default type of non-terminal symbols */

char *start; /* Name of the start symbol for the grammar */

char *stacksize; /* Size of the parser stack */

char *include; /* Code to put at the start of the C file */

char *error; /* Code to execute when an error is seen */

char *overflow; /* Code to execute on a stack overflow */

char *failure; /* Code to execute on parser failure */

char *accept; /* Code to execute when the parser excepts */

char *extracode; /* Code appended to the generated file */

char *tokendest; /* Code to execute to destroy token data */

char *vardest; /* Code for the default non-terminal destructor */

char *filename; /* Name of the input file */

char *outname; /* Name of the current output file */

char *tokenprefix; /* A prefix added to token names in the .h file */

int nconflict; /* Number of parsing conflicts */

int tablesize; /* Size of the parse tables */

int basisflag; /* Print only basis configurations */

int has_fallback; /* True if any %fallback is seen in the grammar */

char *argv0; /* Name of the program */

};

#define MemoryCheck(X) if((X)==0){ \

extern void memory_error(); \

memory_error(); \

}

/**************** From the file "table.h" *********************************/

/*

** All code in this file has been automatically generated

** from a specification in the file

** "table.q"

** by the associative array code building program "aagen".

** Do not edit this file! Instead, edit the specification

** file, then rerun aagen.

*/

/*

** Code for processing tables in the LEMON parser generator.

*/

/* Routines for handling a strings */

char *Strsafe();

void Strsafe_init(/* void */);

int Strsafe_insert(/* char * */);

char *Strsafe_find(/* char * */);

/* Routines for handling symbols of the grammar */

struct symbol *Symbol_new();

int Symbolcmpp(/* struct symbol **, struct symbol ** */);

void Symbol_init(/* void */);

int Symbol_insert(/* struct symbol *, char * */);

struct symbol *Symbol_find(/* char * */);

struct symbol *Symbol_Nth(/* int */);

int Symbol_count(/* */);

struct symbol **Symbol_arrayof(/* */);

/* Routines to manage the state table */

int Configcmp(/* struct config *, struct config * */);

struct state *State_new();

void State_init(/* void */);

int State_insert(/* struct state *, struct config * */);

struct state *State_find(/* struct config * */);

struct state **State_arrayof(/* */);

/* Routines used for efficiency in Configlist_add */

void Configtable_init(/* void */);

int Configtable_insert(/* struct config * */);

struct config *Configtable_find(/* struct config * */);

void Configtable_clear(/* int(*)(struct config *) */);

/****************** From the file "action.c" *******************************/

/*

** Routines processing parser actions in the LEMON parser generator.

*/

/* Allocate a new parser action */

static struct action *Action_new(void){

static struct action *freelist = 0;

struct action *new;

if( freelist==0 ){

int i;

int amt = 100;

freelist = (struct action *)calloc(amt, sizeof(struct action));

if( freelist==0 ){

fprintf(stderr,"Unable to allocate memory for a new parser action.");

exit(1);

}

for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];

freelist[amt-1].next = 0;

}

new = freelist;

freelist = freelist->next;

return new;

}

/* Compare two actions for sorting purposes. Return negative, zero, or

** positive if the first action is less than, equal to, or greater than

** the first

*/

static int actioncmp(

struct action *ap1,

struct action *ap2

){

int rc;

rc = ap1->sp->index - ap2->sp->index;

if( rc==0 ){

rc = (int)ap1->type - (int)ap2->type;

}

if( rc==0 && ap1->type==REDUCE ){

rc = ap1->x.rp->index - ap2->x.rp->index;

}

return rc;

}

/* Sort parser actions */

static struct action *Action_sort(

struct action *ap

){

ap = (struct action *)msort((char *)ap,(char **)&ap->next,

(int(*)(const char*,const char*))actioncmp);

return ap;

}

void Action_add(app,type,sp,arg)

struct action **app;

enum e_action type;

struct symbol *sp;

char *arg;

{

struct action *new;

new = Action_new();

new->next = *app;

*app = new;

new->type = type;

new->sp = sp;

if( type==SHIFT ){

new->x.stp = (struct state *)arg;

}else{

new->x.rp = (struct rule *)arg;

}

}

/********************** New code to implement the "acttab" module ***********/

/*

** This module implements routines use to construct the yy_action[] table.

*/

/*

** The state of the yy_action table under construction is an instance of

** the following structure

*/

typedef struct acttab acttab;

struct acttab {

int nAction; /* Number of used slots in aAction[] */

int nActionAlloc; /* Slots allocated for aAction[] */

struct {

int lookahead; /* Value of the lookahead token */

int action; /* Action to take on the given lookahead */

} *aAction, /* The yy_action[] table under construction */

*aLookahead; /* A single new transaction set */

int mnLookahead; /* Minimum aLookahead[].lookahead */

int mnAction; /* Action associated with mnLookahead */

int mxLookahead; /* Maximum aLookahead[].lookahead */

int nLookahead; /* Used slots in aLookahead[] */

int nLookaheadAlloc; /* Slots allocated in aLookahead[] */

};

/* Return the number of entries in the yy_action table */

#define acttab_size(X) ((X)->nAction)

/* The value for the N-th entry in yy_action */

#define acttab_yyaction(X,N) ((X)->aAction[N].action)

/* The value for the N-th entry in yy_lookahead */

#define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)

/* Free all memory associated with the given acttab */

void acttab_free(acttab *p){

free( p->aAction );

free( p->aLookahead );

free( p );

}

/* Allocate a new acttab structure */

acttab *acttab_alloc(void){

acttab *p = calloc( 1, sizeof(*p) );

if( p==0 ){

fprintf(stderr,"Unable to allocate memory for a new acttab.");

exit(1);

}

memset(p, 0, sizeof(*p));

return p;

}

/* Add a new action to the current transaction set

*/

void acttab_action(acttab *p, int lookahead, int action){

if( p->nLookahead>=p->nLookaheadAlloc ){

p->nLookaheadAlloc += 25;

p->aLookahead = realloc( p->aLookahead,

sizeof(p->aLookahead[0])*p->nLookaheadAlloc );

if( p->aLookahead==0 ){

fprintf(stderr,"malloc failed\n");

exit(1);

}

}

if( p->nLookahead==0 ){

p->mxLookahead = lookahead;

p->mnLookahead = lookahead;

p->mnAction = action;

}else{

if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;

if( p->mnLookahead>lookahead ){

p->mnLookahead = lookahead;

p->mnAction = action;

}

}

p->aLookahead[p->nLookahead].lookahead = lookahead;

p->aLookahead[p->nLookahead].action = action;

p->nLookahead++;

}

/*

** Add the transaction set built up with prior calls to acttab_action()

** into the current action table. Then reset the transaction set back

** to an empty set in preparation for a new round of acttab_action() calls.

**

** Return the offset into the action table of the new transaction.

*/

int acttab_insert(acttab *p){

int i, j, k, n;

assert( p->nLookahead>0 );

/* Make sure we have enough space to hold the expanded action table

** in the worst case. The worst case occurs if the transaction set

** must be appended to the current action table

*/

n = p->mxLookahead + 1;

if( p->nAction + n >= p->nActionAlloc ){

int oldAlloc = p->nActionAlloc;

p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;

p->aAction = realloc( p->aAction,

sizeof(p->aAction[0])*p->nActionAlloc);

if( p->aAction==0 ){

fprintf(stderr,"malloc failed\n");

exit(1);

}

for(i=oldAlloc; i<p->nActionAlloc; i++){

p->aAction[i].lookahead = -1;

p->aAction[i].action = -1;

}

}

/* Scan the existing action table looking for an offset where we can

** insert the current transaction set. Fall out of the loop when that

** offset is found. In the worst case, we fall out of the loop when

** i reaches p->nAction, which means we append the new transaction set.

**

** i is the index in p->aAction[] where p->mnLookahead is inserted.

*/

for(i=0; i<p->nAction+p->mnLookahead; i++){

if( p->aAction[i].lookahead<0 ){

for(j=0; j<p->nLookahead; j++){

k = p->aLookahead[j].lookahead - p->mnLookahead + i;

if( k<0 ) break;

if( p->aAction[k].lookahead>=0 ) break;

}

if( j<p->nLookahead ) continue;

for(j=0; j<p->nAction; j++){

if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;

}

if( j==p->nAction ){

break; /* Fits in empty slots */

}

}else if( p->aAction[i].lookahead==p->mnLookahead ){

if( p->aAction[i].action!=p->mnAction ) continue;

for(j=0; j<p->nLookahead; j++){

k = p->aLookahead[j].lookahead - p->mnLookahead + i;

if( k<0 || k>=p->nAction ) break;

if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;

if( p->aLookahead[j].action!=p->aAction[k].action ) break;

}

if( j<p->nLookahead ) continue;

n = 0;

for(j=0; j<p->nAction; j++){

if( p->aAction[j].lookahead<0 ) continue;

if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;

}

if( n==p->nLookahead ){

break; /* Same as a prior transaction set */

}

}

}

/* Insert transaction set at index i. */

for(j=0; j<p->nLookahead; j++){

k = p->aLookahead[j].lookahead - p->mnLookahead + i;

p->aAction[k] = p->aLookahead[j];

if( k>=p->nAction ) p->nAction = k+1;

}

p->nLookahead = 0;

/* Return the offset that is added to the lookahead in order to get the

** index into yy_action of the action */

return i - p->mnLookahead;

}

/********************** From the file "build.c" *****************************/

/*

** Routines to construction the finite state machine for the LEMON

** parser generator.

*/

/* Find a precedence symbol of every rule in the grammar.

**

** Those rules which have a precedence symbol coded in the input

** grammar using the "[symbol]" construct will already have the

** rp->precsym field filled. Other rules take as their precedence

** symbol the first RHS symbol with a defined precedence. If there

** are not RHS symbols with a defined precedence, the precedence

** symbol field is left blank.

*/

void FindRulePrecedences(xp)

struct lemon *xp;

{

struct rule *rp;

for(rp=xp->rule; rp; rp=rp->next){

if( rp->precsym==0 ){

int i, j;

for(i=0; i<rp->nrhs && rp->precsym==0; i++){

struct symbol *sp = rp->rhs[i];

if( sp->type==MULTITERMINAL ){

for(j=0; j<sp->nsubsym; j++){

if( sp->subsym[j]->prec>=0 ){

rp->precsym = sp->subsym[j];

break;

}

}

}else if( sp->prec>=0 ){

rp->precsym = rp->rhs[i];

}

}

}

}

return;

}

/* Find all nonterminals which will generate the empty string.

** Then go back and compute the first sets of every nonterminal.

** The first set is the set of all terminal symbols which can begin

** a string generated by that nonterminal.

*/

void FindFirstSets(lemp)

struct lemon *lemp;

{

int i, j;

struct rule *rp;

int progress;

for(i=0; i<lemp->nsymbol; i++){

lemp->symbols[i]->lambda = LEMON_FALSE;

}

for(i=lemp->nterminal; i<lemp->nsymbol; i++){

lemp->symbols[i]->firstset = SetNew();

}

/* First compute all lambdas */

do{

progress = 0;

for(rp=lemp->rule; rp; rp=rp->next){

if( rp->lhs->lambda ) continue;

for(i=0; i<rp->nrhs; i++){

struct symbol *sp = rp->rhs[i];

if( sp->type!=TERMINAL || sp->lambda==LEMON_FALSE ) break;

}

if( i==rp->nrhs ){

rp->lhs->lambda = LEMON_TRUE;

progress = 1;

}

}

}while( progress );

/* Now compute all first sets */

do{

struct symbol *s1, *s2;

progress = 0;

for(rp=lemp->rule; rp; rp=rp->next){

s1 = rp->lhs;

for(i=0; i<rp->nrhs; i++){

s2 = rp->rhs[i];

if( s2->type==TERMINAL ){

progress += SetAdd(s1->firstset,s2->index);

break;

}else if( s2->type==MULTITERMINAL ){

for(j=0; j<s2->nsubsym; j++){

progress += SetAdd(s1->firstset,s2->subsym[j]->index);

}

break;

}else if( s1==s2 ){

if( s1->lambda==LEMON_FALSE ) break;

}else{

progress += SetUnion(s1->firstset,s2->firstset);

if( s2->lambda==LEMON_FALSE ) break;

}

}

}

}while( progress );

return;

}

/* Compute all LR(0) states for the grammar. Links

** are added to between some states so that the LR(1) follow sets

** can be computed later.

*/

PRIVATE struct state *getstate(/* struct lemon * */); /* forward reference */

void FindStates(lemp)

struct lemon *lemp;

{

struct symbol *sp;

struct rule *rp;

Configlist_init();

/* Find the start symbol */

if( lemp->start ){

sp = Symbol_find(lemp->start);

if( sp==0 ){

ErrorMsg(lemp->filename,0,

"The specified start symbol \"%s\" is not \

in a nonterminal of the grammar. \"%s\" will be used as the start \

symbol instead.",lemp->start,lemp->rule->lhs->name);

lemp->errorcnt++;

sp = lemp->rule->lhs;

}

}else{

sp = lemp->rule->lhs;

}

/* Make sure the start symbol doesn't occur on the right-hand side of

** any rule. Report an error if it does. (YACC would generate a new

** start symbol in this case.) */

for(rp=lemp->rule; rp; rp=rp->next){

int i;

for(i=0; i<rp->nrhs; i++){

if( rp->rhs[i]==sp ){ /* FIX ME: Deal with multiterminals */

ErrorMsg(lemp->filename,0,

"The start symbol \"%s\" occurs on the \

right-hand side of a rule. This will result in a parser which \

does not work properly.",sp->name);

lemp->errorcnt++;

}

}

}

/* The basis configuration set for the first state

** is all rules which have the start symbol as their

** left-hand side */

for(rp=sp->rule; rp; rp=rp->nextlhs){

struct config *newcfp;

rp->lhsStart = 1;

newcfp = Configlist_addbasis(rp,0);

SetAdd(newcfp->fws,0);

}

/* Compute the first state. All other states will be

** computed automatically during the computation of the first one.

** The returned pointer to the first state is not used. */

(void)getstate(lemp);

return;

}

/* Return a pointer to a state which is described by the configuration

** list which has been built from calls to Configlist_add.

*/

PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */

PRIVATE struct state *getstate(lemp)

struct lemon *lemp;

{

struct config *cfp, *bp;

struct state *stp;

/* Extract the sorted basis of the new state. The basis was constructed

** by prior calls to "Configlist_addbasis()". */

Configlist_sortbasis();

bp = Configlist_basis();

/* Get a state with the same basis */

stp = State_find(bp);

if( stp ){

/* A state with the same basis already exists! Copy all the follow-set

** propagation links from the state under construction into the

** preexisting state, then return a pointer to the preexisting state */

struct config *x, *y;

for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){

Plink_copy(&y->bplp,x->bplp);

Plink_delete(x->fplp);

x->fplp = x->bplp = 0;

}

cfp = Configlist_return();

Configlist_eat(cfp);

}else{

/* This really is a new state. Construct all the details */

Configlist_closure(lemp); /* Compute the configuration closure */

Configlist_sort(); /* Sort the configuration closure */

cfp = Configlist_return(); /* Get a pointer to the config list */

stp = State_new(); /* A new state structure */

MemoryCheck(stp);

stp->bp = bp; /* Remember the configuration basis */

stp->cfp = cfp; /* Remember the configuration closure */

stp->statenum = lemp->nstate++; /* Every state gets a sequence number */

stp->ap = 0; /* No actions, yet. */

State_insert(stp,stp->bp); /* Add to the state table */

buildshifts(lemp,stp); /* Recursively compute successor states */

}

return stp;

}

/*

** Return true if two symbols are the same.

*/

int same_symbol(a,b)

struct symbol *a;

struct symbol *b;

{

int i;

if( a==b ) return 1;

if( a->type!=MULTITERMINAL ) return 0;

if( b->type!=MULTITERMINAL ) return 0;

if( a->nsubsym!=b->nsubsym ) return 0;

for(i=0; i<a->nsubsym; i++){

if( a->subsym[i]!=b->subsym[i] ) return 0;

}

return 1;

}

/* Construct all successor states to the given state. A "successor"

** state is any state which can be reached by a shift action.

*/

PRIVATE void buildshifts(lemp,stp)

struct lemon *lemp;

struct state *stp; /* The state from which successors are computed */

{

struct config *cfp; /* For looping thru the config closure of "stp" */

struct config *bcfp; /* For the inner loop on config closure of "stp" */

struct config *new; /* */

struct symbol *sp; /* Symbol following the dot in configuration "cfp" */

struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */

struct state *newstp; /* A pointer to a successor state */

/* Each configuration becomes complete after it contibutes to a successor

** state. Initially, all configurations are incomplete */

for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;

/* Loop through all configurations of the state "stp" */

for(cfp=stp->cfp; cfp; cfp=cfp->next){

if( cfp->status==COMPLETE ) continue; /* Already used by inner loop */

if( cfp->dot>=cfp->rp->nrhs ) continue; /* Can't shift this config */

Configlist_reset(); /* Reset the new config set */

sp = cfp->rp->rhs[cfp->dot]; /* Symbol after the dot */

/* For every configuration in the state "stp" which has the symbol "sp"

** following its dot, add the same configuration to the basis set under

** construction but with the dot shifted one symbol to the right. */

for(bcfp=cfp; bcfp; bcfp=bcfp->next){

if( bcfp->status==COMPLETE ) continue; /* Already used */

if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */

bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */

if( !same_symbol(bsp,sp) ) continue; /* Must be same as for "cfp" */

bcfp->status = COMPLETE; /* Mark this config as used */

new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);

Plink_add(&new->bplp,bcfp);

}

/* Get a pointer to the state described by the basis configuration set

** constructed in the preceding loop */

newstp = getstate(lemp);

/* The state "newstp" is reached from the state "stp" by a shift action

** on the symbol "sp" */

if( sp->type==MULTITERMINAL ){

int i;

for(i=0; i<sp->nsubsym; i++){

Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);

}

}else{

Action_add(&stp->ap,SHIFT,sp,(char *)newstp);

}

}

}

/*

** Construct the propagation links

*/

void FindLinks(lemp)

struct lemon *lemp;

{

int i;

struct config *cfp, *other;

struct state *stp;

struct plink *plp;

/* Housekeeping detail:

** Add to every propagate link a pointer back to the state to

** which the link is attached. */

for(i=0; i<lemp->nstate; i++){

stp = lemp->sorted[i];

for(cfp=stp->cfp; cfp; cfp=cfp->next){

cfp->stp = stp;

}

}

/* Convert all backlinks into forward links. Only the forward

** links are used in the follow-set computation. */

for(i=0; i<lemp->nstate; i++){

stp = lemp->sorted[i];

for(cfp=stp->cfp; cfp; cfp=cfp->next){

for(plp=cfp->bplp; plp; plp=plp->next){

other = plp->cfp;

Plink_add(&other->fplp,cfp);

}

}

}

}

/* Compute all followsets.

**

** A followset is the set of all symbols which can come immediately

** after a configuration.

*/

void FindFollowSets(lemp)

struct lemon *lemp;

{

int i;

struct config *cfp;

struct plink *plp;

int progress;

int change;

for(i=0; i<lemp->nstate; i++){

for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){

cfp->status = INCOMPLETE;

}

}

do{

progress = 0;

for(i=0; i<lemp->nstate; i++){

for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){

if( cfp->status==COMPLETE ) continue;

for(plp=cfp->fplp; plp; plp=plp->next){

change = SetUnion(plp->cfp->fws,cfp->fws);

if( change ){

plp->cfp->status = INCOMPLETE;

progress = 1;

}

}

cfp->status = COMPLETE;

}

}

}while( progress );

}

static int resolve_conflict();

/* Compute the reduce actions, and resolve conflicts.

*/

void FindActions(lemp)

struct lemon *lemp;

{

int i,j;

struct config *cfp;

struct state *stp;

struct symbol *sp;

struct rule *rp;

/* Add all of the reduce actions

** A reduce action is added for each element of the followset of

** a configuration which has its dot at the extreme right.

*/

for(i=0; i<lemp->nstate; i++){ /* Loop over all states */

stp = lemp->sorted[i];

for(cfp=stp->cfp; cfp; cfp=cfp->next){ /* Loop over all configurations */

if( cfp->rp->nrhs==cfp->dot ){ /* Is dot at extreme right? */

for(j=0; j<lemp->nterminal; j++){

if( SetFind(cfp->fws,j) ){

/* Add a reduce action to the state "stp" which will reduce by the

** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */

Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);

}

}

}

}

}

/* Add the accepting token */

if( lemp->start ){

sp = Symbol_find(lemp->start);

if( sp==0 ) sp = lemp->rule->lhs;

}else{

sp = lemp->rule->lhs;

}

/* Add to the first state (which is always the starting state of the

** finite state machine) an action to ACCEPT if the lookahead is the

** start nonterminal. */

Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);

/* Resolve conflicts */

for(i=0; i<lemp->nstate; i++){

struct action *ap, *nap;

struct state *stp;

stp = lemp->sorted[i];

/* assert( stp->ap ); */

stp->ap = Action_sort(stp->ap);

for(ap=stp->ap; ap && ap->next; ap=ap->next){

for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){

/* The two actions "ap" and "nap" have the same lookahead.

** Figure out which one should be used */

lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);

}

}

}

/* Report an error for each rule that can never be reduced. */

for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;

for(i=0; i<lemp->nstate; i++){

struct action *ap;

for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){

if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;

}

}

for(rp=lemp->rule; rp; rp=rp->next){

if( rp->canReduce ) continue;

ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");

lemp->errorcnt++;

}

}

/* Resolve a conflict between the two given actions. If the

** conflict can't be resolved, return non-zero.

**

** NO LONGER TRUE:

** To resolve a conflict, first look to see if either action

** is on an error rule. In that case, take the action which

** is not associated with the error rule. If neither or both

** actions are associated with an error rule, then try to

** use precedence to resolve the conflict.

**

** If either action is a SHIFT, then it must be apx. This

** function won't work if apx->type==REDUCE and apy->type==SHIFT.

*/