Nombre(s) iniciando por apellidos:

Martínez Rojas José Eduardo

Facultad de Ingeniería entregar 27/julio/2021

Compiladores Semestre 2021-2

Segundo examen parcial

Instrucciones: Contestar en este mismo documento todas las preguntas inmediatamente después de cada
pregunta (puedes usar el espacio que requieras), utilizando otro tipo de fuente; puedes incluir imágenes
para los diagramas. No es aceptable hacer copia de texto o diagramas de las clases publicadas ni de
referencias bibliográficas ni mesográficas. Copias de respuestas entre compañeros se queda sin
calificación. No olvidar poner el (los) nombre(s).

1. Describe brevemente, con tus propias palabras, dos razones por las que no necesariamente se debe
obtener el Autómata Finito Determinístico Mínimo para la implementación de un Analizador Léxico.
(0.75 punto)
Para mí las razones por las que debemos tener un AFD mínimo es porque al hacer está minimización
obtenemos un AFD ya sin estados muertos o inalcanzables, estados equivalentes, ambigüedad,
transiciones vacías, un nodo inicial. Es importante en código ya que al estar bien definido y al ser
mínimo es menor el código de las expresiones regulares hay un ahorro en ejecución al buscar esa
coincidencia de expresión regular, además nos cercioramos de con el AFD mínimo solo reconozca los
componentes léxicos definidos en nuestro lenguaje.

2. Elabora una expresión regular en lex/flex (usando sus operadores) que defina el lenguaje de
números binarios cuyo valor decimal sea impar. Por ejemplo, números binarios que sí deban estar
en el lenguaje que defina la expresión regular son: 1, 11, 101, 1011, 1101, etc. El lenguaje no debe
tener números binarios con cero(s) a la izquierda como: 01, 0011. (0.5 punto)

Binarios_impar 1| 1 (0|1)*1

3. En un solo párrafo menciona la característica principal que tiene cada tipo de gramática libre de
contexto mencionada (0.75 punto):
a. Gramática ambigua.
Cuando reconoce más de una clase de componente léxico o cuando solo hay un árbol de
derivación.

b. Gramática con ciclos.

Cuando presentan bucles infinitos, cuando en un estado tenemos transición que apunta al
mismo estado como es la cerradura positiva y cerradura estrella donde se presentan ciclos.

c. Gramática con no-terminales muertos.

Cuando se presentan no terminales que no llegan a ningúna cadena de símbolos terminales
cuando llegamos a un estado donde y ese estado no tiene producciones que nos dejen llegar
a un terminal.
 d. Gramática con elementos inaccesibles.
Se presenta cuando hay no hay producciones que hagan que pueda llegar a un estado lo cual
lo hace inaccesible, hay un estado al cual no se puede accesar.

4. Elabora la gramática libre de contexto tanto en notación BNF como en diagrama de tren de la
sentencia condicional if de un cierto lenguaje, la cual tiene la siguiente sintaxis (1 punto):

if var [<sentencias>] else [<sentencias>]

Donde:

• ‘if’ y ‘else’ son palabras reservadas; la parte del else es opcional.

• ‘var’ es una variable booleana.
• <sentencias> puede ser 0 o más sentencias; para simplificar, considera que una sentencia
cualquiera se representa por lo pronto con la letra ‘s’ y es un terminal.

Si definimos ‘f’ para if,’e’ para else, ‘v’ para var,

T es:{f v [] e []}

1:<sentIF> à f N [<sents>] e [<sents>]

2:N à v

3: <sents>→ s <sents>

4: <sents> → ξ

5: L→e

6: L→ ξ

7: [→ξ

8: ]→ξ

Ahora para la siguiente sentencia IF, obtener su cadena de terminales y probar que

dicha cadena es una frase gramatical de la gramática definida.

if n [s1 s2]
La correspondiente cadena de terminales es: f v [ss]

1
<sentIF> → fN[<sents>] e [<sents>]

2
→ fv[<sents>] e [<sents>]

3
→ fv[s<sents>] e [<sents>]

3
→ fv[ss<sents>] e [<sents>]

4
→ fv[ss] e [<sents>]

5
→ fv[ss] [<sents>]

7
→ fv[ss] <sents>]

4
→ fv[ss] ]

8
→ fv[ss]

fv[ss]

5. Completa la siguiente tabla con tres diferencias sustanciales entre un reconocimiento sintáctico
descendente versus uno ascendente (0.5 punto):

Análisis sintáctico descendente Análisis sintáctico ascendente

