转变减少冲突

Question

我在理解我知道没有歧义的语法的移位/归约冲突时遇到了问题。 这种情况是 if else 类型之一，但它不是“悬空 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”上以实现右递归。

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

我很欣赏优雅的解决方案，我设法通过消除 /* 空 */ 规则并复制需要空列表的所有内容来做到这一点，但在我正在研究的更大语法中，它最终就像“意大利面条语法综合症”。

以下是一些链接：

http://nitsan.org/~maratb/cs164/bison.html< /a>

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

GPPG，我正在使用的解析器

Bison 手册

Answer 1

您修改后的 ELSEIF 规则没有条件标记——名义上应该添加“(”和“)”。

更严重的是，你现在有一个规则，

elsebody : else
         | elseifs else
         ;

并且

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

不需要“什么”； 它由“elsebody”隐式处理，而无需“elseifs”。

我非常倾向于使用规则“opt_elseifs”、“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 子句无论如何都会引用 elseifs：

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

如果更改 elseifs 会发生什么？：

elseifs : '#' ELSEIF statements else
        ;

Answer 3

上面乔纳森的答案似乎是最好的，但由于它不适合你，我有一些建议你可以尝试，这将帮助你调试错误。

首先，您是否考虑过将哈希/锐利符号作为标记本身的一部分（即#END、#IF 等）？ 这样它们就会被词法分析器取出，这意味着它们不必包含在解析器中。

其次，我敦促您重写规则而不重复任何令牌流。 （“不要重复自己”原则的一部分。）因此，规则“'#'ELSEIF statements else”应该只存在于该文件中的一个位置（而不是像上面那样存在两个位置）。

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

Answer 4

我仍在切换事物，我原来的问题有一些错误，因为 elseifs 序列末尾总是有一个 else ，这是错误的。 这是对这个问题的另一种看法，这次我得到了两个转变/归约冲突：

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

elsebody : else 
         | elseifs else
         ;

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

elseifs : /* empty */
        | elseifs '#' ELSEIF statements
        ;

现在的冲突是：

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

Shift/Reduce conflict on symbol "'#'", parser will shift
 Reduce 12: elseifs -> /* empty */
 Shift "'#'":   State-10 -> State-13
  Items for From-state State 10
    7 flow: '#' IF '(' ')' statements . elsebody 
    4 statements: statements . stmt 
  Items for Next-state State 13
    10 else: '#' . ELSE statements '#' END 
    11 else: '#' . END 
    7 flow: '#' . IF '(' ')' statements elsebody 

Shift/Reduce conflict on symbol "'#'", parser will shift
 Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
 Shift "'#'":   State-24 -> State-6
  Items for From-state State 24
    13 elseifs: elseifs '#' ELSEIF statements .
    -lookahead: '#'
    4 statements: statements . stmt 
  Items for Next-state State 6
    7 flow: '#' . IF '(' ')' statements elsebody 

// End conflict information for parser

空规则只会加剧我担心的 gppg。 但它们使用起来似乎很自然，我一直在尝试它们。

我已经知道正确的递归可以解决问题，正如 1800 INFORMATION 所说。 但我正在寻找在 elseifs 子句上使用左递归的解决方案。

Answer 5

elsebody : elseifs else
         | elseifs
         ;

elseifs : /* empty */
        | elseifs '#' ELSEIF statements
        ;

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

我认为这应该留下递归并始终终止。

Answer 6

好的 - 这是 if 块的语法（不是最小的）。 我从我拥有的一些代码中挖掘出它（称为 adhoc，基于 Kernighan 和 Plauger 的“UNIX 编程环境”中的 hoc）。 这个大纲语法用 Yacc 编译没有冲突。

%token  NUMBER IF ELSE
%token  ELIF END
%token  THEN
%start program

%%

program
    :   stmtlist
    ;

stmtlist
    :   /* Nothing */
    |   stmtlist stmt
    ;

stmt
    :   ifstmt
    ;

ifstmt
    :   ifcond endif
    |   ifcond else begin
    |   ifcond eliflist begin
    ;

ifcond
    :   ifstart cond then stmtlist
    ;

ifstart
    :   IF
    ;

cond
    :   '(' expr ')'
    ;

then
    :   /* Nothing */
    |   THEN
    ;

endif
    :   END IF begin
    ;

else
    :   ELSE stmtlist END IF
    ;

eliflist
    :   elifblock
    |   elifcond eliflist begin         /* RIGHT RECURSION */
    ;

elifblock
    :   elifcond else begin
    |   elifcond endif
    ;

elifcond
    :   elif cond then stmtlist end
    ;

elif
    :   ELIF
    ;

begin
    :   /* Nothing */
    ;

end
    :   /* Nothing */
    ;

expr
    :   NUMBER
    ;

%%

我使用“NUMBER”作为虚拟元素，而不是 THINGS，并且使用 ELIF 而不是 ELSEIF。 它包括一个 THEN，但这是可选的。 “开始”和“结束”操作用于获取生成程序中的程序计数器 - 因此应该可以从中删除而不影响它。

我认为我需要使用右递归而不是正常的左递归是有原因的 - 但我认为这与我正在使用的代码生成策略有关，而不是其他任何东西。 评论中的问号是原文的； 我记得我对此并不高兴。 该计划作为一个整体确实有效 - 这是一个在过去十年左右的时间里一直处于次要地位的项目（嗯......我在 2004 年底和 2005 年初做了一些工作；在此之前，是 1992 年和 1993）。

我没有花时间弄清楚为什么它可以无冲突编译，而我之前概述的却不能。 我希望它有帮助。