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

Question

例如

S-> S + T |

T-> U - T |你

U -> ID | N

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

Answer 1

语法可以同时具有左递归和右递归，就像您展示的那样，但这并不意味着什么。任何语法都可以重写，因此所有递归要么是左递归，要么是右递归(但除非语法是规则的，否则不会始终相同):

A -> B A C

变成:

A -> B X
X -> A C

你现在有一个相互递归，它在一个规则的左边，在另一个规则的右边。您在问题中的语法确实看起来很明确，但这实际上与左递归或右递归没有任何关系。