parsing - reduccion - bison analizador sintactico

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 la variedad 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. 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 esto debería reducirse como "a (-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

Bueno, la respuesta más simple es simplemente ignorarlo y dejar que la resolución predeterminada reduzca / reduzca la resolución: reduzca la regla que 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 desea. Después de ver ab , desea analizarlo como un error binario, en lugar de un signo menos unario y luego aplicar.

Answer 2

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 ''ab c'': ¿es a(b(c)) o (a(b))(c) ? También deberá separar la applied_expression y la requerida (applied_expression) en la gramática.

Creo que esto lo hará, 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