Hispanopedia WikiEn 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 sintáctico por la izquierda . [ 1 ] [ 2 ] Todo lenguaje libre de contexto no vacío admite una gramática ambigua introduciendo, por ejemplo, una regla de duplicación. Un lenguaje que solo admite gramáticas ambiguas se denomina lenguaje inherentemente ambiguo . Las gramáticas libres de contexto deterministas son siempre no ambiguas y constituyen una subclase importante de las gramáticas no ambiguas; sin embargo, existen gramáticas no ambiguas no deterministas.
En los lenguajes de programación , la gramática de referencia suele ser ambigua debido a problemas como el del else colgante . Si existen, estas ambigüedades generalmente se resuelven añadiendo reglas de precedencia u otras reglas de análisis sintáctico sensibles al contexto , de modo que la gramática general de la frase sea inequívoca. Algunos algoritmos de análisis sintáctico (como Earley [ 3 ] o los analizadores GLR ) pueden generar conjuntos de árboles de análisis (o "bosques de análisis") a partir de cadenas sintácticamente ambiguas . [ 4 ]
Ejemplos
Lenguaje trivial
El ejemplo más sencillo es la siguiente gramática ambigua (con símbolo inicial A) para el lenguaje trivial que consiste únicamente en la cadena vacía:
- A → A | ε
... lo que significa que el no terminal A puede derivarse de sí mismo nuevamente o de la cadena vacía. Por lo tanto, la cadena vacía tiene derivaciones hacia la izquierda de longitud 1, 2, 3, e incluso de cualquier longitud, dependiendo de cuántas veces se utilice la regla A → A.
Este idioma también posee una gramática inequívoca, que consta de una única regla de producción :
- A → ε
... lo que significa que la producción única solo puede producir la cadena vacía, que es la única cadena en el lenguaje.
Del mismo modo, cualquier gramática para un lenguaje no vacío puede volverse ambigua añadiendo 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 no ambigua:
- A → aA | ε
... pero también tiene una gramática ambigua:
- A → aA | Aa | ε
Esto corresponde a generar un árbol asociativo derecho (para la gramática no ambigua) o a permitir asociaciones tanto izquierdas como derechas. Esto se explica con más detalle a continuación.
Suma y resta
La gramática libre de contexto
- A → A + A | A − A | a
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 existen dos árboles de análisis sintáctico 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:
- A → A + a | A − a | a
Colgando otra cosa
Un ejemplo común de ambigüedad en los lenguajes de programación es el problema del else colganteelse . En muchos lenguajes, el else en una instrucción If-then(-else) es opcional, lo que da como resultado que las condicionales anidadas tengan múltiples formas de ser reconocidas en términos de la gramática libre de contexto.
Concretamente, en muchos idiomas se pueden escribir condicionales de dos formas válidas: la forma if-then y la forma if-then-else, lo que en la práctica hace que la cláusula else sea opcional.
En una gramática que contiene las reglas [ a ]
Declaración → si Condición entonces Declaración | si Condición entonces Declaración sino Declaración | ... Condición → ...
Pueden aparecer algunas estructuras de frases ambiguas. La expresión
si a entonces si b entonces s sino s2
puede ser analizado como
Si a, entonces comienza; si b, entonces s, finaliza; de lo contrario , s2.
o como
si a entonces empezar si b entonces s sino s2 fin
dependiendo de si elseestá asociado con el primero ifo el segundo if.
Esto se resuelve de diversas maneras en distintos idiomas. A veces, la gramática se modifica para que sea inequívoca, por ejemplo, exigiendo una endifdeclaración o haciendo que sea elseobligatorio. En otros casos, la gramática se deja ambigua, pero la ambigüedad se resuelve haciendo que la gramática de la frase en su conjunto sea sensible al contexto, por ejemplo, asociando un elsecon el más cercano if. 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 basta para indicar que la gramática sea ambigua; solo las múltiples derivaciones más a la izquierda (o, equivalentemente, los múltiples árboles de análisis sintáctico) indican ambigüedad.
Por ejemplo, la gramática simple
S → A + A A → 0 | 1
es una gramática no ambigua 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
Solo la primera derivación es la más a la izquierda.
Reconocer gramáticas ambiguas
El problema de decisión sobre si una gramática arbitraria es ambigua es indecidible porque se puede demostrar que es equivalente al problema de correspondencia de Post . [ 5 ] Al menos, existen herramientas que implementan algún procedimiento de semidecisión para detectar la ambigüedad de las gramáticas libres de contexto. [ 6 ]
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 pila deterministas y pueden ser analizadas en tiempo lineal, por ejemplo, por un analizador LR . [ 7 ] Son un subconjunto estricto de las gramáticas libres de contexto , que son aceptadas por autómatas de pila y pueden ser analizadas en tiempo polinomial, por ejemplo, por el algoritmo CYK .
Las gramáticas libres de contexto no ambiguas 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 libre de contexto no ambigua S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no puede ser analizada sin leer primero todos sus símbolos, lo que significa que un autómata de pila tiene que intentar transiciones de estado alternativas para acomodar las diferentes longitudes posibles de una cadena semi-analizada. [ 8 ]
Sin embargo, eliminar la ambigüedad gramatical puede generar una gramática determinista libre de contexto y, por lo tanto, permitir un análisis sintáctico más eficiente. Los generadores de compiladores, como YACC, incluyen funciones para resolver ciertos tipos de ambigüedad, como el uso de restricciones de precedencia y asociatividad.
Lenguas inherentemente ambiguas
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 que no existe una gramática libre de contexto no ambigua. Dichos lenguajes se denominan inherentemente ambiguos .
No existen lenguajes regulares inherentemente ambiguos. [ 9 ] [ 10 ]
La existencia de lenguajes libres de contexto inherentemente ambiguos fue demostrada con el teorema de Parikh en 1961 por Rohit Parikh en un informe de investigación del MIT. [ 11 ]
El idiomaes inherentemente ambiguo. [ 12 ]
El lema de Ogden [ 13 ] se puede utilizar para demostrar que ciertos lenguajes libres de contexto, como, son inherentemente ambiguos. Véase el lema de Ogden § Ambigüedad inherente para una demostración.
La unión decones inherentemente ambiguo. Este conjunto es libre de contexto, ya que la unión de dos lenguajes libres de contexto siempre es libre de contexto. Pero Hopcroft y Ullman (1979) dan una prueba de que ninguna gramática libre de contexto para este lenguaje de unión puede analizar sin ambigüedad cadenas de forma. [ 14 ]
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. [ 15 ]
Véase también
- Analizador sintáctico GLR , un tipo de analizador sintáctico para gramáticas ambiguas y no deterministas.
- Analizador de gráficos , otro tipo de analizador para gramáticas ambiguas.
- Ambigüedad sintáctica
Citas
Notas
- ↑ El siguiente ejemplo utiliza la sintaxis de Pascal .
Referencias
- ↑ Willem JM Levelt (2008). Introducción a la teoría de los lenguajes formales y los autómatas . John Benjamins Publishing. ISBN 978-90-272-3250-2.
- ↑ Hopcroft, Motwani y Ullman 2006 , pág. 217.
- ↑ Scott, Elizabeth (1 de abril de 2008). "Análisis sintáctico al estilo SPPF a partir de reconocedores de Earley" . Electronic Notes in Theoretical Computer Science . 203 (2): 53– 67. doi : 10.1016/j.entcs.2008.03.044 .
- ↑ Tomita, Masaru. " Un algoritmo de análisis sintáctico aumentado y libre de contexto eficiente ". Lingüística computacional 13.1-2 (1987): 31-46.
- ^ Hopcroft, Motwani y Ullman 2006 , pág. 415, Teorema 9.20.
- ↑ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Análisis de gramáticas libres de contexto mediante un solucionador SAT incremental" (PDF) . Actas del 35.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP'08), Reikiavik, Islandia . Lecture Notes in Computer Science . Vol. 5126. Springer-Verlag. pp. 410–422 . doi : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6.
- ↑ Knuth, DE (julio de 1965). "Sobre la traducción de lenguas de izquierda a derecha". Information and Control . 8 (6): 607– 639. doi : 10.1016/S0019-9958(65)90426-2 .
- ↑ Hopcroft, Motwani y Ullman 2006 , págs. 254–6.
- ↑ Book, R.; Even, S.; Greibach, S.; Ott, G. (febrero de 1971). "Ambigüedad en grafos y expresiones" . IEEE Transactions on Computers . C-20 (2): 149–153 . doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .
- ↑ "Lenguajes formales: ¿Se pueden hacer inequívocas las expresiones regulares?" . MathOverflow . Consultado el 23 de febrero de 2023 .
- ↑ Parikh, Rohit (enero de 1961). Dispositivos generadores de lenguaje . Informe trimestral de progreso, Laboratorio de Investigación de Electrónica, MIT.
- ↑ Parikh, Rohit J. (1966-10-01). "Sobre lenguajes libres de contexto" . Journal of the ACM . 13 (4): 570– 581. doi : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 . Aquí: Teorema 3.
- ↑ Ogden, William (septiembre de 1968). "Un resultado útil para demostrar la ambigüedad inherente" . Mathematical Systems Theory . 2 (3): 191– 194. doi : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .
- ↑ Hopcroft y Ullman 1979 , págs. 99-103, Sec. 4.7.
- ↑ Fredérique Bassino y Cyril Nicaud (16 de diciembre de 2011). «Philippe Flajolet y la combinatoria analítica: ambigüedad inherente de los lenguajes libres de contexto» (PDF) . Archivado (PDF) del original el 25 de septiembre de 2022.
- Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
- Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª ed.). Addison-Wesley. ISBN 0-321-45536-3.
Lecturas adicionales
- Brabrand, Claus; Giegerich, Robert; Møller, Anders (marzo de 2010). "Análisis de la ambigüedad de las gramáticas libres de contexto". Science of Computer Programming . 75 (3). Elsevier: 176– 191. CiteSeerX 10.1.1.86.3118 . doi : 10.1016/j.scico.2009.11.002 .
- Gross, Maurice (septiembre de 1964). "Ambigüedad inherente de las gramáticas lineales mínimas" . Information and Control . 7 (3): 366– 368. doi : 10.1016/S0019-9958(64)90422-X .
- Harrison, Michael (1978). Introducción a la teoría del lenguaje formal . Addison-Wesley. ISBN 0201029553.
Enlaces externos
- dk.brics.grammar - un analizador de ambigüedad gramatical.
- CFGAnalyzer : herramienta para analizar gramáticas libres de contexto con respecto a la universalidad del lenguaje, la ambigüedad y propiedades similares.
- Lenguajes formales
- Ambigüedad
