22, 23 y 24 Análisis sintáctico V - eafranco.com

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

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.

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.

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

• Ingresa a la pila

• Encontrar una subcadena de símbolos que represente la parte derecha de una producción.

• Reduce en la producción

A � a

• Cambia el valor en la pila

• Ingresa el valor de b a la pila.S

B � Ab

• Se moviliza en el árbol e ingresa c.

• Se agrega c a la pila

• Se moviliza en el árbol e ingresa d.

• Se agrega d a la pila

• Se moviliza en el árbol e ingresa e.

• Se agrega e a la pila

B c d e

• Se moviliza en el árbol e ingresa f.

• Se agrega f a la pila

B c d e f

C � e f

B c d C

D � C

B c d D

F � ε

B c E F

Compiladores (Análisis Sintáctico VI - Análisis Ascendente - Edgardo A. Franco)

S � B c E F ε

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

• 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.

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

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.

• 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

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

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.

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

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

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

0Goto( Estado,

Símbolo)

KernelS → ● E

CerraduraE→ ●E + T

| ● T

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.

KernelS → ● E

| ● T … 1 Goto(0, E)

KernelS → E ●

E→ E ● + T

Cerradura

Ejercicio 1• Calcular el conjunto de Estados para las siguientegramática:

• Gramática para generar paréntesis anidados:

A → (A)|a

• Gramática para generar sumas de expresiones:

E → n | E+n

• Gramática para generar suma y multiplicación de números,aceptando los paréntesis

E → E + E | E * E| ( E ) | num

3. Calcular el Siguiente (Follow)

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)

Pasos para el Método SLR4. Construir la tabla de Análisis Sintáctico

Conjunto de Estados

Símbolo Terminal y No Terminales

Se colocan las reducciones o desplazamientosnecesarios para hacer el posterioranálisis.

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.

• 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.

Pila Entrada

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

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

Ejemplo SLR

• 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 ‘)’

KernelS → ● E

| ● T T → ● T x F

| ● F F → ● (E)| ● num

Ejemplo SLR

• 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 ‘)’

KernelS → ● E

| ● T T → ● T x F

| ● F F → ● (E)| ● num

Ejemplo SLR

Partiendo del Estado 0, generamos todos los estados vinculados con este, por medio de los goto´s con los diferentes símbolos.

KernelS→ ● E

| ● 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●

Ejemplo SLR

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

Ejemplo SLR

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.

Ejemplo SLR

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

Ejemplo SLR

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

Ejemplo SLR

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 ●

Ejemplo SLR

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●

Ejemplo SLR

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)

Ejemplo SLR

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●

Ejemplo SLR

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.

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

E $ , +, )

T x, +, $, )

F x, +, $, )

Ejemplo SLR

num + x ( ) $ E T F

Conjunto de Estados

Símbolo Terminal y No Terminales

Ejemplo SLR

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.

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

Tabla SLR

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 $

Ejemplo SLR

Pila Entrada

0 num 5

num x num + num $

x num + num $

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.

Ejemplo SLR

Pila Entrada

0 num 5

num x num + num $

x num + num $

Cuando es una reducción se buscala producción por la que se debe substituir el símbolo-

6 F → num

Ejemplo SLR

Pila Entrada

0 num 5

num x num + num $

x num + num $

Se verifica el siguiente numero a asig-nar , en este caso 0 con F y nos retorna el estado numero 3

Ejemplo SLR

Pila Entrada

0 num 5

0 T 2 x 7

num x num + num $

x num + num $

num + num $

Ejemplo SLR

4. Proceso de análisis SLR

Pila Entrada

0 num 5

0 T 2 x 7

0 T 2 x 7 num 5

0 T 2 x 7 F 10

num x num + num $

x num + num $

num + num $

+ num $

. . . Compiladores (Análisis Sintáctico VII-Análisis SLR - Edgardo A. Franco)

Ejemplo SLR

4. Proceso de análisis SLR

Pila Entrada. . .

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

+ num $

Se acepta la cadena si se logra ingresarpor medio dela unión de es-tado y símboloa la aceptación

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)

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

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

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

Ejercicio 4• Realizar el análisis SLR para la gramática G(Vt, Vn,

Φ, S)

• Analice la cadena: wyyyz

{ }{ }

•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 V - eafranco.com

Documents

Tema 02:Complejidad de los algoritmos - eafranco.com

13 Manejo de cadenas en C - eafranco.com

COMPONENTE SINTÁCTICO

ANÁLISIS MORFO- SINTÁCTICO...anÁlisis morfo- sintÁctico maria sanmartin malvarez actiludis.com. by-nc-sa

Análisis Sintáctico (Parsing)

11 Tipos de sistemas distribuidos - eafranco.com

Análisis sintáctico (simples)

Análisis sintáctico ascendente descendente

Tomasello- Desarrollo sintáctico temprano.pdf

Guía de Análisis Sintáctico

Tema 10: Algoritmos ávidos - eafranco.com

12 Clasificación de gramáticas - eafranco.com

PUNTO SINTÁCTICO

El Analisis sintáctico

Practica 03: Eliminación Gaussiana - eafranco.com

21 Memoria dinámica y su uso en C - eafranco.com

Análisis sintáctico DIPELE

Análisis Sintáctico

ANÁLISIS SINTÁCTICO

Practica 06: Diccionario con AVL - eafranco.com