context-free-grammar - 简单算术的上下文无关文法

Question

如果不使用括号并且只考虑加法、减法、乘法和除法，以下描述这些简单算术运算的上下文无关文法是不正确的，对，因为它是右结合而不是左结合？

 - E -> T | T + E | T - E
 - T -> int | int * T | int / T

正确的语法是：

 - E -> T | E + T | E - T
 - T -> int | T * int | T / int

这个推理正确吗？

Answer 1

“正确”是您定义的任何内容。在文法学校教授的非结合运算符的“传统”含义是左结合，因此从这个意义上说，左递归语法是“正确的”，而右递归语法不是，但这是一个非常循环的定义。

此外，您的左递归语法需要E -> T添加正确（因为它不描述任何有限字符串）