¿Por qué son malas las gramáticas ambiguas?

Entiendo que si existen 2 o más árboles de derivación izquierda o derecha, entonces la gramática es ambigua, pero no puedo entender por qué es tan malo que todos quieran deshacerse de ella.

Considere la siguiente gramática para las expresiones aritméticas:

Según el de la izquierda, debemos interpretar $a-b-c$ como $(a-b)-c$ , que es la interpretación habitual. De acuerdo con el de la derecha, debemos interpretarlo como $a-(b-c) = a-b+c$ , que probablemente no sea lo que se pretendía.

Al compilar un programa, queremos que la interpretación de la sintaxis sea inequívoca. La forma más fácil de hacer cumplir esto es usar una gramática inequívoca. Si la gramática es ambigua, podemos proporcionar reglas de desempate, como la precedencia del operador y la asociatividad. Estas reglas se pueden expresar de manera equivalente haciendo que la gramática sea inequívoca de una manera particular.

Analizar árboles generados con el generador de árbol de sintaxis .

En contraste con las otras respuestas existentes [ 1 , 2 ], de hecho hay un campo de aplicación, donde las gramáticas ambiguas son útiles . En el campo del procesamiento del lenguaje natural (PNL), cuando desea analizar el lenguaje natural (NL) con gramáticas formales, tiene el problema de que el NL es inherentemente ambiguo en diferentes niveles [adaptado de Koh18, cap. 6.4]:

• Ambuigia sintáctica:

  Peter persiguió al hombre en el auto deportivo rojo

  ¿Peter o el hombre del auto deportivo rojo?

• Ambigüedad semántica:

  Peter fue al banco

  ¿Un banco para sentarse o un banco para retirar dinero?

• Ambuigidad pragmática:

  Dos hombres llevaban dos bolsas

  ¿Llevaban las bolsas juntas o cada hombre llevaba dos bolsas?

Los diferentes enfoques para la PNL tratan de manera diferente el procesamiento en general y en particular estas ambigüedades. Por ejemplo, su tubería podría verse de la siguiente manera:

1. Parse NL con gramática ambigua
2. Para cada AST resultante: ejecute la generación de modelos para generar significados semánticos ambiguos y descartar ambigüedades sintácticas imposibles del paso 1
3. Para cada modelo resultante: guárdelo en su caché.

Haces esta tubería para cada oración. Mientras más texto, digamos, del mismo libro que procesas, más puedes descartar modelos superfluos imposibles, que sobrevivieron hasta el paso 3, de oraciones anteriores.

A diferencia del lenguaje de programación, podemos dejar de lado el requisito de que cada oración de NL tenga una semántica precisa. En cambio, podemos simplemente reservar múltiples modelos semánticos posibles a través del análisis de textos más grandes. De vez en cuando, las ideas posteriores nos ayudan a descartar ambigüedades anteriores.

Si desea ensuciarse las manos con los analizadores capaces de generar múltiples derivaciones para una gramática ambigua, eche un vistazo al Marco gramatical . Además, [Koh18, cap. 5] tiene una introducción que muestra algo similar a mi canalización anterior. Sin embargo, tenga en cuenta que dado que [Koh18] son ​​notas de clase, las notas podrían no ser tan fáciles de entender por sí mismas sin las clases.

Referencias

[Koh18]: Michael Kohlhase. "Procesamiento del lenguaje natural basado en la lógica. Semestre de invierno 2018/19. Notas de la conferencia". URL: https://kwarc.info/teaching/LBS/notes.pdf . URL de la descripción del curso: https://kwarc.info/courses/lbs/ (en alemán)

[Koh18, cap. 5]: Véase el capítulo 5, "Implementación de fragmentos: marcos gramaticales y lógicos", en [Koh18]

[Koh18, cap. 6.4] Ver capítulo 6.4, "El papel computacional de las ambigüedades", en [Koh18]

Incluso si hay una forma bien definida de manejar la ambigüedad (las expresiones ambiguas son errores de sintaxis, por ejemplo), estas gramáticas aún causan problemas. Tan pronto como introduce ambigüedad en una gramática, un analizador ya no puede estar seguro de que la primera coincidencia que obtiene es definitiva. Debe seguir intentando todas las otras formas de analizar una declaración, para descartar cualquier ambigüedad. Tampoco está tratando con algo simple como un lenguaje LL (1), por lo que no puede usar un analizador simple, pequeño y rápido. Su gramática tiene símbolos que se pueden leer de varias maneras, por lo que debe estar preparado para retroceder mucho.

