Resolver reducir/reducir conflictos en yacc/ocamlyacc

Question

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?

Answer 1

Desafortunadamente, 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. 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

Answer 2

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.