lemon.c

lalr(1)算法实现

        }else if( spx->prec>spy->prec ){    /* Lower precedence wins */
            apy->type = RD_RESOLVED;
        }else if( spx->prec<spy->prec ){
            apx->type = SH_RESOLVED;
        }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
            apy->type = RD_RESOLVED;                             /* associativity */
        }else if( spx->prec==spy->prec && spx->assoc==LEFT ){  /* to break tie */
            apx->type = SH_RESOLVED;
        }else{
            assert( spx->prec==spy->prec && spx->assoc==NONE );
            apy->type = CONFLICT;
            errcnt++;
        }
    }else if( apx->type==REDUCE && apy->type==REDUCE ){
        spx = apx->x.rp->precsym;
        spy = apy->x.rp->precsym;
        if( spx==0 || spy==0 || spx->prec<0 ||
            spy->prec<0 || spx->prec==spy->prec ){
            apy->type = CONFLICT;
            errcnt++;
        }else if( spx->prec>spy->prec ){
            apy->type = RD_RESOLVED;
        }else if( spx->prec<spy->prec ){
            apx->type = RD_RESOLVED;
        }
    }else{
        assert( 
            apx->type==SH_RESOLVED ||
            apx->type==RD_RESOLVED ||
            apx->type==CONFLICT ||
            apy->type==SH_RESOLVED ||
            apy->type==RD_RESOLVED ||
            apy->type==CONFLICT
            );
            /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
            ** REDUCEs on the list.  If we reach this point it must be because
        ** the parser conflict had already been resolved. */
    }
    return errcnt;
}
/********************* From the file "configlist.c" *************************/
/*
** Routines to processing a configuration list and building a state
** in the LEMON parser generator.
*/

static struct config *freelist = 0;      /* List of free configurations */
static struct config *current = 0;       /* Top of list of configurations */
static struct config **currentend = 0;   /* Last on list of configs */
static struct config *basis = 0;         /* Top of list of basis configs */
static struct config **basisend = 0;     /* End of list of basis configs */

