javascript - 使用解析器组合器解析简单的数学表达式

Question

我正在使用 parsimmon 解析一个简单的数学表达式，但我无法解析一个遵循操作顺序的简单数学表达式(即 */ 的优先级高于 +- )。

即使你不熟悉这个库，请帮我解决没有左递归和无限递归的优先级问题。

谢谢你。

我使用 typescript :

"use strict";

// Run me with Node to see my output!

import * as P from "parsimmon";
import {Parser} from "parsimmon";
// @ts-ignore
import util from "util";


///////////////////////////////////////////////////////////////////////

// Use the JSON standard's definition of whitespace rather than Parsimmon's.
let whitespace = P.regexp(/\s*/m);

// JSON is pretty relaxed about whitespace, so let's make it easy to ignore
// after most text.
function token(parser: Parser<string>) {
  return parser.skip(whitespace);
}

// Several parsers are just strings with optional whitespace.
function word(str: string) {
  return P.string(str).thru(token);
}

let MathParser = P.createLanguage({
  expr: r => P.alt(r.sExpr2, r.sExpr1, r.number),
  sExpr1: r => P.seqMap(r.iExpr, P.optWhitespace, r.plusOrMinus, P.optWhitespace, r.expr, (a, s1, b, s2, c) => [a, b, c]),
  sExpr2: r => P.seqMap(r.iExpr, P.optWhitespace, r.multiplyOrDivide, P.optWhitespace, r.expr, (a, s1, b, s2, c) => [a, b, c]),
  iExpr: r => P.alt(r.iExpr, r.number),    // Issue here! this causes infinite recursion
  // iExpr: r => r.number  // this will fix infinite recursion but yields invalid parse

  number: () =>
    token(P.regexp(/[0-9]+/))
      .map(Number)
      .desc("number"),

  plus: () => word("+"),
  minus: () => word("-"),
  plusOrMinus: r => P.alt(r.plus, r.minus),

  multiply: () => word("*"),
  divide: () => word("/"),
  multiplyOrDivide: r => P.alt(r.multiply, r.divide),

  operator: r => P.alt(r.plusOrMinus, r.multiplyOrDivide)
});

///////////////////////////////////////////////////////////////////////

let text = "3 / 4 - 5 * 6 + 5";

let ast = MathParser.expr.tryParse(text);
console.log(util.inspect(ast, {showHidden: false, depth: null}));

This is my repo

Answer 1

目前，您的解析器实现的语法如下所示(忽略空格):

expr: sExpr2 | sExpr1 | number
sExpr1: iExpr plusOrMinus expr
sExpr2: iExpr multiplyOrDivide expr
// Version with infinite recursion:
iExpr: iExpr | number
// Version without infinite recursion:
iExpr: number

很容易看出 iExpr: iExpr是左递归产生式，也是你无限递归的原因。但即使 Parsimmon 可以处理左递归，该生产也没有任何意义。如果它没有弄乱解析器，它就不会做任何事情。就像一个方程 x = x不传达任何信息，产生 x: x不会使语法匹配以前不匹配的任何内容。它基本上是一个空操作，但是它破坏了无法处理左递归的解析器。所以删除它绝对是正确的解决方案。

修复后，您现在会得到错误的解析树。具体来说，您将获得解析树，就好像所有运算符都具有相同的优先级和右关联性。为什么？因为所有运算符的左侧都是 iExpr那只能匹配单个数字。因此，您将始终将叶子作为运算符节点的左子节点，并且树始终向右生长。

正确解析左结合运算符的明确语法可以这样编写:

expr: expr (plusOrMinus multExpr)?
multExpr: multExpr (multiplyOrDivide primaryExpr)?
primaryExpr: number | '(' expr ')'

(当然， | '(' expr ')' 部分仅在您想允许括号时才需要)

这将导致正确的解析树，因为乘法或除法无法将无括号的加法或减法作为子代，并且如果有多个相同优先级的运算符应用，例如 1 - 2 - 3 ，外减法将包含内减法作为其左 child ，正确地将运算符视为左结合。

现在的问题是这个语法是递归的，所以它不适用于 Parsimmon。一个人的第一个想法可能是将左递归更改为右递归，如下所示:

expr: multExpr (plusOrMinus expr)?
multExpr: primaryExpr (multiplyOrDivide multExpr)?
primaryExpr: number | '(' expr ')'

但问题是现在 1 - 2 - 3错误地联想到右边而不是左边。相反，常见的解决方案是完全删除递归(当然，从 primaryExpr 返回到 expr 的递归除外)并用重复替换它:

expr: multExpr (plusOrMinus multExpr)*
multExpr: primaryExpr (multiplyOrDivide primaryExpr)*
primaryExpr: number | '(' expr ')'

在 Parsimmon 中，你可以使用 sepBy1 来实现。 .所以现在不是有一个左操作数、一个运算符和一个右操作数，而是有一个左操作数，然后在一个数组中任意多个运算符-操作数对。您可以通过简单地在 for 循环中遍历数组来创建一个左生长树。