分类 编译原理 下的文章

根据书上写的,判断一个文法是否为LL(1)文法有三点。将其实际作用结合个人理解记录如下。

  1. [文法]没有左递归;
  2. 同一非终结符推导出的多个[右侧]的FIRST集合的交集为空(显然只有一个右侧的产生式不会违反这条规则);
  3. 若[某一产生式]可以推出ε,则要求该[产生式左侧]的[FIRST集合]和[FOLLOW集合]的交集为空。

具体解释如下: 通过结合LL文法的[预测分析程序]这个实现方法的[预测分析表]可以比较直观地进行解释。LL(1)由于前看符号只有一位,可将其视作[行]为单一[非终结符],[列]为单一[终结符]的一张表格。将表格由每一固定行、列号确定的空间称作一个格子的话,则格子里放的是产生式。显然,为了由当前的分析过程和下一符号确定产生时的推导方向的话,每一个格子里只应该放最多一个产生式。当然,空下来的格子放的都是出错标记,因为当前文法不允许在该情况下进行推导。而上面的三条规则解决了如下问题:

  1. 第一条解决了格子跳转的位置问题。左递归加上最左推导,会将自身不断添加到当前推导过程的最左侧,也就是格子的跳转结果指向自己。由于文法固定,格子的内容是不会变化的,这个时候就相当于跳进了一个while(1)的循环中。而显然这样的推导是失败的,因为它始终不会有结果。通过禁止左递归,避免了跳转过程中出现某些环的问题。(并非不允许环的存在,只是因为在不读入字符的情况下的环会导致无限死循环,所以只能说是禁止了“有害的”环的存在。)
  2. 第二条解决了格子里放产生式的数量问题。只有在同一非终结符、同一输入字符的时候,才会出现多个产生式放在同一格子的问题。预测分析表的部分生成工作可以看作这么一个过程:
    FOR <EVERY Non-terminal P>
      FOR <EVERY Pattern α IN Production P->α1|α2|...>
          FOR <EVERY Terminal e IN FIRST(α)>
              prediction_table[P][e] = P->α

    其中P表示任意非终结符,α表示P的任意单个产生式右部,e表示α的FIRST集合里的任意元素(显然是终结符)。这么一看很容易发现,表格只有二维,而循环有三层,按照概率学的角度来说,肯定是允许在不同的α取值中,遇到同一个e的(即允许不同推导右侧的FIRST集合里有相同终结符)。从程序的角度上来说,格子里的原值要被覆盖,因为设计时是要求能够根据P和e唯一确定一个操作的;而从语法的角度上来说,格子的原值要保留,因为这代表了一条语法规则,覆盖的话会导致语法发生变化。这就产生了矛盾。所以,为了从根本上避免该情况的产生,要求在语法设计时就要避免格子出现重复赋值的问题。回到上面,不难发现解决方法之一就是要求不同的FIRST(α)里面不能有相同的e。而用专业术语来表达的话,这正是第二条规则。

  3. 第三条同样解决了格子里放产生式数量的问题。实际上,FOLLOW集合同样是要在预测分析表里放产生式。FOLLOW集合的目的是,告诉预测分析程序,在允许使用ε(即空字)合法结束当前产生式推导的同时,保证会有下一产生式,能够从当前的输入字符开始,开始新的推导。因而同样要在预测分析表里插入标记以指导跳转:
    FOR <EVERY Non-terminal P>
      IF <EXISTS P->ε>
          FOR <EVERY Terminal e IN FOLLOW(P)>
              prediction_table[P][e] = P->ε

    相比于第二条中的工作,这里只有两层循环,因而工作内部不会出现任何问题(因为根据集合的性质,空集作为元素是不可能重复的呀)。但是该段代码与第二条中操作的是同一个预测分析表啊!因而又可能出现格子覆盖的问题。显然,解决方法又是只要两者没有相同的e就行了。这里的两者指的是FOLLOW(P)和FIRST(P)。虽然第二条的代码段中使用的是FIRST(αi),但是在认为所有元素都等价的时候(即不需要再区分每个e对应的α),完全可以算一下,FIRST(αi)并起来就是FIRST(P)。(甚至不用算好吧)

今天来当当自己的课代表:

  1. “文法没有左递归”解决了在预测分析表中无限循环跳转的问题;
  2. 对于P->α1|α2|...∩(αi)=∅解决了在一个预测分析表里放多个非空产生式的冲突问题;
  3. 对于存在P->εFIRST(P) ∩ FOLLOW(P)=∅解决了在一个预测分析表里空产生式与非空产生式的冲突问题。