Gramática ambigua

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. Todo lenguaje no vacío y libre de contexto admite una gramática ambigua al introducir, por ejemplo, una regla duplicada. 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 ordenadores, la gramática de referencia suele ser ambigua, debido a cuestiones como el problema de los demás colgantes. 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. Algunos algoritmos de análisis (como los analizadores Earley o GLR) pueden generar conjuntos de árboles de análisis (o "bosques de análisis") a partir de cadenas que son sintácticamente ambiguas.

Ejemplos

Lenguaje trivial

El ejemplo más simple es la siguiente gramática ambigua (con el símbolo inicial A) para el lenguaje trivial que consta solo de una cadena vacía:

A → Un ε

…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:

A → ε

…lo que significa que la producción única puede producir solo 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.

Cadena unaria

El lenguaje regular de cadenas unarias de un carácter dado, digamos 'a' (la expresión regular a*), tiene la gramática inequívoca:

A → aA ⋅ ε

…pero también tiene la gramática ambigua:

A → aA Silencio Aa Silencio ε

Estos corresponden 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.

Suma y resta

La gramática libre de contexto

A → A + A TENCIÓN A − A TENCIÓN

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:

El lenguaje que genera, sin embargo, no es inherentemente ambiguo; La siguiente es una gramática no ambigua que genera el mismo idioma:

A → A + a ¦

Colgando más

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, el else en 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 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-else – de hecho, haciendo que la cláusula else sea opcional:

En una gramática que contiene las reglas

Declaración → si Estado entonces Declaración voca
 si Estado entonces Estado más Declaración voca
...
Condición →...

Pueden aparecer algunas estructuras de frases ambiguas. La expresion

si a entonces si b entonces s más s2

se puede analizar como cualquiera

si a entonces comenzar si b entonces s final más s2

o como

si a entonces comenzar si b entonces s más s2 final

dependiendo de si el else está asociado con el primer if o 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 requiriendo una declaración endif o haciendo que else sea obligatorio. 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 un else con el if más cercano. En este último caso la gramática es inequívoca, pero la gramática libre de contexto es ambigua.

Una gramática inequívoca con múltiples derivaciones

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 + A
A → 0 Silencio 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

Solo la derivación anterior es la que se encuentra más a la izquierda.

Reconocer gramáticas ambiguas

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 del Post. Al menos, existen herramientas que implementan algún procedimiento de semidecisión para detectar ambigüedades en gramáticas libres de contexto.

La eficiencia 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. Son un subconjunto estricto de gramáticas libres de contexto, que son aceptadas por autómatas pushdown y pueden analizarse 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.

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.

Lenguajes inherentemente ambiguos

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 libre de contexto inequívoca. Estos lenguajes se denominan intrínsecamente ambiguos.

No existen lenguajes regulares inherentemente ambiguos.

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.

El idioma ${fnfnfnfnfn}pfn}pfn}pfn}m}pf}m=accn}accH00}b^{m}b^{m} {mprime },{text{f}nf}n'm,m,m'gq 1}$ es inherentemente ambiguo.

La lema de Ogden se puede utilizar para demostrar que ciertos idiomas sin contexto, como ${displaystyle {a^{n}b}c^{m}Upm,ngeq 1}cup {m}b^{m}c^{n}$, son inherentemente ambiguos. Vea esta página para una prueba.

La unión de ${displaystyle {a^{n}b}c^{m}d^{m}mid} No, soy yo.$ con ${displaystyle {a^{n}b^ {m}d^{n}mid} No, soy yo.$ es inherentemente ambiguo. Este conjunto es libre de contexto, ya que la unión de dos idiomas libres de contexto es siempre libre de contexto. Pero Hopcroft & Ullman (1979) da una prueba de que cualquier gramática sin contexto para este lenguaje sindical no puede pareciosamente cadenas de forma ${displaystyle a^{n}b^ {n}c^{n}d^{n},(n]}$.

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.