Gramática libre de contexto

Tipo de gramática formal

Extracto simplificado de la gramática formal ^[1] del lenguaje de programación C (izquierda) y una derivación de un fragmento de código C (derecha) a partir del símbolo no terminal . Los símbolos no terminales son azules y los símbolos terminales son rojos. ${\displaystyle \langle {\text{Stmt}}\rangle }$

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

${\displaystyle A\ \to \ \alpha }$

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. ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

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,

${\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

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. ${\displaystyle \langle {\text{Stmt}}\rangle }$ ${\displaystyle \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

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.

Fondo

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:

John, cuyo coche azul estaba en el garaje, caminó hasta la tienda de comestibles.

se puede poner entre paréntesis lógicamente (con los metasímbolos lógicos [ ] ) de la siguiente manera:

[ John [ , [ cuyo [ coche azul ]] [ estaba [ en [ el garaje ]]] , ]] [ caminó [ hasta [ la [ tienda de comestibles ]]]] .

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.

Definiciones formales

Una gramática libre de contexto G se define mediante la tupla de 4 , donde ^[6] ${\displaystyle G=(V,\Sigma ,R,S)}$

1. V es un conjunto finito; cada elemento se denomina carácter no terminal o variable . Cada variable representa un tipo diferente de frase u oración en la oración. Las variables también se denominan a veces categorías sintácticas. Cada variable define un sublenguaje del lenguaje definido por G. ${\displaystyle v\in V}$
2. Σ es un conjunto finito de terminales s, disjuntos de V , que forman el contenido real de la oración. El conjunto de terminales es el alfabeto de la lengua definido por la gramática G .
3. R es una relación finita en , donde el asterisco representa la operación de estrella de Kleene . Los miembros de R se denominan reglas (de reescritura) o reglas de producción de la gramática. (También se simbolizan comúnmente con una P ) ${\displaystyle V\times (V\cup \Sigma )^{*}}$
4. S es la variable de inicio (o símbolo de inicio), que se utiliza para representar la oración completa (o el programa). Debe ser un elemento de V.

Notación de la regla de producción

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: . ${\displaystyle (\alpha ,\beta )\in R}$ ${\displaystyle \alpha \in V}$ ${\displaystyle \beta \in (V\cup \Sigma )^{*}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \rightarrow \beta }$

Se permite que β sea la cadena vacía y, en este caso, se acostumbra denotarlo por ε. La forma se denomina ε -producción. ^[7] ${\displaystyle \alpha \rightarrow \varepsilon }$

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. ${\displaystyle \alpha \rightarrow \beta _{1}}$ ${\displaystyle \alpha \rightarrow \beta _{2}}$ ${\displaystyle \alpha \rightarrow \beta _{1}\mid \beta _{2}}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{2}}$

Aplicación de reglas

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 . ${\displaystyle u,v\in (V\cup \Sigma )^{*}}$ ${\displaystyle u\Rightarrow v\,}$ ${\displaystyle \exists (\alpha ,\beta )\in R}$ ${\displaystyle \alpha \in V}$ ${\displaystyle u_{1},u_{2}\in (V\cup \Sigma )^{*}}$ ${\displaystyle u\,=u_{1}\alpha u_{2}}$ ${\displaystyle v\,=u_{1}\beta u_{2}}$ ${\displaystyle (\alpha ,\beta )}$

Aplicación repetitiva de reglas

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. ${\displaystyle u,v\in (V\cup \Sigma )^{*},}$ ${\displaystyle u_{1},\ldots ,u_{k}\in (V\cup \Sigma )^{*}}$ ${\displaystyle u=u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}=v}$ ${\displaystyle u{\stackrel {*}{\Rightarrow }}v}$ ${\displaystyle u\Rightarrow \Rightarrow v}$ ${\displaystyle k\geq 2}$ ${\displaystyle u{\stackrel {+}{\Rightarrow }}v}$ ${\displaystyle ({\stackrel {*}{\Rightarrow }})}$ ${\displaystyle ({\stackrel {+}{\Rightarrow }})}$ ${\displaystyle (\Rightarrow )}$

Lenguaje libre de contexto

El lenguaje de una gramática es el conjunto ${\displaystyle G=(V,\Sigma ,R,S)}$

${\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}$

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 . ${\displaystyle L\,=\,L(G)}$

Los autómatas pushdown no deterministas reconocen exactamente los lenguajes libres de contexto.

Ejemplos

Palabras concatenadas con su reverso

La gramática , con producciones ${\displaystyle G=(\{S\},\{a,b\},P,S)}$

S → aSa ,

S → bSb ,

S → ε ,

