转换减少冲突

我在理解转换/减少关于语法的转换/减少的问题时遇到了问题，我知道它没有含糊之处。这种情况是if类型之一，但它不是'悬而未决'的问题，因为我有强制性的END子句分隔代码块。转换减少冲突

这里是GPPG语法（它是一种野牛一样编译器编译...这不是一个回声）：

%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

来源

2008-10-12 Caerbanog

您的修订ELSEIF规则没有标记符的条件 - 它应该名义上加'（'和'）'。

更严重的是，你现在有

elsebody : else 
     | elseifs else 
     ;

和

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

的 '无'，不需要的规则;它被隐含地由没有'别名'的'别人'照顾。

我会非常倾向于使用规则“opt_elseifs”，“opt_else”和“结束”：

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

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

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

end : '#' END 
    ;

我不通过解析器生成器上运行这一点，但我觉得这是比较容易理解。

来源

2008-10-12 23:39:21

是的。我也期待它的工作，你说的最容易理解是对的。但是我确实在解析器上运行了它，并且不幸地给出了4个转换/减少冲突。通过gppg运行并亲自查看。我不明白（得到我的'龙'编译器手册回） – Caerbanog 2008-10-12 23:58:19

我认为这个问题是elseifs子句。

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

我觉得不需要的第一个版本，因为else子句指回elseifs反正：

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

如果你改变elseifs？：

elseifs : '#' ELSEIF statements else 
     ;

来源

2008-10-12 22:10:20

你说得对。排队解决冲突。我将原来的语法简化为这个小问题，试图找出问题并最终引入错误。我想我必须重做我原来更复杂的语法，并将其用于解决此问题。 – Caerbanog 2008-10-12 22:17:23

Darn：刚注意到它为什么起作用。它再次是正确的递归。我之后的解决方案应该在elseifs上留下递归，因为它们可能是一个很长的流。 – Caerbanog 2008-10-12 22:20:20

我会发生什么还在原地开关的事情角落找寻，和我原来的问题了，因为elseifs一些错误序列有一个其他 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我是affraid。但他们似乎很自然地使用我一直在尝试他们。

我已经知道权利递归解决问题，因为1800信息说过。但是我正在寻找与的解决方案在elseifs条款左递归。

来源

2008-10-12 22:42:20 Caerbanog

elsebody : elseifs else 
     | elseifs 
     ; 

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

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

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

来源

2008-10-12 23:43:57

上面Jonathan的答案似乎是最好的，但由于它不适合你，我有几个建议你可以尝试一下，这将有助于你调试错误。

首先，你有没有考虑过使用散列/尖角符号作为令牌本身的一部分（即#END，#IF等）？这样他们就可以被词法分析器取出，这意味着它们不必被包含在解析器中。

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

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

来源

2008-10-13 00:40:04 Daemin

好的 - 这里是if语句的语法（不是最小的）。我将它从我有的一些代码中挖出来（称为adhoc，基于Kernighan & Plauger的“UNIX编程环境”）。这个大纲语法与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”作为虚设元件，而不是东西，我使用ELIF代替ELSEIF。它包含THEN，但这是可选的。 '开始'和'结束'操作用于获取生成程序中的程序计数器 - 因此应该可以从中删除而不影响它。

有一个原因，我认为我需要使用正确的递归，而不是正常的左递归 - 但我认为这是与我使用的代码生成策略，而不是其他任何事情。评论中的问号在原文中;我记得对此并不满意。整个计划确实奏效 - 这个项目在过去十年左右一直处于支撑之下（嗯......我在2004年底和2005年初做了一些工作;在此之前，它是在1992年和1993年）。

我没有花时间了解为什么这个编译无冲突，我之前概述的没有。我希望它有帮助。

来源

2008-10-13 04:10:25

转换减少冲突

回答

相关问题