lemon.c

lalr(1)算法实现

                }
            }
        }
    }while( progress ); // 不再合并，不再添加
    return;
}

/* Compute all LR(0) states for the grammar.  Links
** are added to between some states so that the LR(1) follow sets
** can be computed later.
*/
PRIVATE struct state *getstate(struct lemon *);  /* forward reference */
void FindStates(struct lemon *lemp)
{
    struct symbol *sp;
    struct rule *rp;
    
    _("***********************************\nFindStates:\n");

    Configlist_init(); /* current,basis,x4a */
    
    /* Find the start symbol */
    if( lemp->start ){          /* 如果指定start符号，查找此符号，否则取第一个 */
        sp = Symbol_find(lemp->start);
        if( sp==0 ){
            ErrorMsg(lemp->filename,0,
            "The specified start symbol \"%s\" is not \
            in a nonterminal of the grammar.  \"%s\" will be used as the start \
            symbol instead.",lemp->start,lemp->rule->lhs->name);
            lemp->errorcnt++;
            sp = lemp->rule->lhs;
        }
    }else{
        sp = lemp->rule->lhs; // 取第一个
    }
    
    /* Make sure the start symbol doesn't occur on the right-hand side of
    ** any rule.  Report an error if it does.  (YACC would generate a new
    ** start symbol in this case.) */
    /* 确保start符号不出现在右部 */
    for(rp=lemp->rule; rp; rp=rp->next){
        int i;
        for(i=0; i<rp->nrhs; i++){
            if( rp->rhs[i]==sp ){   /* FIX ME:  Deal with multiterminals */
                ErrorMsg(lemp->filename,0,
                "The start symbol \"%s\" occurs on the \
                right-hand side of a rule. This will result in a parser which \
                does not work properly.",sp->name);
                lemp->errorcnt++;
            }
        }
    }
    
    /* The basis configuration set for the first state
    ** is all rules which have the start symbol as their
    ** left-hand side */
    /* 第一个状态的基本项目是以起始符号的左部的规则 */
    for(rp=sp->rule; rp; rp=rp->nextlhs){
        struct config *newcfp;
        _("\t\taddbasis"); 
        RuleOut(rp);
        newcfp = Configlist_addbasis(rp,0);
        SetAdd(newcfp->fws,0); /* fws[0] = 1 */
    }
    
    /* Compute the first state.  All other states will be
    ** computed automatically during the computation of the first one.
    ** The returned pointer to the first state is not used. */
    (void)getstate(lemp);
    return;
}

/* Return a pointer to a state which is described by the configuration
** list which has been built from calls to Configlist_add.
*/
PRIVATE void buildshifts(struct lemon *, struct state *); /* Forwd ref */
PRIVATE struct state *getstate(struct lemon *lemp)
{
    struct config *cfp, *bp;
    struct state *stp;
    
    /* Extract the sorted basis of the new state.  The basis was constructed
    ** by prior calls to "Configlist_addbasis()". */
    Configlist_sortbasis();
    bp = Configlist_basis();
    
    /* Get a state with the same basis */
    stp = State_find(bp);
    if( stp ){
    /* A state with the same basis already exists!  Copy all the follow-set
    ** propagation links from the state under construction into the
        ** preexisting state, then return a pointer to the preexisting state */
        struct config *x, *y;
        for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
            Plink_copy(&y->bplp,x->bplp);
            Plink_delete(x->fplp);
            x->fplp = x->bplp = 0;
        }
        cfp = Configlist_return();
        Configlist_eat(cfp);
    }else{
        /* This really is a new state.  Construct all the details */
        Configlist_closure(lemp);    /* Compute the configuration closure *//* 状态0 的闭包 */
        Configlist_sort();           /* Sort the configuration closure */
        cfp = Configlist_return();   /* Get a pointer to the config list *//* current list */
        stp = State_new();           /* A new state structure */
        MemoryCheck(stp);
        stp->bp = bp;                /* 记录basis(1) *//* Remember the configuration basis */
        stp->cfp = cfp;              /* 记录由basis派生的n个 *//* Remember the configuration closure */
        stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
        stp->ap = 0;                 /* No actions, yet. */
        State_insert(stp,stp->bp);   /* Add to the state table */
        buildshifts(lemp,stp);       /* Recursively compute successor states */
    }
    return stp;
}

