无法在语法中找到减少/减少冲突 [英] Cant find Reduce/Reduce conflict in Grammar

问题描述

我写了以下语法，而Bison警告我减少/减少冲突.

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

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

如何检测语法的哪个部分引起了冲突? Bison生成了日志，我可以在其中查看冲突吗?而且，我该如何解决呢?

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?

语法:

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

推荐答案

如何检测语法的哪个部分引起了冲突? Bison生成了日志，我可以在其中查看冲突吗?而且，我该如何解决呢?

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?

是的.如果在bison命令行上使用-v，它将在名为<filename>.output的文件中生成所有状态的报告.该报告将包括各种冲突，您可以从所指示的状态中看到什么是冲突的模式.在阅读本答案的其余部分之前，您应该先尝试一下.

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

由于seq_comando可以为空，因此单个comando可以匹配:

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

seq_comando: comando seq_comando

或

seq_comando: comando

简单的解决方案是摆脱seq_comando: comando规则.您可能还需要考虑将右递归更改为左递归(seq_comando: seq_comando comando | /* empty */;)，因为这将需要较少的解析器堆栈.

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.

这篇关于无法在语法中找到减少/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！