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}
alle Wörter mit gerader Anzahl von a's
|
|
|
|
|
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} |
a |
2 |
{9,10,11} |
| 1 |
{1,2,3,4,6,7,13} |
[b-c] |
3 |
{2,6,7,8,13,14} |
| 2 |
{9,10,11} |
a |
4 |
{2,3,4,5,6,7,13} |
| 2 |
{9,10,11} |
[b-c] |
5 |
{10,11,12} |
| 3 |
{2,6,7,8,13,14} |
a |
2 |
{9,10,11} |
| 3 |
{2,6,7,8,13,14} |
[b-c] |
3 |
{2,6,7,8,13,14} |
| 4 |
{2,3,4,5,6,7,13} |
a |
2 |
{9,10,11} |
| 4 |
{2,3,4,5,6,7,13} |
[b-c] |
3 |
{2,6,7,8,13,14} |
| 5 |
{10,11,12} |
a |
4 |
{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} |
[a-hj-z] |
2 |
{2,4,5} |
| 1 |
{1} |
i |
3 |
{2,3,4,5} |
| 2 |
{2,4,5} |
[0-9a-z] |
4 |
{2,5,6} |
| 3 |
{2,3,4,5} |
[0-9a-z] |
4 |
{2,5,6} |
| 4 |
{2,5,6} |
[0-9a-z] |
4 |
{2,5,6} |
|
|
|
Beispiel:
if|then|else|
[a-z][a-z0-9]+
|
if, then, else oder identifier
|
|
|
|
|
der äquivalente deterministische Automat
|
|
|
ohne Zustandsmengen
|
|
|
|
Übergangs- Tabelle |
des deterministischen Automaten
|
| q |
{...} |
i |
delta(q,i) |
{...} |
| 1 |
{1} |
[a-df-hj-su-z] |
2 |
{2,10,11} |
| 1 |
{1} |
e |
3 |
{2,7,10,11} |
| 1 |
{1} |
i |
4 |
{2,3,10,11} |
| 1 |
{1} |
t |
5 |
{2,4,10,11} |
| 2 |
{2,10,11} |
[0-9a-z] |
6 |
{2,11,12} |
| 3 |
{2,7,10,11} |
[0-9a-km-z] |
6 |
{2,11,12} |
| 3 |
{2,7,10,11} |
l |
7 |
{2,8,11,12} |
| 4 |
{2,3,10,11} |
[0-9a-z] |
6 |
{2,11,12} |
| 5 |
{2,4,10,11} |
[0-9a-gi-z] |
6 |
{2,11,12} |
| 5 |
{2,4,10,11} |
h |
8 |
{2,5,11,12} |
| 6 |
{2,11,12} |
[0-9a-z] |
6 |
{2,11,12} |
| 7 |
{2,8,11,12} |
[0-9a-rt-z] |
6 |
{2,11,12} |
| 7 |
{2,8,11,12} |
s |
9 |
{2,9,11,12} |
| 8 |
{2,5,11,12} |
[0-9a-df-z] |
6 |
{2,11,12} |
| 8 |
{2,5,11,12} |
e |
10 |
{2,6,11,12} |
| 9 |
{2,9,11,12} |
[0-9a-z] |
6 |
{2,11,12} |
| 10 |
{2,6,11,12} |
[0-9a-z] |
6 |
{2,11,12} |
|
|
|
Beispiel:
if|then|else|
begin|end|
while|do|for|to|
[a-z][a-z0-9]+
[0-9]+
|
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} |
[0-9] |
2 |
{2,27,28} |
| 1 |
{1,27} |
[acg-hj-su-vx-z] |
3 |
{2,24,25} |
| 1 |
{1,27} |
b |
4 |
{2,18,24,25} |
| 1 |
{1,27} |
d |
5 |
{2,14,24,25} |
| 1 |
{1,27} |
e |
6 |
{2,7,22,24,25} |
| 1 |
{1,27} |
f |
7 |
{2,15,24,25} |
| 1 |
{1,27} |
i |
8 |
{2,3,24,25} |
| 1 |
{1,27} |
t |
9 |
{2,4,17,24,25} |
| 1 |
{1,27} |
w |
10 |
{2,10,24,25} |
| 2 |
{2,27,28} |
[0-9] |
2 |
{2,27,28} |
| 3 |
{2,24,25} |
[0-9a-z] |
11 |
{2,25,26} |
| 4 |
{2,18,24,25} |
[0-9a-df-z] |
11 |
{2,25,26} |
| 4 |
{2,18,24,25} |
e |
12 |
{2,19,25,26} |
| 5 |
{2,14,24,25} |
[0-9a-z] |
11 |
{2,25,26} |
| 6 |
{2,7,22,24,25} |
[0-9a-kmo-z] |
11 |
{2,25,26} |
| 6 |
{2,7,22,24,25} |
l |
13 |
{2,8,25,26} |
| 6 |
{2,7,22,24,25} |
n |
14 |
{2,23,25,26} |
| 7 |
{2,15,24,25} |
[0-9a-np-z] |
11 |
{2,25,26} |
| 7 |
{2,15,24,25} |
o |
15 |
{2,16,25,26} |
| 8 |
{2,3,24,25} |
[0-9a-z] |
11 |
{2,25,26} |
| 9 |
{2,4,17,24,25} |
[0-9a-gi-z] |
11 |
{2,25,26} |
| 9 |
{2,4,17,24,25} |
h |
16 |
{2,5,25,26} |
| 10 |
{2,10,24,25} |
[0-9a-gi-z] |
11 |
{2,25,26} |
| 10 |
{2,10,24,25} |
h |
17 |
{2,11,25,26} |
| 11 |
{2,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 12 |
{2,19,25,26} |
[0-9a-fh-z] |
11 |
{2,25,26} |
| 12 |
{2,19,25,26} |
g |
18 |
{2,20,25,26} |
| 13 |
{2,8,25,26} |
[0-9a-rt-z] |
11 |
{2,25,26} |
| 13 |
{2,8,25,26} |
s |
19 |
{2,9,25,26} |
| 14 |
{2,23,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 15 |
{2,16,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 16 |
{2,5,25,26} |
[0-9a-df-z] |
11 |
{2,25,26} |
| 16 |
{2,5,25,26} |
e |
20 |
{2,6,25,26} |
| 17 |
{2,11,25,26} |
[0-9a-hj-z] |
11 |
{2,25,26} |
| 17 |
{2,11,25,26} |
i |
21 |
{2,12,25,26} |
| 18 |
{2,20,25,26} |
[0-9a-hj-z] |
11 |
{2,25,26} |
| 18 |
{2,20,25,26} |
i |
22 |
{2,21,25,26} |
| 19 |
{2,9,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 20 |
{2,6,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 21 |
{2,12,25,26} |
[0-9a-km-z] |
11 |
{2,25,26} |
| 21 |
{2,12,25,26} |
l |
23 |
{2,13,25,26} |
| 22 |
{2,21,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
| 23 |
{2,13,25,26} |
[0-9a-z] |
11 |
{2,25,26} |
|
|
|
|
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 & Formale Sprachen: Transformation: RE -> DFA
