用PEG.js解析完整的数学表达式

本文介绍了用PEG.js解析完整的数学表达式的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试扩展 PEG.js 的示例语法，用于解析所有4个数学表达式我的在线BASIC口译实验的操作员：

I'm trying to extend the example grammar of PEG.js for parsing mathematical expressions with all the 4 operators for my online BASIC interpreter experiment:

www.dantonag.it/basicjs/basicjs.html

但并非所有表达式都被正确解析。

but not all the expressions are parsed correctly.

这是我的PEG语法：

expression = additive additive = left:multiplicative atag:("+" / "-") right:additive { return {tag: atag, left:left, right:right}; } / multiplicative multiplicative = left:primary atag:("*" / "/") right:multiplicative { return {tag: atag, left:left, right:right}; } / primary primary = number / "(" additive:additive ")" { return additive; } number = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

它正确解析2 * 3 + 1（给出7）这样的表达式，但不是像2-1-1，给出2而不是0。

It parses correctly expressions like 2*3+1 (giving 7), but not an expression like 2-1-1, that gives 2 instead of 0.

你能帮我改进和调试吗？

Can you help me improving and debugging this?

提前致谢。

编辑：我已将数字规则添加到语法中。是的，我的语法为输出提供了一个类似于解析树的递归结构。

Edit: I've added the "number" rule to the grammar. And yes, my grammar gives as output a recursive structure that is analogue to a parse tree.

推荐答案

首先：你的语法丢失了数字规则。另外，我确信您已经知道，在您的示例中运行语法（在添加数字之后）不会给出2，而是像解析树一样。您是否介意更新问题以解决这两个问题？

First: your grammar is missing the number rule. Also, as I'm sure you're aware, running your grammar (after adding number) on your example does not give 2, but rather something like a parse tree. Would you mind updating the question to fix those two issues?

问题： 看起来你已经陷入了联想。当两个具有相同优先级的运算符竞争操作数时，关联性发挥作用。在您的示例中， - 与 - 竞争 - 显然它将具有与其本身相同的优先级 - 但是关联性对于打破 + 和 - 之间以及 * 和 / 。

Problem: It looks like you've run into associativity. Associativity comes into play when two operators with the same precedence are competing for an operand. In your example, - is competing with - -- so clearly it will have the same precedence as itself -- but associativity will also be important for breaking ties between + and -, and between * and /.

我假设 2 * 3 + 1 被正确解析，因为这两个运算符具有不同的优先级，这意味着关联性没有发挥作用，并且你的语法正确地实现了优先级（尽管你应该注意 2 + 3 * 1 是一个更标准的例子，表明乘法的优先级高于此外，由于 2 * 3 + 1 的简单从左到右解析会得到与解析器相同的结果。

I assume that 2*3+1 is parsed correctly because the two operators have different precedences, meaning that associativity does not come into play, and that your grammar correctly implements precedence (although you should note that 2+3*1 is a more standard example for showing that multiplication has higher precedence than addition, since simple left-to-right parsing of 2*3+1 gives the same result as your parser).

我假设您希望 - 是左关联的，但基于此示例，它在您的语法中似乎是右关联的：

I assume you want - to be left-associative, but it seems to be right-associative in your grammar, based on this example:

• 输入：

• input:

1-2-3

输出（解析为 1-（2-3））：

{ "tag": "-", "left": "1", "right": { "tag": "-", "left": "2", "right": "3" } }

左关联树看起来像这样（来自（1-2）-3 ）：

The left associative tree would look like this (from (1-2)-3):

{ "tag": "-", "left": { "tag": "-", "left": "1", "right": "2" }, "right": "3" }

您应该注意，您的其他运营商也似乎是右关联而非左 - 。

You should note that your other operators also appear to be right-associative instead of left-.

解决方案：我真的不知道peg.js是如何工作的，但是一些快速的谷歌搜索出现了这个。

Solution: I don't really know how peg.js works, but some quick googling turned up this.

基于语法的运算符优先级和关联性解决方案通常非常讨厌（参见用于证据的Python语法，因此您可能需要查看[自上而下]运算符优先级解析，以获得更灵活和更具表现力的替代方案。 Douglas Crockford，Vaughn Pratt和Annika Aasa在这个主题上有一些很好的文章。

Grammar-based solutions to operator precedence and associativity are often pretty nasty (see a grammar for Python for evidence), so you may want to check out [top down] operator precedence parsing for a more flexible and expressive alternative. Douglas Crockford, Vaughn Pratt, and Annika Aasa have some nice articles on this subject.