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

Parsing complete mathematical expressions with PEG.js

本文关键字：表达式 PEG js 使用      更新时间：2023-09-26

我正在尝试扩展 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。

你能帮我改进和调试这个吗？

提前谢谢。

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

Matt 的答案是正确的，但是关于如何在 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); }

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

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

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

我假设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 语法），因此您可能需要查看 [自上而下] 运算符优先级解析以获得更灵活和更具表现力的替代方案。 Douglas Crockford，Vaughn Pratt和Annika Aasa有一些关于这个主题的好文章。

相关文章：