Ingeniero

Compiladores e Interpretes

EPCI - UNPRG

DIAGRAMAS DE TRANSICIONES
Son grafos dirigidos que especifican el reconocimiento de un token como elemento del lenguaje. En un diagrama de transición (DT) se compila un token. Partes: Estado inicial Estado Estado final Transición Arista
0 id inicio 0

n n 1

Se dice que un token se compila en un DT, si este es reconocido o cumple una ruta desdeel estado inicial hasta un estado de aceptación (estado final). DT básicos:
a

-

ER: a | b L (a | b) = L(a) | L(b) = {a,b}

inicio

0

b

1

-

ER: ab
inicio

L (ab) = L(a) L(b)= {ab} ER: a* L (a*) = L(a)* = {Є, a, aa, aaa, aaaa, ...} ER: a+ L (a+ ) = L(a)+ = {a, aa, aaa, aaaa, ...}

0

a

1

b

2

a inicio Є

-

0

1

-

a inicio a

0

1

a

a+ aa*

inicio

0

a

1

Є

2

a*

Ing. Luis Reyes Lescano

1

Compiladores e Interpretes

EPCI - UNPRG

EJERCICIOS
I. Desarrollar los Diagramas de Transición (DT) de lassiguientes Expresiones Regulares (ER). 1. (a | b) a*bb sobre ={a,b} 2. (a* | b+)* a* | b* sobre ={a, b}
Є a inicio a a inicio 0 b 1 Є 2 b 3 b 4 3 Є Є 4 b Є b Є Є Є a Є

0

1 b

2

5

6

Є3. ((xy* | mn*)* | xy)+ | mn

sobre
Є xy

={xy, mn}

Є Є xy

Є inicio 0 Є 1 Є

2
mn

Є 4 Є 1

Є

2
mn

Є 4 Є 4

Є 3 Є xy

Є 3 Є xy Є
mn

Є

4. ((0* | 1)+ | 0* | 1+)* (0| 1*)*

sobre
Є

={0,1}
Є 1

Є 0 0

3 Є inicio 0 Є 1 1 Є 2 Є 4 0 Є 1 1 7 Є

6 Є 1 Є Є 5 Є 9 Є

11

Є 0 Є
10

Є

8 Є

Ing. Luis Reyes Lescano

2

Compiladores e InterpretesEPCI - UNPRG

II.

Desarrollar los Diagramas de Transición (DT) de las siguientes Definicione s Regulares (DR). 1. Números enteros con signo y sin signo. DR: num_entero  (-|+| ) digito+Inicio 0

digito
digito 1 2
3

+

2. Números reales con signo y sin signo. DR: num_real  (-| +| ) digito+ . digito+
digito inicio a 0 + 1 digito a . 2 3 digito 4 digito

-

3. Numero en...