Cómo reparar el turno YACC / reducir los conflictos de operador de incremento?

Question

Estoy escribiendo una gramática en YACC (en realidad bisonte), y estoy teniendo un desplazamiento / reducción problema. Es el resultado de la inclusión de los operadores de incremento y decremento postfijo. Aquí es una versión reducida de la 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 ')'
;

%%

bisonte me dice que hay 12 de desplazamiento / reducción conflictos, pero si me comente todas las líneas para el incremento y decremento de sufijo, que funciona bien. ¿Alguien sabe cómo solucionar este conflicto? En este punto, estoy considerando mudarse a un generador de analizadores sintácticos LL (k), que hace que sea mucho más fácil, pero gramáticas LALR siempre me han parecido mucho más natural para escribir. También estoy considerando GLR, pero no sé de ningún bien C / C ++ GLR generadores de analizadores sintácticos.

Answer 1

bisonte / Yacc puede generar un analizador GLR si se especifica en la sección %glr-parser opción.

Answer 2

Prueba esto:

%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 ')'
;

%%

La clave es declarar operadores de sufijo como no asociativo . De lo contrario, sería capaz de

++var++--

El paréntesis también necesita ser dado una prioridad para reducir al mínimo desplazamiento / reducción advertencias

Answer 3

Me gusta definir más artículos. No debería ser necesario la izquierda%,% derecha, las cosas 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
;

Juega un poco con este enfoque.

Answer 4

Este problema básico es que usted no tiene un precedente para las fichas INC y DEC, por lo que no sabe cómo resolver las ambigüedades que implican una búsqueda hacia delante de INC o DEC. Si se agrega

%right INC DEC

al final de la lista de prioridades (que quieren unaries a ser mayor precedencia y Postfix más alto que el prefijo), que lo arreglará, e incluso se puede deshacerse de todas las cosas PREINC / POSTINC, ya que es irrelevante.

Answer 5

preincremento y postincremento operadores tienen nonassoc así definir que en la sección precedencia y en las reglas de hacer que la precedencia de estos operadores altas mediante el uso de %prec