/* Return a pointer to a new configuration *//* 每次分配3个 config */
PRIVATE struct config *newconfig(){
    struct config *new;
    if( freelist==0 ){
        int i;
        int amt = 3;
        freelist = (struct config *)malloc( sizeof(struct config)*amt );
        if( freelist==0 ){
            fprintf(stderr,"Unable to allocate memory for a new configuration.");
            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;
}

/* The configuration "old" is no longer used */
/* 添加到freelist */
PRIVATE void deleteconfig(struct config *old)
{
    old->next = freelist;
    freelist = old;
}

/* Initialized the configuration list builder */
void Configlist_init(){
    current = 0;
    currentend = &current;
    basis = 0;
    basisend = &basis;
    Configtable_init();
    return;
}

/* Initialized the configuration list builder */
void Configlist_reset(){
    current = 0;
    currentend = &current;
    basis = 0;
    basisend = &basis;
    Configtable_clear(0);
    return;
}

/* Add another configuration to the configuration list */
/* @rp The rule */
/* @Index into the RHS of the rule where the dot goes eg: expr ::= expr . PLUS expr .*/
struct config *Configlist_add(struct rule *rp,int dot)       
{
    struct config *cfp, model ;
    
   
    assert( currentend!=0 );
    model.rp = rp;
    model.dot = dot;
    
    cfp = Configtable_find(&model);
    if( cfp==0 ){
        cfp = newconfig(); /* from freelist */
        cfp->rp = rp;
        cfp->dot = dot;
        cfp->fws = SetNew();
        cfp->stp = 0;
        cfp->fplp = cfp->bplp = 0;
        cfp->next = 0;
        cfp->bp = 0;
        *currentend = cfp;
        currentend = &cfp->next;
        Configtable_insert(cfp);
    }
    _("\t\t\tConfiglist_add"); 
    ConfigOut(cfp);
    return cfp;
}

/* Add a basis configuration to the configuration list */
/* 添加basis configuration到项目列表 */
struct config *Configlist_addbasis(struct rule *rp,int dot)
{
    struct config *cfp, model;
    
    assert( basisend!=0 );
    assert( currentend!=0 );
    model.rp = rp;
    model.dot = dot;
    cfp = Configtable_find(&model);
    if( cfp==0 ){
        cfp = newconfig();
        _("\t\tnewconfig\n");
        cfp->rp = rp;
        cfp->dot = dot;
        cfp->fws = SetNew();/* follow集 */
        cfp->stp = 0;
        cfp->fplp = cfp->bplp = 0;
        cfp->next = 0;
        cfp->bp = 0;
        *currentend = cfp;  /* 添加到项目表结尾 */
        currentend = &cfp->next;
        *basisend = cfp;
        basisend = &cfp->bp;
        Configtable_insert(cfp);/* 添加到x4a的tbl和ht中 */
    }
    return cfp;
}

/* Compute the closure of the configuration list */
void Configlist_closure(struct lemon *lemp)
{
    struct config *cfp, *newcfp;
    struct rule *rp, *newrp;
    struct symbol *sp, *xsp;
    int i, dot;

    static int times= 0;

    _("++++++++++\nConfiglist_closure(%d):\n", times++);
    
    assert( currentend!=0 );
    for(cfp=current; cfp; cfp=cfp->next){ /* 寻找current的每一个config，将dot后的非终结符展开 */
        ConfigOut(cfp);
        rp = cfp->rp;
        dot = cfp->dot;
        if( dot>=rp->nrhs ) continue;    /* dot在最后 */
        sp = rp->rhs[dot];
        _("\t After dot It is ");
        SymbolOut(sp);
        if( sp->type==NONTERMINAL ){    /* 闭包运算 */
            if( sp->rule==0 && sp!=lemp->errsym ){
                ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.", sp->name);
                lemp->errorcnt++;
            }
            for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){ /* sp引导的规则  */
                _("\t\t\tSearch ");
                RuleOut(newrp);
                newcfp = Configlist_add(newrp,0);     /* .sp *//* 添加到current最后 */
                for(i=dot+1; i<rp->nrhs; i++){        /* 为何+1？ *//* 计算此项目的follow集 */
                    xsp = rp->rhs[i];
                    _("\t\t\t"); SymbolOut(xsp);
                    if( xsp->type==TERMINAL ){
                        _("\t\t\tAdd TERMINAL\n");
                        SetAdd(newcfp->fws,xsp->index);      /* 将终结符号插入 */
                        break;
                    }else if( xsp->type==MULTITERMINAL ){
                        int k;
                         _("\t\t\tAdd MULTITERMINAL(%d)\n", xsp->nsubsym);
                        for(k=0; k<xsp->nsubsym; k++){
                            SetAdd(newcfp->fws, xsp->subsym[k]->index);
                        }
                        break;
                    }else{                              /* 合并非终结符号的firstset to fws，如果非lambda结束 */
                        _("\t\t\tSetUnion NonTERMINAL\'s firstset\n");
                        SetUnion(newcfp->fws,xsp->firstset);
                        if( xsp->lambda==LEMON_FALSE ) break;
                    }
                }
                if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp); /* 是何目的？ */
            }
        }
    }
    return;
}

/* Sort the configuration list */
void Configlist_sort(){
    current = (struct config *)msort((char *)current,(char **)&(current->next),(CMP_FUN)Configcmp);
    currentend = 0;
    return;
}

/* Sort the basis configuration list */
void Configlist_sortbasis(){
    basis = (struct config *)msort((char *)current,(char **)&(current->bp),(CMP_FUN)Configcmp);
    basisend = 0;
    return;
}

/* Return a pointer to the head of the configuration list and
** reset the list */
struct config *Configlist_return(){
    struct config *old;
    old = current;
    current = 0;
    currentend = 0;
    return old;
}

