Problema resolver un desplazamiento y reducción de conflictos en mi gramática

Question

Estoy tratando de escribir un pequeño analizador con Ironía . Por desgracia consigo un "desplazamiento y reducción de conflictos". Gramáticas no son mi punto fuerte, y sólo necesitan para hacer esta pequeña cosita hecho. Aquí está la reducción de la gramática que produce el error:

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

¿Qué significa el "desplazamiento y reducción de conflictos" significa y cómo puedo solucionarlo? Tengo entendido que significa que mi gramática es ambigua, pero no puede torcer mi lógica 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:. Se olvidó de 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 Y u O para ser más fuerte que el otro (que había inteded de todos modos). Pero ahora veo que aparece el error incluso si hay un solo 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

para ser analizada a esto:

(asd OR asd) OR asd

¿Cuál es la forma no 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 ")"

Esta analiza todas las expresiones booleanas, la precedencia de los operadores como NOT-> AND> OR. "Asd" puede ser sustituida por la expresión destinada a sus términos.

Answer 1

Su gramática es ambigua, si sólo utiliza una sola búsqueda hacia delante. Para ilustrar esto, lo que es "asd"? ¿Es una ExpressionTerm o un plazo más largo. Eso es por desplazamiento y reducción de conflictos. Sospecho que un conflicto de reducción-reducción también en este caso.

La mayoría de LL (1) / LALR (1) generadores proporcionará alguna forma de lidiar con el conflicto de reducción por desplazamiento a través de los operadores de precedencia. La mayoría también por defecto en la secuencia más larga en presencia de un conflicto de reducción por desplazamiento, por lo que más que a menudo estos pueden ser ignorados (después de un escrutinio). (En este caso, tal vez usted necesita para mover el único término para la parte inferior para que se comporte correctamente).

Answer 2

desplazamiento y reducción de conflictos significa que su gramática es ambigua. Con su regla recursiva una ficha "asd" podría interpretarse como parte de cualquiera de ExpressionTerm o LogicalExpression y el analizador no puede decidir cuál. Necesitará una regla adicional para romper el empate.

Answer 3

Shift reducir los conflictos son una de las cosas más difíciles de conseguir que su cerebro alrededor cuando se trata de programas de análisis. La forma más fácil para 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 las gramáticas ambiguas, por lo general, definir un valor para indicar el número de espera por desplazamiento y reducción advertencias en su gramática.

Como alternativa, se puede utilizar un LL (k) o LL (*) analizador. Estos tipos de programas de análisis no tienen el desplazamiento / reducción ambigüedad. Dependiendo de la aplicación pueden ser más fácil o más difícil que el (1) analizador LALR.

Answer 4

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