lemon.c

lalr(1)算法实现

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 *new;
    
    if( freelist==0 ){
        int i;
        int amt = 100;
        freelist = (struct action *)malloc( sizeof(struct action)*amt );
        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;
    }
    new = freelist;
    freelist = freelist->next;
    return new;
}

/* 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 ){
        rc = ap1->x.rp->index - ap2->x.rp->index;
    }
    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(app,type,sp,arg)
struct action **app;
enum e_action type;
struct symbol *sp;
char *arg;
{
    struct action *new;
    new = Action_new();
    new->next = *app;
    *app = new;
    new->type = type;
    new->sp = sp;
    if( type==SHIFT ){
        new->x.stp = (struct state *)arg;
    }else{
        new->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
*/
typedef struct acttab acttab;
struct acttab {
    int nAction;                 /* Number of used slots in aAction[] */
    int nActionAlloc;            /* Slots allocated for aAction[] */
    struct {
        int lookahead;             /* Value of the lookahead token */
        int action;                /* Action to take on the given lookahead */
    } *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 = malloc( sizeof(*p) );
    if( p==0 ){
        fprintf(stderr,"Unable to allocate memory for a new acttab.");
        exit(1);
    }
    memset(p, 0, sizeof(*p));
    return p;
}

/* Add a new action to the current transaction set
*/
void acttab_action(acttab *p, int lookahead, int action){
    if( p->nLookahead>=p->nLookaheadAlloc ){
        p->nLookaheadAlloc += 25;
        p->aLookahead = realloc( p->aLookahead,
            sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
        if( p->aLookahead==0 ){
            fprintf(stderr,"malloc failed\n");
            exit(1);
        }
    }
    if( p->nLookahead==0 ){
        p->mxLookahead = lookahead;
        p->mnLookahead = lookahead;
        p->mnAction = action;
    }else{
        if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
        if( p->mnLookahead>lookahead ){
            p->mnLookahead = lookahead;
            p->mnAction = action;
        }
    }
    p->aLookahead[p->nLookahead].lookahead = lookahead;
    p->aLookahead[p->nLookahead].action = action;
    p->nLookahead++;
}

/*
** Add the transaction set built up with prior calls to acttab_action()
** into the current action table.  Then reset the transaction set back
** to an empty set in preparation for a new round of acttab_action() calls.
**
** Return the offset into the action table of the new transaction.
*/
int acttab_insert(acttab *p){
    int i, j, k, n;
    assert( p->nLookahead>0 );
    
    /* Make sure we have enough space to hold the expanded action table
    ** in the worst case.  The worst case occurs if the transaction set
    ** must be appended to the current action table
    */
    n = p->mxLookahead + 1;
    if( p->nAction + n >= p->nActionAlloc ){
        int oldAlloc = p->nActionAlloc;
        p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
        p->aAction = realloc( p->aAction,
            sizeof(p->aAction[0])*p->nActionAlloc);
        if( p->aAction==0 ){
            fprintf(stderr,"malloc failed\n");
            exit(1);
        }
        for(i=oldAlloc; i<p->nActionAlloc; i++){
            p->aAction[i].lookahead = -1;
            p->aAction[i].action = -1;
        }
    }
    
    /* Scan the existing action table looking for an offset where we can
    ** insert the current transaction set.  Fall out of the loop when that
    ** offset is found.  In the worst case, we fall out of the loop when
    ** i reaches p->nAction, which means we append the new transaction set.
    **
    ** i is the index in p->aAction[] where p->mnLookahead is inserted.
    */
    for(i=0; i<p->nAction+p->mnLookahead; i++){
        if( p->aAction[i].lookahead<0 ){
            for(j=0; j<p->nLookahead; j++){
                k = p->aLookahead[j].lookahead - p->mnLookahead + i;
                if( k<0 ) break;
                if( p->aAction[k].lookahead>=0 ) break;
            }
            if( j<p->nLookahead ) continue;
            for(j=0; j<p->nAction; j++){
                if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
            }
            if( j==p->nAction ){
                break;  /* Fits in empty slots */
            }
        }else if( p->aAction[i].lookahead==p->mnLookahead ){
            if( p->aAction[i].action!=p->mnAction ) continue;
            for(j=0; j<p->nLookahead; j++){
                k = p->aLookahead[j].lookahead - p->mnLookahead + i;
                if( k<0 || k>=p->nAction ) break;
                if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
                if( p->aLookahead[j].action!=p->aAction[k].action ) break;
            }
            if( j<p->nLookahead ) continue;
            n = 0;
            for(j=0; j<p->nAction; j++){
                if( p->aAction[j].lookahead<0 ) continue;
                if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
            }
            if( n==p->nLookahead ){
                break;  /* Same as a prior transaction set */
            }
        }
    }
    /* Insert transaction set at index i. */
    for(j=0; j<p->nLookahead; j++){
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
        p->aAction[k] = p->aLookahead[j];
        if( k>=p->nAction ) p->nAction = k+1;
    }
    p->nLookahead = 0;
    
    /* Return the offset that is added to the lookahead in order to get the
    ** index into yy_action of the action */
    return i - p->mnLookahead;
}

/********************** From the file "build.c" *****************************/
/*
** Routines to construction the finite state machine for the LEMON
** parser generator.
*/

/* Find a precedence symbol of every rule in the grammar.
** 
** Those rules which have a precedence symbol coded in the input
** grammar using the "[symbol]" construct will already have the
** rp->precsym field filled.  Other rules take as their precedence
** symbol the first RHS symbol with a defined precedence.  If there
** are not RHS symbols with a defined precedence, the precedence
** symbol field is left blank.
*/
void FindRulePrecedences(struct lemon *xp)
{
    struct rule *rp;

    printf("*****************************************\nFindRulePrecedences:\n");
    
    for(rp=xp->rule; rp; rp=rp->next){

        printf("rule %d:%s\n", rp->ruleline, rp->lhs->name);

        if( rp->precsym==0 ){
            int i, j;
            for(i=0; i<rp->nrhs && rp->precsym==0; i++){
                struct symbol *sp = rp->rhs[i];
                printf("\ttest %s:\n", sp->name);
                if( sp->type==MULTITERMINAL ){
                    printf("\t\t%s:MULTITERMINAL\n", sp->name);
                    for(j=0; j<sp->nsubsym; j++){
                        if( sp->subsym[j]->prec>=0 ){
                            rp->precsym = sp->subsym[j];
                            break;
                        }
                    }
                }else if( sp->prec>=0 ){      /* psp->preccounter统计的次序，left，right */
                    printf("\t\tset %s ::= %s(%d) \n", rp->lhs->name, rp->rhs[i]->name, rp->rhs[i]->prec);
                    rp->precsym = rp->rhs[i]; /* 优先级低于最后一个终结符号 */
                }else{
                    printf("\t\t %s has prec %d, egnor!\n ", rp->rhs[i]->name, sp->prec);
                }
            }
            printf("\t last prec is:");
            if (rp->precsym)
                printf("%s\n", rp->precsym->name);
            else
                printf("nothing!\n");
            
        }else{
            printf("\thas precsym: %s\n", rp->precsym->name);
        }
    }
    return;
}

/* Find all nonterminals which will generate the empty string.
** Then go back and compute the first sets of every nonterminal.
** The first set is the set of all terminal symbols which can begin
** a string generated by that nonterminal.
*/
void FindFirstSets(struct lemon *lemp)
{
    int i, j;
    struct rule *rp;
    int progress;
    
    printf("************************************\nFindFirstSets:\n");

    printf("set %d symbols.lambda ::= False\n", lemp->nsymbol);
    for(i=0; i<lemp->nsymbol; i++){
        lemp->symbols[i]->lambda = LEMON_FALSE;
    }

    printf("set %d symbols.firstset ::= SetNew\n", lemp->nsymbol);
    for(i=lemp->nterminal; i<lemp->nsymbol; i++){
        lemp->symbols[i]->firstset = SetNew();
    }
    
    /* First compute all lambdas */
    do{
        progress = 0;
        for(rp=lemp->rule; rp; rp=rp->next){
            printf("rule %d %s:\n", rp->ruleline, rp->lhs->name);
            if( rp->lhs->lambda )
            {
                printf("\trule has lambda, continue!\n");
                continue;
            }
            
            for(i=0; i<rp->nrhs; i++){
                struct symbol *sp = rp->rhs[i];
                printf("\t %s type:%d,lambda:%s\n", sp->name, sp->type, sp->lambda?"True":"False");
                if( sp->type!=TERMINAL || sp->lambda==LEMON_FALSE )
                {
                    printf("\tGet %s!\n", sp->name);
                    break;
                }
            }
            if( i==rp->nrhs ){
                printf(" \t Set %s.lambda : True\n", rp->lhs->name);
                rp->lhs->lambda = LEMON_TRUE;
                progress = 1;
            }
            else
            {
                printf("\t Noop!\n");
            }
            printf("\t%s.lambda : %s\n", rp->lhs->name, rp->lhs->lambda?"True":"False");
        }
    }while( progress );
    
    _("Now compute all first sets\n");
    do{
        struct symbol *s1, *s2;
        progress = 0;
        for(rp=lemp->rule; rp; rp=rp->next){
            RuleOut(rp);
            s1 = rp->lhs;
            for(i=0; i<rp->nrhs; i++){
                s2 = rp->rhs[i];
                SymbolOut(s2);
                if( s2->type==TERMINAL ){
                    _("\tTERMINAL, index:%d\n", s2->index);
                    progress += SetAdd(s1->firstset,s2->index);
                    break;
                }else if( s2->type==MULTITERMINAL ){     /* MULTITERMINAL 添加每一个终结符号 */
                    _("\t MULTITERMINAL %d nsubsym\n", s2->nsubsym);
                    for(j=0; j<s2->nsubsym; j++){
                        _("sym[%d] index:%d\n",j, s2->subsym[j]->index);
                        progress += SetAdd(s1->firstset,s2->subsym[j]->index);
                    }
                    break;
                }else if( s1==s2 ){              /* 左递归，结束 */
                    _("\t same and break!\n");
                    if( s1->lambda==LEMON_FALSE ) break;
                }else{                           /* 遇到非终结符号，合并 */
                    _("\t SetUnion %s,%s\n", s1->name, s2->name);
                    progress += SetUnion(s1->firstset,s2->firstset);
                    if( s2->lambda==LEMON_FALSE ) break; /* s2非空字符，结束 */