Como turno correção YACC / reduzir conflitos de pós-incremento operador?

Question

Eu estou escrevendo uma gramática em YACC (na verdade Bison), e eu estou tendo um shift / reduzir problema. É o resultado de incluindo o incremento postfix e operadores decréscimo. Aqui está uma versão recortada da gramática:

%token NUMBER ID INC DEC

%left      '+' '-'
%left      '*' '/'
%right     PREINC
%left      POSTINC

%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     INC expr %prec PREINC
|     DEC expr %prec PREINC
|     expr INC %prec POSTINC
|     expr DEC %prec POSTINC
|     '(' expr ')'
;

%%

Bison me diz que há 12 shift / reduzir conflitos, mas se eu comentar as linhas para o incremento postfix e decréscimo, ele funciona bem. Alguém sabe como resolver este conflito? Neste momento, estou pensando em mudar para um gerador de analisador LL (k), o que torna muito mais fácil, mas gramáticas LALR sempre parecia muito mais natural para escrever. Eu também estou considerando GLR, mas eu não sei de qualquer bom C / geradores de analisador C ++ GLR.

Answer 1

Bison / Yacc pode gerar um analisador GLR se você especificar %glr-parser na seção opção.

Answer 2

Tente isto:

%token NUMBER ID INC DEC

%left       '+' '-'
%left       '*' '/'
%nonassoc   '++' '--'
%left       '('
%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     '++' expr 
|     '--' expr 
|     expr '++'
|     expr '--'
|     '(' expr ')'
;

%%

A chave é declarar operadores postfix como não associativo . Caso contrário, você seria capaz de

++var++--

O parêntese também precisa ser dada uma precedência para minimizar shift / reduzir avisos

Answer 3

Eu gosto de definir mais itens. Você não deve precisar o% esquerda,% certo,% coisas prec.

simple_expr: NUMBER
 | INC simple_expr
 | DEC simple_expr
 | '(' expr ')'
;

term: simple_expr
 | term '*' simple_expr
 | term '/' simple_expr
;

expr: term
 | expr '+' term
 | expr '-' term
;

Brinque com esta abordagem.

Answer 4

Este problema básico é que você não tem uma precedência para os INC e DEC fichas, por isso não sei como resolver ambigüidades que envolvem uma visão antecipada de INC ou DEC. Se você adicionar

%right INC DEC

no final da lista de precedência (você quer unaries a ser maior precedência e postfix maior do prefixo), ele irá corrigi-lo, e você ainda pode se livrar de todas as coisas PREINC / POSTINC, como é irrelevante.

Answer 5

pré-incremento e operadores postIncrement tem nonassoc assim definir isso na seção precedência e nas regras fazer a precedência destes operadores alta usando %prec