Cant find Reduce/Reduce conflict in Grammar

Question

I wrote the following grammar and Bison is warning me about a reduce/reduce conflict.

parser.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]

How can I detect which part of the grammar is generating the conflict? Is there a log generated by Bison where I can see the conflicts? And also, how could I solve this?

Grammar:

%left TK_OC_OR TK_OC_AND
%left '<' '>' TK_OC_LE TK_OC_GE TK_OC_EQ TK_OC_NE
%left '+' '-'
%left '*' '/'

%nonassoc LOWER_THAN_ELSE
%nonassoc TK_PR_ELSE

%start s

%type<symbol> decl_var
%type<symbol> cabecalho

%%

s: decl_global s
  | def_funcao s
  |
  ;

decl_global: decl_var ';'
  | decl_vetor ';'
  | decl_var {error("Faltando o ';' no final do comando.", $1->line); return IKS_SYNTAX_ERRO;}
  ;

decl_local: decl_var ';' decl_local
   |
   ;

decl_var
  : tipo_var TK_IDENTIFICADOR {$$ = $2;}
  ;

decl_vetor
   : tipo_var TK_IDENTIFICADOR '[' TK_LIT_INT ']'
   ;


tipo_var: TK_PR_INT
        | TK_PR_FLOAT
        | TK_PR_BOOL
        | TK_PR_CHAR
        | TK_PR_STRING
        ;

def_funcao: cabecalho decl_local bloco_comando
  | cabecalho decl_local bloco_comando ';' {error("Declaração de função com ';' no final do comando.\n",$1->line); return IKS_SYNTAX_ERRO;} 
  ;

chamada_funcao
  : TK_IDENTIFICADOR '(' lista_expressoes ')'
  ;

cabecalho: decl_var '(' lista_parametros ')' {$$ = $1;}
  ;

lista_parametros: lista_parametros_nao_vazia
  |
  ;

lista_parametros_nao_vazia: parametro ',' lista_parametros_nao_vazia
  | parametro
  ;

parametro: decl_var
  ;

comando: bloco_comando
  | controle_fluxo
  | atribuicao
  | entrada
  | saida
  | retorna
  | decl_var ';'
  | chamada_funcao
  | ';'
  ;

bloco_comando: '{' seq_comando '}'
  ;

seq_comando: comando seq_comando
  | comando
  |
  ;

atribuicao: TK_IDENTIFICADOR '=' expressao
  | TK_IDENTIFICADOR '[' expressao ']' '=' expressao
  ;

entrada
  : TK_PR_INPUT TK_IDENTIFICADOR
  ;

saida
  : TK_PR_OUTPUT lista_expressoes_nao_vazia
  ;

lista_expressoes_nao_vazia: expressao ',' lista_expressoes_nao_vazia
  | expressao
  ;

retorna: TK_PR_RETURN expressao ';'
  ;

controle_fluxo
  : TK_PR_IF '(' expressao ')' TK_PR_THEN comando %prec LOWER_THAN_ELSE
  | TK_PR_IF '(' error ')' TK_PR_THEN comando 
  | TK_PR_IF '(' expressao ')' TK_PR_THEN comando TK_PR_ELSE comando
  | TK_PR_WHILE '(' expressao ')' TK_PR_DO comando
  | TK_PR_DO comando TK_PR_WHILE '(' expressao ')'
  | TK_PR_DO comando TK_PR_WHILE '(' error ')'
  ;

expressao: TK_IDENTIFICADOR
  | TK_IDENTIFICADOR '[' expressao ']'
  | TK_LIT_INT
  | TK_LIT_FLOAT
  | TK_LIT_FALSE
  | TK_LIT_TRUE
  | TK_LIT_CHAR
  | TK_LIT_STRING
  | expressao '+' expressao 
  | expressao '-' expressao 
  | expressao '*' expressao 
  | expressao '/' expressao 
  | expressao '<' expressao 
  | expressao '>' expressao 
  | '+' expressao
  | '-' expressao
  | '(' expressao ')'
  | expressao TK_OC_LE expressao
  | expressao TK_OC_GE expressao
  | expressao TK_OC_EQ expressao
  | expressao TK_OC_NE expressao
  | expressao TK_OC_AND expressao
  | expressao TK_OC_OR expressao
  | chamada_funcao
  ;

lista_expressoes: lista_expressoes_nao_vazia
  |
  ;

rici rici · Accepted Answer · 2014-09-06T22:17:07

How can I detect which part of the grammar is generating the conflict? Is there a log generated by Bison where I can see the conflicts? And also, how could I solve this?

Yes. If you use -v on the bison command line, it will produce a report of all states in a file called <filename>.output. The report will include the various conflicts, and you can see from the indicated state what the conflicting patterns are. You should try that before reading the rest of this answer.

If you do that, you'll see the problem:

seq_comando: comando seq_comando
  | comando
  |
  ;

Since seq_comando can be empty, a single comando could match:

seq_comando: comando seq_comando

or

seq_comando: comando

The easy solution is to get rid of the seq_comando: comando rule. You might also want to consider changing the right recursion to left recursion (seq_comando: seq_comando comando | /* empty */;) since that will require less parser stack.

Cant find Reduce/Reduce conflict in Grammar

1 Answers