es independiente del contexto. No es apropiado ya que incluye una ε-producción. Una derivación típica en esta gramática es

S → aSa → aaSaa → aabSbaa → aabbaa .

Esto deja claro que el lenguaje es independiente del contexto, sin embargo, se puede demostrar que no es regular . ${\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}}$

Si las producciones

S → a ,

S → b ,

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]

Paréntesis bien formados

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

S → SS ,

S → ( S ) ,

S → ()

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]

Paréntesis y corchetes anidados bien formados

Un segundo ejemplo canónico son dos tipos diferentes de paréntesis anidados coincidentes, descritos por las producciones:

S → SS

S → ()

S → ( S )

S → []

S → [ S ]

con símbolos terminales [ ] ( ) y no terminal S.

En esa gramática se puede derivar la siguiente secuencia:

([ [ [ ()() [ ][ ] ] ]([ ]) ])

Pares coincidentes

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:

S → aSb

S → ab

Esta gramática genera el lenguaje que no es regular (según el lema de bombeo para lenguajes regulares ). ${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$

El carácter especial ε representa la cadena vacía. Al cambiar la gramática anterior a

S → aSb

S → ε

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. ${\displaystyle \{a^{n}b^{n}:n\geq 0\}}$

Número distinto de a y b

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:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

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.

Segundo bloque de b's de tamaño doble

Otro ejemplo de lenguaje no regular es . Es independiente del contexto, ya que se puede generar mediante la siguiente gramática independiente del contexto: ${\displaystyle \{{\text{b}}^{n}{\text{a}}^{m}{\text{b}}^{2n}:n\geq 0,m\geq 0\}}$

S → bSbb | A

A → aA | ε

Fórmulas de lógica de primer orden

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.

Ejemplos de idiomas que no son libres de contexto

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 . ${\displaystyle {(}^{n}{[}^{n}{)}^{n}{]}^{n}}$ ${\displaystyle {\text{a}}^{n}{\text{b}}^{n}{\text{c}}^{n}}$

Gramáticas regulares

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.

S → un

S → como

S → bS

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 . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$

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:

S → a | aS | bS

Derivaciones y árboles sintácticos

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:

• la regla aplicada en ese paso
• la ocurrencia de su lado izquierdo al que se aplica

Para mayor claridad, normalmente también se proporciona la cadena intermedia.

Por ejemplo, con la gramática:

1. S → S + S
2. S → 1
3. S → un

La cuerda

1 + 1 + un

se puede derivar del símbolo de inicio S con la siguiente derivación:

S

→ S + S (por regla 1. en S )

→ S + S + S (por regla 1. en el segundo S )

→ 1 + S + S (por la regla 2. en el primer S )

→ 1 + 1 + S (por la regla 2. en el segundo S )

→ 1 + 1 + a (por la regla 3. en la tercera S )

A menudo se sigue una estrategia que elige de manera determinista el siguiente no terminal para reescribir:

• en una derivación más a la izquierda , siempre es el no terminal más a la izquierda;
• en una derivación más a la derecha , siempre es el no terminal más a la derecha.

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

S

→ S + S (por la regla 1 en la S más a la izquierda )

→ 1 + S (por la regla 2 en la S más a la izquierda )

→ 1 + S + S (por la regla 1 en la S más a la izquierda )

→ 1 + 1 + S (por la regla 2 en la S más a la izquierda )

→ 1 + 1 + a (por la regla 3 en el S más a la izquierda ),

que se puede resumir como

Regla 1

Regla 2

Regla 1

Regla 2

Regla 3.

Una derivación más a la derecha es:

S

→ S + S (por la regla 1 en la S más a la derecha )

→ S + S + S (por la regla 1 en la S más a la derecha )

→ S + S + a (por la regla 3 en el S más a la derecha )

→ S + 1 + a (por la regla 2 en el S más a la derecha )

→ 1 + 1 + a (por la regla 2 en el S más a la derecha ),

que se puede resumir como

Regla 1

Regla 1

Regla 3

Regla 2

Regla 2.

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:

{{1} _S + {{1} _S + { a } _S } _S } _S

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.

S

→ S + S (por la regla 1 en la S más a la derecha )

→ S + a (por la regla 3 en el S más a la derecha )

→ S + S + a (por la regla 1 en el S más a la derecha )

→ S + 1 + a (por la regla 2 en el S más a la derecha )

→ 1 + 1 + a (por la regla 2 en el S más a la derecha ),

que define una cadena con una estructura diferente

{{{1} _S + {1} _S } _S + { a } _S } _S

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:

S

→ S + S (por la regla 1 en la S más a la izquierda )

→ S + S + S (por la regla 1 en la S más a la izquierda )

→ 1 + S + S (por la regla 2 en la S más a la izquierda )

→ 1 + 1 + S (por la regla 2 en la S más a la izquierda )

→ 1 + 1 + a (por la regla 3 en el S más a la izquierda ),

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 .

Formas normales

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 ).

