Procesadores de lenguaje...$0E Ir_a 1 $ $0E1 Reducir E’ÆE $ $0E' EXITO $ Procesadores de...

Procesadores de lenguajeEjercicios de análisis sintácticoEjercicios de análisis sintáctico

Salvador Sánchez Daniel RodríguezSalvador Sánchez, Daniel RodríguezDepartamento de Ciencias de la ComputaciónUniversidad de Alcalá

Recursividad: ejerciciosRecursividad: ejercicios

Obt l áti dObtener las gramáticas que producen:

1 U á i id d l i i d ( i)1. Una o más aes con recursividad por la izquierda (r.i)2. Cero o más aes (r.i)3. Una o más aes con recursividad por la derecha (r.d)4. Cero o más aes (r.d)5. Una b y cero o más aes (r.i)6 Cero o más aes terminando en b (r d)6. Cero o más aes terminando en b (r.d)7. Cero o más aes separadas por ‘;’ (r.d) 8. Una o más aes separadas por ‘;’ (r.i)

Procesadores de lenguaje – Ejercicios Análisis SintácticoSalvador Sánchez, Daniel Rodríguez

SolucionesSoluciones

B->;aB | ε8. A->A;a | a

Analizador descendente recursivoAnalizador descendente recursivo

Ejemplos:• Ejemplos:

1. Mostrar las acciones de un analizador descendente recursivo que analiza la cadena “aaab” según la gramática: A aA | bcadena “aaab” según la gramática: A aA | b

2. Para la gramática anterior, analizar la cadena “abaab”.

3. Mostrar las acciones de un analizador descendente recursivo que analiza la cadena “aba” según la gramática: A ab | aA

4. Mostrar las acciones de un analizador descendente recursivo para la cadena de entrada “IDENT()” según la gramática:

S t i A i ió | Ll d | tSentencia Asignación | Llamada | otroAsignación Identificador := ValorLlamada Identificador ()

Analizador LL(1) – Conjunto primeroAnalizador LL(1) Conjunto primero

1 C l l l j t P i d A l áti1.Calcular el conjunto Primero de A para la gramática siguiente:

A (A)A | ε

2.Calcular el conjunto Primero de los no terminales A, B y C para la gramática siguiente:

A BCB ε | mB ε | mC ε | s

Analizador LL(1) - Conjunto primeroAnalizador LL(1) Conjunto primero

1 C j t P i d A l áti i i t1.Conjunto Primero de A para la gramática siguiente:A (A)A | ε

SOLUCIÓN: Primero(A) = { ( , є }

2.Conjunto Primero de los no terminales A, B y C:

A BCA BCB ε | mC ε | sC ε | s

SOLUCIÓN: Primero(A) = {m, s, є}, Primero(B) = {m, є}, Primero(C) = {s, ε}

Analizador LL(1) - Conjunto siguienteAnalizador LL(1) Conjunto siguiente

Ej l 1 Ej l 3• Ejemplo 1:

• Ejemplo 3:

S BCdS aBCdB bbC cc

S aBCdB CB | bC cc | ε

• Ejemplo 2: • Ejemplo 4:

S aBCdB bB | d

S if B then S | write B | id := BB bB | dC cc

B id = id | id <> id | true | false

Analizador LL(1) - Conjunto siguienteAnalizador LL(1) Conjunto siguiente

1. Solución:Prim(S)={a}, Prim(B)={b}, Prim(C)={c}Sig(S)={$}, Sig(B)={c}, Sig(C)={d}

2. Solución: Prim(S)={a}, Prim(B)={b,d}, Prim(C)={c}Sig(S)={$}, Sig(B)={c}, Sig(C)={d}

3. Solución:Prim(S)={a}, Prim(B)={b,c}, Prim(C)={c, ε}Sig(S)={$}, Sig(B)={c,d} Sig(C)={b,c,d}

4. Solución:Prim(S)={if, write, id}, Prim(B)={id, true, false}Sig(S)={$}, Sig(B)={then, $}

Analizador LL(1) - AnálisisAnalizador LL(1) Análisis

1. Comprobar si la siguiente gramática es LL(1) y construir la tabla, calculando todos los conjuntos Siguiente y Primero.

S → cAA → aBB → b | ε

2. Reconocer la cadena “cab” con el analizador construido.

SoluciónSolución

Pasos para ver si es LL(1):

1 - No es recursiva a izquierdas1.- No es recursiva a izquierdas.2.- B→ b | є

2.1. Prim(b) ∩ Prim(ε) = vacío2 2 Si ε Prim(ε) > Prim(b) Sig(B) vacío2.2. Si ε ∈ Prim(ε) => Prim(b) ∩ Sig(B) = vacío

Conjuntos primero:j pPrim(S)={c} Prim(A)={a} Prim(B)={b, ε}

Conjuntos siguiente:Sig(S)={$} Sig(A)=Sig(S)={$} Sig(B)=Sig(A)={$}

SoluciónSolución

Tabla de análisis:

A → aBA

S → cAS

B → εB → bB

A → aB

SoluciónSolución

Reconocer la cadena “cab”

cab$Reconocimiento$Accab$$S

ab$Reconocimiento$Baab$A→aB$A

cab$Reconocimiento$Ac

b$Reconocimiento$bb$B→b$B

ab$Reconocimiento$Ba

$éxito$b$Reconocimiento$b

1 C b i l i i t áti LL(1) t i l1. Comprobar si la siguiente gramática es LL(1) y construir la tabla de análisis y todos los conjuntos Siguiente y Primero.

E TE’E’ +TE’ | єT FT’T FTT’ *FT’ | єF (E) | id

2. Reconocer la cadena “(3+5*8)” con el analizador construido.

SoluciónSolución

Prim (E) { ( id } Si (E) { $ ) }Prim (E) = { (, id }Prim (E’) = { +, є }Prim (T) = { (, id }

Sig (E) = { $, ) }Sig (E’) = { $, ) } Sig (T) = {+ $ )}Prim (T) { (, id }

Prim (T’) = { *, є }Prim (F) = { (, id }

Sig (T) = {+, $, )}Sig (T’) = { +, $, )}Sig (F) = {*,+, $, )}g ( ) { )}