/* Return a pointer to the head of the configuration list and
** reset the list */
struct config *Configlist_basis(){
    struct config *old;
    old = basis;
    basis = 0;
    basisend = 0;
    return old;
}

/* Free all elements of the given configuration list */
void Configlist_eat(cfp)
struct config *cfp;
{
    struct config *nextcfp;
    for(; cfp; cfp=nextcfp){
        nextcfp = cfp->next;
        assert( cfp->fplp==0 );
        assert( cfp->bplp==0 );
        if( cfp->fws ) SetFree(cfp->fws);
        deleteconfig(cfp);
    }
    return;
}
/***************** From the file "error.c" *********************************/
/*
** Code for printing error message.
*/

/* Find a good place to break "msg" so that its length is at least "min"
** but no more than "max".  Make the point as close to max as possible.
*/
static int findbreak(msg,min,max)
char *msg;
int min;
int max;
{
    int i,spot;
    char c;
    for(i=spot=min; i<=max; i++){
        c = msg[i];
        if( c=='\t' ) msg[i] = ' ';
        if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
        if( c==0 ){ spot = i; break; }
        if( c=='-' && i<max-1 ) spot = i+1;
        if( c==' ' ) spot = i;
    }
    return spot;
}

/*
** The error message is split across multiple lines if necessary.  The
** splits occur at a space, if there is a space available near the end
** of the line.
*/
#define ERRMSGSIZE  10000 /* Hope this is big enough.  No way to error check */
#define LINEWIDTH      79 /* Max width of any output line */
#define PREFIXLIMIT    30 /* Max width of the prefix on each line */
void ErrorMsg(const char *filename, int lineno, const char *format, ...){
    char errmsg[ERRMSGSIZE];
    char prefix[PREFIXLIMIT+10];
    int errmsgsize;
    int prefixsize;
    int availablewidth;
    va_list ap;
    int end, restart, base;
    
    va_start(ap, format);
    /* Prepare a prefix to be prepended to every output line */
    if( lineno>0 ){
        sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
    }else{
        sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
    }
    prefixsize = strlen(prefix);
    availablewidth = LINEWIDTH - prefixsize;
    
    /* Generate the error message */
    vsprintf(errmsg,format,ap);
    va_end(ap);
    errmsgsize = strlen(errmsg);
    /* Remove trailing '\n's from the error message. */
    while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
        errmsg[--errmsgsize] = 0;
    }
    
    /* Print the error message */
    base = 0;
    while( errmsg[base]!=0 ){
        end = restart = findbreak(&errmsg[base],0,availablewidth);
        restart += base;
        while( errmsg[restart]==' ' ) restart++;
        fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
        base = restart;
    }
}
/**************** From the file "main.c" ************************************/
/*
** Main program file for the LEMON parser generator.
*/

/* Report an out-of-memory condition and abort.  This function
** is used mostly by the "MemoryCheck" macro in struct.h
*/
void memory_error(){
    fprintf(stderr,"Out of memory.  Aborting...\n");
    exit(1);
}

static int nDefine = 0;      /* Number of -D options on the command line */
static char **azDefine = 0;  /* Name of the -D macros */

                             /* This routine is called with the argument to each -D command-line option.
                             ** Add the macro defined to the azDefine array.
*/
static void handle_D_option(char *z){
    char **paz;
    nDefine++;
    azDefine = realloc(azDefine, sizeof(azDefine[0])*nDefine);
    if( azDefine==0 ){
        fprintf(stderr,"out of memory\n");
        exit(1);
    }
    paz = &azDefine[nDefine-1];
    *paz = malloc( strlen(z)+1 );
    if( *paz==0 ){
        fprintf(stderr,"out of memory\n");
        exit(1);
    }
    strcpy(*paz, z);
    for(z=*paz; *z && *z!='='; z++){}
    *z = 0;
}


/* The main program.  Parse the command line and do it... */