Gramática formal

La gramática formal o simplemente gramática en la teoría de los lenguajes formales es una forma de describir un lenguaje formal, es decir, de seleccionar un determinado subconjunto del conjunto de todas las palabras de algún alfabeto finito . Hay gramáticas generativas y de reconocimiento (o analíticas ): las primeras establecen las reglas con las que puedes construir cualquier palabra del idioma, y las segundas te permiten determinar a partir de una palabra dada si está incluida en el idioma o no.

Términos

El terminal (símbolo terminal) es un objeto que está directamente presente en las palabras del idioma correspondiente a la gramática, y tiene un significado específico e inmutable (una generalización del concepto de "letras"). En los lenguajes formales utilizados en una computadora, todos o parte de los caracteres ASCII estándar -letras latinas, números y caracteres especiales- suelen tomarse como terminales .
Non-terminal (símbolo no terminal) es un objeto que denota alguna entidad del lenguaje (por ejemplo: una fórmula, una expresión aritmética, un comando) y no tiene un valor simbólico específico.

Gramáticas generativas

Las palabras del lenguaje dadas por la gramática son todas secuencias de terminales que se emiten (generan) a partir del no terminal inicial de acuerdo con las reglas de salida.

Para configurar la gramática, debe configurar los alfabetos de terminales y no terminales, un conjunto de reglas de inferencia y también seleccionar el inicial en el conjunto de no terminales.

Entonces, la gramática se define por las siguientes características:

$\Sigma$ — conjunto ( alfabeto ) de símbolos terminales
N es un conjunto ( alfabeto ) de símbolos no terminales
P es un conjunto de reglas de la forma: "lado izquierdo" "lado derecho", donde: $\flecha correcta$
- "lado izquierdo" es una secuencia no vacía de terminales y no terminales que contienen al menos un no terminal
- "lado derecho" - cualquier secuencia de terminales y no terminales
S es el símbolo inicial (o inicial) de la gramática del conjunto de no terminales.

Conclusión

Una salida es una secuencia de líneas que consta de terminales y no terminales, donde la primera línea es una línea que consta de un no terminal inicial, y cada línea subsiguiente se obtiene de la anterior reemplazando alguna subcadena de acuerdo con una (cualquiera) de las reglas La cadena final es una cadena que consta completamente de terminales y, por lo tanto, es una palabra del idioma.

La existencia de una derivación para una determinada palabra es un criterio de su pertenencia a la lengua definida por la gramática dada.

Tipos de gramáticas

Según la jerarquía de Chomsky , las gramáticas se dividen en 4 tipos, cada subsiguiente es un subconjunto más limitado del anterior (pero también más fácil de analizar):

tipo 0. gramáticas ilimitadas - cualquier regla es posible
tipo 1. gramáticas sensibles al contexto : la parte izquierda puede contener un no terminal rodeado por un "contexto" (secuencias de caracteres que están presentes en la misma forma en la parte derecha); el no terminal en sí se reemplaza por una secuencia de caracteres no vacía en el lado derecho.
tipo 2. gramáticas libres de contexto : la parte izquierda consta de un no terminal.
tipo 3. Las gramáticas regulares son más simples, equivalentes a los autómatas finitos .

Además, hay:

Gramáticas no abreviadas . Cada regla de tal gramática tiene la forma , donde . La longitud del lado derecho de la regla no es menor que la longitud del lado izquierdo [1] . $\alpha \rightarrow \beta$ $|\alfa |\leqslant |\beta |$
Gramáticas lineales . Cada regla de una gramática de este tipo tiene la forma , o , es decir, el lado derecho de la regla no puede contener más de una aparición de un no terminal [2] . $A \ flecha derecha uBv$ $Una \ flecha derecha u$

Aplicación

Las gramáticas independientes del contexto se aplican ampliamente para definir la estructura gramatical en el análisis gramatical .
Las gramáticas regulares (en forma de expresiones regulares ) se utilizan ampliamente como plantillas para la búsqueda, el desglose y la sustitución de textos, incluso en el análisis léxico .

Un ejemplo son las expresiones aritméticas

