GRAMATICA

INDICE

1. Definición de Gramática
2. Tipos de Gramática
2.1. Gramática Regulares
2.2. Gramática Libre de Contexto

1. Definición de Gramática

La gramática es un ente formal para especificar de una manera finita, el conjunto de cadenas de símbolos que constituyen un lenguaje.

Una definición formal de gramática seria:

Una gramática es una cuádrupla:

                            G=(NT,T,S,R)

Dónde:

NT conjunto de símbolos no terminales

T conjunto de símbolos terminales

S es el símbolo inicial y pertenece a NT

R conjunto de reglas de producción

Todas las cadenas del lenguaje definido por la gramática están formados con símbolos del vocabulario terminal T. el vocabulario terminal se define por numeración de los símbolos terminales.

El vocabulario no terminales NT es el conjunto de símbolos introducidos como elementos auxiliares para la definición de la gramática, y que no figuren en las sentencias del lenguaje.

El símbolo S es un símbolo no terminal a partir del cual se aplican las reglas de producción para obtener las distintas cadenas del lenguaje.

Las producciones R son las reglas que se aplican desde el símbolo inicial para obtener las cadenas del lenguaje.

2. Tipos de Gramática

2.1. Gramática Regulares

Definición:

·         Es una gramática formal que adquirió gran importancia para el desarrollo de lenguajes de programación.

·         Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares.

Las gramáticas regulares de dividen dependiendo de la estructura de las producciones, esto depende de la dirección hacia la que se expanden:

1.     Gramática Regular Derecha: Los símbolos no terminales se ubican al lado derecho de la producción(P) son de la siguiente forma:

·         A → a, A es un símbolo no-terminal en N y a uno terminal en T(terminal).

·         A → aB, donde A y B pertenecen a N(no terminal) y a pertenece a T(terminal).

·         A → ε, donde A pertenece a (no terminal).

1.     Gramática Regular Izquierdo: Los símbolos no terminales se ubican al lado izquierdo de la producción ,sus reglas son las siguientes:

·         A → a, donde A es un símbolo no-terminal en N y a uno terminal en T (terminal).

·         A → Ba, donde A y B pertenecen a N (no terminal) y a pertenece a T (terminal).

·         A → ε, donde A pertenece a N (no terminal).

En ambos casos se incluye A → ε, si el lenguaje que se quiere generar es  contiene una cadena vacía

2.2. Gramática Libre de Contexto

En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma:

V → w

Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera.

Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada, determinen cómo puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto