问题描述
我正在尝试扩展的示例语法,用于解析所有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:
但并非所有表达式都被正确解析。
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.
基于语法的运算符优先级和关联性解决方案通常非常讨厌(参见,因此您可能需要查看[自上而下]运算符优先级解析,以获得更灵活和更具表现力的替代方案。 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.
这篇关于用PEG.js解析完整的数学表达式的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!