使用 PetitParser 解析非对称二元运算符时如何获得正确的关联性？

Question

我正在尝试使用 PetitParser 制作一个基本的数学解析器，但我无法使用非对称二元运算符（如减法或除法）获得正确的顺序。

我有这个小例子，它只能解析（非负）整数和 - 二元运算符，并发出一个带有括号的相同解析表达式的字符串（以便我可以看到关联性） :

import java.util.List;

import org.petitparser.parser.Parser;
import org.petitparser.parser.combinators.SettableParser;

import static org.petitparser.parser.primitive.CharacterParser.*;

public class App {
    public static void main(String[] args) {
        Parser number = digit().plus().flatten().trim();

        SettableParser term = SettableParser.undefined();
        term.set(number.seq(of('-').flatten().trim()).seq(term).map((List<String> values) -> {
            return String.format("(%s - %s)", values.get(0), values.get(2));
        }).or(number));

        Parser expression = term.end();

        System.out.println(expression.parse("1 - 2 - 3").<String>get());
    }
}

这会打印 (1 - (2 - 3)) - 尽管 1 - 2 - 3 的正确关联性是 ((1 - 2) - 3).

现在，我明白我的语法是这样的：

number: [0-9]+
term: number '-' term
expression: number $

所以 ((1 - 2) - 3) 是 term '-' number。但是当我尝试切换它们时：

        term.set(term.seq(of('-').flatten().trim()).seq(number).map((List<String> values) -> {
            return String.format("(%s - %s)", values.get(0), values.get(2));
        }).or(number));

我运行陷入无限递归：

:runException in thread "main" java.lang.WhosebugError
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:22)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        at org.petitparser.parser.combinators.ChoiceParser.parseOn(ChoiceParser.java:22)
        at org.petitparser.parser.combinators.DelegateParser.parseOn(DelegateParser.java:24)
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:25)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        at org.petitparser.parser.combinators.ChoiceParser.parseOn(ChoiceParser.java:22)
        at org.petitparser.parser.combinators.DelegateParser.parseOn(DelegateParser.java:24)
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:25)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        at org.petitparser.parser.combinators.ChoiceParser.parseOn(ChoiceParser.java:22)
        at org.petitparser.parser.combinators.DelegateParser.parseOn(DelegateParser.java:24)
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:25)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        at org.petitparser.parser.combinators.ChoiceParser.parseOn(ChoiceParser.java:22)
        at org.petitparser.parser.combinators.DelegateParser.parseOn(DelegateParser.java:24)
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:25)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        at org.petitparser.parser.combinators.ChoiceParser.parseOn(ChoiceParser.java:22)
        at org.petitparser.parser.combinators.DelegateParser.parseOn(DelegateParser.java:24)
        at org.petitparser.parser.combinators.SequenceParser.parseOn(SequenceParser.java:25)
        at org.petitparser.parser.actions.ActionParser.parseOn(ActionParser.java:29)
        ........

那么...我怎样才能按照应该解析的方式解析表达式？

更新

根据@rici 的建议，我将其更改为使用 ExpressionBuilder:

import java.util.List;

import org.petitparser.parser.Parser;
import org.petitparser.parser.combinators.SettableParser;
import org.petitparser.tools.ExpressionBuilder;

import static org.petitparser.parser.primitive.CharacterParser.*;

public class App {
    public static void main(String[] args) {
        Parser number = digit().plus().flatten().trim();

        SettableParser term = SettableParser.undefined();

        ExpressionBuilder builder = new ExpressionBuilder();
        builder.group().primitive(number);
        builder.group().left(of('-').trim(), (List<String> values) -> {
            return String.format("(%s - %s)", values.get(0), values.get(2));
        });

        term.set(builder.build());
        Parser expression = term.end();
        System.out.println(expression.parse("1 - 2 - 3"));
    }
}

通过使用left()或right()我可以选择二元运算符的结合性。

Answer 1

Top-down 解析器无法处理 left-recursion，并且在没有 left-recursion 的情况下，您无法为 left-associative 表达式文法编写 BNF 文法。那么该怎么办？（除了切换到 bottom-up 解析方法。）

如果解析框架支持，一个简单的可能性是使用重复来解析一系列相似的运算符，使用的语法类似于：

term: factor ( ('-' | '+') factor)*
factor: number ( ( '*' | '/') number)*

然后您可以将您喜欢的任何关联性应用于解析生成的列表。

这是编写简单 shunting-yard 处理器的更通用解决方案的退化情况（简单是因为它不需要处理括号）。如果您希望能够在 run-time.

处定义新的运算符（具有优先级和结合性），您可能需要此解决方案

对于 PetitParser，最简单的解决方案可能是使用包含的 ExpressionBuilder。参见 https://github.com/petitparser/java-petitparser/blob/master/petitparser-core/src/main/java/org/petitparser/tools/ExpressionBuilder.java

使用 PetitParser 解析非对称二元运算符时如何获得正确的关联性？

How to get the associativity correct when parsing non-symmetric binary operators with PetitParser?

java

grammar

petitparser

更新