Resolvendo reduzir/reduzir conflitos em yacc/ocamlyacc
Pergunta
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?
Solução
Infelizmente, a única resposta que consigo encontrar significa aumentar a complexidade da gramática.
- dividir
expr
emsimple_expr
eexpr_with_prefix
- 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
Outras dicas
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.