简明Lemon核心代码分析二–向前看符号集的生成

所谓的向前看符号,就是当某一个项目的点号已经在最右边时,当下一个符号是什么符号时,可以使用该产生式进行归约操作。

比如,有一个项目是T→T*F·,它的向前看符号为=号,那么就意味着,如果当前栈的栈顶的符号为T*F,而下一个输入符号为=号时,可以使用产生式T→T*F进行归约操作,也就是将栈顶的T*F符号弹出,压入符号T=。

如果说,前面的buildshifts函数确定了不同的状态之间,经过哪些符号可以到达,那么向前看符号就决定了何时可以进行归约。要计算向前看符号,过程还是比较复杂,需要好几个辅助变量的计算。

首先要计算的是所有符号的first集合。它的算法,简单描述如下:
1. 直接收取:对形如U->a…的产生式(其中a是终结符),把a收入到First(U)中
2. 反复传送:对形入U->P…的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去】。

Lemon中有一个独立的函数实现这整个过程,加了注释贴在下面,如果已经熟悉了上面的过程可以先不看具体的代码,仅需要知道需要先计算符号的first集合了:

void FindFirstSets(struct lemon *lemp)
{
  int i, j;
  struct rule *rp;
  int progress;

  // 为真时表示文法符号能产生空串
  for(i=0; insymbol; i++){
    lemp->symbols[i]->lambda = LEMON_FALSE;
  }
  // 初始化每个终结符符的first集合
  for(i=lemp->nterminal; insymbol; i++){
    lemp->symbols[i]->firstset = SetNew();
  }

  /* First compute all lambdas */
  // 扫描所有产生式,判断每个在产生式左边出现的符号,是否可以产生出空串,打上标记
  do{
    progress = 0;
    // 遍历所有的产生式
    for(rp=lemp->rule; rp; rp=rp->next){
      // 如果产生式的左部可以是空串,则分析下一个规则
      if( rp->lhs->lambda ) continue;
      // 遍历产生式的右部符号
      for(i=0; inrhs; i++){
        struct symbol *sp = rp->rhs[i];
        assert( sp->type==NONTERMINAL || sp->lambda==LEMON_FALSE );
        // 发现第一个不是空串的符号则退出循环
        if( sp->lambda==LEMON_FALSE ) break;
      }
      if( i==rp->nrhs ){
        // 遍历了产生式的所有右部符号发现都是空串,则说明该产生式的左部可以是空串
        // 同时置progress为1
        rp->lhs->lambda = LEMON_TRUE;
        progress = 1;
      }
    }
    // 当progress不为0时,说明在某次遍历发现了之前没有发现的可以产生空串的文法符号
    // 这是因为假如这个首次发现的可以产生空串的产生式左边符号,也可能出现在其他产生式右边
    // 对其他产生式产生影响, 所以需要再重新扫描一下全部产生式
  }while( progress );

  /* Now compute all first sets */
  do{
    struct symbol *s1, *s2;
    progress = 0;
    // 遍历所有产生式
    for(rp=lemp->rule; rp; rp=rp->next){
      // s1为产生式左部
      s1 = rp->lhs;
      // 遍历产生式右部符号集
      for(i=0; inrhs; i++){
        s2 = rp->rhs[i];
        if( s2->type==TERMINAL ){
          // 如果右部符号是终结符,则直接加入产生式左部的first集合中,
          // progress表示是否对这个first集合有改变
          // 退出本次循环体对下一个产生式进行分析
          progress += SetAdd(s1->firstset,s2->index);
          break;
        }else if( s2->type==MULTITERMINAL ){
          for(j=0; jnsubsym; j++){
            progress += SetAdd(s1->firstset,s2->subsym[j]->index);
          }
          break;
        }else if( s1==s2 ){
          // 如果现在产生式左部右部符合相同,且不是一个空串,退出本次循环体对下一个产生式进行分析
          if( s1->lambda==LEMON_FALSE ) break;
        }else{
          // 否则此时右部符合是非终结符,将两者的first集合进行合并
          // progress表示是否对这个first集合有改变
          progress += SetUnion(s1->firstset,s2->firstset);
          if( s2->lambda==LEMON_FALSE ) break;
        }
      }
    }
    // 当progress不为0时,说明前面的循环中某符合的first集合发生了改变
    // 所以要重新开始扫描所有产生式
  }while( progress );

  return;
}