Propiedades del cierre

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:

• unión K ∪ L ; concatenación K ∘ L ; estrella de Kleene L ^{* [11]}
• sustitución (en particular homomorfismo ) ^[12]
• homomorfismo inverso ^[13]
• intersección con un lenguaje regular ^[14]

No están cerrados bajo intersección general (y por lo tanto tampoco bajo complementación ) y diferencia de conjuntos. ^[15]

Problemas decidibles

Los siguientes son algunos problemas decidibles sobre gramáticas libres de contexto.

Analizando

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:

• Algoritmo CYK (para gramáticas en forma normal de Chomsky )
• Analizador sintáctico Earley
• Analizador GLR
• Analizador LL (solo para la subclase adecuada de gramáticas LL( k ))

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]

Accesibilidad, productividad, nulidad

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 . ${\displaystyle X}$ ${\displaystyle X{\stackrel {*}{\Rightarrow }}w}$ ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle S{\stackrel {*}{\Rightarrow }}\alpha X\beta }$ ${\displaystyle \alpha ,\beta }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X{\stackrel {*}{\Rightarrow }}\varepsilon }$ ${\displaystyle X\rightarrow \varepsilon }$ ${\displaystyle X{\stackrel {+}{\Rightarrow }}X}$

Se sabe que los algoritmos eliminan de una gramática dada, sin cambiar el lenguaje generado,

• símbolos improductivos, ^{[19] [nota 2]}
• símbolos inalcanzables, ^{[21] [22]}
• ε-producciones, con una posible excepción, ^{[nota 3] [23]} y
• ciclos. ^{[nota 4]}

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 .

Regularidad y LL(a) cheques

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}

Vacío y finitud

Existen algoritmos para decidir si el lenguaje de una gramática libre de contexto dada está vacío, así como si es finito. ^[29]

Problemas indecidibles

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.

Universalidad

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.

Igualdad lingüística

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.

Inclusión lingüística

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 . ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle L(G_{1})}$ ${\displaystyle L(G_{2})}$ ${\displaystyle L(G_{2})}$ ${\displaystyle L(G_{1})}$

Estar en un nivel inferior o superior de la jerarquía de Chomsky

Utilizando el teorema de Greibach , se puede demostrar que los dos problemas siguientes son indecidibles:

• Dada una gramática sensible al contexto , ¿describe un lenguaje libre de contexto?
• Dada una gramática libre de contexto, ¿describe un lenguaje regular ? ^{[31] [32]}

Ambigüedad gramatical

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]

Desunión lingüística

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 ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$ ${\displaystyle \{a_{1},\ldots ,a_{k}\}}$ ${\displaystyle G_{1}}$

${\displaystyle S\to \alpha _{1}S\beta _{1}^{rev}|\cdots |\alpha _{N}S\beta _{N}^{rev}|b}$;

donde denota la cadena invertida y no aparece entre los ; y deje que la gramática consista en la regla ${\displaystyle \beta _{i}^{rev}}$ ${\displaystyle \beta _{i}}$ ${\displaystyle b}$ ${\displaystyle a_{i}}$ ${\displaystyle G_{2}}$

${\displaystyle T\to a_{1}Ta_{1}^{rev}|\cdots |a_{k}Ta_{k}^{rev}|b}$;

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. ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$ ${\displaystyle L(G_{1})}$ ${\displaystyle L(G_{2})}$ ${\displaystyle b}$

Extensiones

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 .

Subclases

Hay una serie de subclases importantes de las gramáticas libres de contexto:

• Las gramáticas LR( k ) (también conocidas como gramáticas deterministas libres de contexto ) permiten el análisis (reconocimiento de cadenas) con autómatas de inserción deterministas (PDA), pero solo pueden describir lenguajes deterministas libres de contexto .
• Las gramáticas LR simples y LR anticipadas son subclases que permiten una mayor simplificación del análisis. Las gramáticas SLR y LALR se reconocen utilizando el mismo PDA que LR, pero con tablas más simples, en la mayoría de los casos.
• Las gramáticas LL( k ) y LL( * ) permiten el análisis mediante la construcción directa de una derivación más a la izquierda como se describió anteriormente, y describen incluso menos idiomas.
• Las gramáticas simples son una subclase de las gramáticas LL(1) que son principalmente interesantes por su propiedad teórica de que la igualdad de lenguaje de las gramáticas simples es decidible, mientras que la inclusión de lenguaje no lo es.
• Las gramáticas entre corchetes tienen la propiedad de que los símbolos terminales se dividen en pares de corchetes izquierdo y derecho que siempre coinciden en las reglas.
• Las gramáticas lineales no tienen reglas con más de un no terminal en el lado derecho.
• Las gramáticas regulares son una subclase de las gramáticas lineales y describen los lenguajes regulares , es decir, corresponden a autómatas finitos y expresiones regulares .

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.

