自顶向下语法分析方法：消除左递归

本文主要是介绍自顶向下语法分析方法：消除左递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直接左递归

形如A->Aβ，A∈非终结符，β∈终结符∪非终结符。

消除直接左递归

一般形式：
A->Aα1|Aα2|...|Aαm|β1|β2|...|βn
其中，αi(1≤i≤m)不等于ε,βj(1≤j≤n)不以A开头，消除直接左递归改写为：
A->β1A'|β2A'|...|βnA'
A'->α1A'|α2A'|...|αmA'|ε

例如：

文法：
S->Sa
S->b
消除直接左递归：
S->bS'
S'->aS'|ε

间接左递归

形如A->Bβ，B->Aα，A,B∈非终结符，α,β∈终结符∪非终结符。

消除间接左递归
先通过产生式非终结符置换，变为直接左递归，然后按直接左递归方法消除

例如：

文法：
(1)A->aB
(2)A->Bb
(3)B->Ac
(4)B->d
用（1）、（2）的右部置换（3）中的非终结符A,得到：
B->aBc
B->Bbc
B->d
消除直接左递归：
B->aBcB'|dB'
B'->bcB'|ε
把原来的A产生式加入，最终文法为：
A->aB
A->Bb
B->aBcB'|dB'
B'->bcB'|ε

这篇关于自顶向下语法分析方法：消除左递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---