/*
** Return true if two symbols are the same.
*/
int same_symbol(a,b)
struct symbol *a;
struct symbol *b;
{
    int i;
    if( a==b ) return 1;
    if( a->type!=MULTITERMINAL ) return 0;
    if( b->type!=MULTITERMINAL ) return 0;
    if( a->nsubsym!=b->nsubsym ) return 0;
    for(i=0; i<a->nsubsym; i++){
        if( a->subsym[i]!=b->subsym[i] ) return 0;
    }
    return 1;
}

/* Construct all successor states to the given state.  A "successor"
** state is any state which can be reached by a shift action.
 @stp The state from which successors are computed */
PRIVATE void buildshifts(struct lemon *lemp,struct state *stp) 
{
    struct config *cfp;  /* For looping thru the config closure of "stp" */
    struct config *bcfp; /* For the inner loop on config closure of "stp" */
    struct config *new;  /* */
    struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
    struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
    struct state *newstp; /* A pointer to a successor state */
    
    _("+++++++++++++++++\nbuildshifts:\n");
    _("From ");
    StateOutSimple(stp);

    /* Each configuration becomes complete after it contibutes to a successor
    ** state.  Initially, all configurations are incomplete 
    */
    for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
    
    /* Loop through all configurations of the state "stp" */
    for(cfp=stp->cfp; cfp; cfp=cfp->next){

        _("\tCheck ");ConfigOut(cfp);

        if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */
        if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */
        Configlist_reset();                      /* Reset the new config set */
        sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */

        _("\tGet"); SymbolOut(sp);

         /* For every configuration in the state "stp" which has the symbol "sp"
         ** following its dot, add the same configuration to the basis set under
         ** construction but with the dot shifted one symbol to the right. */
        for(bcfp=cfp; bcfp; bcfp=bcfp->next){
            if( bcfp->status==COMPLETE ) continue;    /* Already used */
            if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
            bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
            if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
            bcfp->status = COMPLETE;                  /* Mark this config as used */
            new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
            Plink_add(&new->bplp,bcfp);
        }
        
        /* Get a pointer to the state described by the basis configuration set
        ** constructed in the preceding loop */
        newstp = getstate(lemp);
        
        /* The state "newstp" is reached from the state "stp" by a shift action
        ** on the symbol "sp" */
        if( sp->type==MULTITERMINAL ){
            int i;
            for(i=0; i<sp->nsubsym; i++){
                Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
            }
        }else{
            Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
        }
    }
}

/*
** Construct the propagation links
*/
void FindLinks(lemp)
struct lemon *lemp;
{
    int i;
    struct config *cfp, *other;
    struct state *stp;
    struct plink *plp;
    
    /* Housekeeping detail:
    ** Add to every propagate link a pointer back to the state to
    ** which the link is attached. */
    for(i=0; i<lemp->nstate; i++){
        stp = lemp->sorted[i];
        for(cfp=stp->cfp; cfp; cfp=cfp->next){
            cfp->stp = stp;
        }
    }
    
    /* Convert all backlinks into forward links.  Only the forward
    ** links are used in the follow-set computation. */
    for(i=0; i<lemp->nstate; i++){
        stp = lemp->sorted[i];
        for(cfp=stp->cfp; cfp; cfp=cfp->next){
            for(plp=cfp->bplp; plp; plp=plp->next){
                other = plp->cfp;
                Plink_add(&other->fplp,cfp);
            }
        }
    }
}

/* Compute all followsets.
**
** A followset is the set of all symbols which can come immediately
** after a configuration.
*/
void FindFollowSets(lemp)
struct lemon *lemp;
{
    int i;
    struct config *cfp;
    struct plink *plp;
    int progress;
    int change;
    
