2

这是右递归语法:

<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 生成相同的解析树吗?下图是左递归。

在此处输入图像描述

但是,我为右递归绘制了解析树,它在节点的位置之间有点不同。我不知道我所做的是否正确。所以我想知道左递归和右递归会产生两个不同的解析树或者应该是相同的解析树。请帮助澄清这个问题。谢谢。

4

2 回答 2

3

左右递归不会产生相同的树。
您可以从A+B+C“顶级”的语法中轻松看出,<term> <op> <exp><exp> <op> <term>(“exp”在一种情况下为“B+C”,在另一种情况下为“A+B”。

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

于 2016-03-23T15:29:22.763 回答
2

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

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

于 2016-03-23T15:47:53.097 回答