Gramática formal

Un ejemplo de gramática formal con oración analizada. Las gramáticas formales constan de un conjunto de símbolos no terminales, símbolos terminales, reglas de producción y un símbolo de inicio designado.

Estructura de un lenguaje formal

Una gramática formal describe qué cadenas de un alfabeto de un lenguaje formal son válidas según la sintaxis del lenguaje . Una gramática no describe el significado de las cadenas ni lo que se puede hacer con ellas en cualquier contexto, sólo su forma. Una gramática formal se define como un conjunto de reglas de producción de dichas cadenas en un lenguaje formal.

La teoría del lenguaje formal, la disciplina que estudia las gramáticas y los lenguajes formales, es una rama de las matemáticas aplicadas . Sus aplicaciones se encuentran en informática teórica , lingüística teórica , semántica formal , lógica matemática y otras áreas.

Una gramática formal es un conjunto de reglas para reescribir cadenas, junto con un "símbolo de inicio" a partir del cual comienza la reescritura. Por lo tanto, se suele pensar que una gramática es un generador de lenguaje. Sin embargo, a veces también se puede utilizar como base para un " reconocedor ", una función informática que determina si una cadena determinada pertenece al idioma o es gramaticalmente incorrecta. Para describir tales reconocedores, la teoría del lenguaje formal utiliza formalismos separados, conocidos como teoría de los autómatas . Uno de los resultados interesantes de la teoría de los autómatas es que no es posible diseñar un reconocedor para ciertos lenguajes formales. ^[1] El análisis es el proceso de reconocer un enunciado (una cadena en lenguajes naturales) dividiéndolo en un conjunto de símbolos y analizando cada uno de ellos con la gramática del lenguaje. La mayoría de los idiomas tienen los significados de sus expresiones estructurados de acuerdo con su sintaxis, una práctica conocida como semántica compositiva . Como resultado, el primer paso para describir el significado de un enunciado en el lenguaje es descomponerlo parte por parte y observar su forma analizada (conocida como árbol de análisis en informática y como estructura profunda en gramática generativa ).

Ejemplo introductorio

Una gramática consiste principalmente en un conjunto de reglas de producción , reglas de reescritura para transformar cadenas. Cada regla especifica un reemplazo de una cadena particular (su lado izquierdo ) por otra (su lado derecho ). Se puede aplicar una regla a cada cadena que contiene su lado izquierdo y produce una cadena en la que una aparición de ese lado izquierdo ha sido reemplazada por su lado derecho.

A diferencia de un sistema semi-Thue , que está totalmente definido por estas reglas, una gramática distingue además entre dos tipos de símbolos: símbolos terminales y no terminales ; cada lado izquierdo debe contener al menos un símbolo no terminal. También distingue un símbolo no terminal especial, llamado símbolo de inicio .

El lenguaje generado por la gramática se define como el conjunto de todas las cadenas sin ningún símbolo no terminal que se puede generar a partir de la cadena que consta de un único símbolo inicial mediante la aplicación (posiblemente repetida) de sus reglas en cualquier forma posible. Si hay formas esencialmente diferentes de generar la misma cadena única, se dice que la gramática es ambigua .

En los siguientes ejemplos, los símbolos terminales son a y b , y el símbolo inicial es S.

Ejemplo 1

Supongamos que tenemos las siguientes reglas de producción:

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

luego comenzamos con S y podemos elegir una regla para aplicarle. Si elegimos la regla 1, obtenemos la cadena aSb . Si luego elegimos nuevamente la regla 1, reemplazamos S con aSb y obtenemos la cadena aaSbb . Si ahora elegimos la regla 2, reemplazamos S con ba y obtenemos la cadena aababb , y listo. Podemos escribir esta serie de elecciones de forma más breve, utilizando símbolos: . ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$

El lenguaje de la gramática es el conjunto infinito , donde se repite veces (y en particular representa el número de veces que se ha aplicado la regla de producción 1). Esta gramática no tiene contexto (sólo los no terminales individuales aparecen en el lado izquierdo) y es inequívoca. ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$ ${\displaystyle a^{k}}$ ${\displaystyle a}$ ${\displaystyle k}$ ${\displaystyle n}$

Ejemplos 2 y 3

Supongamos que las reglas son estas:

