Resolver reducir/reducir conflictos en yacc/ocamlyacc
Pregunta
Estoy intentando analizar una gramática en ocamlyacc (prácticamente igual que el yacc normal) que admita la aplicación de funciones sin operadores (como en Ocaml o Haskell) y la variedad normal de operadores binarios y unarios.Tengo un conflicto de reducción/reducción con el operador '-', que se puede usar tanto para resta como para negación.Aquí hay una muestra de la gramática que estoy usando:
%token <int> INT
%token <string> ID
%token MINUS
%start expr
%type <expr> expr
%nonassoc INT ID
%left MINUS
%left APPLY
%%
expr: INT
{ ExprInt $1 }
| ID
{ ExprId $1 }
| expr MINUS expr
{ ExprSub($1, $3) }
| MINUS expr
{ ExprNeg $2 }
| expr expr %prec APPLY
{ ExprApply($1, $2) };
El problema es que cuando obtienes una expresión como "a - b" el analizador no sabe si debe reducirse a "a (-b)" (negación de b, seguida de aplicación) o "a - b" ( sustracción).La reducción de la resta es correcta.¿Cómo resuelvo el conflicto a favor de esa regla?
Solución
Desafortunadamente, la única respuesta que se me ocurre es aumentar la complejidad de la gramática.
- dividir
expr
ensimple_expr
yexpr_with_prefix
- permitir solo
simple_expr
o(expr_with_prefix)
en un APLICAR
El primer paso convierte su conflicto de reducción/reducción en un conflicto de cambio/reducción, pero los paréntesis lo resuelven.
Vas a tener el mismo problema con 'a b c':Lo es a(b(c))
o (a(b))(c)
?También tendrás que romper applied_expression
y requerido (applied_expression)
en la gramática.
Creo que esto servirá, pero no estoy seguro:
expr := INT
| parenthesized_expr
| expr MINUS expr
parenthesized_expr := ( expr )
| ( applied_expr )
| ( expr_with_prefix )
applied_expr := expr expr
expr_with_prefix := MINUS expr
Otros consejos
Bueno, esta respuesta más simple es simplemente ignorarla y dejar que la resolución de reducción/reducción predeterminada la maneje: reduzca la regla que aparece primero en la gramática.En este caso, eso significa reducir expr MINUS expr
en preferencia a MINUS expr
, que es exactamente lo que quieres.Después de ver a-b
, desea analizarlo como un signo negativo binario, en lugar de un signo negativo unario y luego aplicar.