java如何在使用PetitParser解析非对称二进制运算符时获得正确的关联性?
我试图用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()
,我可以选择二进制运算符的结合性
# 1 楼答案
自顶向下的解析器无法处理左递归,并且您无法为没有左递归的左关联表达式语法编写BNF语法。那怎么办呢?(除了切换到自下而上的解析方法。)
如果解析框架支持,一种简单的可能性是使用重复来解析类似运算符的序列,语法如下:
然后,您可以对解析生成的列表应用您喜欢的任何关联性
这是编写一个简单的调车场处理器的更一般的解决方案的退化情况(很简单,因为它不需要处理括号)。如果希望能够在运行时定义新运算符(具有优先级和关联性),则可能需要此解决方案
使用PetitPasser,最简单的解决方案可能是使用附带的ExpressionBuilder。见https://github.com/petitparser/java-petitparser/blob/master/petitparser-core/src/main/java/org/petitparser/tools/ExpressionBuilder.java