修复Lemon解析冲突

Question

我正在编写一个使用Flex和Lemon解析约束的小解析器。Lemon报告了几个我无法摆脱的解析冲突。在上下文无关的语法中，有什么特殊的技巧可以消除解析冲突吗？

语法如下所示。

// Reprint of input file "Constraint_grammar.y".
// Symbols:
//   0 $          5 NE        10 PLUS        15 NOT         20 error
//   1 IFF        6 GT        11 MINUS       16 LPAREN      21 constraint
//   2 AND        7 GTE       12 TIMES       17 RPAREN      22 bool_expr 
//   3 OR         8 LT        13 DIVIDE      18 VARIABLE    23 int_expr
//   4 EQ         9 LTE       14 POWER       19 INTEGER   
constraint ::= bool_expr.
bool_expr ::= LPAREN bool_expr RPAREN.
int_expr ::= LPAREN int_expr RPAREN.
bool_expr ::= int_expr LT int_expr.
bool_expr ::= int_expr GT int_expr.
bool_expr ::= int_expr EQ int_expr.
bool_expr ::= int_expr NE int_expr.
bool_expr ::= int_expr GTE int_expr.
bool_expr ::= int_expr LTE int_expr.
bool_expr ::= bool_expr AND bool_expr.
bool_expr ::= bool_expr OR bool_expr.
bool_expr ::= bool_expr IFF bool_expr.
int_expr ::= int_expr PLUS int_expr.
int_expr ::= int_expr MINUS int_expr.
int_expr ::= int_expr TIMES int_expr.
int_expr ::= int_expr DIVIDE int_expr.
int_expr ::= int_expr POWER int_expr.
bool_expr ::= NOT bool_expr.
int_expr ::= MINUS int_expr.
int_expr ::= VARIABLE.
bool_expr ::= VARIABLE.
int_expr ::= INTEGER.

%nonassoc IFF.
%left AND.
%left OR.
%nonassoc EQ NE GT GTE LT LTE.
%left PLUS MINUS.
%left TIMES DIVIDE.
%right POWER NOT.
%nonassoc LPAREN RPAREN.

错误如下所示。

State 28:
     (19) int_expr ::= VARIABLE *
     (20) bool_expr ::= VARIABLE *

                             $ reduce 20
                           IFF reduce 20
                           AND reduce 20
                            OR reduce 20
                            EQ reduce 19
                            NE reduce 19
                            GT reduce 19
                           GTE reduce 19
                            LT reduce 19
                           LTE reduce 19
                          PLUS reduce 19
                         MINUS reduce 19
                         TIMES reduce 19
                        DIVIDE reduce 19
                         POWER reduce 19
                        RPAREN reduce 19
                        RPAREN reduce 20  ** Parsing conflict **

State 40:
          bool_expr ::= bool_expr * AND bool_expr
          bool_expr ::= bool_expr * OR bool_expr
          bool_expr ::= bool_expr * IFF bool_expr
     (11) bool_expr ::= bool_expr IFF bool_expr *

                             $ reduce 11
                           IFF shift  4
                           IFF reduce 11  ** Parsing conflict **
                           AND shift  1
                            OR shift  3
                        RPAREN reduce 11

整个解析器生成器报告都在这里。http://pastebin.com/TRsV3WvK

有人知道我哪里做错了吗？我可以忽略这些冲突吗？

Answer 1

我希望通过区分布尔变量和整数变量来修复'State 28‘冲突，使用符号表来帮助确定返回哪种类型的令牌。也许你会有BOOL_VARIABLE和INT_VARIABLE。测试表明，此更改消除了“状态28”冲突。

通过将IFF的关联性从nonassoc更改为left，可以很容易地消除“状态40”冲突。有没有充分的理由不让它具有关联性？

Answer 2

你有解析器冲突，这意味着你指定的语法不是明确的，即对于某些给定的终端符号输入，存在不止一个解析树。这是很常见的，但是如果我们想要一个明确的语法，我们需要指定消除歧义的规则，比如关联性和优先级，这样我们总是可以只选择一个解析树。

我不确定你是用哪种约束来解析语法的，但我很确定你想要一个模糊的语法，编程语言(几乎)总是明确的。(但是，如果约束来自某种自然语言源，那么您可能必须使用更合适的解析器)我不确定解析器lemon会做什么，如果您给它一个模棱两可的语法，可能只是更喜欢它自动机中的一个转换，这很可能导致您不想要的树。