问题1

同一非终结符的多个候选式存在共同前缀,将导致回溯现象

文法G

S → aAd | aBe
A → c
B → b

输入

a b c

问题2

左递归文法会使递归下降分析器陷入无限循环

文法G

E → E + T | E – T | T
T → T * F | T / F | F
F → ( E ) | id

输入

id + id * id

含有A→Aα形式产生式的文法称为是直接左递归的 (immediate left recursive)

如果一个文法中有一个非终结符A使得对某个串α存在一个推导A=>+Aα ,那么这个文法就是左递归的。

经过两步或两步以上推导产生的左递归称为是间接左递归的。

消除直接左递归

消除直接左递归的一般形式

消除左递归是要付出代价的——引进了一些非终结符和ε_产生式

消除间接左递归

将S的定义代入A-产生式,得:

A → A c | A a d | b d | ε

消除A-产生式的直接左递归,得:

消除左递归算法

  • 输入:不含循环推导(即形如A =>+ A的推导)和ε-产生式的文法G
  • 输出:等价的无左递归文法
  • 方法:
按照某个顺序将非终结符号排序为A1,A2,… ,An .
 for ( 从1到n的每个i ) {
     for ( 从1到i -1的每个i ) {
        将每个形如Ai → Aj γ的产生式替换为产生式组 Ai → δ1 γ∣δ2 γ∣…∣δk γ ,
        其中Aj → δ1∣δ2∣… ∣δk ,是所有的Aj 产生式
 }
    消除Ai 产生式之间的立即左递归
 }

提取左公因子(Left Factoring )

文法G

S → aAd | aBe
A → c
B → b

文法G '

S → a S'
S' → Ad | Be
A → c
B → b

通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择。

提取左公因子算法

  • 输入:文法G

  • 输出:等价的提取了左公因子的文法

  • 方法:

    对于每个非终结符A,找出它的两个或多个选项之间的最长公共前缀α。如果α ≠ ε,
    即存在一个非平凡的( nontrivial )公共前缀,那么将所有A-产生式
    A → α β1 | α β2 | … | α βn | γ1 | γ2 | … | γm
    替换为
    A → α A' | γ1 | γ2 | … | γm
    A' → β1 | β2 | … | βn
    其中, γi 表示所有不以α开头的产生式体; A'是一个新的非终结符。不断应用这个
    转换,直到每个非终结符的任意两个产生式体都没有公共前缀为止
最后修改日期:2020年5月31日

留言

撰写回覆或留言