1. ${\displaystyle S\rightarrow a}$

2. ${\displaystyle S\rightarrow SS}$

3. ${\displaystyle aSa\rightarrow b}$

Esta gramática no está libre de contexto debido a la regla 3 y es ambigua debido a las múltiples formas en que se puede usar la regla 2 para generar secuencias de s. ${\displaystyle S}$

Sin embargo, el lenguaje que genera es simplemente el conjunto de todas las cadenas no vacías que consisten en s y/o s. Esto es fácil de ver: para generar a a partir de an , use la regla 2 dos veces para generar , luego la regla 1 dos veces y la regla 3 una vez para producir . Esto significa que podemos generar secuencias arbitrarias no vacías de sy luego reemplazar cada una de ellas con o como queramos. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle SSS}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle b}$

Alternativamente, ese mismo lenguaje puede generarse mediante una gramática no ambigua y libre de contexto; por ejemplo, la gramática regular con reglas

1. ${\displaystyle S\rightarrow aS}$

2. ${\displaystyle S\rightarrow bS}$

3. ${\displaystyle S\rightarrow a}$

4. ${\displaystyle S\rightarrow b}$

Definicion formal

La sintaxis de las gramáticas.

En la formalización clásica de las gramáticas generativas propuesta por primera vez por Noam Chomsky en la década de 1950, ^{[2] [3]} una gramática G consta de los siguientes componentes:

• Un conjunto finito N de símbolos no terminales , que es disjunto con las cadenas formadas a partir de G.
• Un conjunto finito de símbolos terminales que es disjunto de N . ${\displaystyle \Sigma }$
• Un conjunto finito P de reglas de producción , cada regla de la forma

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

donde está el operador estrella de Kleene y denota unión de conjuntos . Es decir, cada regla de producción se asigna de una cadena de símbolos a otra, donde la primera cadena (la "cabeza") contiene un número arbitrario de símbolos siempre que al menos uno de ellos sea un no terminal. En el caso de que la segunda cadena (el "cuerpo") consista únicamente en una cadena vacía , es decir, que no contenga ningún símbolo, se puede denotar con una notación especial (a menudo , e o ) para evitar confusiones. ${\displaystyle {*}}$ ${\displaystyle \cup }$ ${\displaystyle \Lambda }$ ${\displaystyle \epsilon }$

• Un símbolo distinguido que es el símbolo de inicio , también llamado símbolo de oración . ${\displaystyle S\in N}$

Una gramática se define formalmente como la tupla . Esta gramática formal a menudo se denomina sistema de reescritura o gramática de estructura de frase en la literatura. ^{[4] [5]} ${\displaystyle (N,\Sigma ,P,S)}$

Algunas construcciones matemáticas sobre gramáticas formales

El funcionamiento de una gramática se puede definir en términos de relaciones sobre cadenas:

