¿Cómo solucionar el cambio de YACC/reducir conflictos del operador de incremento posterior?

Estoy escribiendo una gramática en YACC (en realidad Bison), y estoy teniendo un problema de cambio/reducción. Resulta de incluir los operadores de incremento y decremento de posfijo. Aquí es una versión reducida de la gramática:¿Cómo solucionar el cambio de YACC/reducir conflictos del operador de incremento posterior?

%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 pasar a un generador de analizadores LL (k), lo que lo hace mucho más fácil, pero las gramáticas LALR siempre me han parecido mucho más naturales para escribir. También estoy considerando GLR, pero no conozco ningún buen generador de analizadores sintácticos GLR C/C++.

Fuente

2009-05-20 Zifre

Agradecería que los votantes de abajo al menos dieran una razón ... – Zifre

Bison/Yacc puede generar un analizador GLR si especifica %glr-parser en la sección de opciones.

Fuente

2009-06-06 11:33:04 tomjen

¡Guau! No sabía eso ... Lo probé, pero sigo teniendo conflictos de cambio de turno con mi gramática original. Supongo que el algoritmo GLR de Bison no coopera bien con la precedencia, pero esto podría funcionar en combinación con la respuesta de David Dolson. – Zifre

Bien, acabo de probar esto con el método de David Dolson, ¡y funciona! – Zifre

-1: Usar el modo GLR no es una buena solución para esto, ya que de todos modos necesitas resolver la ambigüedad y, lo que es peor, si NO solucionas la ambigüedad, el bisonco aceptará silenciosamente la gramática sin quejarse, y dará usted en su lugar, los errores de tiempo de ejecución, por lo que es fácil pensar que ha solucionado el problema cuando no lo ha hecho. –

Me gusta definir más elementos. No debería necesitar las cosas% left,% right,% 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 con este enfoque.

Fuente

2009-05-21 15:45:22

He intentado ese enfoque antes, y no me gusta. Cuando tienes gramáticas de expresión mucho más complejas (como C++), es difícil entender exactamente lo que tienes que hacer si quieres modificarlo. Usar precedencia es mucho más limpio, IMO. – Zifre

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++--

también tienen que ser dado una prioridad para minimizar el desplazamiento El paréntesis/reducir advertencias

Fuente

2010-01-21 12:16:33 goresplatter

En realidad, dado que para un comportamiento C normal quieres '++ var ++' analizar como '++ (var ++)' y no ser rechazado como un error (postfix es mayor prioridad que prefijo), quieres '% right' not'% nonassoc' –

Además, la precedencia para ''(' 'no tiene sentido ya que no hay conflictos que la involucren aquí. La necesitarías si hubiera conflictos (por ejemplo, si agregaste la llamada a la función C-style o la sintaxis), pero en ese caso es probable que desee '% right' not'% left' –

-1

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

Fuente

2013-09-08 13:29:31

Este problema básico es que usted no tiene un precedente para los INCDEC y fichas, 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 desea unaries a ser mayor precedencia y Postfix más alto que el prefijo), que lo arreglará, e incluso se pueden deshacerse de todas las cosas PREINC/POSTINC , ya que es irrelevante.

Fuente

2013-09-08 18:23:16

¿Cómo solucionar el cambio de YACC/reducir conflictos del operador de incremento posterior?

Respuesta

Cuestiones relacionadas