编译原理-第四章

一、知识点:

1.语法分析的过程（自上而下推导，自下而上规约）

2.文法的改造

3.递归下降分析器的设计（LL分析，自上而下的推导）

4.语法分析器的自动生成（LR分析，自下而上的规约）

LL(1) 分析法：

1.消除直接左递归

设有产生式   P→Pα|β        (1)

       其中β不以P开头，α不为ε。那么，我们可以把P的规则改为如下的非直接左递归形式：

       P→βP’

       P’→αP’|ε       (2)

(1)   式和(2)式是等价的

消除直接左递归方法：

设有产生式    P→Pα1|Pα2|…|Pαm|β1|β2|…|βn      其中每个βi不以P开头，每个αi不为ε

消除P的直接左递归性就是把这些规则改写成：

       P→β1P’|β2P’|…|βnP’

       P’→α1P’| α2P’|…|αmP’| ε

按任意顺序对非终结符排序，P1,P2,P3……，然后作如下工作

  FOR i=1 TO  N{

           FOR j=1 TO i-1{

                  对PiPjγ的产生式，改写成

                      Piδ1 γ| δ2 γ|…| δk γ

          }

          消除Pi的直接左递归；

  }

       最后，删除无用（从起始符永远不能到达）的非终结符的产生式。

2.消除间接左递归

(1) 将间接左递归改造为直接左递归

    将文法中所有如下形式的产生式：

            P_i →P_jγ|β₁|β₂|…|β_n

                 P_j→δ₁|δ₂|δ₃|…|δ_k

      改写成：

    P_i →δ₁γ|δ₂γ|δ₃γ|…|δ_kγ|β₁|β₂|…|β_n

（2）消除直接左递归

   P→Pα₁|Pα₂|...|Pα_m|β₁| β₂|...| β_n

   消除P的左递归

   P→ β₁P'| β₂P'|...| β_nP'

   P'→ α₁ P'| α₂ P'|...|α_m P'| ε

（3）化简改写后的文法，即去除那些从开始符号出发却永远无法到达的非终结符的产生规则。

  最终得到无左递归的文法。

3..消除回溯：定义FIRST集
    令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：


特别地，如果α      ε，则ε∈FIRST(α)
如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，则A可以根据所面临的第一个输入符号，准确地指派一个候选式α去执行任务，α是那个FIRST集含a的候选式，即  a ∈FIRST(α)

3.改造文法

改造方法：提取公共左因子
假设A的产生式为
        A→δβ1|δβ2|…|δβn|γ1| γ2|…|γm
其中每个γ不以δ开头
那么把这些产生式改写为:
        A→δA’ |γ1| γ2|…|γm
        A’→β1|β2|…|βn

反复提取左因子(包括对新引进的非终结符，例如A’)

注意：若空字ε属于某个非终结符的候选式的首符集，就会有问题

二、课后练习：