• Dada una gramática , la relación binaria (pronunciada como "G deriva en un paso") en cadenas se define por: ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle {\underset {G}{\Rightarrow }}}$ ${\displaystyle (\Sigma \cup N)^{*}}$

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• la relación (pronunciada como G deriva en cero o más pasos ) se define como la clausura transitiva reflexiva de ${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$ ${\displaystyle {\underset {G}{\Rightarrow }}}$
• aforma oracional es un miembro de que se puede derivar en un número finito de pasos desde el símbolo inicial ; es decir, una forma oracional es miembro de . Una forma oracional que no contiene símbolos no terminales (es decir, es miembro de ) se llama oración . ^[6] ${\displaystyle (\Sigma \cup N)^{*}}$ ${\displaystyle S}$ ${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$ ${\displaystyle \Sigma ^{*}}$
• el lenguaje de , denotado como , se define como el conjunto de oraciones construidas por . ${\displaystyle G}$ ${\displaystyle {\boldsymbol {L}}(G)}$ ${\displaystyle G}$

La gramática es efectivamente el sistema semi-Thue , reescribiendo cadenas exactamente de la misma manera; la única diferencia es que distinguimos símbolos no terminales específicos , que deben reescribirse en reglas de reescritura, y solo estamos interesados ​​en reescribir desde el símbolo inicial designado a cadenas sin símbolos no terminales. ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle (N\cup \Sigma ,P)}$ ${\displaystyle S}$

Ejemplo

Para estos ejemplos, los lenguajes formales se especifican mediante notación de constructor de conjuntos .

Considere la gramática donde ,, es el símbolo inicial y consta de las siguientes reglas de producción : ${\displaystyle G}$ ${\displaystyle N=\left\{S,B\right\}}$ ${\displaystyle \Sigma =\left\{a,b,c\right\}}$ ${\displaystyle S}$ ${\displaystyle P}$

1. ${\displaystyle S\rightarrow aBSc}$

2. ${\displaystyle S\rightarrow abc}$

3. ${\displaystyle Ba\rightarrow aB}$

4. ${\displaystyle Bb\rightarrow bb}$

Esta gramática define el lenguaje donde denota una cadena de n consecutivos . Por tanto, el lenguaje es el conjunto de cadenas que constan de 1 o más 's, seguidas del mismo número de 's, seguidas del mismo número de 's. ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ ${\displaystyle a^{n}}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

Algunos ejemplos de la derivación de cadenas en son: ${\displaystyle L(G)}$

• ${\displaystyle {\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}\\&{\underset {2}{\Rightarrow }}aB{\boldsymbol {abc}}c\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}bcc\\&{\underset {4}{\Rightarrow }}aa{\boldsymbol {bb}}cc\end{aligned}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}{\underset {1}{\Rightarrow }}aB{\boldsymbol {aBSc}}c\\&{\underset {2}{\Rightarrow }}aBaB{\boldsymbol {abc}}cc\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}Babccc{\underset {3}{\Rightarrow }}aaB{\boldsymbol {aB}}bccc{\underset {3}{\Rightarrow }}aa{\boldsymbol {aB}}Bbccc\\&{\underset {4}{\Rightarrow }}aaaB{\boldsymbol {bb}}ccc{\underset {4}{\Rightarrow }}aaa{\boldsymbol {bb}}bccc\end{aligned}}}$

(En notación: dice "La cadena P genera la cadena Q mediante la producción i ", y la parte generada se indica cada vez en negrita). ${\displaystyle P{\underset {i}{\Rightarrow }}Q}$

La jerarquía de Chomsky

Cuando Noam Chomsky formalizó por primera vez las gramáticas generativas en 1956, ^[2] las clasificó en tipos que ahora se conocen como jerarquía de Chomsky . La diferencia entre estos tipos es que tienen reglas de producción cada vez más estrictas y, por lo tanto, pueden expresar menos lenguajes formales. Dos tipos importantes son las gramáticas libres de contexto (Tipo 2) y las gramáticas regulares (Tipo 3). Los lenguajes que se pueden describir con dicha gramática se denominan lenguajes libres de contexto y lenguajes regulares , respectivamente. Aunque son mucho menos poderosas que las gramáticas no restringidas (Tipo 0), que de hecho pueden expresar cualquier lenguaje que pueda ser aceptado por una máquina de Turing , estos dos tipos de gramáticas restringidas se usan con mayor frecuencia porque se pueden implementar analizadores para ellas de manera eficiente. ^[7] Por ejemplo, todos los lenguajes regulares pueden ser reconocidos por una máquina de estados finitos , y para subconjuntos útiles de gramáticas libres de contexto existen algoritmos bien conocidos para generar analizadores LL y LR eficientes para reconocer los lenguajes correspondientes que generan esas gramáticas. .

Gramáticas libres de contexto

Una gramática libre de contexto es una gramática en la que el lado izquierdo de cada regla de producción consta de un solo símbolo no terminal. Esta restricción no es trivial; No todos los idiomas pueden generarse mediante gramáticas libres de contexto. Los que pueden hacerlo se denominan lenguajes libres de contexto .

El lenguaje definido anteriormente no es un lenguaje libre de contexto, y esto se puede probar estrictamente usando el lema de bombeo para lenguajes libres de contexto , pero, por ejemplo, el idioma (al menos 1 seguido por el mismo número de ) está libre de contexto. , como se puede definir mediante la gramática con , , el símbolo de inicio y las siguientes reglas de producción: ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G_{2}}$ ${\displaystyle N=\left\{S\right\}}$ ${\displaystyle \Sigma =\left\{a,b\right\}}$ ${\displaystyle S}$

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ab}$

