Зубр - сдвиг / уменьшение идентификатора конфликта

Question

Зубр - сдвиг / уменьшение идентификатора конфликта

У меня есть 1 сдвиг / уменьшение конфликта в состоянии 19. Я думаю, что могут быть проблемы с разными вхождениями "идентификатора", но я изо всех сил пытаюсь понять отчет о зубрах и разрешить конфликт. Ниже моя грамматика, за которой следует отчет о зубрах с информацией о состоянии:

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

    extern "C" int yylex();
    extern "C" int yyparse();
    void yyerror(const char *s);
%}

%union{
    int int_val;
    double d_val;
    char *strng;
}

%token TLINEC TBLOCKC TPRINT
%token TASSIGN TCPA TOB TCB TCOMMA TSEMIC
%token TIF TELSE TFOR
%token TINT TFLOAT TD TCHAR
%token TPLUS TMINUS TDIV TMULT
%token TLT TGT TAND TOR TEQUAL TNE
%token<int_val> TINTEGER
%token<d_val> TDOUBLE
%token<strng> TID
%token TOPA

%start program

%%

program : command_list

command_list : declaration
    | command_list declaration

declaration : function_dec
| variable_dec
    | expression

variable_dec : type identifier TSEMIC
| type assignment TSEMIC

assignment : identifier TASSIGN expression

var_list : expression
    | var_list TCOMMA expression
    |

function_dec : type identifier TOPA p_list TCPA scope

p_list : variable_dec
    | p_list TCOMMA variable_dec

type : TINT
    | TD
    | TFLOAT
    | TCHAR


/* inside function scope */

scope : TOB command_list TCB
| TOB TCB


function_call : identifier TOPA var_list TCPA TSEMIC

/* expression rules */

expression : assignment
    | function_call
    | TOPA expression TCPA
    | constant arithmetic_op expression
    | constant logical_op expression
    | constant


constant : identifier
    | num

identifier : TID

num : TINTEGER
| TDOUBLE

arithmetic_op : TPLUS | TMINUS | TDIV | TMULT

logical_op : TLT | TGT | TAND | TOR | TEQUAL | TNE

%%

int main(int, char**){
    int y=0;
    do{
        y=yyparse();
    }while(y);
}

void yyerror(const char *s){
    cout << "parse error! Message: " << s << endl;
    exit(-1);
}

Отчет о зубрах:

State 19 conflicts: 1 shift/reduce


Grammar

    0 $accept: program $end

    1 program: command_list

    2 command_list: declaration
    3             | command_list declaration

    4 declaration: function_dec
    5            | variable_dec
    6            | expression

    7 variable_dec: type identifier TSEMIC
    8             | type assignment TSEMIC

    9 assignment: identifier TASSIGN expression

   10 var_list: expression
   11         | var_list TCOMMA expression
   12         | /* empty */

   13 function_dec: type identifier TOPA p_list TCPA scope

   14 p_list: variable_dec
   15       | p_list TCOMMA variable_dec

   16 type: TINT
   17     | TD
   18     | TFLOAT
   19     | TCHAR

   20 scope: TOB command_list TCB
   21      | TOB TCB

   22 function_call: identifier TOPA var_list TCPA TSEMIC

   23 expression: assignment
   24           | function_call
   25           | TOPA expression TCPA
   26           | constant arithmetic_op expression
   27           | constant logical_op expression
   28           | constant

   29 constant: identifier
   30         | num

   31 identifier: TID

   32 num: TINTEGER
   33    | TDOUBLE

   34 arithmetic_op: TPLUS
   35              | TMINUS
   36              | TDIV
   37              | TMULT

   38 logical_op: TLT
   39           | TGT
   40           | TAND
   41           | TOR
   42           | TEQUAL
   43           | TNE


Terminals, with rules where they appear

$end (0) 0
error (256)
TLINEC (258)
TBLOCKC (259)
TPRINT (260)
TASSIGN (261) 9
TCPA (262) 13 22 25
TOB (263) 20 21
TCB (264) 20 21
TCOMMA (265) 11 15
TSEMIC (266) 7 8 22
TIF (267)
TELSE (268)
TFOR (269)
TINT (270) 16
TFLOAT (271) 18
TD (272) 17
TCHAR (273) 19
TPLUS (274) 34
TMINUS (275) 35
TDIV (276) 36
TMULT (277) 37
TLT (278) 38
TGT (279) 39
TAND (280) 40
TOR (281) 41
TEQUAL (282) 42
TNE (283) 43
TINTEGER (284) 32
TDOUBLE (285) 33
TID (286) 31
TOPA (287) 13 22 25


