左递归和右递归是否产生相同的解析树？

Question

这是右递归语法：

<assign> -> <id> = <exp>
<id> -> A | B | C
<exp> -> <term> + <exp> | <temp>
<term> -> <factor> * <term> | <factor>
<factor> -> ( <exp> ) | <id>

这是左递归语法：

<assign> -> <id> = <exp>
<id> -> A | B | C
<exp> -> <exp> + <term> | <term>
<term> -> <term> * <factor> | <factor>
<factor> -> ( <exp> ) | <id>

这些语法会为字符串 B + C + A 生成相同的解析树吗？下图为左递归

但是，我画了右递归的解析树，节点的位置有点不同。我不知道我在做什么是正确的。所以我想知道左递归和右递归会产生两个不同的解析树还是应该是相同的解析树。请帮助澄清这个问题。谢谢

Answer 1

左右递归不会产生相同的树。
您可以从语法中轻松看出 A+B+C 将在 "top-level' have <term> <op> <exp> or <exp> <op> <term> ("exp" 中成为 "B+C" 在一种情况下 "A+B" 在另一种情况下。

只有在所有产生式都直接匹配的微不足道的情况下，树才会相同。
（例如 A（跳过 assign）将是 <exp> --> <term> --> <factor> --> <id>

Answer 2

由于两种语法不同，我希望有不同的解析树。正确的递归将交换顶部标记为 <expr> = <expr> + <term> 的节点上的加法和单个展开。正确的递归语法将扩展为 <expr> = <term> + <expr>，因此两个 children 将被交换。

如果您正在尝试为数学表达式编写编译器，更重要的是运算符优先级，但不确定您在做什么。

Left Recursion and Right recursion produce same parse tree or not?