SoluciónSolución

Reconocimiento de la cadena: (3+5*8)

1 A ti d l i i t áti t i l t bl d áli i1. A partir de la siguiente gramática, construir la tabla de análisis y todos los conjuntos Siguiente y Primero.

B -> DLD -> id ; D | єL > S L |L -> S ; L | єS -> a + a

2. Reconocer la cadena “id;a+a;” con el analizador construido.

P i (B) { id } S ( ) { $ }Prim(B) = { id, a, ε } Prim(D) = { id, є }Prim(L) = { a є }

Sig(B) = { $ }Sig(D) = { a, $ }Sig(L) = { $ }Prim(L) = { a, є }

Prim(S) = { a }Sig(L) = { $ }Sig(S) = { ; }

$ id ; a +B B DL B DL - B DL -B B DL B DL B DLD D є D id;D - D є -L L є - - L S;L -;S - - - S a+a -

Pila Decisión Entrada$B B DL id;a+a;$$LD D id;D id;a+a;$$LD;id Reconocer id id;a+a;$

Reconocer:id;a+a;

$LD;id Reconocer id id;a+a;$$LD; Reconocer ; ;a+a;$$LD D є a+a;$$L L S;L a+a;$$L;S S a+a a+a;$$L;a+a Reconocer a a+a;$$L;a+a Reconocer a a+a;$$L;a+ Reconocer + +a;$$L;a Reconocer a a;$$L; Reconocer ; ;$$L L є $$ EXITO $

Analizador LR(0) - AnálisisAnalizador LR(0) Análisis

1 A ti d l i i t áti t i l tó t fi it1. A partir de la siguiente gramática, construir el autómata finito determinista y la tabla de análisis para el analizador LR(0).

E (E + T) | idT (T * F) | idF id

2 Reconocer la cadena “(6+(4*2))”

2. Reconocer la cadena (6+(4 2)) .

E’ E

