Gramática ambigua - Ambiguous grammar

En ciencias de la computación , 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 , mientras que una gramática inequívoca es una gramática libre de contexto para la cual cada cadena válida tiene una única derivación más a la izquierda. derivación o árbol de análisis. Muchos idiomas admiten tanto gramáticas ambiguas como inequívocas, mientras que algunos idiomas solo admiten gramáticas ambiguas. Cualquier lenguaje no vacío admite una gramática ambigua tomando una gramática inequívoca e introduciendo una regla o sinónimo duplicado (el único lenguaje sin gramáticas ambiguas es el lenguaje vacío). Un lenguaje que solo admite gramáticas ambiguas se denomina lenguaje intrínsecamente ambiguo , y existen lenguajes libres de contexto intrínsecamente ambiguos . 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 no deterministas inequívocas.

Para los lenguajes de programación de computadoras , la gramática de referencia es a menudo ambigua, debido a cuestiones como el problema de colgar else . 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 es inequívoca. 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 de

Lenguaje trivial

El ejemplo más simple es la siguiente gramática ambigua para el lenguaje trivial, que consta solo de la cadena vacía:

A → A | ε

… Lo que significa que una producción puede volver a ser ella misma o 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 la gramática inequívoca, que consiste en una sola regla de producción :

A → ε

… Lo que significa que la producción única solo puede producir la cadena vacía, que es la cadena única en el idioma.

De la misma manera, cualquier gramática para un lenguaje no vacío puede volverse ambigua agregando duplicados.

Cuerda 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 | Aa | ε

Estos corresponden a producir un árbol asociativo por la derecha (para la gramática inequívoca) o permitir la asociación tanto a la izquierda como a la derecha. Esto se detalla a continuación.

Adición y sustracción

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:

     A → A + A      A → A + A
     → a + A      → A + A + A (La primera A se reemplaza por A + A. Reemplazar la segunda A produciría una derivación similar)
     → a + A + A      → a + A + A
     → a + a + A      → a + a + A
     → a + a + a      → 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:

Derivaciones más a la izquierda jaredwf.svg

Sin embargo, el lenguaje que genera no es intrínsecamente ambiguo; la siguiente es una gramática no ambigua que genera el mismo idioma:

A → A + a | A - a | a

Colgando más

Artículo principal: colgando más

Un ejemplo común de ambigüedad en los lenguajes de programación de computadoras es el problema colgando else . En muchos idiomas, el elseen una instrucció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 libre de contexto.

Concretamente, en muchos idiomas se pueden escribir condicionales en dos formas válidas: la forma if-then y la forma if-then-else, en efecto, haciendo que la cláusula else sea opcional:

En una gramática que contiene las reglas 

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

pueden aparecer algunas estructuras de frases ambiguas. La expresion 

if a then if b then s else s2

se puede analizar como 

if a then begin if b then s end else s2

o como 

if a then begin if b then s else s2 end

dependiendo de si elseestá asociado con el primero ifo el segundo if.

Esto se resuelve de varias formas en diferentes idiomas. A veces, la gramática se modifica para que no sea ambigua, como al requerir una endifdeclaración o hacer elseobligatoria. 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, 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 es suficiente para indicar que la gramática es ambigua; solo 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 + A
A → 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

Solo la derivación anterior es la 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 posterior . Al menos, existen herramientas que implementan algún procedimiento de semidecisión para detectar la ambigüedad de las gramáticas libres de contexto.

La eficiencia del análisis gramatical libre de contexto está determinada por el autómata que lo acepta. Las gramáticas deterministas libres de contexto son aceptadas por autómatas de empuje deterministas y pueden analizarse en tiempo lineal, por ejemplo, mediante el analizador LR . Este es un subconjunto de las gramáticas libres de contexto que son aceptadas por el autómata pushdown y pueden analizarse en tiempo polinomial, por ejemplo, mediante el algoritmo CYK . Las gramáticas libres de contexto inequívocas pueden ser no deterministas.

Por ejemplo, el lenguaje de palíndromos pares en el alfabeto de 0 y 1 tiene la gramática libre de contexto inequívoca S → 0S0 | 1S1 | ε. Una cadena arbitraria de este lenguaje no se puede analizar sin leer primero todas sus letras, 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 semi-analizada. Sin embargo, eliminar la ambigüedad gramatical puede producir una gramática libre de 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 mediante el uso de restricciones de precedencia y asociatividad.

Idiomas intrínsecamente ambiguos

La existencia de lenguajes intrínsecamente ambiguos fue probada con el teorema de Parikh en 1961 por Rohit Parikh en un informe de investigación del MIT.

Si bien algunos lenguajes libres de contexto (el conjunto de cadenas que puede generar una gramática) tienen tanto gramáticas ambiguas como inequívocas, existen lenguajes libres de contexto para los que no puede existir una gramática libre de contexto inequívoca. Un ejemplo de un lenguaje intrínsecamente ambiguo es la unión de with . Este conjunto está libre de contexto, ya que la unión de dos lenguajes libres de contexto es siempre libre de contexto. Pero Hopcroft y Ullman (1979) dan una prueba de que no hay forma de analizar cadenas sin ambigüedades en el subconjunto común (no libre de contexto) .

Ver también

Referencias

  1. ^ Willem JM Levelt (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (1 de abril de 2008). "Análisis de estilo SPPF de los reconocedores de Earley" . Notas electrónicas en informática teórica . 203 (2): 53–67. doi : 10.1016 / j.entcs.2008.03.044 .
  3. ^ Tomita, Masaru. " Un algoritmo de análisis sin contexto aumentado eficiente ". Lingüística computacional 13.1-2 (1987): 31-46.
  4. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introducción a la teoría de autómatas, lenguajes y computación (2ª ed.). Addison-Wesley. Teorema 9.20, págs. 405–406. ISBN 0-201-44124-1.
  5. ^ 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), Reykjavik, Islandia . Apuntes de conferencias en informática . 5126 . Springer-Verlag. págs. 410–422. doi : 10.1007 / 978-3-540-70583-3_34 .
  6. ^ Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
  7. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introducción a la teoría de autómatas, lenguajes y computación (2ª ed.). Addison-Wesley. págs. 249-253. ISBN 0-201-44124-1.
  8. ^ Parikh, Rohit (enero de 1961). Dispositivos generadores de lenguaje . Informe de progreso trimestral, Laboratorio de Investigación de Electrónica, MIT.
  9. ↑ p.99-103, Sección 4.7

Notas

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.