简明Lemon核心代码分析之一–LR(0)项目的生成

上一篇提到了Lemon这个项目,对于一个只有4000多行代码量的项目,用了一本400页的书来分析它的实现。我觉得应该把书读薄一点,所以我尝试着把这里我认为最核心的部分做一个我自己的诠释。

Lemon是一个LALR的语法分析器,有它自己自定义的语法规则,分析语法文件之后再根据模板文件输出C代码。这里涉及到几个步骤:词法分析,LALR语法分析,生成C代码文件。词法分析没有太多可说,就是根据语法规则定义状态机,提取词法的token,逐个进行分析。这个过程完毕之后,将产生相应的产生式,符号,产生式的左边符号,右边符号,开始符号等等这些都是在这一步完毕之后可以知道的。这一步不做太多的分析,因为相对而言还是比较简单的。而最后一步,也不做分析。重点在第二步,如何根据LALR算法得到动作表。

在我看来,核心包括两步:LR(0)项目的生成,以及每个LR(0)项目的向前看符号的计算。

首先看如何生成LR(0)项目。简单的说,是从开始符号出发,逐个遍历以它为产生式左边符号的产生式,逐个生成LR(0)项目。
在这里,先引入两个概念:核心项目和非核心项目。核心项目指的是,以开始符号为产生式左边符号的产生式和所有点不在最左边的项目。非核心项目则指的是点在最左边的非初始项目(即左边符号不是开始符号的产生式)。

比如有文法:
E→T
T→T*F
那么核心项目为: E→·T,T→T·*F,T→T*·F,而非核心项目则指的是T→·T*F。之所以是非核心项目,原因是这样的项目是可以根据闭包操作重新计算生成的,在需要节省存储空间的时候可以忽略它们。

Lemon在生成LR(0)项目时使用了两个链表来保存核心和非核心项目,即basis和current指针,而保存每一个项目的config结构体,也有两个不同的指针,分别用于串联起这样的链表,即bp和next。

首先,会找到所有以开始符号做为左边符号的产生式,将这些产生式的点号在最左边的项目加入核心项目链表中,见FindStates函数中:

  // 从开始符号开始遍历所有以开始符号为左部的产生式
  for(rp=sp->rule; rp; rp=rp->nextlhs){
    struct config *newcfp;
    // 置位表示该产生式是以开始符号作为产生式左部的
    rp->lhsStart = 1;
    // 创建一个新的ITEM,它的dot在最左边
    newcfp = Configlist_addbasis(rp,0);
    // 将该ITEM的follow集合的第一个符号(第一个符号是$)置1
    // 也就是说,将$加入这个ITEM的follow集合中
    // 换言之, 任何一个以开始符号最为产生式左部符号的,而且其DOT在最左边位置的ITEM,其follow集合一定有$
    SetAdd(newcfp->fws,0);
  }

这一过程结束时,也就形成了一个核心项目链表(在全局变量basis中)和所有核心非核心项目链表(在全局变量current中)。

然后进入函数getstate中,首先对核心项目进行排序,得到排序后的链表头也就是某个核心项目,再根据该核心项目查找是否已经存在了相应的状态,如果不存在,则调用Configlist_closure对当前的所有项目(也就是current链表中的项目)进行闭包操作,闭包操作的算法相对简单,简单的说就是如果当前点号所在的位置是一个非终结符,则也遍历该非终结符的所有产生式,将它们的点号在最左边的项目加入闭包(但是由上面可知,这些项目都不是核心项目了)。这个过程一直到遍历完所有该非终结符的产生式为止。

还是以前面的产生式为例,如果当前处理到项目E→·T,发现在点号位置的是非终结符T,则将T所在的产生式点号在最左边的项目T→·T*F也加入这个闭包中。

上面的过程,就得到了以开始符号产生式下对应的所有项目。我把这一部分的代码,加注释贴在下面,省略了不相关的部分:

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();
  // 得到基本项目链表头, 同时将链表尾置空, 也将basis链表头置空,
  // 这样下一次再加入该链表的基本项目就是针对下一个项目的基本项目
  bp = Configlist_basis();

  /* Get a state with the same basis */
  // 查找有同一个基本项目的状态
  stp = State_find(bp);
  if( stp ){
  // .....
  }else{
	// 如果之前没有这个STATE
    /* This really is a new state.  Construct all the details */
	// 创建ITEM的闭包
    Configlist_closure(lemp);    /* Compute the configuration closure */
    // 对前面生成闭包时新加入的ITEM进行重新排序
    Configlist_sort();           /* Sort the configuration closure */
    // 得到项目链表头, 同时将链表尾置空, 也将current链表头置空,
    // 这样下一次再加入该链表的基本项目就是针对下一个项目的项目
    cfp = Configlist_return();   /* Get a pointer to the config list */
    // 创建一个新的状态
    stp = State_new();           /* A new state structure */
    MemoryCheck(stp);
    // 设置它的基本项目指针和所有项目指针
    stp->bp = bp;                /* Remember the configuration basis */
    stp->cfp = cfp;              /* Remember the configuration closure */
    stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
    stp->ap = 0;                 /* No actions, yet. */
    // 以基本项目为key, 新增一个STATE
    State_insert(stp,stp->bp);   /* Add to the state table */
    // 从这个状态出发,继续获得其他状态
    buildshifts(lemp,stp);       /* Recursively compute successor states */
  }
  return stp;
}

