example - yacc python

¿Cómo encontrar cambio/reducir conflicto en este archivo yacc?

Question

Cuando intento usar yacc en el siguiente archivo, aparece el mensaje de error: 1 cambio / reducción ¿Cómo puedo encontrar y solucionar el conflicto?

/* C-Minus BNF Grammar */
%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE
%token ID
%token NUM
%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL
%%
program : declaration_list ;
declaration_list : declaration_list declaration | declaration ;
declaration : var_declaration | fun_declaration ;
var_declaration : type_specifier ID '';''
| type_specifier ID ''['' NUM '']'' '';'' ;
type_specifier : INT | VOID ;
fun_declaration : type_specifier ID ''('' params '')'' compound_stmt ;
params : param_list | VOID ;
param_list : param_list '','' param
| param ;
param : type_specifier ID | type_specifier ID ''['' '']'' ;
compound_stmt : ''{'' local_declarations statement_list ''}'' ;
local_declarations : local_declarations var_declaration
| /* empty */ ;
statement_list : statement_list statement
| /* empty */ ;
statement : expression_stmt
| compound_stmt
| selection_stmt
| iteration_stmt
| return_stmt ;
expression_stmt : expression '';''
| '';'' ;
selection_stmt : IF ''('' expression '')'' statement
| IF ''('' expression '')'' statement ELSE statement ;
iteration_stmt : WHILE ''('' expression '')'' statement ;
return_stmt : RETURN '';'' | RETURN expression '';'' ;
expression : var ''='' expression | simple_expression ;
var : ID | ID ''['' expression '']'' ;
simple_expression : additive_expression relop additive_expression
| additive_expression ;
relop : LTE | ''<'' | ''>'' | GTE | EQUAL | NOTEQUAL ;
additive_expression : additive_expression addop term | term ;
addop : ''+'' | ''-'' ;
term : term mulop factor | factor ;
mulop : ''*'' | ''/'' ;
factor : ''('' expression '')'' | var | call | NUM ;
call : ID ''('' args '')'' ;
args : arg_list | /* empty */ ;
arg_list : arg_list '','' expression | expression ;

Answer 1

Como mientefuego señaló, la gramática tiene el problema clásico de "colgar". Podría superar el problema asignando prioridad a las reglas que causan el conflicto.

La regla que causa el conflicto es:

selection_stmt : IF ''('' expression '')'' statement
| IF ''('' expression '')'' statement ELSE statement ;

Primero comience haciendo ELSE y LOWER_THAN_ELSE (un pseudo-token) no asociativo:

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

Esto le da a ELSE más prioridad sobre LOWER_THAN_ELSE simplemente porque LOWER_THAN_ELSE se declara primero.

Luego, en la regla conflictiva, debe asignar una prioridad a la acción de cambio o reducción:

selection_stmt : IF ''('' expression '')'' statement %prec LOWER_THAN_ELSE ;
| IF ''('' expression '')'' statement ELSE statement ;

Aquí, se da mayor prioridad al cambio. He incorporado las correcciones mencionadas anteriormente y enumero la gramática completa a continuación:

/* C-Minus BNF Grammar */
%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE
%token ID
%token NUM
%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL
%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
%%
program : declaration_list ;
declaration_list : declaration_list declaration | declaration ;
declaration : var_declaration | fun_declaration ;
var_declaration : type_specifier ID '';''
| type_specifier ID ''['' NUM '']'' '';'' ;
type_specifier : INT | VOID ;
fun_declaration : type_specifier ID ''('' params '')'' compound_stmt ;
params : param_list | VOID ;
param_list : param_list '','' param
| param ;
param : type_specifier ID | type_specifier ID ''['' '']'' ;
compound_stmt : ''{'' local_declarations statement_list ''}'' ;
local_declarations : local_declarations var_declaration
| /* empty */ ;
statement_list : statement_list statement
| /* empty */ ;
statement : expression_stmt
| compound_stmt
| selection_stmt
| iteration_stmt
| return_stmt ;
expression_stmt : expression '';''
| '';'' ;
selection_stmt : IF ''('' expression '')'' statement %prec LOWER_THAN_ELSE ;
| IF ''('' expression '')'' statement ELSE statement ;
iteration_stmt : WHILE ''('' expression '')'' statement ;
return_stmt : RETURN '';'' | RETURN expression '';'' ;
expression : var ''='' expression | simple_expression ;
var : ID | ID ''['' expression '']'' ;
simple_expression : additive_expression relop additive_expression
| additive_expression ;
relop : LTE | ''<'' | ''>'' | GTE | EQUAL | NOTEQUAL ;
additive_expression : additive_expression addop term | term ;
addop : ''+'' | ''-'' ;
term : term mulop factor | factor ;
mulop : ''*'' | ''/'' ;
factor : ''('' expression '')'' | var | call | NUM ;
call : ID ''('' args '')'' ;
args : arg_list | /* empty */ ;
arg_list : arg_list '','' expression | expression ;

Answer 2

Ejem, la respuesta correcta a este problema suele ser: no hacer nada .

Se esperan conflictos de desplazamiento / reducción con gramáticas ambiguas. No son errores , son conflictos .

El conflicto se resolverá prefiriendo el cambio sobre reducir, lo que simplemente sucede para resolver el problema canónico de otra cosa.

Y bison incluso tiene una declaración% expect n , por lo que no recibe una advertencia de conflicto S / R cuando hay exactamente n conflictos.

Answer 3

Primero, obtenga una salida de máquina de estado de yacc . Un estado que puede ser cambiado o reducido representa un conflicto de cambio / reducción. Encuentra uno y luego resuelve el conflicto reescribiendo la gramática.

Answer 4

tal vez deberías probar un yacc -v <filename> , genera una salida de los detalles.

Probé aquí, y su descripción gramatical falla en el problema clásico de "colgar de otra manera".

Echa un vistazo a este artículo de Wikipedia .

Answer 5

This artículo ofrece una solución alternativa a la publicada por ardsrk.