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

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将在“顶层”有 <term> <op> <exp> 或 <exp> <op> <term> (“exp”在一种情况下为“B+C”，在另一种情况下为“A+B”。

只有在所有产品都直接匹配的小情况下，树才会相同。
(例如 A (跳过 assign )将是 <exp> --> <term> --> <factor> --> <id>