Problema al resolver un conflicto shift-reduce en mi gramática

Estoy tratando de escribir un pequeño analizador con Irony. Lamentablemente, recibo un "conflicto de cambio-reducción". Las gramáticas no son mi punto fuerte, y solo necesito hacer esta pequeña cosa. Aquí está la reducción de la gramática que produce el error:Problema al resolver un conflicto shift-reduce en mi gramática

ExpressionTerm := "asd" 
LogicalExpression := 
    ExpressionTerm | 
    LogicalExpression "AND" LogicalExpression | 
    LogicalExpression "OR" LogicalExpression

Lo que hace el "desplazamiento y reducción de conflictos" significa y cómo puedo solucionarlo? Supongo que significa que mi gramática es ambigua, pero no puedo torcer mi lógica lo suficiente como para ver cómo.

Agregado: Para aclarar - "asd" es simplemente una cadena literal "asd". Por lo que se puede esperar que las siguientes expresiones son analizados por esta gramática:

asd 
asd AND asd 
asd AND asd OR asd 
asd OR asd AND asd OR asd

Agregado 2: olvidaba decir, la raíz de la gramática es LogicalExpression.

Agregado 3: Ahh, lo tengo! La ambigüedad se debe a una expresión como

asd AND asd OR asd

podría interpretarse de dos maneras diferentes:

(asd AND asd) OR asd 
asd AND (asd OR asd)

Pero, ¿cómo puedo solucionar esto? OK, puedo poner uno de AND o O para ser más fuerte que el otro (lo había intentado de todos modos). Pero ahora veo que el error aparece incluso si solo hay un operador. En otras palabras, esto también produce el mismo error:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

En este caso quiero esto:

asd OR asd OR asd

que se consultará a esto:

(asd OR asd) OR asd

¿Cuál es la no manera ambigua de hacer esto?

Agregado 4: ¡Lo tengo!

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2 
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3 
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4 
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

Este análisis sintáctico de todas las expresiones booleanas, la prioridad de los operadores como NOT-> AND> O. "asd" se puede reemplazar con la expresión destinada a sus términos.

Fuente

2009-05-26 Vilx-

Je, ahora que lo pienso de ella, estoy empezando a recordar esto patrón de mis días en la Universidad. : D –

Su gramática es ambigua, si solo usa una única búsqueda anticipada. Para ilustrar, ¿qué es "asd"? Es un ExpressionTerm o un término más largo. Eso es un conflicto de cambio-reducción. Sospecho que aquí también hay un conflicto de reducción-reducción.

La mayoría de los generadores LL (1)/LALR (1) proporcionarán alguna forma de manejar el conflicto de cambio-reducción a través de operadores de precedencia. La mayoría también adoptará de forma predeterminada la secuencia más larga en presencia de un conflicto de desplazamiento-reducción, por lo que más de una vez se pueden ignorar (después de cierto escrutinio). (En este caso, tal vez necesite mover el término individual al final para que se comporte correctamente).

Fuente

2009-05-26 12:41:07 leppie

"asd" es simplemente una cadena literal "asd". –

Todavía no entiendo. AND y O deberían en este caso tener la misma precedencia. –

Con 1 carácter de anticipación, puede olvidarse de AND y OR. El conflicto es anterior :) – leppie

Shift-Reduce conflict significa que su gramática es ambigua. Con su regla recursiva, un token "asd" podría interpretarse como parte de ExpressionTerm o LogicalExpression y el analizador no puede decidir cuál. Necesita una regla adicional para romper el empate.

Fuente

2009-05-26 12:45:25 dwc

Los conflictos de reducción de turnos son una de las cosas más difíciles de manejar cuando se trata de analizadores sintácticos. La forma más fácil de ilustrar el conflicto es en este pseudo-código:

if (a) then 
    if (b) then 
    printf('a + b'); 
    else 
    print('this could be a + !b or !a');

La declaración más podría unirse a la primera o segunda si. En el caso de gramáticas ambiguas, generalmente se define un valor para indicar el número de advertencias de reducción de desplazamiento esperado en su gramática.

Como alternativa, puede usar un analizador LL (k) o LL (*). Estos tipos de analizadores no tienen la ambigüedad de cambio/reducción. Dependiendo de su aplicación, pueden ser más fáciles o más difíciles que el analizador LALR (1).

Fuente

2009-06-04 01:16:17 brianegge

gramática es ambigua en LL(1) o LALR(1) desde el símbolo asd puede ser sustituido en ExpressionTerm y también LogicalExpression aplanar las reglas gramaticales para resolver desplazamiento/reducción conflictos

Fuente

2013-09-08 13:22:16

Problema al resolver un conflicto shift-reduce en mi gramática

Respuesta

Cuestiones relacionadas