compiler-construction - Bison 减少/减少冲突 if else 条件

Question

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

这里有一些信息可能有助于解释以下代码:

• BOOL 是每行开头使用的关键字标记，表示该行是 bool 运算

• BOOLEAN 是“真”或“假”值

• 我正在使用此编译器将一种语言转换为 C 代码，该语言可以包含类似 a,b,c=d+2 的语句，它等同于 a= b=c=d+2 在 C 中；和 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 " << $2 << " = "  << $4 << ";" << endl; }
            | constants STRING '=' HEX      { cout << "const int " << $2 << " = "  << $4 << ";" << endl; }
            | STRING '=' INTEGER            { cout << "const int " << $1 << " = "  << $3 << ";" << endl; }
            | STRING '=' HEX                { cout << "const int " << $1 << " = "  << $3 << ";" << endl; }
            ;

    boolean_declarations:
            BOOLEAN_SECTION booleans       
            ;

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

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

    integer_declarations:
            INTEGER_SECTION integers
            ;

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

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

    timer_declarations:
            TIMER_SECTION timers
            ;

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

    timer:
            STRING                          { cout << "int " << $1 << ";" << 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 << $1; }
            | STRING '[' INTEGER ']'        { cout << $1 << "[" << $3 << "]"; }
            | STRING '[' STRING ']'         { cout << $1 << "[" << $3 << "]"; }
            ;

    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 << $1; } boolean_statement
            | bval
            ;

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

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

    value:
            INTEGER                       { cout << $1; }
            | 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 的两个作品中的中间规则 Action (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 都被认为是独一无二的。这会导致减少/减少冲突，因为一旦解析器读取了 if (，它将需要减少 @3 或 @5 之一，然后才能移动以下标记，无论该标记可能是什么，但下一个标记没有提供关于 else 是否最终会出现的线索。(两个产品都以 boolean_statement 继续，因此以下标记在任何一种情况下都可以是 FIRST(boolean_statement) 中的任何标记。)

冲突以有利于 @3 的方式解决的事实(文本上较早的非终结符)表示 @5永远不能减少， Bison 对此提供了警告。 (至少，我的 Bison 版本做到了。)

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

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

if_statement:
      if_then
    | if_then ELSE block
    ;

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