Zusammenschalten
der Transformationen von REs in NFAs und NFAs in DFAs
Beispiel:((b|c)*a(b|c)*a)*(b|c)*
Alphabet A = {a, b, c}
der äquivalente deterministische Automat
ohne Zustandsmengen
?
Wie würde ein per Hand konstruierter Automat für dieses Beispiel aussehen?
Übergangs- Tabelle
des deterministischen Automaten
q
{...}
i
delta(q,i)
{...}
1
{1,2,3,4,6,7,13}
[b-c]
3
{2,6,7,8,13,14}
1
{1,2,3,4,6,7,13}
a
4
{9,10,11}
2
{2,3,4,5,6,7,13}
[b-c]
3
{2,6,7,8,13,14}
2
{2,3,4,5,6,7,13}
a
4
{9,10,11}
3
{2,6,7,8,13,14}
[b-c]
3
{2,6,7,8,13,14}
3
{2,6,7,8,13,14}
a
4
{9,10,11}
4
{9,10,11}
a
2
{2,3,4,5,6,7,13}
4
{9,10,11}
[b-c]
5
{10,11,12}
5
{10,11,12}
a
2
{2,3,4,5,6,7,13}
5
{10,11,12}
[b-c]
5
{10,11,12}
Beispiel:if|[a-z][a-z0-9]*
if oder identifier
der äquivalente deterministische Automat
ohne Zustandsmengen
Übergangs- Tabelle
des deterministischen Automaten
q
{...}
i
delta(q,i)
{...}
1
{1}
i
2
{2,3,4,5}
1
{1}
[a-hj-z]
3
{2,4,5}
2
{2,3,4,5}
[0-9a-z]
4
{2,5,6}
3
{2,4,5}
[0-9a-z]
4
{2,5,6}
4
{2,5,6}
[0-9a-z]
4
{2,5,6}
Beispiel:if|then|else|
if , then , else oder identifier
der äquivalente deterministische Automat
ohne Zustandsmengen
Übergangs- Tabelle
des deterministischen Automaten
q
{...}
i
delta(q,i)
{...}
1
{1}
i
2
{2,3,10,11}
1
{1}
t
3
{2,4,10,11}
1
{1}
e
6
{2,7,10,11}
1
{1}
[a-df-hj-su-z]
9
{2,10,11}
2
{2,3,10,11}
[0-9a-z]
10
{2,11,12}
3
{2,4,10,11}
h
4
{2,5,11,12}
3
{2,4,10,11}
[0-9a-gi-z]
10
{2,11,12}
4
{2,5,11,12}
e
5
{2,6,11,12}
4
{2,5,11,12}
[0-9a-df-z]
10
{2,11,12}
5
{2,6,11,12}
[0-9a-z]
10
{2,11,12}
6
{2,7,10,11}
l
7
{2,8,11,12}
6
{2,7,10,11}
[0-9a-km-z]
10
{2,11,12}
7
{2,8,11,12}
s
8
{2,9,11,12}
7
{2,8,11,12}
[0-9a-rt-z]
10
{2,11,12}
8
{2,9,11,12}
[0-9a-z]
10
{2,11,12}
9
{2,10,11}
[0-9a-z]
10
{2,11,12}
10
{2,11,12}
[0-9a-z]
10
{2,11,12}
Beispiel:if|then|else|
Schlüsselwörter, Bezeichner und Zahlen
der äquivalente deterministische Automat
ohne Zustandsmengen
Übergangs- Tabelle
des deterministischen Automaten
q
{...}
i
delta(q,i)
{...}
1
{1,27}
i
2
{2,3,24,25}
1
{1,27}
t
3
{2,4,17,24,25}
1
{1,27}
e
6
{2,7,22,24,25}
1
{1,27}
w
9
{2,10,24,25}
1
{1,27}
d
13
{2,14,24,25}
1
{1,27}
f
14
{2,15,24,25}
1
{1,27}
b
16
{2,18,24,25}
1
{1,27}
[acg-hj-su-vx-z]
21
{2,24,25}
1
{1,27}
[0-9]
23
{2,27,28}
2
{2,3,24,25}
[0-9a-z]
22
{2,25,26}
3
{2,4,17,24,25}
h
4
{2,5,25,26}
3
{2,4,17,24,25}
[0-9a-gi-z]
22
{2,25,26}
4
{2,5,25,26}
e
5
{2,6,25,26}
4
{2,5,25,26}
[0-9a-df-z]
22
{2,25,26}
5
{2,6,25,26}
[0-9a-z]
22
{2,25,26}
6
{2,7,22,24,25}
l
7
{2,8,25,26}
6
{2,7,22,24,25}
n
20
{2,23,25,26}
6
{2,7,22,24,25}
[0-9a-kmo-z]
22
{2,25,26}
7
{2,8,25,26}
s
8
{2,9,25,26}
7
{2,8,25,26}
[0-9a-rt-z]
22
{2,25,26}
8
{2,9,25,26}
[0-9a-z]
22
{2,25,26}
9
{2,10,24,25}
h
10
{2,11,25,26}
9
{2,10,24,25}
[0-9a-gi-z]
22
{2,25,26}
10
{2,11,25,26}
i
11
{2,12,25,26}
10
{2,11,25,26}
[0-9a-hj-z]
22
{2,25,26}
11
{2,12,25,26}
l
12
{2,13,25,26}
11
{2,12,25,26}
[0-9a-km-z]
22
{2,25,26}
12
{2,13,25,26}
[0-9a-z]
22
{2,25,26}
13
{2,14,24,25}
[0-9a-z]
22
{2,25,26}
14
{2,15,24,25}
o
15
{2,16,25,26}
14
{2,15,24,25}
[0-9a-np-z]
22
{2,25,26}
15
{2,16,25,26}
[0-9a-z]
22
{2,25,26}
16
{2,18,24,25}
e
17
{2,19,25,26}
16
{2,18,24,25}
[0-9a-df-z]
22
{2,25,26}
17
{2,19,25,26}
g
18
{2,20,25,26}
17
{2,19,25,26}
[0-9a-fh-z]
22
{2,25,26}
18
{2,20,25,26}
i
19
{2,21,25,26}
18
{2,20,25,26}
[0-9a-hj-z]
22
{2,25,26}
19
{2,21,25,26}
[0-9a-z]
22
{2,25,26}
20
{2,23,25,26}
[0-9a-z]
22
{2,25,26}
21
{2,24,25}
[0-9a-z]
22
{2,25,26}
22
{2,25,26}
[0-9a-z]
22
{2,25,26}
23
{2,27,28}
[0-9]
23
{2,27,28}
Die Anzahl der Zustände steigt mit der Anzahl der reservierten Wörter stark an. Dies
führt zu einer großen Übergangstabelle. Daher ist die Strategie, die Schlüsselwörter mittels endlicher
Automaten zu erkennen in manchen Fällen bezüglich des Speicherplatzes ineffizient. Ein Erkennen
eines Namens und anschließendes Nachsehen in einer Tabelle für reservierte Wörter kann hier Speicherplatz sparender sein.
Compilerbau: Transformation: RE -> DFA
