6

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

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

“班次减少冲突”是什么意思，我该如何解决？我认为这意味着我的语法模棱两可，但我无法充分扭曲我的逻辑以了解如何。

补充：澄清 - “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 中的一个设置为比另一个更强大（无论如何我都想这样做）。但是现在我看到即使只有一个操作员也会出现错误。换句话说，这也会产生同样的错误：

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 ")"

这会解析所有布尔表达式，运算符优先级为 NOT->AND->OR。“asd”可以替换为您的条款的表达方式。

4

4 回答 4

3

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

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

于 2009-05-26T12:41:07.613 回答
1

Shift-Reduce 冲突意味着您的语法不明确。使用您的递归规则，标记“asd”可以被解释为ExpressionTermorLogicalExpression的一部分，并且解析器无法决定哪个。需要一个额外的规则来打破平局。

于 2009-05-26T12:45:25.450 回答
0

当涉及到解析器时，减少冲突是让你的大脑更难处理的事情之一。说明冲突的最简单方法是在这个伪代码中：

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

else 语句可以绑定到第一个或第二个 if。在模棱两可的语法的情况下，您通常定义一个值来指示语法中预期的移位减少警告的数量。

或者，您可以使用 LL(k) 或 LL(*) 解析器。这些类型的解析器没有移位/减少歧义。根据您的应用程序，它们可能比 LALR(1) 解析器更容易或更难。

于 2009-06-04T01:16:17.240 回答
0

语法模棱两可，LL(1)或者LALR(1)因为 asd 标记可以被替换，ExpressionTerm并且还可以LogicalExpression展平语法规则以解决移位/减少冲突

于 2013-09-08T13:22:16.040 回答