文法转换
- 例
文法GS→aAd∣aBeA→cB→b输入abc
⚠
同一非终结符的多个候选式存在共同前缀,将导致回溯现象
- 例
文法GE→E+T∣E−T∣TT→T∗F∣T/F∣FF→(E)∣id输入id+id∗idE⇒E+TE⇒E+T+T...
概念
💡
含有A→Aa形式产生式的文法称为是直接左递归
如果一个文法中有一个非终结符A使得对某个串a存在一个推导A⇒+Aa,那么这个文法就是左递归的
经过两步或两步以上推到产生的左递归成为是间接左递归的
消除直接左递归
A→Aα∣β(a=ε,β不以A开头)⇓A→βA′A′→αA′∣ε
更一般地
A→Aα1∣Aα2∣...∣Aαn∣β1∣β2∣...∣βm(αi=ε,βj不以A开头)⇓A→β1A′∣β2A′∣...∣βmA′A′→α1A′∣α2A′∣...∣anA′∣ε
⚠
消除左递归是要付出代价的—引进了一些非终结符和ε_产生式
消除间接左递归
例
S→Aα∣bA→Ac∣Sd∣ε>>将S的定义带入A−产生式,得:A−Ac∣Aad∣bd∣ε>>消除A−产生式的直接左递归,得:A→bdA′∣AA′→cA′∣adA′∣ε
提取左公因子
例
文法G
S→aAd∣aBeA→cB→b⇓
文法G′
S→aS′S′→Ad∣BeA→cB→b
ℹ️
通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择