Diferencia 1 Derivación por la izquierda Derivación por la derecha
Diferencia 2 Predictivo o recursivo su Reducción o identificación su
clasificación gramáticas LR clasificación gramáticas S,q,LL
Diferencia 3 Mas reglas Menos reglas
6. Con base en la siguiente gramática (1.25 puntos):

1: W ® w(E)B 7: R ® e 13: A ® - O;
2: E ® aRO 8: R ® d 14: A ® / O;
3: E ® cRO 9: B ® { L 15: A ® * O;
4: O ® a 10: L ® a= OAC 16: A ® ;
5: O ® c 11: L ® } 17 C ®a=OA L
6: R ® m 12: A ® +O; 18: C ® }

a) Realiza la derivación correspondiente para obtener la sentencia w(cma){a=a*c;a=c;}┤para

realizar un análisis descendente. Después realiza el reconocimiento que hará el analizador
descendente. Indica la secuencia de producciones que va reconociendo.
Cadena Pila Producción reconocida
w(cma){a=a*c;a=c;}┤ W^ No aplica
(cma){a=a*c;a=c;}┤ (E)B^ 1: W ® w(E)B
cma){a=a*c;a=c;}┤ E)B^ No aplica
ma){a=a*c;a=c;}┤ RO)B^ 3: E ® cRO
a){a=a*c;a=c;}┤ O)B^ 6: R ® m
){a=a*c;a=c;}┤ )B^ 4: O ® a
{a=a*c;a=c;}┤ B^ No aplica
a=a*c;a=c;}┤ L^ 9: B ® { L
=a*c;a=c;}┤ =OAC^ 10: L ® a= OAC
a*c;a=c;}┤ OAC^ No aplica
*c;a=c;}┤ AC^ 4: O ® a
c;a=c;}┤ O;C^ 15: A ® * O;
;a=c;}┤ ;C^ 5: O ® c
a=c;}┤ C^ No aplica
=c;}┤ =OAL^ 17 C ®a=OA L
c;}┤ OAL^ No aplica
;}┤ AL^ 5: O ® c
}┤ L^ 16: A ® ;
┤ ^ 11: L ® }
Se reconoce la frase gramatical

b) Realiza la derivación correspondiente para obtener la sentencia w(cma){a=a*c;a=c;}┤para

realizar un análisis ascendente. Después realiza el reconocimiento que hará el analizador
ascendente. Indica la secuencia de producciones que va reconociendo.
1: W ® w(E)B 7: R ® e 13: A ® - O;
2: E ® aRO 8: R ® d 14: A ® / O;
3: E ® cRO 9: B ® { L 15: A ® * O;
4: O ® a 10: L ® a= OAC 16: A ® ;
5: O ® c 11: L ® } 17 C ®a=OAL
6: R ® m 12: A ® +O; 18: C ® }
 Cadena Pila Producción reconocida