Un lenguaje libre de contexto puede reconocerse en el tiempo ( ver notación O grande ) mediante un algoritmo como el reconocedor de Earley . Es decir, para cada lenguaje libre de contexto, se puede construir una máquina que tome una cadena como entrada y determine en el tiempo si la cadena es miembro del lenguaje, donde está la longitud de la cadena. ^[8] Los lenguajes deterministas libres de contexto son un subconjunto de lenguajes libres de contexto que pueden reconocerse en tiempo lineal. ^[9] Existen varios algoritmos que se dirigen a este conjunto de lenguajes o a algún subconjunto del mismo. ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Gramáticas regulares

En gramáticas regulares , el lado izquierdo es nuevamente solo un símbolo no terminal, pero ahora el lado derecho también está restringido. El lado derecho puede ser la cadena vacía, o un símbolo terminal único, o un símbolo terminal único seguido de un símbolo no terminal, pero nada más. (A veces se utiliza una definición más amplia: se pueden permitir cadenas más largas de terminales o no terminales únicos sin nada más, lo que hace que los idiomas sean más fáciles de denotar y al mismo tiempo se define la misma clase de idiomas).

El lenguaje definido anteriormente no es regular, pero el lenguaje (al menos 1 seguido de al menos 1 , donde los números pueden ser diferentes) sí lo es, tal como se puede definir mediante la gramática con ,, el símbolo de inicio y las siguientes reglas de producción . : ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ ${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G_{3}}$ ${\displaystyle N=\left\{S,A,B\right\}}$ ${\displaystyle \Sigma =\left\{a,b\right\}}$ ${\displaystyle S}$

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

Todos los lenguajes generados por una gramática regular pueden ser reconocidos en el tiempo por una máquina de estados finitos. Aunque en la práctica las gramáticas regulares se expresan comúnmente mediante expresiones regulares , algunas formas de expresión regular utilizadas en la práctica no generan estrictamente los lenguajes regulares y no muestran un rendimiento de reconocimiento lineal debido a esas desviaciones. ${\displaystyle O(n)}$

Otras formas de gramáticas generativas

Tanto lingüistas como informáticos han desarrollado muchas extensiones y variaciones de la jerarquía original de gramáticas formales de Chomsky, generalmente para aumentar su poder expresivo o para hacerlas más fáciles de analizar o analizar. Algunas formas de gramáticas desarrolladas incluyen:

• Las gramáticas contiguas a árboles aumentan la expresividad de las gramáticas generativas convencionales al permitir que las reglas de reescritura operen en árboles de análisis en lugar de solo cadenas. ^[10]
• Las gramáticas de afijos ^[11] y las gramáticas de atributos ^{[12] [13]} permiten aumentar las reglas de reescritura con atributos y operaciones semánticas, útiles tanto para aumentar la expresividad gramatical como para construir herramientas prácticas de traducción de idiomas.

Gramáticas recursivas

Una gramática recursiva es una gramática que contiene reglas de producción que son recursivas . Por ejemplo, una gramática para un lenguaje libre de contexto es recursiva a la izquierda si existe un símbolo A no terminal que puede someterse a las reglas de producción para producir una cadena con A como símbolo más a la izquierda. ^[14] Un ejemplo de gramática recursiva es una cláusula dentro de una oración separada por dos comas. ^[15] Todos los tipos de gramáticas en la jerarquía de Chomsky pueden ser recursivas.

Gramáticas analíticas

Aunque existe una enorme cantidad de literatura sobre algoritmos de análisis , la mayoría de estos algoritmos suponen que el lenguaje que se va a analizar se describe inicialmente mediante una gramática formal generativa , y que el objetivo es transformar esta gramática generativa en un analizador funcional. Estrictamente hablando, una gramática generativa no corresponde de ninguna manera al algoritmo utilizado para analizar un lenguaje, y varios algoritmos tienen diferentes restricciones en la forma de las reglas de producción que se consideran bien formadas.

Un enfoque alternativo es formalizar el lenguaje en términos de una gramática analítica en primer lugar, que corresponde más directamente a la estructura y semántica de un analizador del lenguaje. Ejemplos de formalismos gramaticales analíticos incluyen los siguientes:

