Невозможно найти Уменьшить/уменьшить конфликт в грамматике

Question

Я написал следующую грамматику, и Бизон предупреждает меня о конфликте уменьшения/уменьшения.

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

Как определить, какая часть грамматики порождает конфликт? Есть ли журнал, созданный Bison, где я вижу конфликты? А также, как я мог это решить?

Грамматика:

%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 
    | 
    ; 

Answer 1

Как я могу обнаружить, какая часть грамматики порождает конфликт? Есть ли журнал, созданный Bison, где я вижу конфликты? А также, как я мог это решить?

Да. Если вы используете -v в командной строке bison, он выдаст отчет о всех состояниях в файле с именем <filename>.output. Отчет будет включать в себя различные конфликты, и вы можете видеть из указанного состояния, что такое конфликтующие шаблоны. Вы должны попробовать это, прежде чем читать остальную часть этого ответа.

Если вы сделаете это, вы будете видеть проблему:

seq_comando: comando seq_comando 
    | comando 
    | 
    ; 

С seq_comando может быть пустым, один comando может соответствовать:

seq_comando: comando seq_comando 

или

seq_comando: comando 

Простое решение - избавиться от правила seq_comando: comando. Вы также можете рассмотреть возможность изменения правильной рекурсии на левую рекурсию (seq_comando: seq_comando comando | /* empty */;), поскольку для этого потребуется меньше стека парсера.