Resolvendo reduzir/reduzir conflitos em yacc/ocamlyacc

Question

Estou tentando analisar uma gramática em ocamlyacc (praticamente igual ao yacc normal) que suporta aplicação de função sem operadores (como em Ocaml ou Haskell) e a variedade normal de operadores binários e unários.Estou tendo um conflito de redução/redução com o operador '-', que pode ser usado tanto para subtração quanto para negação.Aqui está um exemplo da gramática que estou 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) };

O problema é que quando você obtém uma expressão como "a - b" o analisador não sabe se deve ser reduzida como "a (-b)" (negação de b, seguida de aplicação) ou "a - b" ( subtração).A redução da subtração está correta.Como faço para resolver o conflito em favor dessa regra?

Answer 1

Infelizmente, a única resposta que consigo encontrar significa aumentar a complexidade da gramática.

1. dividir expr em simple_expr e expr_with_prefix
2. permitir apenas simple_expr ou (expr_with_prefix) em um APLICAR

A primeira etapa transforma seu conflito de redução/redução em um conflito de mudança/redução, mas os parênteses resolvem isso.

Você terá o mesmo problema com 'a b c':é isso a(b(c)) ou (a(b))(c)?Você também precisará interromper applied_expression e obrigatório (applied_expression) na gramática.

Acho que isso vai resolver, mas não tenho certeza:

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

Bem, esta resposta mais simples é simplesmente ignorá-la e deixar que a resolução padrão de redução/redução cuide disso - reduza a regra que aparece primeiro na gramática.Neste caso, isso significa reduzir expr MINUS expr de preferência para MINUS expr, que é exatamente o que você deseja.Depois de ver a-b, você deseja analisá-lo como um sinal de menos binário, em vez de um sinal de menos unário e, em seguida, aplicar.