// 以当前current链表上的ITEM为基础,计算它们的闭包
void Configlist_closure(struct lemon *lemp)
{
  struct config *cfp, *newcfp;
  struct rule *rp, *newrp;
  struct symbol *sp, *xsp;
  int i, dot;

  assert( currentend!=0 );
  // 遍历当前的current链表
  for(cfp=current; cfp; cfp=cfp->next){
    // 得到产生式和dot位置
    rp = cfp->rp;
    dot = cfp->dot;
    // 如果dot位置在最右边,则继续下一个循环
    if( dot>=rp->nrhs ) continue;
    // 获得在dot位置的符号
    sp = rp->rhs[dot];
    // 如果是非终结符, 那么遍历以这个符号为产生式左部的所有产生式,
    // 将DOT位置在最左边的ITEM加入该closure中
    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++;
      }
      // 遍历所有以sp作为产生式左边非终结符的产生式
      for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
    	// 创建一个新的ITEM,其DOT位置在该产生式右部最左边
    	// 通过这个动作,将所有以某非终结符为产生式左边的产生式的基本项目添加到current链表中
    	// 后面继续遍历时会处理到这些项目的闭包
        newcfp = Configlist_add(newrp,0);
        // ......
      }
    }
  }
  return;
}

如此得到了一个状态,以及属于它的所有项目,接着就可以从这个状态的项目出发,依次得到点号在下一个位置的核心项目,将它们加入到项目链表中,再计算得到下一个状态。紧跟着再根据新得到的状态以同样的过程再计算其他的状态。这部分代码在函数buildshifts,也将注释加入贴在下面:

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

  /* Each configuration becomes complete after it contibutes to a successor
   ** state.  Initially, all configurations are incomplete */
  // 首先置该状态的所有ITEM状态为INCOMPLETE
  for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;

  /* Loop through all configurations of the state "stp" */
  // 遍历一个状态下的所有item
  for(cfp=stp->cfp; cfp; cfp=cfp->next){
	// 已经处理完毕则继续下一个循环
    if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */
    // DOT位置已经在最右则继续下一个循环
    if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */
    // 清空重置ITEM链表和集合,因为下面的循环要重新计算它们
    Configlist_reset();                      /* Reset the new config set */
    // 取得在dot位置的符号
    sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */

    /* 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. */
    // 遍历当前ITEM的在同一个STATE中的ITEM链表,注意前面已经对ITEM进行了排序,
    // 而这次是从当前ITEM开始的,所以也就是遍历链表中在cfp之后位置的所有ITEM
    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 */
      // 得到该ITEM在该DOT位置的符号
      bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
      // 如果两者不是同一个符号,则继续
      if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
      // 置该ITEM为已经处理过的状态
      bcfp->status = COMPLETE;                  /* Mark this config as used */
      // 在该ITEM的DOT+1位置添加一个新的基本项目
      newcfg = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
      // 如果bcfp为  A->B * CD, 而newcfg为A->BC*D
      Plink_add(&newcfg->bplp,bcfp);
    }

    /* Get a pointer to the state described by the basis configuration set
     ** constructed in the preceding loop */
    // 根据前面循环得到的新的ITEM链表得到下一个状态
    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; insubsym; i++){
        Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
      }
    }else{
      // 新增一个SHIFT动作到这个新的STATE
      Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
    }
  }
}

总而言之,这就是一个从开始符号的产生式出发,计算核心项目,再根据核心项目计算对应的状态,再由当前新计算得到的状态中的项目出发,将点号向前移动一步得到新的核心项目,再计算状态的过程。比较绕,但是看明白了就发现其实还是比较容易理解的,其实就是第一个递归遍历的过程。

One Comment

  1. 说:

    您好,您是否有lemon.c lempar.c 能发给我一份么,我在网上找的lemon.c和书上讲的有些不一样。多谢,jltxgcy@163.com

    [回复]

Leave a Reply