context-free-grammar - 上下文无关语法可以左右递归吗？

Question

前任。

S-> S + T | 吨

T-> U - T | ü

U -> ID | ñ

显然没有保留关联性。但无论如何我都看不出它是模棱两可的。那么这是一个非模棱两可的cfg吗？

Answer 1

正如您所展示的，语法可以同时具有左右递归，但这并不意味着什么。任何语法都可以重写，因此所有递归都是左或右（但除非语法是规则的，否则不会始终相同）：

A -> B A C

变成：

A -> B X
X -> A C

您现在有一个相互递归，它在一个规则的左侧和另一个规则的右侧。您在问题中的语法似乎是明确的，但这实际上与左递归或右递归没有任何关系。