5

我正在尝试扩展PEG.js的示例语法，以使用我的在线 BASIC 解释器实验的所有 4 个运算符解析数学表达式：

http://www.dantonag.it/basicjs/basicjs.html

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

这是我的 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 的表达式。

你能帮我改进和调试吗？

提前致谢。

编辑：我在语法中添加了“数字”规则。是的，我的语法给出了一个类似于解析树的递归结构作为输出。

4

2 回答 2

9

马特的答案是正确的，但是关于如何在 pegjs 中实现左关联性：

expression = additive

additive
  = first:multiplicative rest:(("+" / "-") multiplicative)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / multiplicative

multiplicative
  = first:primary rest:(("*" / "/") primary)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / primary

primary
  = number
  / "(" additive:additive ")" { return additive; }

number
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

javascript.pegjs示例 Matt 链接到使用类似的方法。关键是处理具有与列表相同优先级的操作字符串，这允许您构建具有正确关联性的树。

于 2015-06-12T08:34:11.667 回答
6

首先：您的语法缺少number规则。另外，我相信你知道，number在你的例子上运行你的语法（在添加之后）不会给出 2，而是像解析树一样的东西。您介意更新问题以解决这两个问题吗？

问题： 看起来你遇到了联想。当具有相同优先级的两个运算符竞争一个操作数时，关联性就会发挥作用。在您的示例中，-is 竞争-- 很明显它将具有与自身相同的优先级 - 但关联性对于打破 and 之间的联系也很重要，+以及-and 之间*的联系/。

我认为这2*3+1是正确解析的，因为这两个运算符具有不同的优先级，这意味着关联性不会起作用，并且您的语法正确地实现了优先级（尽管您应该注意这2+3*1是一个更标准的示例，用于显示乘法比加法具有更高的优先级，因为简单的从左到右的解析2*3+1给出了与解析器相同的结果）。

我假设你想要-左结合，但它在你的语法中似乎是右结合的，基于这个例子：

  • 输入：

    1-2-3

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

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

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

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

您应该注意，您的其他运算符也似乎是右结合而不是左结合。

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

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

于 2013-10-16T14:33:30.413 回答