转移减少冲突

Question

我在理解移位/缩小语法的问题时遇到了问题,我知道语法没有歧义.这个案例是if else类型之一,但它不是'悬空的'问题,因为我有强制的END子句来分隔代码块.

这是gppg的语法(它是一个像编译器编译器一样的Bison ......而且它不是一个echo):

%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解析器.

我会欣赏优雅的解决方案,我设法做到这一点,通过消除/*空*/规则和复制所有需要空列表的东西但是在更大的语法中我正在努力它最终就像'sparghetti语法综合症'.

以下是一些链接:

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

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

GPPG,我正在使用的解析器

野牛手册

Answer 1

您修订的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
    ;

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