移位减少冲突

Question

我在理解一个我知道没有歧义的语法的移位/归约混淆时遇到了问题。case是if else类型之一，但它不是'dangling else‘问题，因为我有强制的END子句来分隔代码块。

下面是gppg的语法(它是一个类似Bison的编译器……这不是回声)：

%output=program.cs

%start program

%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%

program : statements
        ;

statements : /*empty */
           | statements stmt
           ;

stmt : flow
     | THINGS
     ;

flow : '#' IF '(' ')' statements else
     ;

else : '#' END
     | '#' ELSE statements '#' END
     | elseifs
     ;

elseifs : elseifs '#' ELSEIF statements else
        | '#' ELSEIF statements else
        ;

下面是冲突输出：

// Parser Conflict Information for grammar file "program.y"

Shift/Reduce conflict on symbol "'#'", parser will shift
 Reduce 10: else -> elseifs
 Shift "'#'":   State-22 -> State-23
  Items for From-state State 22
    10 else: elseifs .
    -lookahead: '#', THINGS, EOF
    11 elseifs: elseifs . '#' ELSEIF statements else 
  Items for Next-state State 23
    11 elseifs: elseifs '#' . ELSEIF statements else 

// End conflict information for parser

我已经改变了一切，我确实知道如何解决它，但这个解决方案涉及到放弃'elseif‘上的左递归，而是右递归。

我已经浏览了我在互联网上找到的关于这个问题的所有scarse文档(我在最后发布了一些链接)，仍然没有找到一个优雅的解决方案。我知道ANTLR，但我现在不想考虑它。请将您的解决方案限制为Yacc/Bison解析器。

我很欣赏优雅的解决方案，我设法去掉了/*的空*/规则，并复制了所有需要空列表的东西，但在更大的语法中，我正在研究它，结果就像“sparghetti语法综合症”。

以下是一些链接：

http://nitsan.org/~maratb/cs164/bison.html

http://compilers.iecc.com/comparch/article/98-01-079

GPPG, the parser I'm using

Bison manual

Answer 1

修改后的ELSEIF规则没有用于条件的标记--它名义上应该添加'(‘和')’。

更严重的是，您现在有了一条规则

elsebody : else
         | elseifs else
         ;

和

elseifs : /* Nothing */
        | elseifs ...something... 
        ;

“什么都不需要”是不需要的；它是由没有“elseifs”的“elsebody”隐式处理的。

我非常倾向于使用规则‘opt_else I’，'opt_else‘和'end'：

flow : '#' IF '(' ')' statements opt_elseifs opt_else end
     ;

opt_elseifs : /* Nothing */
            | opt_elseifs '#' ELSIF '(' ')' statements 
            ;

opt_else : /* Nothing */
         | '#' ELSE statements
         ;

end : '#' END
    ;

我没有通过解析器生成器运行这段代码，但我发现这相对容易理解。

Answer 2

我认为问题出在elseifs条款中。

elseifs : elseifs '#' ELSEIF statements else
        | '#' ELSEIF statements else
        ;

我认为第一个版本不是必需的，因为else子句无论如何都会引用回else I：

else : '#' END
     | '#' ELSE statements '#' END
     | elseifs
     ;

如果您更改了elseifs if，会发生什么？

elseifs : '#' ELSEIF statements else
        ;

Answer 3

上面来自Jonathan的答案似乎是最好的，但因为它对你不起作用，所以我有一些建议，你可以尝试一下，这将有助于你调试错误。

首先，您是否考虑过将hash/sharp符号作为标记本身的一部分(即#END、#IF等)？这样它们就会被lexer取出，这意味着它们不需要包含在解析器中。

其次，我强烈建议您在不复制任何令牌流的情况下重写规则。(“不要重复自己”原则的一部分。)因此，规则“'#‘ELSEIF statements else”应该只存在于该文件中的一个位置(而不是上面的两个位置)。

最后，我建议您研究IF/ELSEIF/ELSE标记的优先级和关联性。我知道您应该能够编写一个不需要这个的解析器，但在这种情况下，它可能是您需要的东西。