编程语言语法

Question

假设我有以下语法

program = mul
mul = add {"*" add}
add = NUM {"+" NUM}

和以下输入

1 + 2 * 3

现在通常我会假设输入会给出 7，因为 BIDMAS（先做乘法，然后做加法），但是在阅读了递归下降解析器之后我很困惑这是否会输出

A.

(1 + 2) * 3 = 9

或B.

1 + (2 * 3) = 7

我希望解析器执行 B，因为这通常是数学的处理方式，那么我创建的语法是否正确？

Answer 1

我现在发现不，这不是正确的语法。语法应该是

program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}

这样它总是将乘法加在一起，而不是乘法加法。

Answer 2

嗯，解析器不会自己做任何事情，它只会生成一个抽象语法树 (AST)。我相信要完全实现数学运算顺序，您需要稍微扩展一下语法。在那个简短的例子中，我希望它（除非我误解了这个特定的语法）抛出一个错误，因为你定义了两个二进制操作并传递了三个数字。 1 + 2 * 3 + 4 似乎是更明智的测试输入，是的，它会完全错误（它会告诉你你有一个由两个加法相乘组成的表达式）：mul(add(1,2),add(3,4))

倒置的例子可能有效：

program = add
mul = NUM {"*" NUM}
add = mul {"+" mul}

我希望它将 1 * 2 + 3 * 4 解析为 add(mul(1,2),mul(3,4))。但是，如您所见，我不得不再次更改输入：您期待非常严格的输入。

尝试使用一些抽象语法进行练习 - 创建 "p" 和 "q"（或任何其他字符）的特定模式，以更加习惯使用 [ 时所需的相当落后的思维方式=27=].

编程语言语法

Programming language grammars

grammar

parsing

abstract-syntax-tree