Considere un lenguaje simple que define un subconjunto limitado de fórmulas aritméticas que consta de números naturales , paréntesis y signos aritméticos. Vale la pena señalar que aquí en cada regla en el lado izquierdo de la flecha solo hay un símbolo no terminal. Estas gramáticas se denominan libres de contexto . $\flecha correcta$

Alfabeto terminal:

\Sigma

= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}

Alfabeto no terminal:

{ FÓRMULA, SIGNO, NÚMERO, NÚMERO }

Normas:

1. FÓRMULA FÓRMULA SIGNO FÓRMULA

\a

(una fórmula tiene dos fórmulas conectadas por un signo) 2. NÚMERO DE FÓRMULA

\a

(la fórmula es un número) 3. FÓRMULA (FÓRMULA)

\a

(una fórmula es una fórmula entre paréntesis) 4. FIRMAR + | - | * | /

\a

(el signo es más o menos, o multiplicar o dividir) 5. NÚMERO DÍGITO

\a

(un número es un número) 6. NÚMERO NÚMERO DÍGITO

\a

(un número es un número y un número) 7. NÚMERO 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\a

(el dígito es 0 o 1, o ... 9)

Inicial no terminal:

FÓRMULA

Conclusión :

Derivemos la fórmula (12+5) usando las reglas de inferencia enumeradas. Para mayor claridad, los lados de cada reemplazo se muestran en pares, en cada par se subraya la parte reemplazada.

FÓRMULA (FÓRMULA)

{\ stackrel {3}{\to ))

( FÓRMULA ) ( FÓRMULA SIGNO FÓRMULA )

{\ stackrel {1}{\to ))

(FÓRMULA SIGNO FÓRMULA) (FÓRMULA + FÓRMULA)

{\ stackrel {4}{\to ))

( FÓRMULA + FÓRMULA ) ( FÓRMULA + NÚMERO )

{\ stackrel {2}{\to ))

( FÓRMULA + NÚMERO ) ( FÓRMULA + NÚMERO )

{\ stackrel {5}{\to ))

( FÓRMULA + NÚMERO ) ( FÓRMULA + 5 )

{\ stackrel {7}{\to ))

( FÓRMULA + 5) ( NÚMERO + 5)

{\ stackrel {2}{\to ))

( NÚMERO + 5) ( NÚMERO DÍGITO + 5)

{\ stackrel {6}{\to ))

( NÚMERO DÍGITO + 5) ( DÍGITO DÍGITO + 5)

{\ stackrel {5}{\to ))

( DÍGITO DÍGITO + 5) ( 1 DÍGITO + 5)

{\ stackrel {7}{\to ))

(1 DÍGITO + 5) (1 2 + 5)

{\ stackrel {7}{\to ))

Gramáticas analíticas

Las gramáticas generativas no son el único tipo de gramáticas, pero son las más comunes en las aplicaciones de programación. A diferencia de las gramáticas generativas, la gramática analítica (de reconocimiento) define un algoritmo que le permite determinar si una palabra determinada pertenece al idioma. Por ejemplo, cualquier lenguaje regular puede reconocerse usando una gramática definida por una máquina de estado , y cualquier gramática libre de contexto puede reconocerse usando un autómata basado en pila . Si una palabra pertenece a un idioma, dicho autómata construye su salida de forma explícita, lo que hace posible analizar la semántica de esta palabra.

Véase también

JFLAP - simulador de autómatas, máquinas de Turing, gramáticas
analizando
gramática ambigua
El problema de gramática mínima
Gramática con estructura de frase

Literatura

Belousov A. I., Tkachev S. B. Matemáticas discretas. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Gramáticas y lenguajes formales. — M .: Nauka, 1973.
Kasyanov VN Conferencias sobre la teoría de lenguajes formales, autómatas y complejidad computacional. - Novosibirsk: NGU, 1995. - 112 p.
Chomsky N., Miller J. Introducción al análisis formal de los lenguajes naturales // Colección cibernética / Ed. A. A. Lyapunova y O. B. Lupanova. — M .: Mir, 1965.
Gross M., Lanten A. Teoría de las gramáticas formales. — M .: Mir, 1971. — 296 p.

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami