lemon.c

lalr(1)算法实现

int main(int argc,char **argv)
{
    static int version = 0;
    static int rpflag = 0;
    static int basisflag = 0;
    static int compress = 0;
    static int quiet = 0;
    static int statistics = 0;
    static int mhflag = 0;
    static struct s_options options[] = {
        {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
        {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
        {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
        {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},             /* 打印解析结果，不生成动作 */
        {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file"},       /* 不生成头文件 */
        {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
        {OPT_FLAG, "s", (char*)&statistics,"Print parser stats to standard output."},  /* 打印统计结果 */
        {OPT_FLAG, "x", (char*)&version, "Print the version number."},
        {OPT_FLAG,0,0,0}
    };
    int i;
    struct lemon lem;
    
    OptInit(argv,options,stderr);
    if( version ){
        printf("Lemon version 1.0\n");
        exit(0); 
    }
    if( OptNArgs()!=1 ){
        fprintf(stderr,"Exactly one filename argument is required.\n");
        exit(1);
    }
    memset(&lem, 0, sizeof(lem));
    lem.errorcnt = 0;
    
    /* Initialize the machine */
    Strsafe_init();
    Symbol_init();
    State_init();
    lem.argv0 = argv[0];
    lem.filename = OptArg(0);
    lem.basisflag = basisflag;
    Symbol_new("$");
    lem.errsym = Symbol_new("error");
    
    /* Parse the input file */
    Parse(&lem);
    if( lem.errorcnt ) exit(lem.errorcnt);
    if( lem.nrule==0 ){
        fprintf(stderr,"Empty grammar.\n");
        exit(1);
    }
    
    /* Count and index the symbols of the grammar */
    lem.nsymbol = Symbol_count();
    Symbol_new("{default}");
    lem.symbols = Symbol_arrayof();    /* 返回解析出的符号（Symbol*）数组，原本保存于（ s_x2 ）x2a->tbl[i].data*/
    for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
    qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*), /* 大写开头的终结符在前，非终结符在后，内部稳定 */
        (int(*)(const void*,const void*))Symbolcmpp);
    for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;/* 按排序后的顺序设定次序 */
    for(i=1; isupper(lem.symbols[i]->name[0]); i++);        /* 记录终结符个数 */
    lem.nterminal = i;
    
    /* Generate a reprint of the grammar, if requested on the command line */
    if( rpflag ){
        Reprint(&lem);
    }else{
        /* Initialize the size for all follow and first sets */
        SetSize(lem.nterminal);     /* 设置集合大小为： 终结符号个数n+1 */
        
        /* Find the precedence for every production rule (that has one) */
        FindRulePrecedences(&lem);  /* 查找前驱规则 ？？？ */
        
        /* Compute the lambda-nonterminals and the first-sets for every
        ** nonterminal */
        FindFirstSets(&lem); /* 计算可空的终结符，非终结符号的first。 */
        
        /* Compute all LR(0) states.  Also record follow-set propagation
        ** links so that the follow-set can be computed later */
        lem.nstate = 0;
        FindStates(&lem);
        lem.sorted = State_arrayof();
        
        /* Tie up loose ends on the propagation links */
        FindLinks(&lem);
        
        /* Compute the follow set of every reducible configuration */
        FindFollowSets(&lem);
        
        /* Compute the action tables */
        FindActions(&lem);
        
        /* Compress the action tables */
        if( compress==0 ) CompressTables(&lem);
        
        /* Reorder and renumber the states so that states with fewer choices
        ** occur at the end. */
        ResortStates(&lem);
        
        /* Generate a report of the parser generated.  (the "y.output" file) */
        if( !quiet ) ReportOutput(&lem);
        
        /* Generate the source code for the parser */
        ReportTable(&lem, mhflag);
        
        /* Produce a header file for use by the scanner.  (This step is
        ** omitted if the "-m" option is used because makeheaders will
        ** generate the file for us.) */
        if( !mhflag ) ReportHeader(&lem);
    }
    if( statistics ){
        printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
            lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
        printf("                   %d states, %d parser table entries, %d conflicts\n",
            lem.nstate, lem.tablesize, lem.nconflict);
    }
    if( lem.nconflict ){
        fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
    }
    exit(lem.errorcnt + lem.nconflict);
    return (lem.errorcnt + lem.nconflict);
}
/******************** From the file "msort.c" *******************************/
/*
** A generic merge-sort program.
**
** USAGE:
** Let "ptr" be a pointer to some structure which is at the head of
** a null-terminated list.  Then to sort the list call:
**
**     ptr = msort(ptr,&(ptr->next),cmpfnc);
**
** In the above, "cmpfnc" is a pointer to a function which compares
** two instances of the structure and returns an integer, as in
** strcmp.  The second argument is a pointer to the pointer to the
** second element of the linked list.  This address is used to compute
** the offset to the "next" field within the structure.  The offset to
** the "next" field must be constant for all structures in the list.
**
** The function returns a new pointer which is the head of the list
** after sorting.
**
** ALGORITHM:
** Merge-sort.
*/

/*
** Return a pointer to the next structure in the linked list.
*/
#define NEXT(A) (*(char**)(((unsigned long)A)+offset))

/*
** Inputs:
**   a:       A sorted, null-terminated linked list.  (May be null).
**   b:       A sorted, null-terminated linked list.  (May be null).
**   cmp:     A pointer to the comparison function.
**   offset:  Offset in the structure to the "next" field.
**
** Return Value:
**   A pointer to the head of a sorted list containing the elements
**   of both a and b.
**
** Side effects:
**   The "next" pointers for elements in the lists a and b are
**   changed.
*/
static char *merge(
                   char *a,
                   char *b,
                   int (*cmp)(const char*,const char*),
                   int offset
                   ){
    char *ptr, *head;
    
    if( a==0 ){
        head = b;
    }else if( b==0 ){
        head = a;
    }else{
        if( (*cmp)(a,b)<0 ){
            ptr = a;
            a = NEXT(a);
        }else{
            ptr = b;
            b = NEXT(b);
        }
        head = ptr;
        while( a && b ){
            if( (*cmp)(a,b)<0 ){
                NEXT(ptr) = a;
                ptr = a;
                a = NEXT(a);
            }else{
                NEXT(ptr) = b;
                ptr = b;
                b = NEXT(b);
            }
        }
        if( a ) NEXT(ptr) = a;
        else    NEXT(ptr) = b;
    }
    return head;
}

/*
** Inputs:
**   list:      Pointer to a singly-linked list of structures.
**   next:      Pointer to pointer to the second element of the list.
**   cmp:       A comparison function.
**
** Return Value:
**   A pointer to the head of a sorted list containing the elements
**   orginally in list.
**
** Side effects:
**   The "next" pointers for elements in list are changed.
*/
#define LISTSIZE 30
static char *msort(
                   char *list,
                   char **next,
                   int (*cmp)(const char*,const char*)
                   ){
    unsigned long offset;
    char *ep;
    char *set[LISTSIZE];
    int i;
    offset = (unsigned long)next - (unsigned long)list;
    for(i=0; i<LISTSIZE; i++) set[i] = 0;
    while( list ){
        ep = list;
        list = NEXT(list);
        NEXT(ep) = 0;
        for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
            ep = merge(ep,set[i],cmp,offset);
            set[i] = 0;
        }
        set[i] = ep;
    }
    ep = 0;
    for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
    return ep;
}
/************************ From the file "option.c" **************************/
static char **argv;
static struct s_options *op;
static FILE *errstream;

#define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)

/*
** Print the command line with a carrot pointing to the k-th character
** of the n-th field.
*/
static void errline(n,k,err)
int n;
int k;
FILE *err;
{
    int spcnt, i;
    if( argv[0] ) fprintf(err,"%s",argv[0]);
    spcnt = strlen(argv[0]) + 1;
    for(i=1; i<n && argv[i]; i++){
        fprintf(err," %s",argv[i]);
        spcnt += strlen(argv[i])+1;
    }
    spcnt += k;
    for(; argv[i]; i++) fprintf(err," %s",argv[i]);
    if( spcnt<20 ){
        fprintf(err,"\n%*s^-- here\n",spcnt,"");
    }else{
        fprintf(err,"\n%*shere --^\n",spcnt-7,"");
    }
}

/*
** Return the index of the N-th non-switch argument.  Return -1
** if N is out of range.
*/
static int argindex(n)
int n;
{
    int i;
    int dashdash = 0;
    if( argv!=0 && *argv!=0 ){
        for(i=1; argv[i]; i++){
            if( dashdash || !ISOPT(argv[i]) ){
                if( n==0 ) return i;
                n--;
            }
            if( strcmp(argv[i],"--")==0 ) dashdash = 1;
        }
    }
    return -1;
}

static char emsg[] = "Command line syntax error: ";

/*
** Process a flag command line argument.
*/
static int handleflags(i,err)
int i;
FILE *err;
{
    int v;
    int errcnt = 0;
    int j;
    for(j=0; op[j].label; j++){
        if( strncmp(&argv[i][1],op[j].label,strlen(op[j].label))==0 ) break;
    }
    v = argv[i][0]=='-' ? 1 : 0;
    if( op[j].label==0 ){
        if( err ){
            fprintf(err,"%sundefined option.\n",emsg);
            errline(i,1,err);
        }
        errcnt++;
    }else if( op[j].type==OPT_FLAG ){
        *((int*)op[j].arg) = v;
    }else if( op[j].type==OPT_FFLAG ){
        (*(void(*)())(op[j].arg))(v);
    }else if( op[j].type==OPT_FSTR ){
        (*(void(*)())(op[j].arg))(&argv[i][2]);
    }else{
        if( err ){
            fprintf(err,"%smissing argument on switch.\n",emsg);
            errline(i,1,err);
        }
        errcnt++;
    }
    return errcnt;
}

/*
** Process a command line switch which has an argument.
*/
static int handleswitch(i,err)
int i;
FILE *err;
{
    int lv = 0;
    double dv = 0.0;
    char *sv = 0, *end;
    char *cp;
    int j;
    int errcnt = 0;
    cp = strchr(argv[i],'=');
    assert( cp!=0 );
    *cp = 0;
    for(j=0; op[j].label; j++){
        if( strcmp(argv[i],op[j].label)==0 ) break;
    }
    *cp = '=';
    if( op[j].label==0 ){
        if( err ){
            fprintf(err,"%sundefined option.\n",emsg);
            errline(i,0,err);
        }
        errcnt++;
    }else{
        cp++;
        switch( op[j].type ){
        case OPT_FLAG:
        case OPT_FFLAG:
            if( err ){
                fprintf(err,"%soption requires an argument.\n",emsg);
                errline(i,0,err);
            }
            errcnt++;
            break;