“消除左递归”和“构造一个等价的无歧义语法”的区别

Question

例如：

R → R bar R|RR|R star|(R)|a|b

构造一个等价的无歧义语法：

R → S|RbarS S→T|ST
T → U|Tstar U→a|b|(R)

如何消除R → R bar R|RR|R star|(R)|a|b的左递归

Eliminate left-recursion和construct an equivalent unambiguous grammar有什么不同

Answer 1

一个明确的语法是，对于语言中的每个字符串，只有一种方法可以从语法中派生出来。在编译器构造的上下文中，歧义语法的问题是，从语法上看，给定输入字符串的解析树应该是什么并不明显。一些工具使用它们用于解决歧义的规则来解决这个问题，而另一些工具则只要求语法明确。

左递归语法是这样一种语法，其中给定非终结符的派生可以再次产生相同的非终结符，而无需首先产生终结符。这会在递归下降风格的解析器中导致无限循环，但对于shift-reduce解析器则没有问题。

请注意，无歧义的语法仍然可以是左递归的，而没有左递归的语法仍然可以是歧义的。还要注意，根据您的工具，您可能只需要删除歧义，而不是左递归，或者您可能需要删除左递归，但不需要歧义(尽管明确的语法通常更可取)。

所以不同的是，消除左递归和歧义解决了不同的问题，在不同的情况下是必要的。