Gramática libre de contexto
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de enero de 2022; la verificación requiere 1 edición .La gramática libre de contexto ( CS-grammar , gramática libre de contexto ) es un caso especial de gramática formal (tipo 2 según la jerarquía de Chomsky ), en el que las partes izquierdas de todas las producciones son no terminales simples (objetos que denotan cualquier esencia de el idioma (por ejemplo: una fórmula, una expresión aritmética, un comando) y no tener un significado simbólico específico). El significado del término "sin contexto" es que es posible aplicar la producción a un no terminal y, además, independientemente del contexto de este no terminal (a diferencia del caso general de la gramática de Chomsky sin restricciones ).
Un lenguaje que puede ser especificado por un CFG se denomina lenguaje libre de contexto o CFL.
De hecho, la gramática KS es otra forma de BNF .
Aplicación
Las gramáticas COP tienen mucho uso en informática . Establecen la estructura gramatical de la mayoría de los lenguajes de programación , datos estructurados, etc. (ver análisis gramatical )
Para analizar una gramática COP, un autómata push-down es suficiente , para analizar gramáticas que no son COP, se puede requerir una máquina completa de Turing .
Tipos de gramáticas CS
Reconocedores
Hay dos clases diferentes de reconocedores (autómatas para el reconocimiento) de lenguajes CF. Sus nombres están relacionados con el orden en que se construye el árbol de salida. Como regla general, todos los reconocedores leen la cadena de caracteres de entrada de izquierda a derecha, ya que se espera tal notación al escribir el código fuente de los programas.
Resolutores aguas abajo
Resolutores de arriba hacia abajo que generan cadenas de salida a la izquierda y construyen el árbol de salida de arriba a abajo.
Utilizan modificaciones del algoritmo con la selección de alternativas. Al crearlos, se utiliza un método que le permite seleccionar de forma única una y solo una alternativa en cada paso del autómata MP (el paso de "expulsión" en este autómata siempre se realiza de forma única).
Reconocedores ascendentes
Resolutores ascendentes que generan cadenas de salida a la derecha y construyen el árbol de salida de abajo hacia arriba.
Los reconocedores aguas arriba utilizan modificaciones del algoritmo shift-fold (o shift-fold, que es lo mismo). Al crearlos, se utilizan métodos que le permiten elegir sin ambigüedad entre realizar un "cambio" ("transferencia") o "convolución" en cada paso del autómata MP extendido, y cuando se realiza la convolución, puede elegir sin ambigüedad la regla por el cual se realizará la convolución. Algoritmo "shift-convolution".
Ejemplos
Ejemplos de gramáticas SF y sus correspondientes lenguajes SF:
Voltear palabra
Dado por fórmula
- Terminales: letras del alfabeto ;
- No terminal: ;
- Productos:
- El no terminal inicial es .
Corchetes anidados
- Terminales: y ;
- no terminal: ;
- productos: ;
- inicial no terminal - .
Esta gramática especifica el idioma de los corchetes anidados .
El lenguaje de Dick
Expresión aritmética
- Terminales: '+', '-', '*', '/', '(', ')', 'x'
- no terminales: <expresión>, <término>, <multiplicador>
- productos:
- no terminal inicial: <expresión>.
Esta gramática define una expresión aritmética que contiene las operaciones aritméticas más simples sobre la variable x. Si reemplazamos el terminal 'x' con el no terminal <número>, obtenemos una gramática que especifica una expresión aritmética que consta de operaciones de suma, resta, multiplicación y división en números enteros.
Limitaciones de las gramáticas COP
No todos los idiomas se pueden definir usando gramáticas CF. La forma más fácil de probar esto es la siguiente: las gramáticas COP forman un conjunto numerable, mientras que la cardinalidad del conjunto de todos los idiomas es un continuo . Se puede obtener una prueba constructiva del mismo hecho, por ejemplo, sobre la base de que el lenguaje { a n b n c n | n ≥1} no está libre de contexto; sin embargo, no parece haber una prueba breve de la última afirmación: las pruebas publicadas se basan en el teorema de crecimiento para lenguajes libres de contexto.
Generalizaciones
La gramática de adición de árboles generaliza la gramática libre de contexto en el sentido de que la unidad elemental en las reglas de inferencia son los árboles, no los caracteres individuales.
Véase también
Literatura
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
- Belousov A. I., Tkachev S. B. Matemáticas discretas. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| Tipo 3 |
|
| analizando | |