    for(i=0; i<lemp->nstate; i++){
        for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
            cfp->status = INCOMPLETE;
        }
    }
    
    do{
        progress = 0;
        for(i=0; i<lemp->nstate; i++){
            for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
                if( cfp->status==COMPLETE ) continue;
                for(plp=cfp->fplp; plp; plp=plp->next){
                    change = SetUnion(plp->cfp->fws,cfp->fws);
                    if( change ){
                        plp->cfp->status = INCOMPLETE;
                        progress = 1;
                    }
                }
                cfp->status = COMPLETE;
            }
        }
    }while( progress );
}

static int resolve_conflict();

/* Compute the reduce actions, and resolve conflicts.
*/
void FindActions(lemp)
struct lemon *lemp;
{
    int i,j;
    struct config *cfp;
    struct state *stp;
    struct symbol *sp;
    struct rule *rp;
    
    /* Add all of the reduce actions 
    ** A reduce action is added for each element of the followset of
    ** a configuration which has its dot at the extreme right.
    */
    for(i=0; i<lemp->nstate; i++){   /* Loop over all states */
        stp = lemp->sorted[i];
        for(cfp=stp->cfp; cfp; cfp=cfp->next){  /* Loop over all configurations */
            if( cfp->rp->nrhs==cfp->dot ){        /* Is dot at extreme right? */
                for(j=0; j<lemp->nterminal; j++){
                    if( SetFind(cfp->fws,j) ){
                    /* Add a reduce action to the state "stp" which will reduce by the
                        ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
                        Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
                    }
                }
            }
        }
    }
    
    /* Add the accepting token */
    if( lemp->start ){
        sp = Symbol_find(lemp->start);
        if( sp==0 ) sp = lemp->rule->lhs;
    }else{
        sp = lemp->rule->lhs;
    }
    /* Add to the first state (which is always the starting state of the
    ** finite state machine) an action to ACCEPT if the lookahead is the
    ** start nonterminal.  */
    Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
    
    /* Resolve conflicts */
    for(i=0; i<lemp->nstate; i++){
        struct action *ap, *nap;
        struct state *stp;
        stp = lemp->sorted[i];
        /* assert( stp->ap ); */
        stp->ap = Action_sort(stp->ap);
        for(ap=stp->ap; ap && ap->next; ap=ap->next){
            for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
            /* The two actions "ap" and "nap" have the same lookahead.
                ** Figure out which one should be used */
                lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
            }
        }
    }
    
    /* Report an error for each rule that can never be reduced. */
    for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;
    for(i=0; i<lemp->nstate; i++){
        struct action *ap;
        for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
            if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;
        }
    }
    for(rp=lemp->rule; rp; rp=rp->next){
        if( rp->canReduce ) continue;
        ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
        lemp->errorcnt++;
    }
}

/* Resolve a conflict between the two given actions.  If the
** conflict can't be resolve, return non-zero.
**
** NO LONGER TRUE:
**   To resolve a conflict, first look to see if either action
**   is on an error rule.  In that case, take the action which
**   is not associated with the error rule.  If neither or both
**   actions are associated with an error rule, then try to
**   use precedence to resolve the conflict.
**
** If either action is a SHIFT, then it must be apx.  This
** function won't work if apx->type==REDUCE and apy->type==SHIFT.
*/
static int resolve_conflict(apx,apy,errsym)
struct action *apx;
struct action *apy;
struct symbol *errsym;   /* The error symbol (if defined.  NULL otherwise) */
{
    struct symbol *spx, *spy;
    int errcnt = 0;
    assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
    if( apx->type==SHIFT && apy->type==SHIFT ){
        apy->type = CONFLICT;
        errcnt++;
    }
    if( apx->type==SHIFT && apy->type==REDUCE ){
        spx = apx->sp;
        spy = apy->x.rp->precsym;
        if( spy==0 || spx->prec<0 || spy->prec<0 ){
            /* Not enough precedence information. */
            apy->type = CONFLICT;
            errcnt++;