Bison reduce/reduce if else 条件冲突

Question

我原以为 if else 会出现 shift/reduce 冲突，但它在“| IF '(' boolean_statement ')' 块”行上出现了 reduce/reduce 冲突。

以下信息可能有助于解释以下代码：

BOOL 是每行开头使用的关键字标记，表示该行是布尔运算
BOOLEAN 是 "true" 或 "false" 值

我正在使用这个编译器将一种语言转换为 C 代码，该语言可以包含像 a,b,c=d+2 这样的语句，相当于 C 中的 a=b=c=d+2；和 bool e = f * .N. g + h，相当于 e = f && !g || h.

statements:
        statements statement
        | statement
        ;

statement:
        if_statement
        | BOOL variable_list '=' boolean_statement
        | variable_list '=' integer_statement
        ;

if_statement:
        IF '(' boolean_statement ')' block ELSE block
        | IF '(' boolean_statement ')' block
        ;

variable_list:
        variable_list ',' variable
        | variable
        ;

variable:
        STRING 
        | STRING '[' INTEGER ']'
        | STRING '[' STRING ']'
        ;

boolean_statement:
        '(' boolean_statement ')'
        | bval '*' boolean_statement
        | bval '+' boolean_statement
        | bval EQ boolean_statement
        | bval NEQ boolean_statement
        | NOT boolean_statement
        | bval
        ;

bval:
        BOOLEAN   
        | variable
        ;

integer_statement:
        '(' integer_statement ')'
        | value '+' integer_statement
        | value '*' integer_statement
        | value
        ;

value:
        INTEGER        
        | variable
        ;

block:
        statement
        | '{' statements '}'
        ;

这是完整的代码

   %{

    #include <cstdio>
    #include <iostream>
    using namespace std;

    //stuff from flex that bison needs to know about:
    extern "C" int yylex();
    extern "C" int yyparse();
    extern "C" FILE *yyin;
    extern int line_num;

    void yyerror(const char *s);

    %}

    //C union holding each of the types of tokens that Flex could return
    %union { 
            int ival;
            bool bval;
            char const *sval;
    }

    //symbol defination
    %token <sval> STRING;
    %token <sval> NOT
    %token CONSTANT_SECTION
    %token BOOLEAN_SECTION
    %token INTEGER_SECTION
    %token LOGIC_SECTION
    %token TIMER_SECTION
    %token <sval> BOOLEAN
    %token <ival> INTEGER
    %token <ival> HEX 
    %token ENDL 
    %token BOOL
    %token IF
    %token ELSE
    %token EQ NEQ
    %token AND
    %token OR
    %token SUBROUTINE_END
    %token SUBROUTINE_START
    %token DELAY SECONDS HOURS MINUTES MSEC
    %token GOTO
    %token LABEL
    %token CALL
    //end of declaration section
    %%

    logic:
            costants_declarations boolean_declarations integer_declarations timer_declarations logic_statements
            | boolean_declarations integer_declarations timer_declarations logic_statements
            | logic_statements
            ;

    costants_declarations:
            CONSTANT_SECTION constants  
            ;

    constants:
            constants STRING '=' INTEGER    { cout << "const int " <<  << " = "  <<  << ";" << endl; }
            | constants STRING '=' HEX      { cout << "const int " <<  << " = "  <<  << ";" << endl; }
            | STRING '=' INTEGER            { cout << "const int " <<  << " = "  <<  << ";" << endl; }
            | STRING '=' HEX                { cout << "const int " <<  << " = "  <<  << ";" << endl; }
            ;

    boolean_declarations:
            BOOLEAN_SECTION booleans       
            ;

    booleans:
            booleans ',' boolean             
            | booleans boolean               
            | boolean                       
            ;        

    boolean:
            STRING '[' INTEGER ']'          { cout << "bool " <<  << "[" <<  << "]" << ";" << endl; }
            | STRING '[' STRING ']'         { cout << "bool " <<  << "[" <<  << "]" << ";" << endl; }
            | STRING                        { cout << "bool " <<  << " = true;" << endl; }
            ;

    integer_declarations:
            INTEGER_SECTION integers
            ;

    integers:
            integers ',' integer            
            | integers integer              
            | integer                      
            ;

    integer:
            STRING '[' INTEGER ']'          { cout << "int " <<  << "[" <<  << "]" << ";" << endl; }
            | STRING '[' STRING ']'         { cout << "int " <<  << "[" <<  << "]" << ";" << endl; }
            | STRING                        { cout << "int " <<  << " = 0;" << endl; }
            ;

    timer_declarations:
            TIMER_SECTION timers
            ;

    timers:
            timers ',' timer
            | timers timer
            | timer
            ;

    timer:
            STRING                          { cout << "int " <<  << ";" << endl; }
            ;

    logic_statements:
            LOGIC_SECTION subroutines statements
            ;

    subroutines:
            /* empty */
            | SUBROUTINE_START STRING statements SUBROUTINE_END STRING
            ;

    statements:
            statements statement
            | statement
            ;

    statement:
            if_statement
            | delay_statement
            | GOTO STRING
            | LABEL
            | CALL STRING
            | BOOL variable_list '=' { cout << " = "; } boolean_statement { cout << ";\n"; } 
            | variable_list '=' { cout << " = "; } integer_statement { cout << ";\n"; }
            ;

    if_statement:
            IF '(' { cout << "if("; } boolean_statement ')' { cout << ")" << endl; } block
            | IF '(' { cout << "if("; } boolean_statement ')' { cout << ")" << endl; } block ELSE block
            ;

    delay_statement:
            DELAY '=' INTEGER SECONDS statement 
            ;

    variable_list:
            variable_list ',' { cout << " = "; } variable
            | variable
            ;

    variable:
            STRING                          { cout << ; }
            | STRING '[' INTEGER ']'        { cout <<  << "[" <<  << "]"; }
            | STRING '[' STRING ']'         { cout <<  << "[" <<  << "]"; }
            ;

    boolean_statement:
            '('{ cout << "("; } boolean_statement ')'{ cout << ")"; }
            | bval '+' { cout << " || "; } boolean_statement
            | bval OR { cout << " || "; } boolean_statement
            | bval '*' { cout << " && "; } boolean_statement
            | bval AND { cout << " && "; } boolean_statement
            | bval EQ { cout << " == "; } boolean_statement
            | bval NEQ { cout << " != "; } boolean_statement
            | NOT { cout << ; } boolean_statement
            | bval
            ;

    bval:
            BOOLEAN                          { cout << ; }
            | variable
            ;

    integer_statement:
            '('{ cout << "("; } integer_statement ')'{ cout << ")"; }
            | value '+'{ cout << " + "; } integer_statement
            | value '*'{ cout << " * "; } integer_statement
            | value
            ;

    value:
            INTEGER                       { cout << ; }
            | variable
            ;

    block:
            { cout << "{" << endl; } statement { cout << "}" << endl; }
            | '{' { cout << "{" << endl; } statements '}' { cout << "}" << endl; }
            ;

    //end of grammer section
    %%

    int main(int argc, char *argv[]) {

            // default input is stdin
            // if file is given read from it
            if(argc == 2)
            {
                    // open a file handle to a particular file:
                    FILE *myfile = fopen(argv[1], "r");
                    // make sure it's valid:
                    if (!myfile) {
                            cout << "Can't open "<< argv[1] <<" file" << endl;
                            cout << "Usage: " << argv[0] << " <filename>\n";
                            return -1;
                    }
                    // set lex to read from it instead of defaulting to STDIN:
                    yyin = myfile;
            }
            else if(argc != 1)
            {
                    cout << "Usage: " << argv[0] << " <filename>\n";
                    cout << "Usage: " << argv[0] << endl;
                    return -1;
            }

            // parse through the input until there is no more:
            do 
            {
                    yyparse();
            } while (!feof(yyin));
    }

    void yyerror(const char *s) {
        cout << "Parse error on line " << line_num << "!  Message: " << s << endl;
        // might as well halt now:
        exit(-1);
    }

