En informática , una gramática ambigua es una gramática libre de contexto para la que existe una cadena que puede tener más de una derivación o árbol de análisis más a la izquierda . [1] Todo lenguaje libre de contexto no vacío admite una gramática ambigua introduciendo, por ejemplo, una regla de duplicado. Un lenguaje que solo admite gramáticas ambiguas se denomina lenguaje inherentemente ambiguo. Las gramáticas libres de contexto deterministas siempre son inequívocas y son una subclase importante de gramáticas inequívocas; sin embargo, existen gramáticas inequívocas no deterministas.
En el caso de los lenguajes de programación informática , la gramática de referencia suele ser ambigua debido a problemas como el problema de los else pendientes . Si están presentes, estas ambigüedades se resuelven generalmente añadiendo reglas de precedencia u otras reglas de análisis sensibles al contexto , de modo que la gramática general de la frase sea inequívoca. [ cita requerida ] Algunos algoritmos de análisis (como Earley [2] o los analizadores GLR ) pueden generar conjuntos de árboles de análisis (o "bosques de análisis") a partir de cadenas que son sintácticamente ambiguas . [3]
El ejemplo más simple es la siguiente gramática ambigua (con símbolo de inicio A) para el lenguaje trivial que consta únicamente de la cadena vacía:
…lo que significa que el no terminal A puede derivarse a sí mismo nuevamente o a la cadena vacía. Por lo tanto, la cadena vacía tiene derivaciones más a la izquierda de longitud 1, 2, 3 y, de hecho, de cualquier longitud, dependiendo de cuántas veces se use la regla A → A.
Este lenguaje también tiene una gramática inequívoca, que consiste en una única regla de producción :
…lo que significa que la producción única solo puede producir la cadena vacía, que es la cadena única en el lenguaje.
De la misma manera, cualquier gramática de un idioma no vacío puede volverse ambigua al agregarle duplicados.
El lenguaje regular de cadenas unarias de un carácter dado, digamos 'a'(la expresión regular a*), tiene la gramática inequívoca:
…pero también tiene la gramática ambigua:
Estos corresponden a la producción de un árbol asociativo por la derecha (para la gramática inequívoca) o a la posibilidad de permitir la asociación tanto por la izquierda como por la derecha. Esto se explica a continuación.
La gramática libre de contexto
es ambiguo ya que hay dos derivaciones más a la izquierda para la cadena a + a + a:
Como otro ejemplo, la gramática es ambigua ya que hay dos árboles de análisis para la cadena a + a − a:
Sin embargo, el lenguaje que genera no es inherentemente ambiguo; la siguiente es una gramática no ambigua que genera el mismo lenguaje:
Un ejemplo común de ambigüedad en los lenguajes de programación informática es el problema de los else pendienteselse . En muchos lenguajes, el in de una declaración If–then(–else) es opcional, lo que da como resultado que los condicionales anidados tengan múltiples formas de ser reconocidos en términos de la gramática independiente del contexto.
Concretamente, en muchos lenguajes se pueden escribir condicionales en dos formas válidas: la forma if-then y la forma if-then-else – haciendo que la cláusula else sea opcional: [nota 1]
En una gramática que contiene las reglas
Declaración → si Condición entonces Declaración | si Condición entonces Declaración else Declaración | ...Condición → ...
Pueden aparecer algunas estructuras de frases ambiguas. La expresión
Si a entonces si b entonces s de lo contrario s2
se puede analizar como
Si a entonces comienza Si b entonces s termina De lo contrario s2
o como
Si a entonces comienza Si b entonces s De lo contrario s2 Fin
dependiendo de si elseestá asociado con el primero ifo el segundo if.
Esto se resuelve de varias maneras en diferentes idiomas. A veces, la gramática se modifica para que no sea ambigua, como por ejemplo, al requerir una endifdeclaración o hacer elseque sea obligatoria. En otros casos, la gramática se deja ambigua, pero la ambigüedad se resuelve haciendo que la gramática general de la frase sea sensible al contexto, como por ejemplo, asociando an elsecon el if. En este último caso, la gramática es inequívoca, pero la gramática libre del contexto es ambigua. [ aclaración necesaria ]
La existencia de múltiples derivaciones de la misma cadena no es suficiente para indicar que la gramática es ambigua; sólo múltiples derivaciones más a la izquierda (o, equivalentemente, múltiples árboles de análisis) indican ambigüedad.
Por ejemplo, la gramática simple
S → A + AA → 0 | 1
es una gramática inequívoca para el lenguaje { 0+0, 0+1, 1+0, 1+1 }. Si bien cada una de estas cuatro cadenas tiene solo una derivación más a la izquierda, tiene dos derivaciones diferentes, por ejemplo
S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0
y
S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0
Sólo la derivación anterior es la más a la izquierda.
El problema de decisión de si una gramática arbitraria es ambigua es indecidible porque se puede demostrar que es equivalente al problema de correspondencia posterior . [4] Al menos, existen herramientas que implementan algún procedimiento de semidecisión para detectar la ambigüedad de gramáticas libres de contexto. [5]
La eficiencia del análisis de una gramática libre de contexto está determinada por el autómata que la acepta. Las gramáticas libres de contexto deterministas son aceptadas por autómatas de inserción deterministas y pueden analizarse en tiempo lineal, por ejemplo, mediante un analizador LR . [6] Son un subconjunto estricto de las gramáticas libres de contexto , que son aceptadas por autómatas de inserción y pueden analizarse en tiempo polinomial, por ejemplo, mediante el algoritmo CYK .
Las gramáticas inequívocas e independientes del contexto pueden ser no deterministas. Por ejemplo, el lenguaje de palíndromos de longitud par en el alfabeto de 0 y 1 tiene la gramática inequívoca e independiente del contexto S → 0S0 | 1S1 | ε. No se puede analizar una cadena arbitraria de este lenguaje sin leer primero todos sus símbolos, lo que significa que un autómata de inserción tiene que probar transiciones de estado alternativas para adaptarse a las diferentes longitudes posibles de una cadena semianalizada. [7]
Sin embargo, la eliminación de la ambigüedad gramatical puede producir una gramática independiente del contexto determinista y, por lo tanto, permitir un análisis sintáctico más eficiente. Los generadores de compiladores como YACC incluyen funciones para resolver algunos tipos de ambigüedad, como por ejemplo mediante el uso de restricciones de precedencia y asociatividad.
Si bien algunos lenguajes libres de contexto (el conjunto de cadenas que puede generar una gramática) tienen gramáticas tanto ambiguas como no ambiguas, existen lenguajes libres de contexto para los cuales no puede existir una gramática no ambigua libre de contexto. Dichos lenguajes se denominan inherentemente ambiguos .
No existen lenguajes regulares inherentemente ambiguos. [8] [9]
La existencia de lenguajes inherentemente ambiguos e independientes del contexto fue demostrada mediante el teorema de Parikh en 1961 por Rohit Parikh en un informe de investigación del MIT. [10]
El lenguaje es inherentemente ambiguo. [11]
El lema de Ogden [12] se puede utilizar para demostrar que ciertos lenguajes independientes del contexto, como , son inherentemente ambiguos. Consulte esta página para obtener una prueba.
La unión de with es inherentemente ambigua. Este conjunto es independiente del contexto, ya que la unión de dos lenguajes independientes del contexto siempre es independiente del contexto. Pero Hopcroft y Ullman (1979) dan una prueba de que cualquier gramática independiente del contexto para este lenguaje de unión no puede analizar sin ambigüedades cadenas de la forma . [13]
Bassino y Nicaud (2011) ofrecen más ejemplos y una revisión general de las técnicas para demostrar la ambigüedad inherente de los lenguajes libres de contexto. [14]
