lemon.c

lalr(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__
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

typedef int (*CMP_FUN)(const char*, const char*);

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(struct lemon *xp );
void FindFirstSets(struct lemon *lemp);
void FindStates(struct lemon *lemp);
void FindLinks(struct lemon *lemp);
void FindFollowSets(struct lemon *lemp);
void FindActions(struct lemon *lemp);

/********* 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();                  /* 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 predecence is defined */ 
    char *firstset;          /* First()集合 *//* First-set for all rules of this symbol */ 
    Boolean lambda;          /* ?? *//* True if NT and can generate an empty string */
    char *destructor;        /* Pop出栈时执行的代码 *//* Code which executes whenever this symbol is popped from the stack during error processing */
    int destructorln;        /* destructor的行号 *//* 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;          /* lhs标识符简称 */   /* 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;              /* 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;    /* 相同lhs的下一个规则*/ /* 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(); \
}

/************************************************************************/
/* add by zhsh                                                          */
/************************************************************************/

#define _ printf

static int size = 0;

void FirstOut(char *s)
{
    int i;
    printf("\t\t");
    for (i=0; i<size; i++)
    {
        printf("%d,", s[i]);
    }
    printf("\n");
}
void RuleOut(struct rule *r)
{
    _("rule %d %s:\n", r->ruleline, r->lhs->name);
}

void SymbolOut(struct symbol *sy)
{
    _("\t Symbol %s:\n", sy->name);
}

void ConfigOut(struct config*c)
{
    _("\tconfig %d %s(%d):\n", c->rp->ruleline, c->rp->lhs->name, c->dot);
}
void StateOut(struct state*s)
{
    struct config* c;

    _("state (%d):\n", s->statenum);
    _("++basis config %d %s(%d)\n", s->bp->rp->ruleline, s->bp->rp->lhs->name, s->bp->dot);

    c = s->cfp;

    while (c)
    {
        _("++");
        ConfigOut(c);
        c = c->next;
    }
}
void StateOutSimple(struct state*s)
{
    _("state (%d):\n", s->statenum);
}

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