Gramática ambigua

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de noviembre de 2014; las comprobaciones requieren 5 ediciones .

En informática , una gramática ambigua es una gramática formal que puede generar una cadena dada en más de una forma (es decir, hay más de un árbol de análisis para una cadena). Se dice que una lengua es esencialmente ambigua si sólo puede ser generada por gramáticas ambiguas.

Las gramáticas de algunos lenguajes de programación son ambiguas. Al analizar dichos idiomas, se debe tener en cuenta la información semántica para seleccionar la variante correcta. Por ejemplo, en lenguaje C la siguiente entrada:

x*y;

puede interpretarse como:

declarando un identificador y de tipo puntero -a- x, o
una expresión en la que xse multiplica por yy el resultado se ignora.

Para elegir entre estas interpretaciones, el compilador debe consultar su tabla de símbolos para ver si la declaración xera un nombre typedef en un ámbito determinado.

Ejemplo

gramática libre de contexto

A → A + A | UN − UN | a

es ambiguo, ya que hay dos salidas a la izquierda para la cadena a + a + a:

A	→A+A	A	→A+A
	→ un+A		→A+A+A
	→ a+A+A		→ a+A+A
	→ a+a+A		→ a+a+A
	→ un + un + un		→ un + un + un

Además, la gramática es ambigua porque hay dos árboles de análisis para la cadena a + a − a:

Sin embargo, el lenguaje que genera no es esencialmente ambiguo, ya que la siguiente gramática inequívoca genera el mismo lenguaje:

A → A + A | un - un | a

Reconocimiento de gramática ambigua

El problema general de determinar si una gramática es ambigua es algorítmicamente indecidible . No puede haber un algoritmo que determine la ambigüedad de una gramática, ya que el problema de correspondencia irresoluble de Post se reduce a un problema de ambigüedad.

Hay una dificultad obvia en analizar una gramática ambigua con un analizador determinista , pero el análisis no determinista da como resultado una pérdida significativa de eficiencia. La mayoría de las construcciones que requieren análisis sintáctico pueden reconocerse mediante gramáticas inequívocas. Algunas gramáticas ambiguas se pueden convertir en gramáticas no ambiguas, pero no existe un procedimiento general para esta conversión, al igual que no existe un algoritmo para determinar la ambigüedad de una gramática. Los generadores de compiladores , como YACC , son capaces de eliminar la ambigüedad de ciertos tipos, por ejemplo, mediante el uso de restricciones de precedencia y asociatividad .

Idiomas significativamente ambiguos

Si bien algunos idiomas (conjuntos de cadenas generados por una gramática) tienen gramáticas tanto inequívocas como ambiguas, hay idiomas para los que no existe una gramática inequívoca. Un ejemplo de un lenguaje esencialmente ambiguo es la unión de y . Es un lenguaje libre de contexto como una amalgama de lenguajes libres de contexto, pero Introducción a la teoría de los autómatas... contiene pruebas de que no es posible analizar cadenas de manera única en el subconjunto (no libre de contexto) que es la intersección de los dos idiomas ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\))$ $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\))$

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami