如何在清晰的语法中解决shift-reduce冲突

我正在尝试使用LALR（1）解析器生成器（Bison，但该问题不是特定于该工具）解析简单语法，而且正在打击转变 - 减少冲突。我发现有关解决这些文档和其他来源往往说一个或多个以下：如何在清晰的语法中解决shift-reduce冲突

如果语法是不明确的（如IF-THEN-ELSE歧义），改变语言来解决歧义。
如果是运算符优先级问题，请明确指定优先级。
接受默认分辨率，并告诉生成器不要抱怨它。

然而，所有的这些似乎适用于我的情况：语法是明确的，只要我可以告诉（当然这是不明确的，只有一个字先行的），它只有一个运营商，以及默认分辨率导致在正确形成的输入上解析错误。是否有任何技术可以重新定义语法以消除不属于上述桶的转换 - 减少冲突？

为了具体，这里所讨论的语法：

%token LETTER 

%% 
%start input; 
input:   /* empty */ | input input_elt; 
input_elt:  rule | statement; 
statement:  successor ';'; 
rule:   LETTER "->" successor ';'; 
successor:  /* empty */ | successor LETTER; 
%%

意图是解析形式的分号分隔的线 “[A-ZA-Z] +” 或“[A-ZA-Z ] - > [A-Za-z] +“。

来源

2009-06-06 Geoff Romer

Bah，我用编辑理论有些生疏...... 你知道你的语法里冲突在哪里吗？ – 2009-06-06 03:23:08

Bison表示“POSIX表示％开始规则必须出现在%%行之前”。 – 2009-06-06 04:41:56

使用的yacc的Solaris版本，我得到：

1: shift/reduce conflict (shift 5, red'n 7) on LETTER 
state 1 
    $accept : input_$end 
    input : input_input_elt 
    successor : _ (7) 

    $end accept 
    LETTER shift 5 
    . reduce 7 

    input_elt goto 2 
    rule goto 3 
    statement goto 4 
    successor goto 6

所以，麻烦的是，因为它往往是，空的规则 - 特别是空的继任者。目前尚不完全清楚您是否希望允许分号作为有效输入 - 目前情况如此。如果您将后续规则修改为：

successor: LETTER | successor LETTER;

消除了转换/减少冲突。

来源

2009-06-06 04:48:40

感谢您削减语法并发布它。将后续规则更改为 -

successor:  /* empty */ | LETTER successor;

...为我工作。 ITYM 语言看起来毫不含糊。

来源

2009-06-06 04:03:40

如何在清晰的语法中解决shift-reduce冲突

回答

相关问题