/*** 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/* #define PRIVATE static */#define PRIVATE#ifdef TEST#define MAXRHS 5       /* Set low to exercise exception code */#else#define MAXRHS 1000#endifstatic 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 {B_FALSE=0, B_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 predecence is defined */  char *firstset;          /* First-set for all rules of this symbol */  Boolean lambda;          /* True if NT and can generate an empty string */  char *destructor;        /* Code which executes whenever this symbol is                           ** popped from the stack during error processing */  int destructorln;        /* Line number of destructor code */  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 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,    CONFLICT,                /* 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;            /* Sequencial 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 */  int  includeln;          /* Line number for start of include code */  char *error;             /* Code to execute when an error is seen */  int  errorln;            /* Line number for start of error code */  char *overflow;          /* Code to execute on a stack overflow */  int  overflowln;         /* Line number for start of overflow code */  char *failure;           /* Code to execute on parser failure */  int  failureln;          /* Line number for start of failure code */  char *accept;            /* Code to execute when the parser excepts */  int  acceptln;           /* Line number for the start of accept code */  char *extracode;         /* Code appended to the generated file */  int  extracodeln;        /* Line number for the start of the extra code */  char *tokendest;         /* Code to execute to destroy token data */  int  tokendestln;        /* Line number for token destroyer code */  char *vardest;           /* Code for the default non-terminal destructor */  int  vardestln;          /* Line number for default non-term destructor code*/  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 grammer */  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 *)malloc( sizeof(struct action)*amt );    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 ){    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 );