(E’ .EE (E T)

E’ E.

E (.E+T)E (E+T)

E (E +T)

E .(E+T)E .id

E (E.+T)E

E (E+.T)T .(T*F)T .id

(T (T.*F)

idE (E+T.)

T (.T*F)T .(T*F)T .id

T (T*.F)F .id

id T id.

E (E+T).

T (T*F.)

T (T*F).

1132Desplazamiento0FTEid+*)(ReglaAcciónEstado

Ir_aEntrada

5146Desplazamiento44Desplazamiento3

3132Desplazamiento2E’ EReducción1

9Desplazamiento8E (E+T)Reducción7

F idReducción12T (T*F)Reducción11

9esp a a e to8

T idReducción14E idReducción13F idReducción12

Pila Decisión EntradaPila Decisión Entrada

$0 Desplazar (6+(4*2))$$0(2 Desplazar 6+(4*2))$$0(2613 Reducir E id +(4*2))$

Reconocer:(6+(4*2)) $ ( Reducir E id ( ))$

$0(2E Ir_a 3 +(4*2))$$0(2E3 Desplazar +(4*2))$$0(2E3+4 Desplazar (4*2))$$0(2E3+4(6 Desplazar 4*2))$$0(2E3+4(6414 Reducir T id *2))$$0(2E3+4(6T Ir_a 8 *2))$$0(2E3+4(6T8 Desplazar *2))$$0(2E3+4(6T8*9 Desplazar ))$$0(2E3+4(6T8*9212 Reducir F id ))$$0(2E3+4(6T8*9F Ir_a 10 ))$$0(2E3+4(6T8*9F10 Desplazar ))$$0(2E3+4(6T8*9F10)11 Reducir T (T*F) )$

Reconocer:(6+(4*2))

Pila Decisión Entrada

... ... ...$0(2E3+4T Ir_a 5 )$$0(2E3+4T5 Desplazar )$$0(2E3+4T5)7 Reducir E (E+T) $( )

$0E Ir_a 1 $$0E1 Reducir E’ E $$0E' EXITO $

1 A ti d l i i t áti t i l tó t fi it1. A partir de la siguiente gramática, construir el autómata finito determinista y la tabla de análisis para el analizador LR(0).

S ( S ) S | ε

2. Reconocer la cadena “(())()”.

Conflictos:

E t d I

Conflictos:

S0: Desplazamiento-reducciónS2: Desplazamiento-reducciónS4: Desplazamiento-reducción Entrada Ir a

Acción Regla ( )

S4: Desplazamiento reducción

0 Desplazar / Reducir S Є 2 1

1 Reducir S’ S

3 Desplazar - 4

5 Reducir S (S)S

1 A ti d l i i t áti t i l tó t fi it1. A partir de la siguiente gramática, construir el autómata finito determinista y la tabla de análisis para el analizador SLR(1).

E (E + T) | idT (T * F) | idF id

2 Reconocer la cadena “(6+(4*2))”

2. Reconocer la cadena (6+(4 2)) .

Analizador SLR(1) - AnálisisAnalizador SLR(1) Análisis

) A li l átia) Ampliar la gramática:

E’ EE (E + T) | idT (T * F) | idF id

b) Conjuntos Siguiente:b) Conjuntos Siguiente:

Sig (E’) = { $ }Sig (E) = { + , $ }Sig (E) { , $ }Sig (T) = { * , ) }Sig (F) = { ) }

) A tó tE

(E’ .E

E’ E.

E (.E+T)

S2 (S3

c) Autómata:

E .(E+T)E .id

E (E.+T)E

E (E+.T)T .(T*F)T .id

(T (T.*F)

idE (E+T.)

T (.T*F)T .(T*F)T .id

T (T*.F)F .id

id T id.

E (E+T).

S7F .id

T (T*F.)

T (T*F).

d) T bl áli i

FTEid+*)($Estado

d) Tabla análisis:

D: 433D: 13D: 22

Aceptar11D: 13D: 20

8D: 14D: 66D: 75

5D: 14D: 64D: 43

D: 111010D: 129

D: 98R: E (E+T)7 R:E (E+T)

R: T id14R: E idR: E id13

R: F id12R:T (T*F)11

R: T id

R:T (T*F)

$0 D:2 (6+(4*2))$$0(2 D:13 6+(4*2))$$0(2613 R: E id +(4*2))$

e) Reconocer(6+(4*2))

$ ( R: E id ( ))$$0(2E Ir_a 3 +(4*2))$$0(2E3 D:4 +(4*2))$$0(2E3+4 D:6 (4*2))$$0(2E3+4(6 D:14 4*2))$$0(2E3+4(6414 R: T id *2))$$0(2E3+4(6T Ir_a 8 *2))$$0(2E3+4(6T8 D:9 *2))$$0(2E3+4(6T8*9 D:12 ))$$0(2E3+4(6T8*9212 R: F id ))$$0(2E3+4(6T8*9F Ir_a 10 ))$$0(2E3+4(6T8*9F10 D:11 ))$$0(2E3+4(6T8*9F10)11 R: T (T*F) )$

e) Reconocer (6+(4*2)):

... ... ...$0(2E3+4T Ir_a 5 )$$0(2E3+4T5 D:7 )$$0(2E3+4T5)7 R: E (E+T) $( )

$0E Ir_a 1 $$0E1 Aceptar $

1 A ti d l i i t áti t i l tó t fi it1. A partir de la siguiente gramática, construir el autómata finito determinista y la tabla de análisis para el analizador SLR(1).

S (S) S | ε

2 Reconocer la cadena “( ( ) )( )”2. Reconocer la cadena ( ( ) )( ) .

Análisis sintáctico SLR(1)Análisis sintáctico SLR(1)

A tó tAutómata:

Análisis sintáctico SLR(1)Análisis sintáctico SLR(1)

T bl• Tabla:Siguiente(S’) = { $ }

Siguiente(S) = { ) , $ }

( ) $ S

