10

我在理解我知道没有歧义的语法的移位/减少冲突时遇到问题。该案例是 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 解析器。

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

以下是一些链接：

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

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

GPPG，我正在使用的解析器

野牛手册

4

6 回答 6

6

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

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

elsebody : else
         | elseifs else
         ;

和

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

不需要“无”；它由没有“elseifs”的“elsebody”隐含地照顾。

我非常倾向于使用规则“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
    ;

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

于 2008-10-12T23:39:21.253 回答
2

我认为问题出在 elseifs 子句中。

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

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

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

如果你改变 elseifs 会发生什么？：

elseifs : '#' ELSEIF statements else
        ;
于 2008-10-12T22:10:20.403 回答
1

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

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

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

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

于 2008-10-13T00:40:04.190 回答
0

我仍在切换事情，我最初的问题有一些错误，因为elseifs序列最后有一个else allways 是错误的。这是对这个问题的另一种看法，这次我遇到了两个班次/减少冲突：

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 子句上使用左递归的解决方案。

于 2008-10-12T22:42:20.730 回答
0 
elsebody : elseifs else
         | elseifs
         ;

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

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

我认为这应该离开递归并始终终止。

于 2008-10-12T23:43:57.813 回答
0

好的 - 这是 if 块的语法（不是最小的）。我从我拥有的一些代码中挖掘出来（称为 adhoc，基于 Kernighan & Plauger 的“The UNIX Programming Environment”中的 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 年）。

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

于 2008-10-13T04:10:25.183 回答