Aplicaciones lingüísticas

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]

Véase también

• Análisis de la gramática de expresiones
• Gramática estocástica independiente del contexto
• Algoritmos para la generación de gramática independiente del contexto
• Lema de bombeo para lenguajes libres de contexto

Referencias

1. Brian W. Kernighan y Dennis M. Ritchie (abril de 1988). El lenguaje de programación C. Serie de software de Prentice Hall (segunda edición). Englewood Cliffs/Nueva Jersey: Prentice Hall. ISBN 0131103628.Aquí: App.A
2. Introducción a la teoría de autómatas, lenguajes y computación , John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
3. Hopcroft y Ullman (1979), pág. 106.
4. Chomsky, Noam (septiembre de 1956), "Tres modelos para la descripción del lenguaje", IEEE Transactions on Information Theory , 2 (3): 113–124, doi :10.1109/TIT.1956.1056813, S2CID  19519474
5. Jurafsky, Daniel; Martin, James H. (29 de diciembre de 2021). "Constituency Grammars" (PDF) . Universidad de Stanford . Archivado (PDF) del original el 14 de marzo de 2017 . Consultado el 28 de octubre de 2022 .
6. La notación aquí es la de Sipser (1997), p. 94. Hopcroft y Ullman (1979) (p. 79) definen gramáticas libres de contexto como 4-tuplas de la misma manera, pero con diferentes nombres de variables.
7. Hopcroft y Ullman (1979), págs. 90-92.
8. Hopcroft y Ullman (1979), Ejercicio 4.1a, pág. 103.
9. Hopcroft y Ullman (1979), Ejercicio 4.1b, pág. 103.
10. Aho, Alfred Vaino ; Lam, Monica S.; Sethi , Ravi ; Ullman, Jeffrey David (2007). "4.2.7 Gramáticas libres de contexto frente a expresiones regulares" (versión impresa) . Compilers: Principles, Techniques, & Tools (2.ª ed.). Boston, MA, EE. UU.: Pearson Addison-Wesley. págs. 205–206. ISBN 9780321486813Toda construcción que pueda describirse mediante una expresión regular puede describirse mediante una gramática [libre de contexto], pero no viceversa.
11. Hopcroft y Ullman (1979), pág. 131, Teorema 6.1
12. Hopcroft y Ullman (1979), págs. 131-132, Teorema 6.2
13. Hopcroft y Ullman (1979), págs. 132-134, Teorema 6.3
14. Hopcroft y Ullman (1979), págs. 135-136, Teorema 6.5
15. Hopcroft y Ullman (1979), págs. 134-135, Teorema 6.4
16. Leslie Valiant (enero de 1974). Reconocimiento general sin contexto en un tiempo inferior al cúbico (informe técnico). Universidad Carnegie Mellon. pág. 11.
17. Leslie G. Valiant (1975). "Reconocimiento general sin contexto en un tiempo menor que el cúbico". Journal of Computer and System Sciences . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
18. Lillian Lee (2002). "El análisis gramatical rápido sin contexto requiere una multiplicación rápida de matrices booleanas" (PDF) . J ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491. Archivado (PDF) desde el original el 27 de abril de 2003.
19. Hopcroft y Ullman (1979), Lema 4.1, pág. 88.
20. Aiken, A.; Murphy, B. (1991). "Implementación de expresiones de árbol regular". Conferencia ACM sobre lenguajes de programación funcional y arquitectura informática . págs. 427–447. CiteSeerX 10.1.1.39.3766 . ; aquí: Sec.4
21. Hopcroft y Ullman (1979), Lema 4.2, pág. 89.
22. Hopcroft, Motwani y Ullman (2003), Teorema 7.2, Secc.7.1, p.255ff
23. Hopcroft y Ullman (1979), Teorema 4.3, pág. 90.
24. John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introducción a la teoría de autómatas, lenguajes y computación . Addison Wesley.; aquí: Sect.7.1.1, p.256
25. Nijholt, Anton (1980), Gramáticas libres de contexto: coberturas, formas normales y análisis , Lecture Notes in Computer Science, vol. 93, Springer, pág. 8, ISBN 978-3-540-10245-8, Sr.  0590047.
26. Esto es fácil de ver en las definiciones gramaticales.
27. DJ Rosenkrantz y RE Stearns (1970). "Propiedades de las gramáticas deterministas de arriba hacia abajo". Información y control . 17 (3): 226–256. doi : 10.1016/S0019-9958(70)90446-8 .
28. Hopcroft y Ullman (1979), Ejercicio 8.10a, p. 214. El problema sigue siendo indecidible incluso si el lenguaje es producido por una gramática "lineal" libre de contexto (es decir, con como máximo un no terminal en el lado derecho de cada regla, cf. Ejercicio 4.20, p. 105).
29. Hopcroft y Ullman (1979), págs. 137-138, Teorema 6.6
30. Sipser (1997), Teorema 5.10, pág. 181.
31. Hopcroft y Ullman (1979), pág. 281.
32. Hazewinkel, Michiel (1994), Enciclopedia de matemáticas: una traducción actualizada y anotada de la "Enciclopedia matemática" soviética, Springer, vol. IV, pág. 56, ISBN 978-1-55608-003-6.
33. Hopcroft y Ullman (1979, págs. 200-201, Teorema 8.9)
34. Ogden, William (septiembre de 1968). "Un resultado útil para demostrar la ambigüedad inherente". Teoría de sistemas matemáticos . 2 (3): 191–194. doi :10.1007/bf01694004. ISSN  0025-5661. S2CID  13197551. Aquí: p.4
35. Norvell, Theodore. "Una breve introducción a las expresiones regulares y las gramáticas libres de contexto" (PDF) . pág. 4. Archivado (PDF) desde el original el 24 de marzo de 2005. Consultado el 24 de agosto de 2012 .
36. Shieber, Stuart (1985), "Evidencia contra la falta de contexto del lenguaje natural" (PDF) , Linguistics and Philosophy , 8 (3): 333–343, doi :10.1007/BF00630917, S2CID  222277837, archivado (PDF) desde el original el 2004-04-15.
37. Pullum, Geoffrey K.; Gerald Gazdar (1982), "Lenguajes naturales y lenguajes libres de contexto", Lingüística y filosofía , 4 (4): 471–504, doi :10.1007/BF00360802, S2CID  189881482.
38. Culy, Christopher (1985), "La complejidad del vocabulario del bambara", Lingüística y filosofía , 8 (3): 345–351, doi :10.1007/BF00630918, S2CID  189881984.

