1.直接消除左递归

假定P关于的全部产生式是

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

        P->Pα1|Pα2|…|Pαm|β1|β2|…|βn

(每个α都不等于ε，每个β都不以P开头)

方法：左递归变右递归

         P->β1P'|β2P'|…|βnP'

         P'->α1P'|α2P'|…|αmP'|ε

例：给定文法G(S):

E->E+T|T

T->T*F|F

F->(E)|i

消除其直接左递归G(E):

E->TE'

E'->+TE'|ε

T->FT'

T'->*FT'|ε

F->(E)|i

2.间接左递归的消除

例:

消除文法左递归 随笔

再利用直接消除左递归得到

S->abcS'|bcS'|cS'

S'->abcS'|ε

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