w(cma){a=a*c;a=c;}┤ ^ No aplica
(cma){a=a*c;a=c;}┤ ^w Corrimiento de ‘w’
cma){a=a*c;a=c;}┤ ^w( Corrimiento de ‘(’
ma){a=a*c;a=c;}┤ ^w(c Corrimiento de ‘c’
a){a=a*c;a=c;}┤ ^w(cm Corrimiento de ‘m’
a){a=a*c;a=c;}┤ ^w(cR Reducción por producción 6
){a=a*c;a=c;}┤ ^w(cRa Corrimiento de ‘A’
){a=a*c;a=c;}┤ ^w(cRO Reducción por producción 4
){a=a*c;a=c;}┤ ^w(E Reducción por producción 3
{a=a*c;a=c;}┤ ^w(E) Corrimiento de ‘)’
a=a*c;a=c;}┤ ^w(E){ Corrimiento de ‘{’
=a*c;a=c;}┤ ^w(E){a Corrimiento de ‘a’
a*c;a=c;}┤ ^w(E){a= Corrimiento de ‘=’
*c;a=c;}┤ ^w(E){a=a Corrimiento de ‘A’
*c;a=c;}┤ ^w(E){a=O Reducción por producción 4
c;a=c;}┤ ^w(E){a=O* Corrimiento de ‘*’
;a=c;}┤ ^w(E){a=O*c Corrimiento de ‘c’
a=c;}┤ ^w(E){a=O*c; corrimiento de ‘;’
a=c;}┤ ^w(E){a=OA Reducción por producción 15
=c;}┤ ^w(E){a=OAa corrimiento de ‘a’
c;}┤ ^w(E){a=OAa= corrimiento de ‘=’
;}┤ ^w(E){a=OAa=c corrimiento de ‘c’
;}┤ ^w(E){a=OAa=O Reducción por producción 5
}┤ ^w(E){a=OAa=O; corrimiento de ‘;’
}┤ ^w(E){a=OAa=OA Reducción por producción 16
┤ ^w(E){a=OAa=OA} corrimiento de ‘}’
┤ ^w(E){a=OAa=OAL Reducción por producción 11
┤ ^w(E){a=OAC Reducción por producción 17
┤ ^w(E){L Reducción por producción 10
┤ ^w(E)B Reducción por producción 9
┤ ^W Reducción por producción 1
Se reconoce la frase gramatical

Nota: Utiliza los procedimientos estudiados en el tema 3.

7. Obtén una gramática S para el lenguaje L={abnabn+2 | n≥ 0} (1 punto)

Las producciones de la grmática serían:

1:S-> aBC
2:C->bb
3:C->aBbb
4:B->b
5:B->a
6:B->bB
 Comprobando
Para n=0 es aabb
aabb S-> aBC -> aaC ->aabb
1 5 2
n=1 ababbb
ababbb S-> aBC -> aBaBabb -> aabb
1 3 4
n=2 abbabbbb
abbabbbb S-> aBC -> aBaBbb -> abBabBbb-> abbabbbb
2 3 6 4

8. Realiza un análisis de la siguiente gramática, para obtener una gramática S equivalente. ¿Cómo
resolverías la producción 4? (1 punto)

1: S ® c(I):M 5: R ® {sB}
2: I ® a 6: R ® s;
3: I ® i 7: B ® sB
4: M ® R 8: B ® ξ
5: T ® b

No es una gramática S porque la producción 8 y la producción 4 no cumplen con la regla 1 y 2.

Recordando que las producciones ξ no son producciones que inicien en su lado derecho con
terminal, ya que ξ no es terminal y M->R es terminal.

No terminales anulables
M,B
Producciones anulables
4,8
b)
First(1)={c} First(5)={b} First(S)={c}
First(2)={a} First(6)={s} First(M)={s {}
First(3)={i} First(7)={s} First(B)={s}
First(4)={ ‘{‘ s} First(8)={} First(I)={a i}

a) Este análisis inicia localizando al no-terminal de la producción R, el cual es M. Observamos que se

encuentra sólo en la producción 1.
1: S ® c(I):M

b) A continuación, debemos observar qué elementos son antecesores al no terminal M en esa

producción:

1: S ® c(I):M

Le antecede el “:”
c) Considerando primeramente el terminal “:” , entonces en la producción 4 se agregará a el “:” antes
del terminal. La gramática queda de la siguiente manera:

1: S ® c(I)M 5: R ® {sB}
2: I ® a 6: R ® s;
3: I ® i 7: B ® sB
4: M ® :R 8: B ® ξ
5: T ® b
Otro problema que podemos notar es tenemos un estado inaccesible T->b que podemos despreciar
además que tiene número de producción repetido La gramática queda de la siguiente manera:

1: S ® c(I)M 5: R ® {sB}
2: I ® a 6: R ® s;
3: I ® i 7: B ® sB
4: M ® :R 8: B ® ξ

Ahora para la producción ξ podemos notar que está en 7 y 5.

A continuación, debemos observar qué elementos le siguen al no terminal B en esas producciones:
5: R ® {sB} podemos ver que le sigue el símbolo “}” que es un elemento terminal
7: B ® sB
Considerando primeramente el terminal “}” , entonces en la producción 8 se sustituiría a ξ por “}”

1: S ® c(I)M 5: R ® {sB
2: I ® a 6: R ® s;
3: I ® i 7: B ® sB
4: M ® :R 8: B ® }

9. Obtén el conjunto de selección para cada producción de la siguiente gramática y determina si es

gramática q. Muestra el procedimiento. (1 punto)

1: S ® aBbC 5: C ® d
2: B ® bB 6: D ® d
3: B ® ξ 7: D ® ξ
4: C ® cDB

1: S ® aBbC c.s(1)={a} 5: C ® d c.s(1)={d}

2: B ® bB c.s(2)={b} 6: D ® d c.s(1)={d}
3: B ® ξ c.s(3)={} 7: D ® ξ c.s(1)={}
4: C ® cDB c.s(4)={c}
 a)No terminales anulables
B,D

b)Producciones anulables
4,8

First(1)={a} First(5)={d} First(S)={a}

First(2)={b} First(6)={d} First(B)={b}
First(3)={} First(7)={} First(D)={d}
First(4)={c}

