En informática , una gramática ambigua es una gramática libre de contexto para la cual 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 no vacío y libre de contexto admite una gramática ambigua al introducir, por ejemplo, una regla de duplicación. Un lenguaje que sólo admite gramáticas ambiguas se llama lenguaje inherentemente ambiguo. Las gramáticas deterministas libres de contexto son siempre inequívocas y son una subclase importante de gramáticas inequívocas; Sin embargo, existen gramáticas inequívocas no deterministas.
Para los lenguajes de programación de computadoras , la gramática de referencia es a menudo ambigua, debido a problemas como el problema de colgar . Si están presentes, estas ambigüedades generalmente se resuelven agregando reglas de precedencia u otras reglas de análisis sensibles al contexto , por lo que la gramática general de la frase no es ambigua. [ cita necesaria ] Algunos algoritmos de análisis (como ( Earley [2] o 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 el símbolo inicial A) para el lenguaje trivial que consta únicamente de una cadena vacía:
…lo que significa que el no terminal A se puede derivar 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 consta de una única regla de producción :
…lo que significa que la producción única puede producir sólo la cadena vacía, que es la cadena única en el idioma.
De la misma manera, cualquier gramática de un lenguaje no vacío puede volverse ambigua agregando 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:
Esto corresponde a producir un árbol asociativo por la derecha (para la gramática inequívoca) o permitir la asociación tanto por la izquierda como por la derecha. Esto se detalla 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 idioma:
Un ejemplo común de ambigüedad en los lenguajes de programación de computadoras es el problema de lo demás . En muchos idiomas, la elsedeclaració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 gramática libre de contexto.
Concretamente, en muchos idiomas se pueden escribir condicionales en dos formas válidas: la forma si-entonces y la forma si-entonces-si no; de hecho, la cláusula else es opcional: [nota 1]
En una gramática que contiene las reglas.
Declaración → si Condición entonces Declaración | if Condición entonces Declaración else Declaración | ...Condición → ...
Pueden aparecer algunas estructuras de frases ambiguas. La expresion
si a entonces si b entonces s si no s2
se puede analizar como cualquiera
si a entonces comienza si b entonces s termina si no s2
o como
si a entonces comienza si b entonces s si no s2 finaliza
dependiendo de si elseestá asociado al primero ifo al segundo if.
Esto se resuelve de varias maneras en diferentes idiomas. A veces, la gramática se modifica para que no sea ambigua, como exigir una endifdeclaración o hacerla elseobligatoria. En otros casos, la gramática queda ambigua, pero la ambigüedad se resuelve haciendo que la gramática general de la frase sea sensible al contexto, como asociando an elsecon el if. En este último caso la gramática es inequívoca, pero la gramática libre de contexto es ambigua. [ se necesita aclaración ]
La existencia de múltiples derivaciones de la misma cadena no basta para indicar que la gramática es ambigua; sólo múltiples derivaciones más a la izquierda (o, de manera equivalente, múltiples árboles de análisis) indican ambigüedad.
Por ejemplo, la gramática simple
S → A + AUn → 0 | 1
es una gramática inequívoca para el idioma { 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 primera derivación es la que se encuentra 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 la correspondencia postal . [4] Al menos, existen herramientas que implementan algún procedimiento de semi-decisión para detectar la ambigüedad de gramáticas libres de contexto. [5]
La eficacia de analizar una gramática libre de contexto está determinada por el autómata que la acepta. Las gramáticas deterministas libres de contexto son aceptadas por autómatas pushdown 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 pushdown y pueden ser analizadas en tiempo polinómico, por ejemplo mediante el algoritmo CYK .
Las gramáticas inequívocas y libres de 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 y libre de contexto S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no se puede analizar sin leer primero todos sus símbolos, lo que significa que un autómata pushdown tiene que probar transiciones de estado alternativas para adaptarse a las diferentes longitudes posibles de una cadena semianalizada. [7]
Sin embargo, eliminar la ambigüedad gramatical puede producir una gramática determinista libre de contexto y así permitir un análisis más eficiente. Los generadores de compiladores como YACC incluyen funciones para resolver algunos tipos de ambigüedad, como 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 inequívocas, existen lenguajes libres de contexto para los cuales no puede existir una gramática libre de contexto inequívoca. Estos lenguajes se denominan inherentemente ambiguos .
No existen lenguajes regulares inherentemente ambiguos. [8] [9]
La existencia de lenguajes inherentemente ambiguos y libres de contexto fue demostrada con 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 libres de contexto, como , son inherentemente ambiguos. Consulte esta página para obtener una prueba.
La unión de con es inherentemente ambigua. Este conjunto está libre de contexto, ya que la unión de dos lenguajes libres de contexto siempre está libre de contexto. Pero Hopcroft y Ullman (1979) dan una prueba de que cualquier gramática libre de contexto para este lenguaje de unión no puede analizar cadenas de forma sin ambigüedades . [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]
