2

我正在编写一个使用 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

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

4

2 回答 2

1

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

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

于 2011-01-03T21:41:09.587 回答
0

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

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

于 2011-01-03T21:56:44.770 回答