g ( ) { ) }

( ) $ S

0 D-2 R: S Є R: S Є 1

1 Aceptar

2 D-2 R: S Є R: S Є 3

4 D-2 R: S Є R: S Є 54 D-2 R: S Є R: S Є 5

5 R: S (S)S R: S (S)S

$0 D:2 (())()$$0(2 D:2 ())()$$0(2(2 R: S Є ))()$

• Reconocer(())()

$ ( ( R: S Є ))()$$0(2(2S Ir_a 3 ))()$$0(2(2S3 D: 4 ))()$$0(2(2S3)4 R: S Є )()$$0(2(2S3)4S Ir_a 5 )()$$0(2(2S3)4S5 R: S (S)S )()$$0(2S Ir_a 3 )()$$0(2S3 D: 4 )()$$0(2S3)4 D:2 ()$$0(2S3)4(2 R: S Є )$$0(2S3)4(2S Ir_a 3 )$$0(2S3)4(2S3 D: 4 )$$0(2S3)4(2S3)4 R: S Є $

e) Reconocer (())()

... ... ...$0(2S3)4(2S3)4 R: S Є $$ ( ) ( ) R: S Є $$0(2S3)4(2S3)4S Ir_a 5 $$0(2S3)4(2S3)4S5 R: S (S)S $$0(2S3)4S Ir_a 5 $_

$0(2S3)4S5 R: S (S)S $$0 R: S Є $$0S Ir_a 1 $$0S1 Aceptar $

Análisis SLR(1)Análisis SLR(1)

E E OR EE -> E OR E| E AND E| (E)| 0| 1

Cont. SoluciónCont. Solución

Estado OR AND ( ) 0 1 # EEstado OR AND ( ) 0 1 # E

0 s6 s9 s10 1

1 s2 s3 r1 aceptar

2 s6 s9 s10 4

3 s6 s9 s10 5

4 s2/r2 s3/r2 r2 r2

5 s2/r3 s3/r3 r3 r3

6 s6 s9 s10 76 s6 s9 s10 7

7 s2 s3 s8

8 r4 r4 r4 r4

9 r5 r5 r5 r5

10 r6 r6 r6 r6

Analizador LALR(1)Analizador LALR(1)

S’ SS S S L=R | RL *R | idR LR L

Hay un conflicto de ReducciónHay un conflicto de Reducción por Desplazamiento en S2:

- La gramática no es SLR

Analizador LALR(1) - Autómata IAnalizador LALR(1) Autómata I

Analizador LALR(1) - Autómata IIAnalizador LALR(1) Autómata II

Analizador LALR(1) - Tabla de análisisAnalizador LALR(1) Tabla de análisis

R0: S’ SR0: S S R1: S L=RR2: S RR3: L *RR3: L R R4: L idR5: R L

Analizador LALR(1) - AnálisisAnalizador LALR(1) Análisis

Procesadores de lenguaje...$0E Ir_a 1 $ $0E1 Reducir E’ÆE $ $0E' EXITO $ Procesadores de...

Documents

procesadores superescalares

Procesadores de Textos Procesadores de Textos Procesadores de Textos Concepto – Tipos - Versiones Concepto – Tipos - Versiones

0E-3. MUROS Y TABIQUES 1NA.pptx

Tema 1: PROCESADORES SEGMENTADOS - … · Tema 1: PROCESADORES SEGMENTADOS • 1.1. Procesadores RISC frente a procesadores CISC. • 1.2. ... Tarea ejecutada mediante un procesador

Procesadores Procesadores de audio digital FM

081,&,3$/,'$' '( -,0e1(= · 081,&,3$/,'$' '( -,0e1(= 3ijlqd 35(6838(672 &2162/,'$'2 'hwdooh gh ,qjuhvrv &rqvrolgdgr -xvwlilfdflyq gh ,qjuhvrv 'hwdooh hqhudo sru 3duwlgd hqhudo \

Demo procesadores

Resultados CEN 0e NUEVO

Procesadores intel

Procesadores intell

los procesadores

Otros procesadores

Generaciones Procesadores

81,9(56,'$'1$&,21$/$87Ï120$' (0e;,&2 - UNAM

Procesadores (8)

FRANCISCO JAVIER CORELLA VALLEJO TA 2 · grupo 2.11 curso 2013/2014 ta 2 francisco javier corella vallejo 02,6e6 -,0e1(= -,0e1(= 6,/9,$ &$5,'$' 52'5Ë*8(= ,%Èf(= 01 10 25 escala

Benchmark Procesadores

Procesadores PowerPC

PROCESADORES CISC

685*,0,(172 < '(&$'(1&,$ '( /$ &$6$&,Ï1 (1 0e;,&2