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.