TALLER

UNIVERSIDAD DE CALDAS
FACULTAD DE INGENIERÍA
PROGRAMA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN
ESTRUCTURA DE LENGUAJES
TALLER GRAMATICAS INDEPENDIENTES DEL CONTEXTO
6/12/2013Individual, para entregar en hoja para el viernes 20 de diciembre de 2013, es calificable.
1. Cree Gramáticas Independientes del Contexto para los siguientes lenguajes
a. El conjunto detodas las cadenas de símbolos a y b tales que toda a va seguida
inmediatamente de una b.
b. Las cadenas de símbolos a y b con un número igual de a y b.
c. Las cadenas de símbolos ay b de la forma aa..aabb..bb con número igual de a y de
b.
d. Las cadenas de símbolos de a y b que solo generan palíndromes (se leen igual de
derecha a izquierda que de izquierda aderecha).
2. Para la siguiente gramática:
a. S  A | aBa | AbA
A  aBaD |SBBb
B  bB |Bb | BC
C  aA |Aa | Є
D  CB | CA | b
a) Quitar la recursividad por la izquierda de estasgramáticas
b) Factorizar por la izquierda las gramáticas
Nota: Recuerde que la recursividad por izquierda puede ser en cero o más pasos.
3. Para la gramática de expresiones enposfijo, siguiente;
E  EE+
E  EEE  EE*
E  EE/
E  EE^
Ex
Ey
E0
E1
a) Escribir la gramática en formato de escritura visto en clase
b) Compruebe que se deriva la cadenaX0+y1-^xy^11+/*
c) Quitar la recursividad por izquierda para esta gramática
d) Si es del caso factorizar la gramática por izquierda.
e) Compruebe que se genera la cadenaX0+y1-^xy^11+/* con la gramática sin
recursividad y factorizada.
f) Genere los conjuntos PRIMERO y SIGUIENTE
g) Genere la tabla de análisis sintáctico.
h) Genere los movimientos realizados porel analizador sintáctico para derivar la entrada
X0+y1-^xy^11+/*, mostrando el estado de la pila, de la cadena y de la salida de las
producciones derivadas.
Rubén García.