Bison уменьшить/уменьшить конфликт, если условие else

Question

Я ожидал, что shift/уменьшить конфликт будет, если else, но он дал уменьшить/уменьшить конфликт в строке «IF» («boolean_statement») «block».

Вот некоторая информация, которая может помочь объяснить следующий код:

• BOOL является маркером для ключевого слова, используемого в начале каждой строки для указания линии является булевой операцией

• BOOLEAN либо «истинно» или «false»

• Я использую этот компилятор для преобразования языка в код 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:

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), но зубры не проверяют, что; каждый MRA считается уникальным. И это приводит к снижению/уменьшения конфликтов, потому что как только анализатор прочитал если(, ему необходимо будет уменьшить одну из @3 или @5, прежде чем он может перенести следующий маркер, независимо от того, что этот маркер может быть, но следующий маркер не дает никакого понятия о том, является ли или не еще в конце концов появятся. (Оба спектакля продолжать boolean_statement, так что следующий маркер может быть любым маркером в FIRST(boolean_statement), в любом случае.)

Тот факт, что конфликт разрешается в пользу @3 (текстовое более раннее не-терминальное) означает, что @5 никогда не может быть уменьшено, а bison pro предупреждает об этом. (По крайней мере, моя версия bison сделала.)

Это классическая проблема с MRA, достаточно обычная, что она требует раздел в bison manual.

В этом случае, вы можете решить эту проблему, просто левой факторинга:

if_statement: 
     if_then 
    | if_then ELSE block 
    ; 

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