编译原理-消除左递归(自己看)

参考:https://blog.csdn.net/liyun123gx/article/details/19924993

  • 左递归分为两种:
    • 直接左递归:经过一次推导(直接看出来)的左递归式子,例如
    • (1)A→Aβ

    • 间接左递归:经过若干次推导得到左递归式子
    • 1)A→Bβ,B→Aα

消除左递归

  • 1、消除直接左递归
  • a)  把直接左递归改写为右递归:
           设有文法产生式:A→Aβ|γ。其中β非空,γ不以A打头。
           可写为:A → γA'
                         A' → βA'|ε
    一般情况下,假定关于A的产生式是:
           A → Aα1| Aα2 |… |Aαm|β1|β2 |…|βn
           其中,αi( 1 ≤ i ≤ m)均不为空,βj(1 ≤ j ≤ n)均不以A打头。
           则消除直接左递归后改写为:
           A→ β1A'| β2 A' |…| βnA'
           A'→ α1A' | α2A' |…| αmA' |ε

案例

E → E + T | T
T → T * F | F
F → (E) | i

转换后:(记得多个ε

E → TE'
E' → +TE'| ε
T → FT'
T' → *FT' | ε
F → (E) | i

  • 2、消除间接左递归
  • 方法:对于间接左递归的消除需要先将间接左递归变为直接左递归,然后再按a)清除左递归。

案例

(1)A → aB

(2)A → Bb

(3)B → Ac

(4)B → d
  • 若干次推导得到:
(1)B → aBc

(2)B → Bbc

(3)B → d
  • a)方法消除左递归:
B → aBcB' | dB'

B' → bcB' | ε
  • 再把原来其余的产生式A→aB,A→Bb加入,最终得到等价文法为:
(1) A → aB

(2) A → Bb

(3) B → (aBc|d)B'

(4) B' → bcB'| ε

还有一个万能方法,懒得看了
参考:https://blog.csdn.net/liyun123gx/article/details/19924993

上一篇:社区规则


下一篇:CodeForces571A. Lengthening Sticks(组合数学-容斥)