En la teoría del lenguaje formal , una gramática libre de contexto ( CFG ) 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 terminales y/o no terminales ( puede estar vacío). Independientemente de los símbolos que lo rodeen, el único no terminal del lado izquierdo siempre se puede reemplazar por el del lado derecho. Esto la 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 simples reemplazos. Por ejemplo, la primera regla de la imagen,
reemplaza con . Puede haber múltiples reglas de reemplazo para un símbolo no terminal determinado. El lenguaje generado por una gramática es el conjunto de todas las cadenas de símbolos terminales que pueden derivarse, mediante aplicaciones repetidas de reglas, de algún símbolo no terminal particular ("símbolo inicial"). Los símbolos no terminales se utilizan durante el proceso de derivación, pero no aparecen en la 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 de la lengua (propiedades intrínsecas) de las propiedades de una gramática particular (propiedades extrínsecas). La cuestión de la igualdad lingüística (¿dos gramáticas dadas libres de contexto generan el mismo lenguaje?) es indecidible .
Las gramáticas libres de contexto surgen en la 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 fin. Por el contrario, en informática , a medida que aumentó el uso de conceptos definidos recursivamente, se utilizaron cada vez más. En una de las primeras aplicaciones, las gramáticas se utilizan para describir la estructura de los lenguajes de programación . En una aplicación más nueva, se utilizan en una parte esencial del lenguaje de marcado extensible (XML) denominada definición de tipo de documento . [2]
En lingüística, algunos autores utilizan el término gramática de estructura de frase para referirse a gramáticas libres de contexto, por lo que las gramáticas de estructura de frase se distinguen de las gramáticas de dependencia . En informática, una notación popular para gramáticas libres de contexto es la forma Backus-Naur , o BNF.
Al menos desde 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 de bloques y han descrito cómo las oraciones se construyen de forma recursiva a partir de frases más pequeñas y, finalmente, palabras individuales o elementos de palabras. Una propiedad esencial de estas estructuras de bloques es que las unidades lógicas nunca se superponen. Por ejemplo, la frase:
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 mediante 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 forma natural. Su simplicidad hace que el formalismo sea susceptible de un estudio matemático riguroso. Las características importantes de la sintaxis del lenguaje natural, como la concordancia y la referencia , no forman parte de la gramática libre de contexto, sino de 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 se ubican las listas de adjetivos y adverbios. tragado por sustantivos y verbos, se describe exactamente.
Las gramáticas libres de contexto son una forma especial de 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 los años 1950 por Noam Chomsky , [3] y también su clasificación como un tipo especial de gramática formal (a las 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 de frases también se conocen como gramáticas de circunscripciones. El rasgo definitorio de las gramáticas de estructura sintagmática es, por tanto, su adherencia a la relación de circunscripción, a diferencia de 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 mediante el proyecto Algol (1957-1960), que, como consecuencia, también incluía 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 las gramáticas utilizadas en descripciones concretas de lenguajes informáticos pasó 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 libres de contexto son lo suficientemente simples como para permitir la construcción de algoritmos de análisis eficientes que, para una cadena determinada, determinan si se puede generar a partir de la gramática y cómo. Un analizador Earley es un ejemplo de tal algoritmo, mientras que los analizadores LR y LL ampliamente utilizados son algoritmos más simples que tratan sólo con subconjuntos más restrictivos de gramáticas libres de contexto.
Una gramática G libre de contexto está definida por la 4- tupla , 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 su lado izquierdo y β como su lado derecho: .
Se permite que β sea la cadena vacía , y en este caso se acostumbra denotarla con ε. La forma se llama ε -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. Reglas y, por tanto, puede escribirse como . En este caso, y se denominan primera y segunda alternativa, respectivamente.
Para cualquier cadena , decimos que u produce directamente v , escrito como , if with y tal que y . Por tanto, v es el 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 , o en algunos libros de texto. Si , la relación se mantiene. En otras palabras, y son el cierre transitivo reflexivo (que permite que una cadena ceda por 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
está libre de 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 no tiene contexto, sin embargo, se puede demostrar que no es regular .
Si las producciones
se agregan, 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 libre de contexto es la coincidencia entre 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 recursividad. [9]
Un segundo ejemplo canónico son dos tipos diferentes de paréntesis anidados coincidentes, descritos por las producciones:
con símbolos terminales [ ] ( ) y S no terminal.
La siguiente secuencia se puede derivar de esa gramática:
En una gramática libre de contexto, podemos emparejar caracteres como 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 . Esto sólo difiere 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 el mismo número 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 . Está libre de contexto ya que puede generarse mediante la siguiente gramática libre de 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 inicial.
A diferencia de los paréntesis anidados y corchetes bien formados de 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 el otro , donde los dos tipos no necesitan anidarse dentro de uno. otro, por ejemplo:
o
El hecho de que este lenguaje no está libre de contexto se puede probar usando un lema de bombeo para lenguajes libres de contexto y una prueba por contradicción, observando que todas las palabras de la forma deben pertenecer al idioma. Este lenguaje pertenece, en cambio, a una clase más general y puede describirse mediante una gramática conjuntiva , que a su vez también incluye otros lenguajes no libres de contexto, como el lenguaje de todas las palabras de la forma .
Toda gramática normal está 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.
Las 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.
Cada 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 inicial en la cadena. Una derivación demuestra que la cadena pertenece al idioma de la gramática.
Una derivación se determina completamente dando, para cada paso:
Para mayor claridad, generalmente también se proporciona la cadena intermedia.
Por ejemplo, con la gramática:
la cuerda
se puede derivar del símbolo inicial S con la siguiente derivación:
A menudo, se sigue una estrategia que elige de manera determinista el siguiente no terminal a reescribir:
Dada una estrategia de este tipo, la 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 derivación más a la izquierda y derivación más a la derecha es importante porque en la mayoría de los analizadores la transformación de la entrada se define dando un fragmento de código para cada regla gramatical que se ejecuta cada vez que se aplica la regla. Por lo tanto, es importante saber si el analizador 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 las piezas de código. Consulte para ver un ejemplo de analizadores LL y analizadores LR .
Una derivación también impone en cierto sentido una estructura jerárquica en 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 o "árbol de sintaxis concreta" de la cadena, en contraste con el árbol de sintaxis abstracta . En este caso, las derivaciones presentadas más a la izquierda y más a la derecha definen el mismo árbol de análisis; sin embargo, hay 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 a la izquierda como a la derecha. Por ejemplo, el último árbol se puede obtener con la derivación más a 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 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 inequívoca que genere el mismo lenguaje libre de contexto. Sin embargo, hay ciertos lenguajes que sólo pueden generarse mediante gramáticas ambiguas; estos lenguajes se denominan lenguajes inherentemente ambiguos .
Cada gramática libre de contexto sin producción ε 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 forma normal de Chomsky tiene implicaciones tanto teóricas como prácticas. Por ejemplo, dada una gramática libre de contexto, se puede utilizar la forma normal de Chomsky para construir un algoritmo de tiempo polinomial que decide si una cadena determinada está en el lenguaje representado por esa gramática o no (el algoritmo CYK ).
Los lenguajes libres de contexto se cierran bajo las diversas operaciones, es decir, si los lenguajes K y L están libres de contexto, también lo será el resultado de las siguientes operaciones:
No están cerrados bajo intersección general (por lo tanto, tampoco bajo complementación ) y establecen diferencia. [15]
Los siguientes son algunos problemas decidibles sobre gramáticas libres de contexto.
El problema de análisis, comprobar si una palabra dada pertenece al lenguaje dado por una gramática libre de contexto, se puede resolver utilizando uno de los algoritmos de análisis de propósito general:
Leslie G. Valiant demostró que el análisis sin contexto de las gramáticas de forma normal de Chomsky es reducible 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−ε ) es reducible al análisis CFG de O ( n 3−3ε ), estableciendo así algún tipo de límite inferior para este último. . [18]
Un símbolo no terminal se llama productivo o generador si existe una derivación para alguna cadena de símbolos terminales. se llama alcanzable si hay una derivación para algunas cadenas de símbolos terminales y no terminales desde el símbolo inicial. se llama inútil si es inalcanzable o improductivo. se llama anulable si hay una derivación . Una regla se llama producción ε . Una derivación se llama ciclo .
Se sabe que los algoritmos eliminan de una gramática determinada, sin cambiar el lenguaje generado,
En particular, una alternativa que contenga un símbolo no terminal inútil se puede eliminar del lado derecho de una regla. Estas reglas y alternativas se consideran inútiles . [24]
En el ejemplo de gramática representado, el no terminal D es inalcanzable y E es improductivo, mientras que C → C provoca un ciclo. Por lo tanto, omitir las últimas tres reglas no cambia el lenguaje generado por la gramática, ni omitir las alternativas "| Cc | Ee " del lado derecho de la regla para S .
Se dice que una gramática libre de contexto es adecuada si no tiene símbolos inútiles ni ε-producciones ni ciclos. [25] Combinando los algoritmos anteriores, cada gramática libre de contexto que no genera ε puede transformarse en una gramática propia 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 determinada gramática libre de contexto 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 las gramáticas sensibles al contexto , pero sí decidible para las gramáticas libres de contexto.
Sin embargo, muchos problemas son indecidibles incluso para gramáticas libres de contexto; los más destacados se tratan 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 historial de cálculo , una cadena que describe un cálculo completo de una máquina de Turing . Se puede construir un CFG que genere todas las cadenas que no acepten historiales de cálculo 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 trivial CFG que define el lenguaje de todas las cadenas.
Dados dos CFG, ¿puede el primero generar todas las cadenas que puede generar el segundo? [31] [32]
Si este problema fuera decidible, entonces también se podría decidir la igualdad del lenguaje: 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 la correspondencia postal , que se sabe que es indecidible. [33] Esto puede demostrarse 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 postal (PCP) también podría resolverse: dadas cadenas sobre algún alfabeto , dejemos que la gramática consista en la regla
donde denota la cadena invertida y no aparece entre ; y deja que la gramática consista en la regla
Entonces la instancia de PCP dada por tiene solución si y solo si y comparten una cadena derivable. La izquierda de la cadena (antes de ) representará la parte superior de la solución para la instancia de PCP, mientras que el lado derecho será la parte inferior a la inversa.
Una forma obvia de ampliar 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 correcto y la definición de 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 coincidir en número. En informática, 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 extendida libre de contexto (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 las 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 de terminales adicionales en el lado izquierdo de las reglas, lo que limita su aplicación. Esto produce el formalismo de las gramáticas sensibles al contexto .
Hay varias subclases importantes de gramáticas libres de contexto:
El análisis LR amplía 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 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 lenguajes nuevos y generadores de analizadores continúan basándose en el análisis LL, LALR o LR hasta el día de hoy.
Inicialmente, Chomsky esperaba superar las limitaciones de las gramáticas libres de contexto añadiendo reglas de transformación . [4]
Estas reglas son otro recurso estándar en la lingüística tradicional; por ejemplo, pasivació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 puedan expresarse exactamente los tipos de cosas que el lenguaje natural realmente permite. Permitir transformaciones arbitrarias no cumple con ese objetivo: son demasiado poderosas, siendo Turing completo a menos que se agreguen restricciones significativas (por ejemplo, no hay transformaciones que introduzcan y luego reescriban símbolos de manera libre de contexto).
La posición general de Chomsky sobre la falta de contexto del lenguaje natural se ha mantenido desde entonces, [36] aunque sus ejemplos específicos sobre la insuficiencia de las gramáticas libres de contexto en términos de su débil capacidad generativa fueron posteriormente refutados. [37] Gerald Gazdar y Geoffrey Pullum han argumentado que a pesar de algunas construcciones no libres de contexto en lenguaje natural (como las dependencias entre series en alemán suizo [36] y la reduplicación en bambara [38] ), la gran mayoría de las formas en lenguaje natural son de hecho libres de contexto. [37]
Cada construcción que puede describirse mediante una expresión regular puede describirse mediante una gramática [libre de contexto], pero no al revés.