Notas

1. En los artículos de Valiant se da O ( n ^{2,81 ), el límite superior mejor conocido en aquel momento. Véase} Multiplicación de matrices#Complejidad computacional para conocer las mejoras de los límites desde entonces.
2. Para las gramáticas de árboles regulares , Aiken y Murphy ofrecen un algoritmo de punto fijo para detectar no terminales improductivos. ^[20]
3. Si la gramática puede generar , no se puede evitar una regla . ${\displaystyle \varepsilon }$ ${\displaystyle S\rightarrow \varepsilon }$
4. Esto es una consecuencia del teorema de eliminación de la producción unitaria en Hopcroft y Ullman (1979), p.91, Teorema 4.4

Lectura adicional

• Hopcroft, John E.; Ullman , Jeffrey D. (1979), Introducción a la teoría de autómatas, lenguajes y computación , Addison-WesleyCapítulo 4: Gramáticas libres de contexto, págs. 77–106; Capítulo 6: Propiedades de los lenguajes libres de contexto, págs. 125–137.
• Hopcroft; Motwani, Rajeev; Ullman, Jeffrey D. (2003). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Upper Saddle River: Pearson Education International. ISBN 978-0321210296.
• Sipser, Michael (1997), Introducción a la teoría de la computación, PWS Publishing, ISBN 978-0-534-94728-6Capítulo 2: Gramáticas libres de contexto, págs. 91–122; Sección 4.1.2: Problemas decidibles relacionados con lenguajes libres de contexto, págs. 156–159; Sección 5.1.1: Reducciones mediante historias de computación: págs. 176–183.
• J. Berstel, L. Boasson (1990). Jan van Leeuwen (ed.). Context-Free Languages ​​. Manual de informática teórica. Vol. B. Elsevier. págs. 59–102.

Enlaces externos

• Los programadores de computadoras pueden encontrar útil la respuesta de Stack Exchange.
• CFG Developer creado por Christopher Wong en la Universidad de Stanford en 2014; modificado por Kevin Gibbons en 2015.