Zerlegung einer Zeichenfolge in eine Folgen von Symbolen (Tokens)
Aufgabe
eines Scanners ist es eine Zeichenfolge über dem Eingabe-Alphabet zu
zerlegen in eine Folge von Symbolen.
Es reicht beim Zerlegen der Eingabefolge also nicht,
nur die Folge der längsten Teilwörter zu berechnen, zusätzlich müssen
diesen Teilwörter auch noch einem Symbol zugeordnet werden.
mit dem zugehörigen NFA und der Eingabe
i if if8 42 42. 42.195 .1 --123
({2,3,4,5}, "i")
({2,18,19}, " ")
({2,5,6}, "if")
({2,18,19}, " ")
({2,5,6}, "if8")
({2,18,19}, " ")
({2,7,8,9,10,11}, "42")
({2,18,19}, " ")
({2,12,13}, "42.")
({2,18,19}, " ")
({2,13,14}, "42.195")
({2,18,19}, " ")
({2,16,17}, ".1")
({2,18,19}, " ")
({2,20}, "-")
({2,20}, "-")
({2,7,8,9,10,11}, "123")
minimaler DFA
Scanner-Lauf
mit dem zugehörigen minimalem DFA
und der gleichen Eingabe
i if if8 42 42. 42.195 .1 --123
( 3, "i")
(11, " ")
( 3, "if")
(11, " ")
( 3, "if8")
(11, " ")
( 6, "42")
(11, " ")
( 7, "42.")
(11, " ")
( 7, "42.195")
(11, " ")
( 7, ".1")
(11, " ")
(12, "-")
(12, "-")
( 6, "123")
Problem: In den Endzuständen ist nicht mehr bekannt,
auf welchem Weg diese erreicht wurden.
Also ist die Zuordung zu den korrekten
Symbolen nicht mehr möglich.
Problem: Beim Transformieren des DFA in den minimalen DFA wird mit
einer Anfangspartition gearbeitet, in der alle Endzustände in einer Menge
liegen.
Es werden also möglicherweise Endzustände als äquivalent betrachtet,
die zu verschiedenen Symbolen gehören, z.B. IF und ID.
Lösung
Die regulären Ausdrücke in der Scanner-Spezifikation
werden alle einzeln in NFAs transformiert.
Die Endzustände werden mit dem zugehörigen Symbol markiert.
Diese Markierungen bleiben bei der Transformation in einen DFA
erhalten.
Sollten mehrere Markierungen in einer Zustandsmenge landen, so bleibt das
Symbol mit der höchsten Priorität erhalten, die anderen werden gelöscht.
Bei der Transformation in den minimalen Automaten werden Endzustände mit
unterschiedlichen Markierungen als nicht äquivalent betrachtet.
Die Anfangspartition ist also feiner.
Beim Abspalten des längsten Prefixes wird die Markierung des
Endzustandes genutzt, um das zugehörige Symbol zuzuordnen.
Beispiel
Scanner für IF, ID, NUM, REAL, WS und ERR
Scanner
Spezifikation
[("IF","if")
,("ID","[a-z][a-z0-9]*")
,("NUM","[0-9]+")
,("REAL","([0-9]+[.][0-9]*)|([.][0-9]+)")
,("WS","[ \n\t]+")
,("CMT","--[a-z]*\n")
,("ERR",".")
]
NFA
DFA
minimaler DFA
Scanner-Lauf
mit dem zugehörigen minimalem DFA
mit den markierten Endzuständen und der Eingabe
i if if8 42 42. 42.195 .1 --123
( 3 ID, "i")
(12 WS, " ")
( 2 IF, "if")
(12 WS, " ")
( 4 ID, "if8")
(12 WS, " ")
( 6 NUM, "42")
(12 WS, " ")
( 8 REAL, "42.")
(12 WS, " ")
( 8 REAL, "42.195")
(12 WS, " ")
( 8 REAL, ".1")
(12 WS, " ")
(15 ERR, "-")
(15 ERR, "-")
( 6 NUM, "123")
Durch diese Markierung und die daraus resultierende feinere
Anfangspartition bei der Transformation in den minimalen Automaten erhöht sich
die Anzahl der Zustände.
In diesem Beispiel werden anstatt 8
jetzt 12 Zustände benötigt.
Compilerbau: Automaten als Scanner
