Gramática libre de contexto

Tipo de gramática formal

Extracto simplificado de la gramática formal ^[1] para el 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 ( 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

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

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. ${\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 simples reemplazos. Por ejemplo, la primera regla de 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 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. ${\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 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.

Fondo

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:

John, cuyo auto 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 [ auto 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 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 los 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.

Definiciones formales

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

1. V es un conjunto finito; cada elemento se llama carácter no terminal o variable . Cada variable representa un tipo diferente de frase o cláusula en la oración. A las variables también se les llama 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 constituyen 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 la estrella de Kleene . Los miembros de R se denominan reglas (de reescritura) o producciones de la gramática. (también comúnmente simbolizado por una P ) ${\displaystyle V\times (V\cup \Sigma )^{*}}$
4. S es la variable inicial (o símbolo inicial), utilizada para representar la oración (o programa) completa. Debe ser un elemento de V .

Notación de reglas 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 como lado izquierdo y β como 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 denotarla con ε. La forma se llama ε -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. Reglas y, por tanto, puede escribirse como . En este caso, y se denominan primera y segunda alternativa, 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 tal que y . Por tanto, v es el 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 de reglas repetitivas

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. ${\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 → ε ,

está libre de 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 no tiene contexto, sin embargo, se puede demostrar que no es regular . ${\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}}$

Si las producciones

S → un ,

S → segundo ,

se agregan, 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 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

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 recursividad. ^[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 S no terminal.

La siguiente secuencia se puede derivar de esa gramática:

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

Parejas coincidentes

En una gramática libre de contexto, podemos emparejar caracteres como 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 . Esto sólo difiere 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 | Ud.

T → IVA | 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 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.

Segundo bloque de b's de doble tamaño.

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

S → bSbb | A

A → aA | ε

Fórmulas lógicas 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 inicial.

Ejemplos de idiomas que no están libres de contexto

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

Gramáticas regulares

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.

S → un

S → comoS

S → bS

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 . ${\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.

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:

S → una | como | bs

Derivaciones y árboles de sintaxis.

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 prueba 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 aparición de su lado izquierdo al que se aplica

Para mayor claridad, generalmente 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 inicial S con la siguiente derivación:

S

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

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

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

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

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

A menudo, se sigue una estrategia que elige de manera determinista el siguiente no terminal a 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 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

S

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

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

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

→ 1 + 1 + S (por la regla 2 en el 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 el S más a la derecha )

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

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

→ S + 1 + a (por la regla 2 en la 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 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:

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

S

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

→ S + a (por la regla 3 en el extremo derecho S )

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

→ S + 1 + a (por la regla 2 en la 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 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:

S

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

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

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

→ 1 + 1 + S (por la regla 2 en el 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 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 .

Ejemplo: expresiones algebraicas

Aquí hay una gramática libre de contexto para expresiones algebraicas infijas sintácticamente correctas en las variables x, y y z:

1. S → x
2. S → y
3. S → z
4. S → S + S
5. S → S – S
6. S → S * S
7. S → S / S
8. S → ( S )

Esta gramática puede, por ejemplo, generar la cadena

( x + y ) * x – z * y / ( x + x )

como sigue:

S

→ S – S (por la regla 5)

→ S * S – S (por la regla 6, aplicada al S más a la izquierda )

→ S * S – S / S (por la regla 7, aplicada al S más a la derecha )

→ ( S ) * S – S / S (por la regla 8, aplicada al S más a la izquierda )

→ ( S ) * S – S / ( S ) (por la regla 8, aplicada al S más a la derecha )

→ ( S + S ) * S – S / ( S ) (por la regla 4, aplicada al S más a la izquierda )

→ ( S + S ) * S – S * S / ( S ) (por la regla 6, aplicada a la cuarta S )

→ ( S + S ) * S – S * S / ( S + S ) (por la regla 4, aplicada al S más a la derecha )

→ ( x + S ) * S – S * S / ( S + S ) (etc.)

→ ( x + y ) * S – S * S / ( S + S )

→ ( x + y ) * x – S * S / ( S + S )

→ ( x + y ) * x – z * S / ( S + S )

→ ( x + y ) * x – z * y / ( S + S )

→ ( x + y ) * x – z * y / ( x + S )

→ ( x + y ) * x – z * y / ( x + x )

Tenga en cuenta que se tomaron muchas decisiones sobre qué reescritura se realizaría a continuación. Estas elecciones parecen bastante arbitrarias. De hecho, lo son, en el sentido de que la cadena finalmente generada es siempre la misma. Por ejemplo, la segunda y tercera reescrituras.

→ S * S – S (por la regla 6, aplicada al S más a la izquierda )

→ S * S – S / S (por la regla 7, aplicada al S más a la derecha )

se podría hacer en el orden inverso:

→ S – S / S (por la regla 7, aplicada a la S más a la derecha )

→ S * S – S / S (por la regla 6, aplicada al S más a la izquierda )

Además, se tomaron muchas decisiones sobre qué regla aplicar a cada S seleccionado . Cambiar las elecciones realizadas y no sólo el orden en que se realizaron normalmente afecta qué cadena de terminales sale al final.

Veamos esto con más detalle. Considere el árbol de análisis de esta derivación:

Comenzando desde arriba, paso a paso, se expande una S en el árbol, hasta que no queden más S es (no terminales) sin expandir. Elegir un orden de expansión diferente producirá una derivación diferente, pero el mismo árbol de análisis. El árbol de análisis solo cambiará si elegimos una regla diferente para aplicar en alguna posición del árbol.

Pero, ¿puede un árbol de análisis diferente seguir produciendo la misma cadena terminal, que es ( x + y ) * x – z * y / ( x + x ) en este caso? Sí, para esta gramática en particular, esto es posible. Las gramáticas con esta propiedad se llaman ambiguas .

Por ejemplo, x + y * z se puede producir con estos dos árboles de análisis diferentes:

Sin embargo, el lenguaje descrito por esta gramática no es inherentemente ambiguo: se puede dar una gramática alternativa e inequívoca para el lenguaje, por ejemplo:

T → x

T → y

T → z

S → S + T

S → S – T

S → S * T

S → S / T

T → ( S )

S → T ,

una vez más eligiendo S como símbolo de inicio. Esta gramática alternativa producirá x + y * z con un árbol de análisis similar al de la izquierda arriba, es decir, asumiendo implícitamente la asociación ( x + y ) * z , que no sigue el orden estándar de operaciones . Se pueden construir gramáticas más elaboradas, inequívocas y libres de contexto que produzcan árboles de análisis que obedezcan todas las reglas de asociatividad y precedencia de operadores deseadas .

Formas normales

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

Propiedades de cierre

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:

• unión K ∪ L ; concatenación K ∘ L ; Estrella 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 (por lo tanto, tampoco bajo complementación ) y establecen diferencia. ^[15]

Problemas decidibles

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

Analizando

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:

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

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]

Accesibilidad, productividad, nulidad

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 . ${\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 determinada, 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 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 .

Controles de regularidad y LL( k )

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 determinada gramática libre de contexto 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 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.

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

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 trivial CFG que define el lenguaje de todas las cadenas.

Inclusión de idiomas

Dados dos CFG, ¿puede el primero generar todas las cadenas que el segundo puede generar? ^{[31] [32]}

Si este problema fuera decidible, entonces también se podría decidir la igualdad del lenguaje: dos CFG G1 y G2 generan el mismo lenguaje si L(G1) es un subconjunto de L(G2) y L(G2) es un subconjunto de L(G1).

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 la correspondencia postal , que se sabe que es indecidible. ^[33] Esto puede demostrarse mediante el lema de Ogden . ^[34]

Desarticulación del lenguaje

Dados dos CFG, ¿hay alguna cadena derivable de ambas gramáticas?

Si este problema fuera decidible, el problema indecidible de la correspondencia postal también podría resolverse: dadas cadenas sobre algún alfabeto , dejemos 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 ; y dejemos 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}|\cdots |a_{k}Ta_{k}|b}$;

Entonces el problema de publicación dado por tiene una solución si y solo si y comparten una cadena derivable. ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$ ${\displaystyle L(G_{1})}$ ${\displaystyle L(G_{2})}$

Extensiones

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 características del lenguaje natural, como la concordancia y la referencia , y 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 .

Subclases

Hay varias subclases importantes de 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 pushdown deterministas (PDA), pero solo pueden describir lenguajes deterministas libres de contexto .
• Las gramáticas LR simples y Look-Ahead LR son subclases que permiten una mayor simplificación del análisis. SLR y LALR se reconocen utilizando la misma PDA que LR, pero con tablas más sencillas, 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 lenguajes.
• Las gramáticas simples son una subclase de las gramáticas LL(1), principalmente interesantes por su propiedad teórica de que la igualdad lingüística de las gramáticas simples es decidible, mientras que la inclusión del 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 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.

Aplicaciones lingüísticas

Chomsky inicialmente 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 se permiten transformaciones que introduzcan y luego reescriban símbolos sin 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]

Ver también

• Análisis de gramática de expresiones
• Gramática estocástica libre de contexto
• Algoritmos para la generación de gramática libre de 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 (2ª ed.). Englewood Cliffs/Nueva Jersey: Prentice Hall. ISBN 0131103628.Aquí: Aplicación.A
2. Introducción a la teoría, los lenguajes y la computación de los autómatas , 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; Martín, James H. (29 de diciembre de 2021). "Gramáticas de distritos electorales" (PDF) . Universidad Stanford . Archivado (PDF) desde el 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 las 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. 103.
9. Hopcroft y Ullman (1979), Ejercicio 4.1b, pág. 103.
10. Ah, Alfred Vaino ; Lam, Mónica S .; Sethi, Ravi ; Ullman, Jeffrey David (2007). "4.2.7 Gramáticas libres de contexto versus expresiones regulares" (imprimir) . Compiladores: principios, técnicas y herramientas (2ª ed.). Boston, MA EE.UU.: Pearson Addison-Wesley. págs. 205-206. ISBN 9780321486813. 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.
11. Hopcroft y Ullman (1979), p.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áginas 135-136, teorema 6.5
15. Hopcroft y Ullman (1979), páginas 134-135, teorema 6.4
16. Leslie Valiant (enero de 1974). Reconocimiento general libre de contexto en menos de tiempo cúbico (Informe técnico). Universidad de Carnegie mellon. pag. 11.
17. Leslie G. Valiente (1975). "Reconocimiento general libre de contexto en menos de tiempo cúbico". Revista de Ciencias de la Computación y de Sistemas . 10 (2): 308–315. doi : 10.1016/s0022-0000(75)80046-8 .
18. Lillian Lee (2002). "El análisis gramatical rápido y libre de 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 regulares". Conferencia ACM sobre Lenguajes de Programación Funcionales y Arquitectura de Computadores . págs. 427–447. CiteSeerX 10.1.1.39.3766 . ; aquí: Sección 4
21. Hopcroft y Ullman (1979), Lema 4.2, pág. 89.
22. Hopcroft, Motwani y Ullman (2003), Teorema 7.2, Sección 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, los lenguajes y la computación de autómatas . Addison Wesley.; aquí: Sección 7.1.1, p.256
25. Nijholt, Anton (1980), Gramáticas libres de contexto: portadas, formas normales y análisis , Lecture Notes in Computer Science, vol. 93, Springer, pág. 8, ISBN 978-3-540-10245-8, señor  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áginas 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 comentada 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) . pag. 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 libertad de contexto del lenguaje natural" (PDF) , Lingüística y Filosofía , 8 (3): 333–343, doi :10.1007/BF00630917, S2CID  222277837, archivado (PDF) del 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 de 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 más conocido en ese momento.} Consulte Multiplicación de matrices # Complejidad computacional para conocer las mejoras vinculadas desde entonces.
2. Para gramáticas de árboles normales , 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 & Ullman (1979), p.91, Teorema 4.4

Otras lecturas

• Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley. Capí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, los lenguajes y la computación de los autómatas (2ª ed.). Río Upper Saddle: 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-6. Capí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 historiales de cálculo: págs. 176–183.
• J. Berstel, L. Boasson (1990). Jan van Leeuwen (ed.). Idiomas libres de contexto . Manual de informática teórica. vol. B. Elsevier. págs. 59-102.

enlaces externos

• Los programadores informáticos pueden encontrar útil la respuesta del intercambio de pila.
• Desarrollador CFG creado por Christopher Wong en la Universidad de Stanford en 2014; modificado por Kevin Gibbons en 2015.