修复 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

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

通过将 IFF 的关联性从 nonassoc 更改为 left，可以轻松消除“State 40”冲突。有充分的理由不使其具有关联性吗？

Answer 2

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

我不确定你用什么样的约束来解析语法，但我很确定你想要一个简单的语法，编程语言（几乎）总是明确的。 （但是，如果约束来自某种自然语言源，那么您可能必须使用更合适的解析器）我不确定如果您给它一个不明确的语法，解析器柠檬会做什么，可能只是更喜欢其中一个转换在它的自动机中，这很可能会导致你不想要的树。