优先权问题

Question

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

我已经设法减少到 15 个 shift/reduce 个错误，但我不知道如何修复剩下的几个 - 它们可能与我的优先级问题有关。

我有这样定义的语法：

%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(  ); }
                ;

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

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

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

据我所知，问题可能是由隐含的 and（规则 3 和 4）引起的。如果这是问题的根源，我该如何解决？

谢谢！

Answer 1

在写这个问题的时候，我才意识到隐含的可能是问题的根源。现在，对可能出现的问题有了更深入的了解，我能够编写正确的 google 查询，将我引导至 this post.

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

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

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

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

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

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

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

这给了我 0 shift/reduce 个冲突和我目前在所有测试中期望的值。同样以这种方式安排我的语法使语言的更微妙的细微差别变得明显，例如以下陈述的有效性：

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

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

优先权问题

Trouble With Precedence

parsing

bison

bisonc++