如何在用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.StackOverflowError
        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

自顶向下的解析器不能处理左递归，如果没有左递归，就不能为左联想表达式文法编写BNF语法。那该怎么办呢？(除了切换到自下而上的解析方法之外。)

一个简单的可能性，如果解析框架支持它的话，就是使用类似的语法来使用类似的语法来解析一系列类似的操作符：

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

然后，您可以将任何您喜欢的结合性应用到由解析产生的列表中。

这是编写简单的调车场处理器(简单，因为它不需要处理括号)的更通用解决方案的退化情况。如果您希望能够在运行时定义新的运算符(具有优先级和相干性)，您可能需要此解决方案。

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