Page 76 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

76

Relación de derivación general entre cadenas:

+
Sea Α y sea Α cadenas pertenecientes al vocabulario , se puede indicar que están en una
1

relación de derivación en la gramática G, si existen: Α , Α , Α , Α …… Α tal que:
2
1
4

3

Α  Α
1
2
Α  Α
2
3
Α  Α
4
3
……
………
………..
Α ( −1)  Α Desprendiéndose de aquí que: Α  Α

1

O sea que induce a realizar las producciones en un orden, de presentación, sin embargo, no
necesariamente es así. Lo que sí debe detectarse, aplicando las reglas es el patrón general que
describe las cadenas generadas, a fin de identificar el lenguaje. Esto es así, porque: una gramática
genera un único lenguaje, pero un mismo lenguaje puede ser generado por varias gramáticas
Según la forma de las producciones, las gramáticas se clasifican en:
1- Regulares: en la parte izquierda sólo hay un no terminal, y la parte derecha puede haber:
No terminal → terminal

No terminal → terminal y no terminal
No terminal → cadena vacía λ

2- Independientes del contexto (context-free): en la parte izquierda sólo hay un no
terminal, en la parte derecha no hay restricciones.

Importante: en los compiladores solo se usa gramáticas regulares y gramáticas GIC. Las
gramáticas regulares se usan para especificar tokens, las GIC se usan para verificar la
sintaxis de las construcciones del lenguaje fuente.

3- Dependientes del contexto: en la parte izquierda puede haber terminales y no terminales,
pero al menos debe haber un no terminal, y la longitud de la parte derecha debe ser mayor
o igual que la de la parte izquierda.

4- No restringidas

Concluyendo:

 Una producción o regla tiene una parte derecha y una izquierda. Tanto la parte izquierda
como derecha son cadenas de símbolos terminales y no terminales.
 El símbolo inicial de la gramática es la parte izquierda de la primera producción.
 Una derivación es una secuencia de cadenas de símbolos, en las que cada cadena es
resultado de la aplicación de una regla de la gramática a la cadena anterior. Una derivación
válida es aquella en que la primera cadena de la secuencia es el símbolo inicial y la última
es una cadena de terminales.