En algunos dominios restringidos, es posible que pueda probar que todas las formas posibles de analizar una expresión son equivalentes (por ejemplo, porque representan una operación asociativa). (a + b) + c = a + (b + c).

¿El IF a THEN IF b THEN x ELSE ymedia

IF a THEN
    IF b THEN
        x
    ELSE
        y

o

IF a THEN
    IF b THEN x
ELSE
    y

? También conocido como el problema pendiente .

Tome el análisis más irritante en C ++, por ejemplo:

bar foo(foobar());

¿Es esta una declaración foode tipo de función bar(foobar())(el parámetro es un puntero de función que devuelve a foobar), o una declaración foode tipo variable inte inicializada con un valor predeterminado inicializado foobar?

Esto se diferencia en los compiladores asumiendo el primero, a menos que la expresión dentro de la lista de parámetros no se pueda interpretar como un tipo.

cuando obtienes una expresión tan ambigua, el compilador tiene 2 opciones

1. suponga que la expresión es una derivación particular y agregue un desambigador a la gramática para permitir que se exprese la otra derivación.

2. error y requiere desambiguación de cualquier manera

El primero puede caer naturalmente, el segundo requiere que el programador compilador conozca la ambigüedad.

Si esta ambigüedad permanece sin ser detectada, entonces es posible que 2 compiladores diferentes usen diferentes derivaciones para esa expresión ambigua. Lo que lleva a que el código no sea portátil por razones no obvias. Lo que lleva a la gente a asumir que es un error en uno de los compiladores, mientras que en realidad es un error en la especificación del lenguaje.

Creo que la pregunta contiene una suposición que solo es correcta en el mejor de los casos.

En la vida real es bastante común simplemente vivir con gramáticas ambiguas, siempre que no sean (por así decirlo) demasiado ambiguas.

Por ejemplo, si observa las gramáticas compiladas con yacc (o similares, como bison o byacc), encontrará algunas advertencias sobre "conflictos N shift / reduct" cuando las compila. Cuando yacc encuentra un cambio de desplazamiento / reducción, eso indica una ambigüedad en la gramática.

Sin embargo, un conflicto de cambio / reducción suele ser un problema bastante menor. El generador de analizadores resolverá el conflicto a favor del "cambio" en lugar de reducirlo. La gramática está perfectamente bien si eso es lo que quieres (y parece funcionar perfectamente en la práctica).

Un conflicto de desplazamiento / reducción generalmente surge en un caso en este orden general (usando mayúsculas para no terminales y minúsculas para terminales):

A -> B | c
B -> a | c

Cuando encontramos un c, hay una ambigüedad: ¿deberíamos analizar el cdirectamente como un A, o deberíamos analizarlo como un B, que a su vez es un A? En un caso como este, yacc y tal elegirán la ruta más simple / más corta y analizarán cdirectamente como una ruta A, en lugar de ir a la ruta c-> B-> A. Esto puede estar mal, pero si es así, probablemente significa que tiene un error realmente simple en su gramática, y no debe permitir la copción como una posibilidad A.

Ahora, por el contrario, podríamos tener algo más como esto:

A -> B | C
B -> a | c
C -> b | c

Ahora, cuando nos encontramos con un, ctenemos un conflicto entre si tratarlo ccomo a Bo a C. Hay muchas menos posibilidades de que una estrategia automática de resolución de conflictos elija lo que realmente queremos. Ninguno de estos es un "cambio": ambos son "reducciones", por lo que se trata de un "conflicto de reducción / reducción" (que los que están acostumbrados a YACC y en general reconocen como un problema mucho mayor que un conflicto de cambio / reducción).

Entonces, aunque no estoy seguro de ir tan lejos como para decir que alguien realmente agradece la ambigüedad en su gramática, al menos en algunos casos es lo suficientemente menor como para que a nadie realmente le importe mucho. En resumen, puede que les guste la idea de eliminar toda ambigüedad, pero no lo suficiente como para hacerlo siempre. Por ejemplo, una gramática pequeña y simple que contiene una ambigüedad menor puede ser preferible a una gramática más grande y compleja que elimine la ambigüedad (especialmente cuando entras en el ámbito práctico de generar realmente un analizador sintáctico a partir de la gramática y descubres que no es ambiguo) la gramática produce un analizador que no se ejecutará en su máquina de destino).