Gramaticas

1.- GRAMATICAS

1.1 Introducción a las Gramáticas
Una gramática es una herramienta o notación que nos
permite definir un lenguaje por medio de una serie de reglas
que nos dicen como construír cadenas v´alidas (oraciones)
para el lenguaje.
Chomski formalizó el concepto de una gramatica, al hacer
observaciones importantes en la complejidad de una
gramática que a su vez establece la complejidad de el lenguaje
Como se estableció antes, un lenguaje es un conjunto finíto
de cadenas desde un alfabeto. Una gramática es una forma de
describir al lenguaje.

1.2 Estructuras de las gramáticas
Una gramática G consiste de:
Un alfabeto de símbolos terminales ∑
Un conjunto finíto de variables (símbolos no-terminales) V
Un conjunto de reglas de substitución o producciones P
Un símbolo inicial ∑

G = (∑, V, P, S)

Una regla de substitución o producción está formada por
una parte izquierda α y una parte derecha β: α → β
Su significado es reemplazar α con β.

La parte izquierda son cadenas desde V U ∑, que contienen al
menos una variable desde V: α es un miembro de

(V U ∑)* V (V U ∑)*

Mientras que el lado derecho son cadenas desde V U ∑: β es
un miembro de

(V U ∑)*

La gramática produce cadenas de ∑* al aplicar las producciones e
iniciando con el símbolo inicial hasta que no existan variables.
Cada vez que una producción o regla es aplicada, una forma de
sentencia (cadenas de variables de V y terminales de ∑) es
producida.

El lenguaje generado por la gramática, L(G), es el conjunto de
cadenas que pueden generarse aplicando las reglas anteriormente
descritas.

Ejemplo: Consideremos la siguiente gramática
G = (∑, V, P, S)

V= {S, A}

∑= {a, m, o, t}

P={(1) S → toAto, (2) A → ma, (3) A → maA }
Que genera el lenguaje
L(G)= {tomato, tomamato, tomamamato,...}
Usando las siguientes reglas para la cadena tomamato
S→(1) toAto→(3) tomaAto→(2)tomamato

1.3 Clasificación de las Gramáticas
N. Chomsky en 1959 en su famoso artículo “On certain formal
properties of grammars” definió cuatro familias de gramáticas
(y lenguajes) que forman lo que se llama la jerarquía de
Chomsky. Estas son: gramáticas sin restricciones, de contexto
sensitivo, de contexto libre y regulares (tipo 0, 1, 2 y 3).
La restricciones puestas en cada regla aumentan con el número
de la gramática.

Gramáticas sin Restricciones.
Son el tipo de gramática mas generales. Una producción u→v
indica que una ocurrencia de una subcadena u en una cadena
puede ser reemplazada con la cadena v. La única restricción
en una producción es que el lado izquierdo no sea cadena nula.

Una definición formal de una gramática sin restricciones es
la siguiente:
Un cuadruplo (V, ∑, P, S) donde V es un conjunto finito de
variables, ∑ (el alfabeto) es un conjunto de símbolos terminales
(del alfabeto), P es un conjunto de producciones y S es el
símbolo inicial de V. Una producción de esta clase de gramática
tiene la forma u→v, donde u es miembro de (V U ∑)+ y v es
miembro de (V U ∑)* .

Ejemplo: La gramática sin restricciones
V= {S, A, C}
∑= {a,b,c}
S → aAbc | λ
A → aAbC | λ
Cb → bC
Cc → cc
Con símbolo inicial S genera el lenguaje {ai bi ci | i>=0}.

Gramáticas de Contexto Sensitivo
Estas gramáticas representan un paso intermedio entre las
gramáticas de contexto libre y las gramáticas sin restricciones.
Para estas gramáticas no existe restricción alguna en la parte
izquierda de la producción, pero la longitud de la parte derecha
debe ser al menos la longitud de la parte izquierda.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:
Un cuadruplo G= (V, ∑, P, S) donde cada producción tiene la
forma u → v, donde u es un miembro de (V U ∑)+ , v es miembro
de (V U ∑)+ y longitud(u) >= longitud (v). Un lenguaje generado
por una gramática de contexto sensitivo es llamado lenguaje
de contexto sensitivo (en gramáticas sin restricciones el lenguaje
también es llamado sin restricciones).

Si eliminamos las producciones de cadena vacía de la anterior
gramática sin restricciones, tenemos una gramática de contexto
sensitivo.
S → aAbc | abc
A → aAbC | abC
que produce un lenguaje similar al ejemplo anterior.

Gramáticas de Contexto Libre
La flexibilidad proporcionada por las gramáticas de contexto
libre es tal que es la mas usada para definir la sintaxis de los
lenguajes de programación.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:

Es un cuadruplo G= (V, ∑, P, S) donde V es un conjunto finito
de variables, ∑ es un conjunto finito de símbolos terminales,
P es un conjunto finito de reglas y S es el símbolo inicial.
Cada producción tiene la forma u→v, donde u es una variable
del conjunto V, y v es un miembro de (V U ∑)* . Esto quiere decir
En la parte izquierda dela producción viene siempre una variable
(símbolo no terminal) y en la parte derecha pueden venir
cualquier número de símbolos terminales y no terminales
incluyendo la cadena nula.

Una gramática de contexto libre produce un lenguaje también de
contexto libre: G → L(G).

Ejemplo: La siguiente gramática genera el lenguaje que consiste
de cadenas con un número par positivo de a’s.

G= (V, ∑ , P, S)
V={S,A}
∑={a,b}
P: S → AA
A → AAA | bA | Ab | a

Una derivación por la izquierda es la siguiente:
S→AA→bAA→baA→baa

Una derivación por la derecha
S→AA→AbA→Aba→aba

Gramáticas Regulares
Estas gramáticas constituyen una importante subclase de
las gramáticas de contexto libre. Son también útiles en la
definición de lenguajes de programación.
Una gramática es regular (GR) si cada regla o producción
cumple con las siguientes formas:

1.- A → a
2.- A → aB
3.- A → λ

Donde A, B son miembros de V y a es miembro de ∑ .
Una GR G genera un lenguaje regular L(G).

Ejemplo
La siguiente es una GCL ( λ U (ab)+a*)


G: S → abSA | λ
A → Aa | λ

una correspondiente gramática regular sería:

S → aB | λ
B → bS | bA
A → aA | λ

1.4 Representación de Gramáticas
En las secciones anteriores, se usaron pequeñas gramáticas
para generar lenguajes también pequeños. Esos ejemplos
sirvieron para ilustrar el uso de gramáticas para definir lenguajes.
Por otra parte, en el diseño de lenguajes de programación se
maneja sintaxis y alfabetos mas complejas y mas grandes. Esto
Por supuesto, incrementa la complejidad de las reglas para
generar el lenguaje.

Notación de BNF.
John Backus y Peter Naur inventaron un sistema de reglas para
definir el lenguaje de programación ALGOL 60. Este sistema
recibió el nombre de Backus-Naur Form o BNF. La sintaxis del
Pascal también fue definido con este sistema o técnica, y hoy en
día se usa para definir la gran mayoría de los lenguajes de
programación

Una especificación BNF es un conjunto de reglas de producción,
escritas como:
::=

Diagramas Sintácticos
Es también un tipo de notación para especificar la sintaxis de
Un lenguaje. La diferencia con la notación BNF es que en esta
se usan líneas y figuras en lugar de nombres.