C)Cálculo del follow

Follow(C)=Follow(s)U{⊣}={⊣}
Follow(B)={d}U Follow(C)= {b}{U}{⊣}= {b ⊣}
Follow(D)=First{B}U{Follow(C)}={b}U{⊣}={b ⊣}

1: S ® aBbC c.s(1)={a} 5: C ® d c.s(1)={d}

2: B ® bB c.s(2)={b} 6: D ® d c.s(1)={d}
3: B ® ξ c.s(3)={ b ⊣} 7: D ® ξ c.s(1)={ b ⊣}
4: C ® cDB c.s(4)={c}

* Son conjuntos de selección disjuntos

Conclusión: Sí es una gramática q debido a que cumple las dos condiciones.

10. Realiza un análisis del porqué una gramática LL(1) no es recursiva por la izquierda. Tip: ¿Qué
sucedería al calcular los conjuntos de selección? Debes realizar tu propio análisis, no buscar la
respuesta en bibliografía o mesografía. (1 punto)

No es recursiva por la izquieda ya que para ser gramática LL(1) debe cumplir que no sea recursiva
por la izquieda desde un principio, análizando una gramática nos podemos dar cuenta que cuando
hay un no terminal que tiene una producción que produce ese mismo no terminal se vuelve un bucle
infinito en lo que es la programación a la hora del reconocimiento de cadena, es el problema que
presenta la recursividad por la izquierda por eso se le debe dar un tratamiento para eliminar esa
recursividad. Entonces si tenemos esa producción en nuestra gramática a la hora de análizar vamos a
ver que alguno de nuestros conjuntos de selección es no disjunto exactamente del no terminal que
produce ese mismo no terminal, pero si se le dio tratamiento y no existe ese no terminal que se
produce así mismo vamos a ver que nuestros conjuntos de selección son disjuntos. En conclusión si
los conjuntos de selección si son disjuntos no hay recursividad por la izquierda y es una gramática
LL(1) y si hay un conjunto de selección no disjunto entonces hay una producción que se produce así
misma y significa que hay recursividad por la izquierda.
11. Para la siguiente gramática (1.25 puntos):

1: F ® f ( E E A P 6: P ® { M
2: E ® e; 7: P ® ;
3: E ® ; 8: M ® }
4: A ® e) 9: M ® s M
5: A ® )

a) Encuentra los conjuntos de selección de cada producción.

a)No terminales anulables
no hay
b)Producciones anulables
No hay

1: F ® f ( E E A P c.s(1)={f} 6: P ® { M c.s(6)={{}
2: E ® e; c.s(2)={e} 7: P ® ; c.s(7)={;}
3: E ® ; c.s(3)={;} 8: M ® } c.s(8)={}}
4: A ® e) c.s(4)={e} 9: M ® s M c.s(9)={s}
5: A ® ) c.s(5)={)}
Los conjuntos de selección son disjuntos
b) Elabora la Tabla de Parser.
Columnas:∑ 𝑝=∑ 𝐺 U ⊣={f ( e ; ) { } s ⊣}

Γ= N U {Ʌ} U { a Є ΣG | a no esté exclusivamente al inicio del lado derecho de las producciones }

donde: N ® Conjunto de elementos no terminales de la gramática
Ʌ ® Indicador de pila vacía.

Renglones:{𝐹 ( 𝐸 𝐴 𝑃 𝑀 Ʌ )}
f ( e ; ) { } s ⊣
F Reem( ( E
E A P)r
avanza
( Pop
Avanza
E Reem( ; )r Pop
avanza Avanza
r
A Reem( ) ) Pop
avanza Avanza
P Reem(M)r
avanza
M Pop Reem(M)r
Avanza avanza
) Pop
Avanza
Ʌ acepta
 c) Con base en la Tabla de Parser, realiza el reconocimiento de las cadenas:
1) f(e;;){ss}˧ 2) f(;e){s}˧

1)f(e;;){ss}˧
Cadena Pila
f(e;;){ss}˧ FɅ
(e;;){ss}˧ (EEAPɅ
e;;){ss}˧ EEAPɅ
;){ss}˧ APɅ
){ss}˧ )PɅ
{ss}˧ PɅ
ss}˧ MɅ
s}˧ MɅ
}˧ MɅ
˧ Ʌ
acepta
2) f(;e){s}˧
Cadena Pila
f(;e){s}˧ FɅ
(;e){s}˧ (EEAPɅ
;e){s}˧ EEAPɅ
e){s}˧ EAPɅ
){s}˧ ;APɅ
error