Answer 1

问题不在于 IF 语句。 if_statement:

的两个产品中的中间规则操作 (MRA)

if_statement:
          IF '(' { cout << "if("; } boolean_statement ')' { cout << ")" << endl; } block
        | IF '(' { cout << "if("; } boolean_statement ')' { cout << ")" << endl; } block ELSE block
        ;

中间规则动作，如 { cout << "if("; }，被翻译成一个唯一命名的空非终结符。实际上，上述产生式变成了以下形式：

if_statement:
          IF '(' @3 boolean_statement ')' @4 block
        | IF '(' @5 boolean_statement ')' @6 block ELSE block
        ;

@3: %empty { cout << "if("; }        ;
@4: %empty { cout << ")" << endl; }  ;
@5: %empty { cout << "if("; }        ;
@6: %empty { cout << ")" << endl; }  ;

在上面，@3 和 @5 相同（@4 和 @6 相同），但 bison 不检查；每个 MRA 都被认为是独一无二的。这会导致 reduce/reduce 冲突，因为一旦解析器读取了 if (，它将需要减少其中一个 @3 或 @5 在它可以移动以下标记之前，无论该标记可能是什么，但下一个标记没有提供关于 else 最终是否会出现的线索出现。（两个产品都以 boolean_statement 继续，因此在任何一种情况下，以下标记都可以是 FIRST(boolean_statement) 中的任何标记。）

冲突的解决有利于 @3（文本上较早的非终结符）这一事实意味着 @5 永远无法减少，野牛对此提供了警告。（至少，我的野牛版本做到了。）

这是 MRA 的一个经典问题，非常常见，因此需要在 bison manual 中有一节。

在这种情况下，您可以通过左因式简单地解决问题：

if_statement:
      if_then
    | if_then ELSE block
    ;

if_then:
      IF '('                   { cout << "if("; }
      boolean_statement ')'    { cout << ")" << endl; }
      block
    ;

Bison reduce/reduce if else 条件冲突

Bison reduce/reduce conflict if else condition

compiler-construction

bison