0

我正在尝试为相对简单的语法生成解析器，但我无法让我的优先级正常工作。

我已经设法减少了 15 个移位/减少错误，但我不知道如何解决剩下的几个错误——它们可能与我的优先级问题有关。

我有一个这样定义的语法：

%nonassoc T_LEN T_OPENPAREN T_CLOSEPAREN T_NUM T_ID T_QUOTE T_TRUE T_FALSE
%left T_GT T_GTE T_LT T_LTE T_EQ
%left T_OR
%left T_AND
%left T_NOT

Start           : Expression                                    { astRoot = new MainNode( $1 ); }
                ;

Expression      : Expression T_OR Expression                    { $$ = new OrNode( $1, $3 ); }
                | Expression T_AND Expression                   { $$ = new AndNode( $1, $3 ); }
                | Expression Expression                         { $$ = new AndNode( $1, $2 ); }
                | T_NOT Expression                              { $$ = new NotNode( $2 ); }
                | T_GT Expression                               { $$ = new GreaterNode( $2 ); }
                | T_GTE Expression                              { $$ = new GreaterEqualNode( $2 ); }
                | T_LT Expression                               { $$ = new LessNode( $2 ); }
                | T_LTE Expression                              { $$ = new LessEqualNode( $2 ); }
                | T_EQ Expression                               { $$ = new EqualNode( $2 ); }
                | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN          { $$ = new LenNode( new IntegerNode( $3 ) ); }
                | T_OPENPAREN Expression T_CLOSEPAREN           { $$ = $2; }
                | T_TRUE                                        { $$ = new BoolTrueNode; }
                | T_FALSE                                       { $$ = new BoolFalseNode; }
                | T_ID                                          { $$ = new IdentifierNode( $1 ); }
                | T_NUM                                         { $$ = new IntegerNode( $1 ); }
                | T_QUOTE                                       { $$ = new QuoteNode( new IdentifierNode( $1 ) ); }
                ;

尝试解析以下内容时，我没有得到我想要的值：

100 T_AND 200 T_AND 300 T_AND 400 T_OR 1000
output => And( "100", And( "200", And( "300", Or( "400", "1000" ) ) ) );
expect => Or( And( "100", And( "200", And( "300", "400" ) ) ), "1000" );

最后，我的解析器输出的相关部分是：

State 27 conflicts: 15 shift/reduce

0 $accept: Start $end

1 Start:       Expression

2 Expression:  Expression T_OR Expression
3            | Expression T_AND Expression
4            | Expression Expression
5            | T_NOT Expression
6            | T_GT Expression
7            | T_GTE Expression
8            | T_LT Expression
9            | T_LTE Expression
10           | T_EQ Expression
11           | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN
12           | T_OPENPAREN Expression T_CLOSEPAREN
13           | T_TRUE
14           | T_FALSE
15           | T_ID
16           | T_NUM
17           | T_QUOTE

State 27

    2 Expression: Expression . T_OR Expression
    3           | Expression . T_AND Expression
    4           | Expression . Expression
    4           | Expression Expression .

    T_LEN        shift, and go to state 1
    T_OPENPAREN  shift, and go to state 2
    T_NUM        shift, and go to state 3
    T_ID         shift, and go to state 4
    T_QUOTE      shift, and go to state 5
    T_TRUE       shift, and go to state 6
    T_FALSE      shift, and go to state 7
    T_GT         shift, and go to state 8
    T_GTE        shift, and go to state 9
    T_LT         shift, and go to state 10
    T_LTE        shift, and go to state 11
    T_EQ         shift, and go to state 12
    T_OR         shift, and go to state 25
    T_AND        shift, and go to state 26
    T_NOT        shift, and go to state 13

    T_LEN        [reduce using rule 4 (Expression)]
    T_OPENPAREN  [reduce using rule 4 (Expression)]
    T_NUM        [reduce using rule 4 (Expression)]
    T_ID         [reduce using rule 4 (Expression)]
    T_QUOTE      [reduce using rule 4 (Expression)]
    T_TRUE       [reduce using rule 4 (Expression)]
    T_FALSE      [reduce using rule 4 (Expression)]
    T_GT         [reduce using rule 4 (Expression)]
    T_GTE        [reduce using rule 4 (Expression)]
    T_LT         [reduce using rule 4 (Expression)]
    T_LTE        [reduce using rule 4 (Expression)]
    T_EQ         [reduce using rule 4 (Expression)]
    T_OR         [reduce using rule 4 (Expression)]
    T_AND        [reduce using rule 4 (Expression)]
    T_NOT        [reduce using rule 4 (Expression)]
    $default     reduce using rule 4 (Expression)

    Expression  go to state 27

我能理解的最好的是，这个问题可能是由隐含的和（规则 3 和 4）引起的。如果这是问题的根源，我该如何解决？

谢谢！

4

1 回答 1

0

在写这个问题时，我只是意识到隐含的可能是问题的根源。现在，对可能出现的问题有了更深入的了解，我能够编写正确的谷歌查询，引导我找到这篇文章。

阅读答案后，解决方案就到位了。我选择了通过语法的显式优先级，而不是通过 bison 的优先级声明的隐式优先级。这给了我以下语法：

Start           : Expression                                    { astRoot = new MainNode( $1 ); }
                ;

Term            : T_TRUE                                        { $$ = new BoolTrueNode; }
                | T_FALSE                                       { $$ = new BoolFalseNode; }
                | T_ID                                          { $$ = new IdentifierNode( $1 ); }
                | T_NUM                                         { $$ = new IntegerNode( $1 ); }
                | T_QUOTE                                       { $$ = new QuoteNode( new IdentifierNode( $1 ) ); }
                | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN          { $$ = new LenNode( new IntegerNode( $3 ) ); }
                | T_OPENPAREN Expression T_CLOSEPAREN           { $$ = $2; }
                ;

Prefix          : Term
                | T_NOT Prefix                                  { $$ = new NotNode( $2 ); }
                | T_GT Term                                     { $$ = new GreaterNode( $2 ); }
                | T_GTE Term                                    { $$ = new GreaterEqualNode( $2 ); }
                | T_LT Term                                     { $$ = new LessNode( $2 ); }
                | T_LTE Term                                    { $$ = new LessEqualNode( $2 ); }
                | T_EQ Term                                     { $$ = new EqualNode( $2 ); }
                ;

Factor          : Prefix
                | Prefix Factor                                 { $$ = new AndNode( $1, $2 ); }
                ;

Andor           : Factor
                | Andor T_AND Factor                            { $$ = new AndNode( $1, $3 ); }
                ;

Expression      : Andor
                | Expression T_OR Andor                         { $$ = new OrNode( $1, $3 ); }
                ;

这给了我 0 个移位/减少冲突以及我在迄今为止所有测试中所期望的值。同样以这种方式安排我的语法使语言的更微妙的细微差别变得明显，例如以下陈述的有效性：

T_NOT T_GT 100 => Not( Greater( "100" ) ) => valid
T_GT T_NOT 100 => Greater( Not( "100" ) ) => invalid

除非有人看到我提出的语法有任何隐藏的问题，否则我相信这已经完全解决了我的问题。

于 2017-11-01T10:39:30.437 回答