En la teoría del lenguaje formal , una gramática libre de contexto ( GLC ) es una gramática formal cuyas reglas de producción se pueden aplicar a un símbolo no terminal independientemente de su contexto. En particular, en una gramática libre de contexto, cada regla de producción tiene la forma
con un único símbolo no terminal y una cadena de símbolos terminales y/o no terminales ( puede estar vacío). Independientemente de qué símbolos lo rodeen, el único símbolo no terminal del lado izquierdo siempre se puede reemplazar por en el lado derecho. Esto lo distingue de una gramática sensible al contexto , que puede tener reglas de producción en la forma con un símbolo no terminal y , , y cadenas de símbolos terminales y/o no terminales.
Una gramática formal es esencialmente un conjunto de reglas de producción que describen todas las cadenas posibles en un lenguaje formal determinado. Las reglas de producción son reemplazos simples. Por ejemplo, la primera regla en la imagen,
reemplaza con . Puede haber múltiples reglas de reemplazo para un símbolo no terminal dado. El lenguaje generado por una gramática es el conjunto de todas las cadenas de símbolos terminales que se pueden derivar, mediante aplicaciones repetidas de reglas, de algún símbolo no terminal particular ("símbolo de inicio"). Los símbolos no terminales se utilizan durante el proceso de derivación, pero no aparecen en su cadena de resultado final.
Los lenguajes generados por gramáticas libres de contexto se conocen como lenguajes libres de contexto (CFL). Diferentes gramáticas libres de contexto pueden generar el mismo lenguaje libre de contexto. Es importante distinguir las propiedades del lenguaje (propiedades intrínsecas) de las propiedades de una gramática particular (propiedades extrínsecas). La cuestión de la igualdad de lenguajes (¿dos gramáticas libres de contexto dadas generan el mismo lenguaje?) es indecidible .
Las gramáticas libres de contexto surgen en lingüística, donde se utilizan para describir la estructura de oraciones y palabras en un lenguaje natural , y fueron inventadas por el lingüista Noam Chomsky con este propósito. Por el contrario, en informática , a medida que aumentó el uso de conceptos definidos recursivamente, se utilizaron cada vez más. En una aplicación temprana, las gramáticas se utilizan para describir la estructura de los lenguajes de programación . En una aplicación más reciente, se utilizan en una parte esencial del lenguaje de marcado extensible (XML) llamada definición de tipo de documento . [2]
En lingüística, algunos autores utilizan el término gramática de estructura sintagmática para referirse a las gramáticas libres de contexto, por lo que las gramáticas de estructura sintagmática se distinguen de las gramáticas de dependencia . En informática, una notación popular para las gramáticas libres de contexto es la forma Backus–Naur o BNF.
Desde al menos la época del antiguo erudito indio Pāṇini , los lingüistas han descrito las gramáticas de las lenguas en términos de su estructura en bloques y han descrito cómo las oraciones se construyen recursivamente a partir de frases más pequeñas y, finalmente, palabras individuales o elementos de palabras. Una propiedad esencial de estas estructuras en bloques es que las unidades lógicas nunca se superponen. Por ejemplo, la oración:
se puede poner entre paréntesis lógicamente (con los metasímbolos lógicos [ ] ) de la siguiente manera:
Una gramática libre de contexto proporciona un mecanismo simple y matemáticamente preciso para describir los métodos por los cuales las frases en algún lenguaje natural se construyen a partir de bloques más pequeños, capturando la "estructura de bloques" de las oraciones de una manera natural. Su simplicidad hace que el formalismo sea susceptible a un estudio matemático riguroso. Las características importantes de la sintaxis del lenguaje natural, como la concordancia y la referencia , no son parte de la gramática libre de contexto, pero la estructura recursiva básica de las oraciones, la forma en que las cláusulas se anidan dentro de otras cláusulas y la forma en que las listas de adjetivos y adverbios son absorbidas por los sustantivos y verbos, se describe exactamente.
Las gramáticas libres de contexto son una forma especial de los sistemas Semi-Thue que en su forma general se remontan al trabajo de Axel Thue .
El formalismo de las gramáticas libres de contexto fue desarrollado a mediados de la década de 1950 por Noam Chomsky , [3] y también su clasificación como un tipo especial de gramática formal (a la que llamó gramáticas de estructura sintagmática ). [4] Algunos autores, sin embargo, reservan el término para gramáticas más restringidas en la jerarquía de Chomsky: gramáticas sensibles al contexto o gramáticas libres de contexto. En un sentido más amplio, las gramáticas de estructura sintagmática también se conocen como gramáticas de circunscripción. El rasgo definitorio de las gramáticas de estructura sintagmática es, por tanto, su adhesión a la relación de circunscripción, en oposición a la relación de dependencia de las gramáticas de dependencia . En el marco de la gramática generativa de Chomsky , la sintaxis del lenguaje natural se describía mediante reglas libres de contexto combinadas con reglas de transformación. [5]
La estructura de bloques fue introducida en los lenguajes de programación informática por el proyecto Algol (1957-1960), que, como consecuencia, también incluyó una gramática libre de contexto para describir la sintaxis Algol resultante. Esto se convirtió en una característica estándar de los lenguajes informáticos, y la notación para gramáticas utilizadas en descripciones concretas de lenguajes informáticos llegó a conocerse como forma Backus-Naur , en honor a dos miembros del comité de diseño del lenguaje Algol. [3] El aspecto de "estructura de bloques" que capturan las gramáticas libres de contexto es tan fundamental para la gramática que los términos sintaxis y gramática a menudo se identifican con reglas gramaticales libres de contexto, especialmente en informática. Las restricciones formales no capturadas por la gramática se consideran entonces parte de la "semántica" del lenguaje.
Las gramáticas independientes del contexto son lo suficientemente simples como para permitir la construcción de algoritmos de análisis eficientes que, para una cadena dada, determinan si se puede generar a partir de la gramática y cómo hacerlo. Un analizador sintáctico de Earley es un ejemplo de este tipo de algoritmo, mientras que los analizadores sintácticos LR y LL, ampliamente utilizados , son algoritmos más simples que se ocupan solo de subconjuntos más restrictivos de gramáticas independientes del contexto.
Una gramática libre de contexto G se define mediante la tupla de 4 , donde [6]
Una regla de producción en R se formaliza matemáticamente como un par , donde es un no terminal y es una cadena de variables y/o terminales; en lugar de utilizar la notación de pares ordenados , las reglas de producción generalmente se escriben utilizando un operador de flecha con como su lado izquierdo y β como su lado derecho: .
Se permite que β sea la cadena vacía y, en este caso, se acostumbra denotarlo por ε. La forma se denomina ε -producción. [7]
Es común enumerar todos los lados derechos del mismo lado izquierdo en la misma línea, usando | (la barra vertical ) para separarlos. Las reglas y pueden, por lo tanto, escribirse como . En este caso, y se denominan primera y segunda alternativas, respectivamente.
Para cualquier cadena , decimos que u produce directamente v , escrito como , si con y tales que y . Por lo tanto, v es un resultado de aplicar la regla a u .
Para cualquier cadena decimos que u produce v o v se deriva de u si hay un entero positivo k y cadenas tales que . Esta relación se denota como , o en algunos libros de texto. Si , la relación se cumple. En otras palabras, y son el cierre transitivo reflexivo (que permite que una cadena se produzca a sí misma) y el cierre transitivo (que requiere al menos un paso) de , respectivamente.
El lenguaje de una gramática es el conjunto
de todas las cadenas de símbolos terminales derivables del símbolo inicial.
Se dice que un lenguaje L es un lenguaje libre de contexto (CFL), si existe un CFG G , tal que .
Los autómatas pushdown no deterministas reconocen exactamente los lenguajes libres de contexto.
La gramática , con producciones
es independiente del contexto. No es apropiado ya que incluye una ε-producción. Una derivación típica en esta gramática es
Esto deja claro que el lenguaje es independiente del contexto, sin embargo, se puede demostrar que no es regular .
Si las producciones
se añaden, se obtiene una gramática libre de contexto para el conjunto de todos los palíndromos sobre el alfabeto { a , b } . [8]
El ejemplo canónico de una gramática independiente del contexto es la coincidencia de paréntesis, que es representativa del caso general. Hay dos símbolos terminales "(" y ")" y un símbolo no terminal S. Las reglas de producción son
La primera regla permite que el símbolo S se multiplique; la segunda regla permite que el símbolo S quede encerrado entre paréntesis coincidentes; y la tercera regla termina la recursión. [9]
Un segundo ejemplo canónico son dos tipos diferentes de paréntesis anidados coincidentes, descritos por las producciones:
con símbolos terminales [ ] ( ) y no terminal S.
En esa gramática se puede derivar la siguiente secuencia:
En una gramática independiente del contexto, podemos emparejar caracteres de la misma forma que lo hacemos con los corchetes . El ejemplo más simple:
Esta gramática genera el lenguaje que no es regular (según el lema de bombeo para lenguajes regulares ).
El carácter especial ε representa la cadena vacía. Al cambiar la gramática anterior a
En su lugar , obtenemos una gramática que genera el lenguaje . Esta se diferencia únicamente en que contiene la cadena vacía, mientras que la gramática original no la contenía.
Una gramática libre de contexto para el lenguaje que consta de todas las cadenas sobre {a,b} que contienen un número desigual de a y b:
Aquí, la T no terminal puede generar todas las cadenas con más a que b, la U no terminal genera todas las cadenas con más b que a y la V no terminal genera todas las cadenas con un número igual de a y b. Omitir la tercera alternativa en las reglas para T y U no restringe el lenguaje de la gramática.
Otro ejemplo de lenguaje no regular es . Es independiente del contexto, ya que se puede generar mediante la siguiente gramática independiente del contexto:
Las reglas de formación de los términos y fórmulas de la lógica formal se ajustan a la definición de gramática libre de contexto, excepto que el conjunto de símbolos puede ser infinito y puede haber más de un símbolo de inicio.
A diferencia de los paréntesis anidados y corchetes bien formados en la sección anterior, no existe una gramática libre de contexto para generar todas las secuencias de dos tipos diferentes de paréntesis, cada uno equilibrado por separado sin tener en cuenta al otro , donde los dos tipos no necesitan anidarse uno dentro del otro, por ejemplo:
o
El hecho de que este lenguaje no sea independiente del contexto se puede demostrar utilizando el lema de bombeo para lenguajes independientes del contexto y una prueba por contradicción, observando que todas las palabras de la forma deberían pertenecer al lenguaje. Este lenguaje pertenece en cambio a una clase más general y se puede describir mediante una gramática conjuntiva , que a su vez también incluye otros lenguajes no independientes del contexto, como el lenguaje de todas las palabras de la forma .
Toda gramática regular es libre de contexto, pero no todas las gramáticas libres de contexto son regulares. [10] La siguiente gramática libre de contexto, por ejemplo, también es regular.
Los terminales aquí son a y b , mientras que el único no terminal es S . El lenguaje descrito son todas las cadenas no vacías de s y s que terminan en .
Esta gramática es regular : ninguna regla tiene más de un no terminal en su lado derecho, y cada uno de estos no terminales está en el mismo extremo del lado derecho.
Toda gramática regular corresponde directamente a un autómata finito no determinista , por lo que sabemos que se trata de un lenguaje regular .
Usando barras verticales, la gramática anterior se puede describir de manera más concisa de la siguiente manera:
Una derivación de una cadena para una gramática es una secuencia de aplicaciones de reglas gramaticales que transforman el símbolo de inicio en la cadena. Una derivación demuestra que la cadena pertenece al lenguaje de la gramática.
Una derivación se determina completamente dando, para cada paso:
Para mayor claridad, normalmente también se proporciona la cadena intermedia.
Por ejemplo, con la gramática:
La cuerda
se puede derivar del símbolo de inicio S con la siguiente derivación:
A menudo se sigue una estrategia que elige de manera determinista el siguiente no terminal para reescribir:
Dada esta estrategia, una derivación está completamente determinada por la secuencia de reglas aplicadas. Por ejemplo, una derivación más a la izquierda de la misma cadena es
que se puede resumir como
Una derivación más a la derecha es:
que se puede resumir como
La distinción entre la derivación más a la izquierda y la más a la derecha es importante porque en la mayoría de los analizadores sintácticos la transformación de la entrada se define proporcionando un fragmento de código para cada regla gramatical que se ejecuta siempre que se aplica la regla. Por lo tanto, es importante saber si el analizador sintáctico determina una derivación más a la izquierda o más a la derecha porque esto determina el orden en el que se ejecutarán los fragmentos de código. Consulte, por ejemplo, los analizadores sintácticos LL y LR .
Una derivación también impone en cierto sentido una estructura jerárquica a la cadena que se deriva. Por ejemplo, si la cadena "1 + 1 + a" se deriva según la derivación más a la izquierda descrita anteriormente, la estructura de la cadena sería:
donde {...} S indica una subcadena reconocida como perteneciente a S . Esta jerarquía también puede verse como un árbol:
Este árbol se denomina árbol de análisis sintáctico o "árbol de sintaxis concreta" de la cadena, en contraste con el árbol de sintaxis abstracta . En este caso, las derivaciones que se presentan más a la izquierda y más a la derecha definen el mismo árbol de análisis sintáctico; sin embargo, existe otra derivación más a la derecha de la misma cadena.
que define una cadena con una estructura diferente
y un árbol de análisis diferente:
Sin embargo, tenga en cuenta que ambos árboles de análisis se pueden obtener mediante derivaciones tanto de la izquierda como de la derecha. Por ejemplo, el último árbol se puede obtener con la derivación de la izquierda de la siguiente manera:
Si una cadena en el lenguaje de la gramática tiene más de un árbol de análisis, entonces se dice que la gramática es una gramática ambigua . Estas gramáticas suelen ser difíciles de analizar porque el analizador no siempre puede decidir qué regla gramatical debe aplicar. Por lo general, la ambigüedad es una característica de la gramática, no del lenguaje, y se puede encontrar una gramática no ambigua que genere el mismo lenguaje libre de contexto. Sin embargo, hay ciertos lenguajes que solo pueden generarse mediante gramáticas ambiguas; dichos lenguajes se denominan lenguajes inherentemente ambiguos .
Toda gramática libre de contexto sin producción de ε tiene una gramática equivalente en forma normal de Chomsky y una gramática en forma normal de Greibach . "Equivalente" aquí significa que las dos gramáticas generan el mismo lenguaje.
La forma especialmente simple de las reglas de producción en las gramáticas de la forma normal de Chomsky tiene implicaciones tanto teóricas como prácticas. Por ejemplo, dada una gramática independiente del contexto, se puede utilizar la forma normal de Chomsky para construir un algoritmo de tiempo polinomial que decide si una cadena dada está en el lenguaje representado por esa gramática o no (el algoritmo CYK ).
Los lenguajes libres de contexto están cerrados bajo las distintas operaciones, es decir, si los lenguajes K y L son libres de contexto, también lo es el resultado de las siguientes operaciones:
No están cerrados bajo intersección general (y por lo tanto tampoco bajo complementación ) y diferencia de conjuntos. [15]
Los siguientes son algunos problemas decidibles sobre gramáticas libres de contexto.
El problema de análisis, que consiste en comprobar si una palabra dada pertenece al idioma dado por una gramática libre de contexto, se puede decidir utilizando uno de los siguientes algoritmos de análisis de propósito general:
Leslie G. Valiant demostró que el análisis sintáctico independiente del contexto para las gramáticas de forma normal de Chomsky se puede reducir a la multiplicación de matrices booleanas , heredando así su límite superior de complejidad de O ( n 2,3728639 ). [16] [17] [nota 1] Por el contrario, Lillian Lee ha demostrado que la multiplicación de matrices booleanas O ( n 3−ε ) se puede reducir al análisis sintáctico CFG O ( n 3−3ε ), estableciendo así algún tipo de límite inferior para este último. [18]
Un símbolo no terminal se denomina productivo o generador si existe una derivación para alguna cadena de símbolos terminales. se denomina alcanzable si existe una derivación para algunas cadenas de símbolos no terminales y terminales a partir del símbolo de inicio. se denomina inútil si es inalcanzable o improductivo. se denomina anulable si existe una derivación . Una regla se denomina ε-producción . Una derivación se denomina ciclo .
Se sabe que los algoritmos eliminan de una gramática dada, sin cambiar el lenguaje generado,
En particular, una alternativa que contenga un símbolo no terminal inútil puede eliminarse del lado derecho de una regla. Tales reglas y alternativas se denominan inútiles . [24]
En la gramática del ejemplo representado, la D no terminal es inalcanzable y E es improductiva, mientras que C → C provoca un ciclo. Por lo tanto, omitir las últimas tres reglas no cambia el lenguaje generado por la gramática, como tampoco lo hace omitir las alternativas "| Cc | Ee " del lado derecho de la regla para S .
Se dice que una gramática libre de contexto es apropiada si no tiene símbolos inútiles ni ε-producciones ni ciclos. [25] Combinando los algoritmos anteriores, cada gramática libre de contexto que no genere ε puede transformarse en una gramática apropiada débilmente equivalente .
Es decidible si una gramática dada es una gramática regular , [26] así como si es una gramática LL( k ) para un k ≥0 dado . [27] : 233 Si no se da k , el último problema es indecidible. [27] : 252
Dada una gramática libre de contexto, no es decidible si su lenguaje es regular, [28] ni si es un lenguaje LL( k ) para un k dado . [27] : 254
Existen algoritmos para decidir si el lenguaje de una gramática libre de contexto dada está vacío, así como si es finito. [29]
Algunas preguntas que son indecidibles para clases más amplias de gramáticas se vuelven decidibles para gramáticas libres de contexto; por ejemplo, el problema del vacío (si la gramática genera alguna cadena terminal), es indecidible para gramáticas sensibles al contexto , pero decidible para gramáticas libres de contexto.
Sin embargo, muchos problemas son indecidibles incluso para gramáticas libres de contexto; los más destacados se abordan a continuación.
Dado un CFG, ¿genera el lenguaje de todas las cadenas sobre el alfabeto de símbolos terminales utilizados en sus reglas? [30] [31]
Se puede demostrar una reducción de este problema a partir del conocido problema indecidible de determinar si una máquina de Turing acepta una entrada particular (el problema de la detención ). La reducción utiliza el concepto de un historial de cómputo , una cadena que describe un cómputo completo de una máquina de Turing . Se puede construir un CFG que genere todas las cadenas que no aceptan historiales de cómputo para una máquina de Turing particular en una entrada particular y, por lo tanto, aceptará todas las cadenas solo si la máquina no acepta esa entrada.
Dados dos CFG, ¿generan el mismo lenguaje? [31] [32]
La indecidibilidad de este problema es una consecuencia directa del anterior: es imposible siquiera decidir si un CFG es equivalente al CFG trivial que define el lenguaje de todas las cadenas.
Dados dos CFG, ¿puede el primero generar todas las cadenas que el segundo puede generar? [31] [32]
Si este problema fuera decidible, entonces la igualdad de lenguaje también podría decidirse: dos CFG y generan el mismo lenguaje si es un subconjunto de y es un subconjunto de .
Utilizando el teorema de Greibach , se puede demostrar que los dos problemas siguientes son indecidibles:
Dado un CFG, ¿es ambiguo ?
La indecidibilidad de este problema se deriva del hecho de que si existiera un algoritmo para determinar la ambigüedad, se podría resolver el problema de correspondencia de Post , que se sabe que es indecidible. [33] Esto se puede demostrar mediante el lema de Ogden . [34]
Dados dos CFG, ¿hay alguna cadena derivable de ambas gramáticas?
Si este problema fuera decidible, el indecidible problema de correspondencia posterior (PCP) también podría resolverse: dadas cadenas sobre algún alfabeto , sea que la gramática consista en la regla
donde denota la cadena invertida y no aparece entre los ; y deje que la gramática consista en la regla
Entonces, la instancia PCP dada por tiene una solución si y solo si y comparten una cadena derivable. El lado izquierdo de la cadena (antes de ) representará la parte superior de la solución para la instancia PCP, mientras que el lado derecho será la parte inferior a la inversa.
Una forma obvia de extender el formalismo gramatical libre de contexto es permitir que los no terminales tengan argumentos, cuyos valores se transmiten dentro de las reglas. Esto permite que las características del lenguaje natural, como la concordancia y la referencia , y los análogos del lenguaje de programación, como el uso y la definición correctos de los identificadores, se expresen de forma natural. Por ejemplo, ahora podemos expresar fácilmente que en oraciones en inglés, el sujeto y el verbo deben concordar en número. En informática, los ejemplos de este enfoque incluyen gramáticas de afijos , gramáticas de atributos , gramáticas indexadas y gramáticas de dos niveles de Van Wijngaarden . Existen extensiones similares en lingüística.
Una gramática libre de contexto extendida (o gramática regular de la parte derecha ) es aquella en la que se permite que el lado derecho de las reglas de producción sea una expresión regular sobre los terminales y no terminales de la gramática. Las gramáticas libres de contexto extendidas describen exactamente los lenguajes libres de contexto. [35]
Otra extensión es permitir que aparezcan símbolos terminales adicionales en el lado izquierdo de las reglas, lo que restringe su aplicación. Esto produce el formalismo de las gramáticas sensibles al contexto .
Hay una serie de subclases importantes de las gramáticas libres de contexto:
El análisis LR extiende el análisis LL para admitir una gama más amplia de gramáticas; a su vez, el análisis LR generalizado extiende el análisis LR para admitir gramáticas arbitrarias libres de contexto. En gramáticas LL y gramáticas LR, esencialmente realiza análisis LL y análisis LR, respectivamente, mientras que en gramáticas no deterministas, es tan eficiente como se puede esperar. Aunque el análisis GLR se desarrolló en la década de 1980, muchas definiciones de lenguaje nuevas y generadores de analizadores continúan basándose en el análisis LL, LALR o LR hasta el día de hoy.
Chomsky inicialmente esperaba superar las limitaciones de las gramáticas libres de contexto agregando reglas de transformación . [4]
Estas reglas son otro recurso habitual en la lingüística tradicional; por ejemplo, la pasivización en inglés. Gran parte de la gramática generativa se ha dedicado a encontrar formas de refinar los mecanismos descriptivos de la gramática de estructura sintagmática y las reglas de transformación de modo que se puedan expresar exactamente los tipos de cosas que el lenguaje natural realmente permite. Permitir transformaciones arbitrarias no cumple ese objetivo: son demasiado poderosas, siendo completas en el sentido de Turing a menos que se añadan restricciones significativas (por ejemplo, no se permiten transformaciones que introduzcan y luego reescriban símbolos de una manera libre de contexto).
La posición general de Chomsky respecto de la no independencia del contexto del lenguaje natural se ha mantenido desde entonces, [36] aunque sus ejemplos específicos respecto de la insuficiencia de las gramáticas libres de contexto en términos de su débil capacidad generativa fueron refutados posteriormente. [37] Gerald Gazdar y Geoffrey Pullum han argumentado que a pesar de unas pocas construcciones no libres de contexto en el lenguaje natural (como las dependencias entre series en el alemán suizo [36] y la reduplicación en el bambara [38] ), la gran mayoría de las formas en el lenguaje natural son, de hecho, libres de contexto. [37]
construcción que pueda describirse mediante una expresión regular puede describirse mediante una gramática [libre de contexto], pero no viceversa.