parsing - 解决我的语法中的 shift-reduce 冲突的问题

Question

我正在尝试使用 Irony 编写一个小型解析器.不幸的是，我遇到了“移位减少冲突”。语法不是我的强项，我只需要完成这件小事。这是产生错误的简化语法:

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

“shift-reduce 冲突”是什么意思，我该如何解决？我认为这意味着我的语法含糊不清，但我无法充分扭曲我的逻辑以了解如何。

补充:澄清一下 - “asd”只是一个文字字符串“asd”。所以我希望以下表达式能被这个语法解析:

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

添加 2:忘了说了，语法的根是 LogicalExpression .

添加 3:啊，我明白了!歧义是因为像这样的表达式

asd AND asd OR asd

可以用两种不同的方式来解释:

(asd AND asd) OR asd
asd AND (asd OR asd)

但是我该如何解决这个问题？好的，我可以将 AND 或 OR 中的一个设置为比另一个更强(无论如何我已经打算这样做了)。但是现在我看到即使只有一个运算符(operator)也会出现错误。换句话说，这也会产生同样的错误:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

在这种情况下，我想要这个:

asd OR asd OR asd

被解析为:

(asd OR asd) OR asd

这样做的明确方法是什么？

添加 4:知道了!

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

这将解析所有 bool 表达式，运算符优先级为 NOT->AND->OR。 “asd”可以替换为用于您的术语的表达方式。

Answer 1

如果你只使用一个前瞻，你的语法是模棱两可的。为了说明，什么是“asd”？它是一个 ExpressionTerm 还是一个更长的术语。这就是移减冲突。我怀疑这里也有减少 - 减少冲突。

大多数 LL(1)/LALR(1) 生成器将通过优先运算符提供一些方法来处理移归冲突。大多数情况下也会在存在移位减少冲突时默认为最长序列，因此通常可以忽略这些(经过一些审查)。 (在这种情况下，您可能需要将单个项移到底部才能使其正确运行)。