En la teoría del lenguaje formal , una gramática (cuando no se da el contexto, a menudo llamada gramática formal para mayor claridad) describe cómo formar cadenas del alfabeto de un idioma que sean válidas de acuerdo con la sintaxis del idioma . Una gramática no describe el significado de las cadenas o lo que se puede hacer con ellas en cualquier contexto, solo su forma. Una gramática formal se define como un conjunto de reglas de producción de 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 en una gramática como un generador de lenguaje. Sin embargo, a veces también se puede utilizar como base para un " reconocedor ", una función en informática que determina si una determinada cadena 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 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 los lenguajes naturales) dividiéndolo en un conjunto de símbolos y analizando cada uno contra la gramática del idioma. La mayoría de los lenguajes tienen los significados de sus enunciados 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 desglosarlo parte por parte y observar su forma analizada (conocida como su árbol de análisis sintáctico en informática y como su estructura profunda en gramática generativa ).
Historia
Pāṇini 's tratado Astadyayi da reglas formales de producción y definiciones para describir la gramática formal de sánscrito . [2] Existen diferentes usos de "forma" y "formalismo", que han cambiado con el tiempo, dependiendo de los campos con los que el autor relevante estuvo en contacto. En [3] se ofrece una descripción histórica del concepto .
Ejemplo introductorio
Una gramática consiste principalmente en un conjunto de reglas de producción , que reescriben reglas para transformar cadenas. Cada regla especifica un reemplazo de una cadena en 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 ocurrencia 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 no terminales y 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 de inicio mediante la aplicación (posiblemente repetida) de sus reglas de cualquier forma posible. Si hay esencialmente diferentes formas de generar la misma cadena, se dice que la gramática es ambigua .
En los siguientes ejemplos, los símbolos de terminal son una y b , y el símbolo de inicio es S .
Ejemplo 1
Supongamos que tenemos las siguientes reglas de producción:
- 1.
- 2.
luego comenzamos con S , y podemos elegir una regla para aplicarle. Si elegimos la regla 1, obtenemos la cadena aSb . Si luego elegimos la regla 1 nuevamente, 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 opciones más brevemente, usando símbolos:.
El lenguaje de la gramática es el conjunto infinito , dónde es repetido 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 (solo aparecen no terminales individuales como lados izquierdos) y no es ambigua.
Ejemplos 2 y 3
Supongamos que las reglas son las siguientes:
- 1.
- 2.
- 3.
Esta gramática no está libre de contexto debido a la regla 3 y es ambigua debido a las múltiples formas en que la regla 2 puede usarse para generar secuencias de s.
Sin embargo, el lenguaje que genera es simplemente el conjunto de todas las cadenas no vacías que consta de sy / o s. Esto es fácil de ver: para generar un desde un , 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 desy luego reemplace cada uno de ellos con o como nos plazca.
Ese mismo lenguaje puede ser generado alternativamente por una gramática no ambigua y libre de contexto; por ejemplo, la gramática regular con reglas
- 1.
- 2.
- 3.
- 4.
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, [4] [5] una gramática G consta de los siguientes componentes:
- Un conjunto finito N de símbolos no terminales , que es disjunta con las cadenas formadas a partir de G .
- Un conjunto finito de símbolos terminales que es disjuntos de N .
- Un conjunto finito P de reglas de producción , cada regla de la forma
- dónde es 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 no terminal. En el caso de que la segunda cadena (el "cuerpo") consista únicamente en la 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.
- Un símbolo distinguido ese es el símbolo de inicio , también llamado símbolo de oració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 frases en la literatura. [6] [7]
Algunas construcciones matemáticas sobre gramáticas formales
El funcionamiento de una gramática se puede definir en términos de relaciones en cadenas:
- Dada una gramática , la relación binaria (pronunciado como "G deriva en un paso") en cadenas en es definido por:
- la relación (pronunciado como G deriva en cero o más pasos ) se define como el cierre transitivo reflexivo de
- a forma oracional es miembro de que se puede derivar en un número finito de pasos desde el símbolo de inicio ; 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 . [8]
- el idioma de, denotado como , se define como todas aquellas oraciones que pueden derivarse en un número finito de pasos desde el símbolo de inicio ; es decir, el conjunto.
Tenga en cuenta que 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 las reglas de reescritura, y solo están interesados en reescribir desde el símbolo de inicio designado a cadenas sin símbolos no terminales.
Ejemplo
Para estos ejemplos, los lenguajes formales se especifican mediante la notación del generador de conjuntos .
Considere la gramática dónde , , es el símbolo de inicio, y consta de las siguientes reglas de producción:
- 1.
- 2.
- 3.
- 4.
Esta gramática define el idioma dónde denota una cadena de n consecutivos's. Por tanto, el idioma es el conjunto de cadenas que constan de 1 o más, seguido del mismo número de , seguido del mismo número de 's.
Algunos ejemplos de la derivación de cadenas en están:
- (Nota sobre la 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).
La jerarquía de Chomsky
Cuando Noam Chomsky formalizó por primera vez las gramáticas generativas en 1956, [4] 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 idiomas que pueden describirse con una gramática tal son llamados lenguajes libres de contexto y lenguajes regulares , respectivamente. Aunque son mucho menos potentes 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 restringidos de gramáticas se utilizan con mayor frecuencia porque los analizadores sintácticos para ellos se pueden implementar de manera eficiente. [9] 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 analizadores 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 lenguajes pueden ser generados por gramáticas libres de contexto. Los que pueden se denominan lenguajes libres de contexto .
El idioma definido anteriormente no es un lenguaje libre de contexto, y esto se puede probar estrictamente utilizando el lema de bombeo para lenguajes libres de contexto , pero por ejemplo el lenguaje (al menos 1 seguido por el mismo número de 's) es libre de contexto, ya que puede ser definido por la gramática con , , el símbolo de inicio y las siguientes reglas de producción:
- 1.
- 2.
Un lenguaje libre de contexto se puede reconocer en tiempo ( ver notación Big O ) 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 tiempo si la cadena es un miembro del idioma, donde es la longitud de la cuerda. [10] Los lenguajes libres de contexto deterministas son un subconjunto de lenguajes libres de contexto que se pueden reconocer en tiempo lineal. [11] Existen varios algoritmos que apuntan a este conjunto de lenguajes o algún subconjunto de él.
Gramáticas regulares
En las 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 solo símbolo de terminal, o un solo símbolo de terminal seguido de un símbolo no terminal, pero nada más. (A veces se usa 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 lenguajes sean más fáciles de denotar sin dejar de definir la misma clase de idiomas).
El idioma definido anteriormente no es regular, pero el idioma (al menos 1 seguido de al menos 1 , donde los números pueden ser diferentes) es, como puede ser definido por la gramática con , , el símbolo de inicio y las siguientes reglas de producción:
Todos los idiomas generados por una gramática regular se pueden reconocer en tiempo por una máquina de estados finitos. Aunque, en la práctica, las gramáticas regulares se expresan comúnmente usando 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.
Otras formas de gramáticas generativas
Tanto los lingüistas como los informáticos han desarrollado muchas extensiones y variaciones de la jerarquía original de Chomsky de las gramáticas formales, 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 adyacentes 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. [12]
- Las gramáticas de afijos [13] y las gramáticas de atributos [14] [15] 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 no terminal A que se puede pasar por las reglas de producción para producir una cadena con A como el símbolo más a la izquierda. [16] Un ejemplo de gramática recursiva es una cláusula dentro de una oración separada por dos comas. [17] Todos los tipos de gramáticas en la jerarquía de Okoye pueden ser recursivos. [ cita requerida ]
Gramáticas analíticas
Aunque hay una enorme cantidad de literatura sobre algoritmos de análisis sintáctico , la mayoría de estos algoritmos asumen que el idioma que se va a analizar es inicialmente descrito por medio de un generador gramática formal, y que el objetivo es transformar esta gramática generativa en un analizador de trabajo. Estrictamente hablando, una gramática generativa no se corresponde de ninguna manera con el algoritmo utilizado para analizar un lenguaje, y varios algoritmos tienen diferentes restricciones sobre 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 sintáctico para el lenguaje. Ejemplos de formalismos de gramática analítica incluyen los siguientes:
- Language Machine implementa directamente gramáticas analíticas sin restricciones. Las reglas de sustitución se utilizan para transformar una entrada para producir salidas y comportamiento. El sistema también puede producir el diagrama lm , que muestra lo que sucede cuando se aplican las reglas de una gramática analítica sin restricciones.
- Lenguaje de análisis sintáctico descendente (TDPL): un formalismo gramatical analítico altamente minimalista desarrollado a principios de la década de 1970 para estudiar el comportamiento de los analizadores sintácticos descendentes . [18]
- Gramáticas de enlace : una forma de gramática analítica diseñada para la lingüística , que deriva la estructura sintáctica al examinar las relaciones posicionales entre pares de palabras. [19] [20]
- 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 redactores de lenguajes de programación y compiladores . [21]
Ver también
- Árbol de sintaxis abstracta
- Gramática adaptativa
- Gramática ambigua
- Forma Backus – Naur (BNF)
- Gramática categórica
- Árbol de sintaxis concreta
- Formulario extendido Backus – Naur (EBNF)
- Marco gramatical
- Sistema L
- Lojban
- Sistema poscanónico
- Forma gramatica
- Fórmula bien formada
Referencias
- ^ Meduna, Alexander (2014), Computación y lenguajes formales: modelos y sus aplicaciones , CRC Press, p. 233, ISBN 9781466513457. Para obtener más información sobre este tema, consulte Problema indecidible .
- ^ "Biografía de Panini" . www-history.mcs.st-andrews.ac.uk . Archivado desde el original el 15 de agosto de 2018.
- ^ McElvenny J (2019). McElvenny J (ed.). Forma y formalismo en lingüística (pdf) . Berlín: Language Science Press. doi : 10.5281 / zenodo.2654375 . ISBN 978-3-96110-182-5.
- ^ a b 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 .
- ^ Chomsky, Noam (1957). Estructuras sintácticas . La Haya: Mouton .
- ^ Ginsburg, Seymour (1975). Propiedades teóricas algebraicas y autómatas de los lenguajes formales . Holanda Septentrional. págs. 8–9. ISBN 978-0-7204-2506-2.
- ^ Harrison, Michael A. (1978). Introducción a la teoría del lenguaje formal . Reading, Mass .: Addison-Wesley Publishing Company. pag. 13. ISBN 978-0-201-02955-0.
- ^ Formas oracionales, Gramáticas libres de contexto, David Matuszek
- ^ Grune, Dick & Jacobs, Ceriel H., Técnicas de análisis: una guía práctica , Ellis Horwood, Inglaterra, 1990.
- ^ Earley, Jay, " Un algoritmo de análisis sin contexto eficiente ", Comunicaciones del ACM , vol. 13 No. 2, págs. 94-102, febrero de 1970.
- ^ Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
- ^ Joshi, Aravind K., et al. , " Gramáticas adjuntas de árboles ", Journal of Computer Systems Science , vol. 10, núm. 1, págs. 136-163, 1975.
- ^ Koster, Cornelis HA, "Gramáticas de afijo", en Implementación de ALGOL 68 , North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
- ^ Knuth, Donald E., " Semántica de lenguajes libres de contexto ", Teoría de sistemas matemáticos , vol. 2, núm. 2, págs. 127-145, 1968.
- ^ Knuth, Donald E., "Semántica de lenguajes libres de contexto (corrección)", Teoría de sistemas matemáticos , vol. 5 No. 1, págs. 95-96, 1971.
- ^ Notas sobre análisis y teoría del lenguaje formal , James Power, Departamento de Ciencias de la Computación de la Universidad Nacional de Irlanda, Maynooth Maynooth, Co. Kildare, Irlanda. JPR02
- ^ Borenstein, Seth (27 de abril de 2006). "Los pájaros cantores también comprenden la gramática" . Northwest Herald . pag. 2 - a través de Newspapers.com.
- ^ Birman, Alexander, The TMG Recognition Schema , tesis doctoral, Universidad de Princeton, Departamento de Ingeniería Eléctrica, febrero de 1970.
- ^ Sleator, Daniel D. & Temperly, Davy, " Análisis del inglés con una gramática de enlace ", Informe técnico CMU-CS-91-196, Ciencias de la computación de la Universidad Carnegie Mellon, 1991.
- ^ Sleator, Daniel D. & Temperly, Davy, "Análisis del inglés con una gramática de enlace", tercer taller internacional sobre tecnologías de análisis , 1993. (Versión revisada del informe anterior).
- ^ Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking , Tesis de maestría, Instituto de Tecnología de Massachusetts, septiembre de 2002.