Resolviendo reducir/reducir el conflicto en yacc/ocamlyacc

Question

Estoy tratando de analizar una gramática en ocamlyacc (más o menos lo mismo que el yacc normal) que admite la aplicación de funciones sin operadores (como en Ocaml o Haskell) y el surtido normal de operadores binarios y unarios. Obtengo un conflicto de reducción/reducción con el operador '-', que puede usarse tanto para la sustracción como para la negación. Este es un ejemplo 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 se obtiene una expresión como "A - B" el analizador no sabe si esto se debe reducir como "una (- b) "(negación de b, seguida de la 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?

Answer 1

Lamentablemente, la única respuesta que se me ocurre es aumentar la complejidad de la gramática.

1. dividir expr en simple_expr y expr_with_prefix
2. sólo permiten simple_expr o (expr_with_prefix) en un APLICA

El primer paso convierte su reducción/reducción de conflictos en un desplazamiento/reducción de conflictos, pero la determinación paréntesis que .

Vas a tener el mismo problema con 'a b c': ¿es a(b(c)) o (a(b))(c)? Necesitarás también romper applied_expression y requiriste (applied_expression) en la gramática.

creo que esto va a hacer, 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 

Answer 2

Bueno, esta respuesta más sencilla es simplemente ignorarlo y dejar el valor por defecto de Reducción/Reducción resolución manejarlo - reducir la regla eso aparece primero en la gramática. En este caso, eso significa reducir expr MINUS expr con preferencia a MINUS expr, que es exactamente lo que quiere. Después de ver a-b, quiere analizarlo como un error binario, en lugar de un signo menos unario y luego aplicar.