其次再根据first集合计算follow集合。计算follow的算法描述如下:
1. 直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。
2.直接收取:对形如“…UP…”(P是非终结符)的组合,把First(P)直接收入到Follow(U)中【在这里,如果First(P)中有空字符,那么就要把左部(假设是S)的Follow(S)送入到Follow(U)中。还有就是Follow集中是没有空字符的】。
3. 直接收取:若S->…U,即以U结尾,则#∈Follow(U)
4.*反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中。

需要说明的是,Lemon中计算的是针对项目的Follow集合,它有一个传播的过程。有如下几种情况要考虑。
对每个产生式,从点号在最左边的项目开始,依次查找每个符号,做以下的操作:
1) 如果当前项目的下一个符号是一个终结符,那么直接将该终结符加入到该项目的follow集合中。
2) 如果当前项目的下一个符号是一个非终结符,那么将该非终结符的first集合加入到该项目的follow集合中(这就是前面需要计算每个符号的first集合的原因)。
以上两种情况中,如果找到第一个终结符,和找到第一个不会推导出空串的非终结符时,都将终止不再继续寻找点号下一个位置的符号。而如果当循环终止时,点号已经在最右边,那么说明点号后面或者没有符号,也或者都是可以推导出空串的非终结符,当这种情况出现时,需要将新的项目加入旧项目的传播链中,因为新项目的后面都是可以推导出空串(包括空串)的符号,所以follow集合可以从旧项目传播到新项目中。

比如,当前项目是T→T·*F,而对这个项目而言点号下一个位置的项目是T→T*·F,而非终结符F可以推导出空串,那么说明项目T→T·*F的follow集合可以传播到项目T→T*·F,即需要将T→T*·F加入到项目T→T·*F的fplp(Follow-set forward propagation links)中,而对于项目T→T·*F而言,点号在它前面的项目T→T*·F就在它的bplp中(Follow-set backwards propagation links)。

换言之,follow集合,从这个项目的产生式左边符号开始进行传播,随着点号的向右移动,中间经过的所有项目也将它们的follow集合传递给后面的项目。

比如,有产生式A→bC,从该产生式点号最左边的项目A→·bC开始,首先将b加入该项目的follow集合中。点号继续往前走一步,得到另一个状态的项目A→b·C,假设非终结符C的first集合为{c},那么将它的前一个项目的follow集合与这个first集合求并集得到{b,c}。点号继续往前走一步,得到项目A→bC·,这时点号已经在最右边,传播结束,该项目的follow集合为{b,c},也就是说,如果当前栈顶符号为bC,而下一个符号为{b,c}中的其中一个,则可以按照产生式A→bC进行归约操作。(老实说,这里的数学原理我还是没怎么明白,只是照着算法看是这样做的:)

之所以需要fplp这样的指针,是因为需要某种机制保存当前项目会传播到哪些项目中,否则的话就需要有一个栈,将当前项目压栈后面再从栈中弹出来计算点号向前之后得到哪些项目可以进行传播。加入传播链的函数是Plink_add,可以搜索一下相应的调用点就明白前面的算法了。

以上的过程,涉及到将某项目加入到另一个项目的fplp或者bplp指针中,搜索相应的代码就可以看到了,基本上就是前面的算法。

在整个过程完毕之后,在函数FindLinks中,将遍历项目的bplp指针,将挂载在上面的项目加入到fplp中。
最后,在函数FindFollowsets中,将遍历一个项目的fplp,将该项目之前的所有项目的follow集合合并进来。

比如,项目A→bC·(假设命名为A)的点号前一个位置的项目是A→b·C(假设命名为B),于是项目B就在项目A的fplp指针中,反过来项目A在项目B的bplp指针中,因此项目A的follow集合将被传播到项目B中,也就是项目B将合并项目A的follow集合。

Lemon中提供了函数输出follow集合的传播过程,可以搜索SetPrint函数并且将它们打开编译条件即可,输出结果类似于:

         expr ::= * expr MINUS expr
            [$ PLUS MINUS DIVIDE TIMES]
            To   (state  5) expr ::= expr * MINUS expr

这里的意思是项目expr ::= * expr MINUS expr将它的follow集合 [$ PLUS MINUS DIVIDE TIMES]传递到了项目 expr ::= expr * MINUS expr中。

——————- 分割线 ———————
以上,完成LR(0)和向前看符号的算法分析,有了这两个,计算动作表,也就是何时将SHIFT操作,何时进行归约操作就有了依据。后面的过程不再分析。

Leave a Reply