Nonterminals, with rules where they appear

$accept (33)
    on left: 0
program (34)
    on left: 1, on right: 0
command_list (35)
    on left: 2 3, on right: 1 3 20
declaration (36)
    on left: 4 5 6, on right: 2 3
variable_dec (37)
    on left: 7 8, on right: 5 14 15
assignment (38)
    on left: 9, on right: 8 23
var_list (39)
    on left: 10 11 12, on right: 11 22
function_dec (40)
    on left: 13, on right: 4
p_list (41)
    on left: 14 15, on right: 13 15
type (42)
    on left: 16 17 18 19, on right: 7 8 13
scope (43)
    on left: 20 21, on right: 13
function_call (44)
    on left: 22, on right: 24
expression (45)
    on left: 23 24 25 26 27 28, on right: 6 9 10 11 25 26 27
constant (46)
    on left: 29 30, on right: 26 27 28
identifier (47)
    on left: 31, on right: 7 9 13 22 29
num (48)
    on left: 32 33, on right: 30
arithmetic_op (49)
    on left: 34 35 36 37, on right: 26
logical_op (50)
    on left: 38 39 40 41 42 43, on right: 27



state 18

   26 expression: constant . arithmetic_op expression
   27           | constant . logical_op expression
   28           | constant .  [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TINTEGER, TDOUBLE, TID, TOPA]
   34 arithmetic_op: . TPLUS
   35              | . TMINUS
   36              | . TDIV
   37              | . TMULT
   38 logical_op: . TLT
   39           | . TGT
   40           | . TAND
   41           | . TOR
   42           | . TEQUAL
   43           | . TNE

    TPLUS   shift, and go to state 26
    TMINUS  shift, and go to state 27
    TDIV    shift, and go to state 28
    TMULT   shift, and go to state 29
    TLT     shift, and go to state 30
    TGT     shift, and go to state 31
    TAND    shift, and go to state 32
    TOR     shift, and go to state 33
    TEQUAL  shift, and go to state 34
    TNE     shift, and go to state 35

    $default  reduce using rule 28 (expression)

    arithmetic_op  go to state 36
    logical_op     go to state 37


state 19

    9 assignment: identifier . TASSIGN expression
   22 function_call: identifier . TOPA var_list TCPA TSEMIC
   29 constant: identifier .  [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TPLUS, TMINUS, TDIV, TMULT, TLT, TGT, TAND, TOR, TEQUAL, TNE, TINTEGER, TDOUBLE, TID, TOPA]

    TASSIGN  shift, and go to state 38
    TOPA     shift, and go to state 39

    TOPA      [reduce using rule 29 (constant)]
    $default  reduce using rule 29 (constant)


state 20

   30 constant: num .

    $default  reduce using rule 30 (constant)

1

parsing compiler-construction bison shift-reduce-conflict

Источник

user4680872 17 мар '15 в 13:26

1 ответ

Решение

Другие вопросы по тегам parsing compiler-construction bison shift-reduce-conflict

user1566221 17 мар '15 в 17:25 2015-03-17 17:25 · Accepted Answer · 2015-03-17 17:25

По выводу зубров, из состояния 19 можно уменьшить expression на взгляд (. Как это может быть возможно? Другими словами, при каких обстоятельствах может expression сопровождаться открытой скобкой?

Поиск по грамматике показывает только три использования TOPA, Два из них (объявления функций и вызовы функций) следуют identifier а также identifier не может получить expressionтак что это должен быть третий

expression: TOPA expression TCPA;

Тем не менее, единственный способ сокращения expression может произойти непосредственно перед этим экземпляром ( если бы это было возможно для двух expressionдолжно происходить последовательно. Обычно в C-подобных языках эта возможность устраняется с помощью требования ; разделить утверждения (которые могут быть, начинаться с или заканчиваться expression) и я полагаю, что это было вашим намерением.

Однако мы видим, что:

command_list: declaration
            | command_list declaration

declaration: expression

который позволяет два последовательных выражения без промежуточной точки с запятой.

Как всегда, я рекомендую использовать более читаемые токены в грамматике бизонов. '(' гораздо легче понять, чем TOPAи я, честно говоря, понятия не имею, что COB возможно. Но это вопрос стиля.