• Lenguaje de análisis de arriba hacia abajo (TDPL): un formalismo gramatical analítico altamente minimalista desarrollado a principios de la década de 1970 para estudiar el comportamiento de los analizadores de arriba hacia abajo . ^[dieciséis]
• Gramáticas de enlace : una forma de gramática analítica diseñada para la lingüística , que deriva la estructura sintáctica examinando las relaciones posicionales entre pares de palabras. ^{[17] [18]}
• Análisis de gramáticas de expresión (PEG): una generalización más reciente de TDPL diseñada en torno a las necesidades prácticas de expresividad de los escritores de lenguajes de programación y compiladores . ^[19]

Ver también

• Árbol de sintaxis abstracta
• Gramática adaptativa
• Gramática ambigua
• Forma Backus-Naur (BNF)
• gramática categorial
• Árbol de sintaxis concreto
• Forma extendida Backus-Naur (EBNF)
• Gramática
• Marco gramatical
• sistema L
• Lojban
• Sistema poscanónico
• Gramática de formas
• Fórmula bien formada

Referencias

1. Meduna, Alexander (2014), Lenguajes formales y computación: modelos y sus aplicaciones, CRC Press, p. 233, ISBN 9781466513457. Para más información sobre este tema, consulte problema indecidible .
2. Chomsky, Noam (septiembre de 1956). "Tres modelos para la descripción del lenguaje". Transacciones IRE sobre teoría de la información . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
3. Chomsky, Noam (1957). Estructuras sintácticas . La Haya: Mouton .
4. Ginsburg, Seymour (1975). Propiedades teóricas algebraicas y de autómatas de los lenguajes formales . Holanda del Norte. págs. 8–9. ISBN 978-0-7204-2506-2.
5. Harrison, Michael A. (1978). Introducción a la teoría del lenguaje formal . Reading, Massachusetts: Addison-Wesley Publishing Company. pag. 13.ISBN​ 978-0-201-02955-0.
6. Formas oracionales, gramáticas libres de contexto, David Matuszek
7. Grune, Dick & Jacobs, Ceriel H., Técnicas de análisis: una guía práctica , Ellis Horwood, Inglaterra, 1990.
8. Earley, Jay, "Un algoritmo de análisis eficaz y libre de contexto", Communications of the ACM , vol. 13 No. 2, págs. 94-102, febrero de 1970.
9. Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha". Información y Control . 8 (6): 607–639. doi :10.1016/S0019-9958(65)90426-2.
10. Joshi, Aravind K. y otros. , "Gramáticas adjuntas de árboles", Revista de ciencia de sistemas informáticos , vol. 10 N° 1, págs. 136-163, 1975.
11. Koster, Cornelis HA, "Affix Grammars", en Implementación de ALGOL 68 , North Holland Publishing Company, Ámsterdam, pág. 95-109, 1971.
12. Knuth, Donald E., "Semántica de lenguajes libres de contexto", Teoría de sistemas matemáticos , vol. 2 N° 2, págs. 127-145, 1968.
13. Knuth, Donald E., "Semántica de lenguajes libres de contexto (corrección)", Teoría de sistemas matemáticos , vol. 5 N° 1, págs. 95-96, 1971.
14. Notas sobre análisis y teoría del lenguaje formal Archivado el 28 de agosto de 2017 en Wayback Machine , James Power, Departamento de Ciencias de la Computación de la Universidad Nacional de Irlanda, Maynooth Maynooth, Co. Kildare, Irlanda.JPR02
15. Borenstein, Seth (27 de abril de 2006). "Los pájaros cantores también comprenden la gramática". Heraldo del Noroeste . pag. 2 - a través de Newspapers.com.
16. Birman, Alexander, The TMG Recognition Schema , tesis doctoral, Universidad de Princeton, Departamento de Ingeniería Eléctrica, febrero de 1970.
17. Sleator, Daniel D. & Temperly, Davy, "Análisis del inglés con una gramática de vínculo", Informe técnico CMU-CS-91-196, Ciencias de la Computación de la Universidad Carnegie Mellon, 1991.
18. Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar", Tercer taller internacional sobre tecnologías de análisis , 1993 (versión revisada del informe anterior).
19. Ford, Bryan, Packrat Parsing: un algoritmo práctico de tiempo lineal con retroceso , tesis de maestría, Instituto de Tecnología de Massachusetts, septiembre de 2002.

enlaces externos