22, 23 y 24 análisis sintáctico v - eafranco.com
TRANSCRIPT
![Page 1: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/1.jpg)
![Page 2: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/2.jpg)
Contenido
• Análisis Sintáctico Ascendente
• Métodos Ascendentes
• Método Ascendente SLR
• Pasos para el método SLR
• Ejemplo SLR
• Resumen
• Ejercicios
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)2
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
2
![Page 3: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/3.jpg)
Análisis Ascendente
• Se construye el árbol de análisis sintáctico de lacadena de entradadesde las hojas hasta la raíz.
• En las hojas tenemos la cadena a analizar(lossímbolos terminales)que se intentanreducir alaxioma, que se encontrará en la raíz, si la cadena escorrecta sintácticamente.
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)3
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
3
![Page 4: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/4.jpg)
Análisis Ascendente
¿Comoconstruir el árbol?• Se trata de desplazarse en la entrada hastaencontrar una subcadena de símbolos querepresente la parte derecha de una producción, enese momento sustituimos esa subcadena por el no-terminal de la parte izquierda correspondiente de laproducción, lareducimos.
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)4
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
4
![Page 5: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/5.jpg)
Métodos Ascendentes
• Partiendo del árbol de derivación se comprueba la siguiente cadena
abcdef• Partiendo de abajo hacia arriba
utilizando la pila y reduciendo las producciones
S
B
A
a
b
c E
d D
C
e f
F
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)5
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
5
![Page 6: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/6.jpg)
Métodos Ascendentes
• Ingresa a la pila
• Encontrar una subcadena de símbolos que represente la parte derecha de una producción.
S
B
A b
c E
d D
C
e f
Fa
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)6
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
6
![Page 7: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/7.jpg)
Métodos Ascendentes
• Reduce en la producción
A � a
• Cambia el valor en la pila
S
B
b
c E
d D
C
e f
F
A
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)7
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
7
![Page 8: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/8.jpg)
Métodos Ascendentes
• Ingresa el valor de b a la pila.S
B c E
d D
C
e f
F
A b
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)8
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
8
![Page 9: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/9.jpg)
Métodos Ascendentes
• Reduce en la producción
B � Ab
• Cambia el valor en la pila
S
c E
d D
C
e f
F
B
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)9
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
9
![Page 10: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/10.jpg)
Métodos Ascendentes
• Se moviliza en el árbol e ingresa c.
• Se agrega c a la pila
S
E
d D
C
e f
F
B c
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)10
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
10
![Page 11: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/11.jpg)
Métodos Ascendentes
• Se moviliza en el árbol e ingresa d.
• Se agrega d a la pila
S
E
D
C
e f
F
B c d
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)11
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
11
![Page 12: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/12.jpg)
Métodos Ascendentes
• Se moviliza en el árbol e ingresa e.
• Se agrega e a la pila
S
E
D
C
f
F
B c d e
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)12
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
12
![Page 13: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/13.jpg)
Métodos Ascendentes
• Se moviliza en el árbol e ingresa f.
• Se agrega f a la pila
S
E
D
C
F
B c d e f
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)13
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
13
![Page 14: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/14.jpg)
Métodos Ascendentes
• Reduce en la producción
C � e f
• Cambia el valor en la pila
S
E
D
F
B c d C
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)14
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
14
![Page 15: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/15.jpg)
Métodos Ascendentes
• Reduce en la producción
D � C
• Cambia el valor en la pila
S
E F
B c d D
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)15
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
15
![Page 16: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/16.jpg)
Métodos Ascendentes
• Reduce en la producción
F � ε
• Cambia el valor en la pila
S
F
B c E F
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
16
![Page 17: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/17.jpg)
Métodos Ascendentes
• Reduce en la producción
S � B c E F ε
• Cambia el valor en la pila
S
Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)17
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
17
![Page 18: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/18.jpg)
Método Ascendente SLR
• Proviene del ingles Simple LR, es el más elemental de losanalizadores ascendentes.
• El principal objetivo es construir unautómata finitodeterminístico para reconocer los prefijos de la cadena,esos elementos se agrupan por estados.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)18
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
18
![Page 19: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/19.jpg)
Método Ascendente SLR
• Es el método ascendente que tiene un menornúmero de gramáticas para reconocer, en contrastecon los otros métodos.
• Si existe una confusión en la tabla de análisis, alser en el mismo estado una“reducción” y un“desplazamiento” no se puede realizar por esemétodo.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)19
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
19
![Page 20: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/20.jpg)
Características del método
• La gramática debe ser no ambigua
• La gramática puede tener recursividad a laizquierda
• La gramática puede estar no factorizada
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)20
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
20
![Page 21: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/21.jpg)
Funciones importantes
• Kernel: Producción que da origen al estado.
• Cerradura: Producción del NOTERMINAL a la derechadel apuntador.
• Transición: Pasos en los que se desglosa la gramática paraobtener los desplazamientos y reducciones.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)21
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
21
![Page 22: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/22.jpg)
Método Ascendente SLR
• Buffer de EntradaCadena de entrada a analizar, finaliza con el carácter $
• PilaSímbolos gramaticales que se van utilizando
• Tabla de Análisis SintácticoMatriz bidimensional que sirve para el análisis
• Cadena de SalidaCadena de Salida posterior al análisis
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)22
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
22
![Page 23: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/23.jpg)
Método Ascendente SLR
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)23
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
23
![Page 24: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/24.jpg)
Pasos para el Método SLR
1. Evaluar la gramática.
2. Calcular el conjunto de estados de la gramática.
3. Calcular el Siguiente (follow)
4. Construir la tabla de Análisis Sintáctico
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)24
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
24
![Page 25: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/25.jpg)
Pasos para el Método SLR
1.- Evaluar la gramática
Generar un estado inicial S para la gramática,partiendo del símbolo que de origen a las demásproducciones.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)25
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
25
![Page 26: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/26.jpg)
Pasos para el Método SLR
Kernel
Para calcularlos, se parte de unagramática y se coloca un punto(.) al iniciar la producción. Enese momento se crea el primerKernel, y es el estado.
2. Calcular el conjunto de EstadosNo.
EstadoGoto( Estado, Símbolo)
Kernel
S → .E
Cerradura
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)26
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
26
![Page 27: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/27.jpg)
Pasos para el Método SLR
Un estado esta formadopor un Kernel, unacerradura y conjunto deGoto´s o desplazamientos.
2. Calcular el conjunto de Estados
No.Estado
Goto( Estado, Símbolo)
Kernel
Cerradura
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)27
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
27
![Page 28: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/28.jpg)
Pasos para el Método SLR
Cerradura
Son las producciones que songeneradas por el símbolo que seencuentra después del punto. Todasellas deben comenzar nuevamentecon punto. Si es no terminalagregar sus producciones también
2. Calcular el conjunto de Estados
0Goto( Estado,
Símbolo)
KernelS → ● E
CerraduraE→ ●E + T
| ● T
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)28
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
28
![Page 29: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/29.jpg)
Pasos para el Método SLR
Goto / Desplazamiento
Al mover el punto dentro delkernel, con un único símbolo seconstruye un Goto.
Es posible que un kernel poseavarios desplazamientos, pasandode diferentes estados con el mismosímbolo.
2. Calcular el conjunto de Estados
0
KernelS → ● E
CerraduraE→ ●E + T
| ● T … 1 Goto(0, E)
KernelS → E ●
E→ E ● + T
Cerradura
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)29
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
29
![Page 30: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/30.jpg)
Ejercicio 1• Calcular el conjunto de Estados para las siguientegramática:
• Gramática para generar paréntesis anidados:
A → (A)|a
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
30
![Page 31: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/31.jpg)
Ejercicio 2• Calcular el conjunto de Estados para las siguientegramática:
• Gramática para generar sumas de expresiones:
E → n | E+n
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
31
![Page 32: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/32.jpg)
Ejercicio 3• Calcular el conjunto de Estados para las siguientegramática:
• Gramática para generar suma y multiplicación de números,aceptando los paréntesis
E → E + E | E * E| ( E ) | num
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
32
![Page 33: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/33.jpg)
Pasos para el Método SLR
3. Calcular el Siguiente (Follow)
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)33
Símbolo SIGUIENTE
Si B es símbolo inicial SIGUIENTE (B) = { $}
Si A → α B M
Producción
1. SIGUIENTE (B) = PRIMERO(M) excepto ε.
2. Si el PRIMERO(M) contiene ε entonces añadir el
SIGUIENTE (A) a SIGUIENTE (B)
Si A → B
ProducciónAñadir el SIGUIENTE (A) a SIGUIENTE (B)
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
33
![Page 34: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/34.jpg)
Pasos para el Método SLR4. Construir la tabla de Análisis Sintáctico
Conjunto de Estados
Símbolo Terminal y No Terminales
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)34
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
34
![Page 35: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/35.jpg)
Pasos para el Método SLR
4. Construir la tabla de Análisis Sintáctico
Se colocan las reducciones o desplazamientosnecesarios para hacer el posterioranálisis.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)35
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
35
![Page 36: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/36.jpg)
Pasos para el Método SLR
4. Construir la tabla de Análisis Sintáctico
Desplazamiento:
Se identifica con el número de estado al que se desplaza. Y si es un símbolo terminal se le antepone una letra “d”.
Reducción:
Si el kernel es de la forma A →α se coloca una reducción a todos los elementos de su follow, con el numero del estado al que corresponde.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)36
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
36
![Page 37: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/37.jpg)
Pasos para el Método SLR
4. Construir la tabla de Análisis Sintáctico
• Solamente puede existir un elemento en cada casilla.
• Puede darse conflictos shift – reduce
• Puede ser conflictos reduce – reduce
• Y en ese caso no aplica a método SLR.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)37
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
37
![Page 38: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/38.jpg)
Pasos para el Método SLR
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada
. . .
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)38
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
38
![Page 39: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/39.jpg)
Ejemplo SLR
Partiendo de la Gramática:
E → E ‘+’ T | T
T → T ‘x’ F | F
F → num | ‘(‘ E ‘)’
Para poder utilizar esta gramática, se le debe aumentar unaproducción, en este caso
S → E
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)39
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
39
![Page 40: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/40.jpg)
Ejemplo SLR
1. Escribir adecuadamente la gramática
S → E
1 E → E ‘+’ T
2 E → T
3 T → T ‘x’ F
4 T → F
5 F → ‘(‘ E ‘)’
6 F → num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)40
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
40
![Page 41: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/41.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
• Se coloca el punto, y se generan todas las producciones de los símbolos no terminales que se encuentren a su derecha.
S → EE → E ‘+’ T | TT → T ‘x’ F | FF → num | ‘(‘ E ‘)’
0
KernelS → ● E
CerraduraE→ ●E + T
| ● T T → ● T x F
| ● F F → ● (E)| ● num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)41
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
41
![Page 42: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/42.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
• Para calcular el siguiente kernel se hace el desplazamiento con el símbolo “E”
S → EE → E ‘+’ T | TT → T ‘x’ F | FF → num | ‘(‘ E ‘)’
0
KernelS → ● E
CerraduraE→ ●E + T
| ● T T → ● T x F
| ● F F → ● (E)| ● num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)42
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
42
![Page 43: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/43.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
Partiendo del Estado 0, generamos todos los estados vinculados con este, por medio de los goto´s con los diferentes símbolos.
0
KernelS→ ● E
CerraduraE→ ●E + T
| ● T T → ● T x F
| ● F F → ● (E)| ● num
1 Goto(0, E)
S → E ●E→ E ● + T
2 Goto(0, T)
E → T ●T → T ● x F
4 Goto(0, “(“)
F → ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
3 Goto(0, F)
T → F ●
5 Goto(0, “(“)
F → num●
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)43
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
43
![Page 44: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/44.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
Luego se continua con todos los elementos del kernel, de los estados generados. Movilizando el punto para crear un desplazamiento.
1 Goto(0, E)
S → E ●E→ E ● + T
6 Goto(1, “+“)
E→ E + ● T
T → ● T x F| ● F
F → ● (E)| ● num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)44
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
44
![Page 45: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/45.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
Luego se continua con todos los elementos del kernel, de los estados generados. Movilizando el punto para crear un desplazamiento.
2 Goto(0, T)
E → T ●T → T ● x F
7 Goto(2, “x” )
T→ T x ● F
F → ● (E)| ● num
3 Goto(0, F)
E → F ●
En el caso de no poder movilizarse,por falta de símbolos se continua conel siguiente estado.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)45
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
45
![Page 46: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/46.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
8 Goto(4, E )
F→ ( E ● )E→ E ● + T
Es importante ir en orden de cada estado, movilizando cada uno de los símbolos.
4 Goto(0, “(“)
F→ ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)46
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
46
![Page 47: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/47.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
9 Goto(4, T )
E → T ●T → T ● x F
Al hacer los cálculos de los estados, puede que se repita el kernel, y que el movimiento sea con el mismo símbolo. Por lo que al estado, únicamente se agrega el movimiento y no se agrega un nuevo estado.
4 Goto(0, “(“)
F→ ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
2 Goto(0, T ) Goto(4, T )
E → T ●T → T ● x F
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)47
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
47
![Page 48: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/48.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
Al hacer los cálculos de los estados, puede que se repita el kernel, y que el movimiento sea con el mismo símbolo. Por lo que al estado, únicamente se agrega el movimiento y no se agrega un nuevo estado.
4 Goto(0, “(“)
F→ ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
9 Goto(0, F)
E → F ●
3 Goto(0, F) Goto(4, F)
E → F ●
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)48
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
48
![Page 49: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/49.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
El mismo caso es con los siguientes estados, y no se agregan, solo se modifican los desplazamientos.
2 Goto(0, T) Goto(4, T)
E → T ●T → T ● x F 4 Goto(0, “(“) Goto(4, “(“)
F → ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
3 Goto(0, F) Goto(4, F)
E → F ●
5Goto(0, “num“) Goto(4, “num“)
F → num●
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)49
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
49
![Page 50: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/50.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
9 Goto(6, T)
E→ E + T ●T → T ● x F
6 Goto(1, “+“)
E→ E + ● T
T → ● T x F| ● F
F → ● (E)| ● num
- Goto(6, F)
E → F ●
Agregar a Estado 3
- Goto(6, “(“)
F → ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
- Goto(6, “num“)
F → num●
Agregar a Estado 5
Agregar a Estado 4Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)
50
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
50
![Page 51: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/51.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
Se modifican los goto´s de los estaddos 3,4 y 5-
4Goto(0, “(“) Goto(4, “(“)
Goto(6, “(“)
F → ( ●E)
E→ ● E + T| ● T
T → ● T x F| ● F
F → ● (E)| ● num
3Goto(0, F) Goto(4, F)
Goto(6, F)
E → F ●
5Goto(0, “num“) Goto(4, “num“)Goto(6, “num“)
F → num●
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)51
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
51
![Page 52: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/52.jpg)
Ejemplo SLR
2. Calcular el conjunto de Estados
11 Goto(8, ‘)’)
F→ ( E )●
10 Goto(7, F)
T→ T x F●
8 Goto(4, E )
F→ ( E ● )E→ E ● + T
7 Goto(2, “x” )
T→ T x ● F
F → ● (E)| ● num
Finalizado el proceso se construye la tabla.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)52
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
52
![Page 53: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/53.jpg)
Ejemplo SLR
3. Cálculo del Siguiente (Follow)
S → E1 E → E ‘+’ T 2 E → T3 T → T ‘x’ F 4 T → F5 F → ‘(‘ E ‘)’ 6 F → num
Símbolo
No TerminalFollow
S $
E $ , +, )
T x, +, $, )
F x, +, $, )
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)53
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
53
![Page 54: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/54.jpg)
Ejemplo SLR
4. Construir la tabla de Análisis Sintáctico
num + x ( ) $ E T F
0
1
2
…
11
Conjunto de Estados
Símbolo Terminal y No Terminales
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)54
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
54
![Page 55: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/55.jpg)
Ejemplo SLR
4. Construir la tabla de Análisis Sintáctico
num + x ( ) $ E T F
0 d5 d4 1 2 3
1 d6 ACEP
2 r2 d7 r2 r2
D [Estado] para los desplazamientosR [# Producción] para las reducciones, se agrega a todos los símbolos del follow.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)55
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
55
![Page 56: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/56.jpg)
Ejemplo SLR
num + x ( ) $ E T F
0 d5 d4 1 2 3
1 d6 ACEP
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 8 2 3
5 r6 r6 r6 r6
6 d5 d4 9 3
7 d5 d4 10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)56
Tabla SLR
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
56
![Page 57: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/57.jpg)
Ejemplo SLR5. Hacer el análisis de sintáctico por medio de la pila y
la tabla de análisis
Pila Entrada
0 num + num x num $
num ‘x’ num ‘+’ num
Colocar 0 como estado inicial
Colocar la cadena de entrada y $
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)57
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
57
![Page 58: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/58.jpg)
Ejemplo SLR
Pila Entrada
0
0 num 5
num x num + num $
x num + num $
num
0 d5
Se busca el estado y el símbolo, remplazándolo por el símbolo y el nú-mero del estado y eliminando de la entrada dicho símbolo.
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)58
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
58
![Page 59: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/59.jpg)
Ejemplo SLR
Pila Entrada
0
0 num 5
0 F
num x num + num $
x num + num $
x num + num $
X
5 r6
Cuando es una reducción se buscala producción por la que se debe substituir el símbolo-
6 F → num
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)59
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
59
![Page 60: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/60.jpg)
Ejemplo SLR
Pila Entrada
0
0 num 5
0 F 3
num x num + num $
x num + num $
x num + num $
F
0 3
Se verifica el siguiente numero a asig-nar , en este caso 0 con F y nos retorna el estado numero 3
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)60
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
60
![Page 61: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/61.jpg)
Ejemplo SLR
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada
0
0 num 5
0 F 3
0 T 2
0 T 2 x 7
num x num + num $
x num + num $
x num + num $
x num + num $
num + num $
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)61
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
61
![Page 62: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/62.jpg)
Ejemplo SLR
4. Proceso de análisis SLR
Pila Entrada
0
0 num 5
0 F 3
0 T 2
0 T 2 x 7
0 T 2 x 7 num 5
0 T 2 x 7 F 10
0 T
. . .
num x num + num $
x num + num $
x num + num $
x num + num $
num + num $
+ num $
+ num $
+ num $
. . . Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)
62
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
62
![Page 63: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/63.jpg)
Ejemplo SLR
4. Proceso de análisis SLR
Pila Entrada. . .
0 T 2
0 E 1
0 E 1
0 E 1 + 6
0 E 1 + 6 num 5
0 E 1 + 6 F 3
0 E 1 + 6 T
0 E 1 + 6 T 9
0 E
0 E 1
. . .
+ num $
+ num $
+ num $
+ num $
$
$
$
$
$
$
Se acepta la cadena si se logra ingresarpor medio dela unión de es-tado y símboloa la aceptación
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)63
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
63
![Page 64: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/64.jpg)
Resumen
Proceso de construcción SLR1. Evaluar la gramática.
2. Calcular el conjunto de estados de la gramática.
3. Calcular el Siguiente (follow)
4. Construir la tabla de Análisis Sintáctico
5. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)64
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
64
![Page 65: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/65.jpg)
Ejercicio 1
• Realizar el análisis SLR para la siguiente gramática con las 3 entradas dadas.
• Gramática para generar paréntesis anidados:
A → (A)|a
a) (((((a)))))
b) ((a)a(a))
c) a(a(a(a)a
Compiladores (Clase 26 “Análisis Sintáctico VIII” - Edgardo A. Franco)65
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
65
![Page 66: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/66.jpg)
Ejercicio 2• Realizar el análisis SLR para la siguiente gramática con las 3 entradas dadas.
• Gramática para generar sumas de expresiones:
E → n | E+n
a) n+n+n
b) n++n
c) n+nn
Compiladores (Clase 26 “Análisis Sintáctico VIII” - Edgardo A. Franco)66
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
66
![Page 67: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/67.jpg)
Ejercicio 3• Realizar el análisis SLR para la siguiente gramática con las 3 entradas dadas.
• Gramática para generar suma y multiplicación de números, aceptando los paréntesis
E → E + E | E * E| ( E ) | num
a) num*num+num
b) (num+num)*num
c) num(*)num
Compiladores (Clase 26 “Análisis Sintáctico VIII” - Edgardo A. Franco)67
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
67
![Page 68: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/68.jpg)
Ejercicio 4• Realizar el análisis SLR para la gramática G(Vt, Vn,
Φ, S)
• Analice la cadena: wyyyz
Compiladores (Clase 26 “Análisis Sintáctico VIII” - Edgardo A. Franco)68
{ }{ }
ES
YXEV
zyxwV
zyYY
zyXX
xYwXE
N
T
=
=
→
→
→
=Φ
,,
,,,
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
68
![Page 69: 22, 23 y 24 Análisis sintáctico V - eafranco.com](https://reader035.vdocumento.com/reader035/viewer/2022071015/62c986f716136155f236ca4f/html5/thumbnails/69.jpg)
•Entregar víapágina web con el titulo"Ejercicios SLR", a más tardar el díaViernes 03 de junio de 2011 a las23:59:59hrs.
•Deberánestar resueltos a detalle y debenserenformatodigital.
69Compiladores (Análisis Sintáctico V - Edgardo A. Franco)
Ejercicios 3 y 4
22, 23 y 24 Análisis sintáctico VCompiladores - Profr. Edgardo Adrián Franco Martínez
69