/*

 * My changes over the original lemon.c from SQLite are encased in

 *  #if __MOJOSHADER__ blocks.  --ryan.

 */

#define __MOJOSHADER__ 1

/*

** 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__

#ifdef __cplusplus

extern "C" {

#endif

extern int access(const char *path, int mode);

#ifdef __cplusplus

}

#endif

#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 const char **made_files = NULL;

static int made_files_count = 0;

static int successful_exit = 0;

static void LemonAtExit(void)

{

    /* if we failed, delete (most) files we made, to unconfuse build tools. */

    int i;

    for (i = 0; i < made_files_count; i++) {

        if (!successful_exit) {

            remove(made_files[i]);

        }

    }

    free(made_files);

    made_files_count = 0;

    made_files = NULL;

}

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

/*

** Compilers are getting increasingly pedantic about type conversions

** as C evolves ever closer to Ada....  To work around the latest problems

** we have to define the following variant of strlen().

*/

#define lemonStrlen(X)   ((int)strlen(X))

/* a few forward declarations... */

struct rule;

struct lemon;

struct action;

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(struct lemon *);

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" ******************************************/

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

         OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR};

struct s_options {

  enum option_type type;

  const char *label;

  char *arg;

  const 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 *, int);

void ReportHeader(struct lemon *);

void CompressTables(struct lemon *);

void ResortStates(struct lemon *);

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

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

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

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

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

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

int SetUnion(char *,char *);    /* 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: */

enum symbol_type {

  TERMINAL,

  NONTERMINAL,

  MULTITERMINAL

};

enum e_assoc {

    LEFT,

    RIGHT,

    NONE,

    UNK

};

struct symbol {

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

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

  enum symbol_type 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 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 */

  const 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 */

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

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

  const 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: */

enum cfgstatus {

  COMPLETE,

  INCOMPLETE

};

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 cfgstatus status;   /* used during followset and shift computations */

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

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

};

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 */

};

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

struct action {

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

  enum e_action 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 */

#if __MOJOSHADER__

  int nexpected;           /* Number of expected parsing conflicts */

#endif

  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 */

  int nolinenosflag;       /* True if #line statements should not be printed */

  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 */

const char *Strsafe(const char *);

void Strsafe_init(void);

int Strsafe_insert(const char *);

const char *Strsafe_find(const char *);

/* Routines for handling symbols of the grammar */

struct symbol *Symbol_new(const char *);

int Symbolcmpp(const void *, const void *);

void Symbol_init(void);

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

struct symbol *Symbol_find(const char *);

struct symbol *Symbol_Nth(int);

int Symbol_count(void);

struct symbol **Symbol_arrayof(void);

/* Routines to manage the state table */

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

struct state *State_new(void);

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 *newaction;

  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;

  }

  newaction = freelist;

  freelist = freelist->next;

  return newaction;

}

/* 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;

  }

  if( rc==0 ){

    rc = (int) (ap2 - ap1);

  }

  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(

  struct action **app,

  enum e_action type,

  struct symbol *sp,

  char *arg

){

  struct action *newaction;

  newaction = Action_new();

  newaction->next = *app;

  *app = newaction;

  newaction->type = type;

  newaction->sp = sp;

  if( type==SHIFT ){

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

  }else{

    newaction->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.

**

** The yy_action table maps the pair (state_number, lookahead) into an

** action_number.  The table is an array of integers pairs.  The state_number

** determines an initial offset into the yy_action array.  The lookahead

** value is then added to this initial offset to get an index X into the

** yy_action array. If the aAction[X].lookahead equals the value of the

** of the lookahead input, then the value of the action_number output is

** aAction[X].action.  If the lookaheads do not match then the

** default action for the state_number is returned.

**

** All actions associated with a single state_number are first entered

** into aLookahead[] using multiple calls to acttab_action().  Then the 

** actions for that single state_number are placed into the aAction[] 

** array with a single call to acttab_insert().  The acttab_insert() call

** also resets the aLookahead[] array in preparation for the next

** state number.

*/

struct lookahead_action {

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

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

};

typedef struct acttab acttab;

struct acttab {

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

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

  struct lookahead_action

    *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 = (acttab *) calloc( 1, sizeof(*p) );

  if( p==0 ){

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