Aufgabe
|
Zerlegung des Eingabe-Zeichenstrom in Symbole der Programmiersprache
|
|
Überlesen von nicht signifikanten Zeichen, wie Leerraum und Kommentar
|
|---|
| |
Tokens
|
ein selbstdefiniertes Alphabet für die Symbole einer Programmiersprache
|
| |
Spezifikation
|
der Symbole durch reguläre Ausdrücke
|
| |
Wiederholung
|
reguläre Ausdrücke: Notation
|
|
| ε | (oder nichts) |
| z | für alle z ∈ A |
| r1 | r2 | |
| r1 ⋅ r2 | (oder r1r2) |
| r* | |
| r+ | Abkürzung für rr* |
| r? | Abkürzung für r|ε |
| r{n} | Abkürzung für n-fache Wiederholung: r...r
r{0} = ε
r{1} = r
r{n} = r(r{n-1}) für n > 1 |
| r{n,} | Abkürzung für mindestens n-fache Wiederholung
r{0,} = r*
r{n,} = r(r{n-1,}) für n > 0 |
| r{n,m} | Abkürzung für n-fache bis m-fache Wiederholung
r{n,n} = r{n}
r{0,m} = r?r{0,m-1} für m > 0
r{n,m} = r(r{n-1,m-1}) für n > 0, m > n
|
| [z1-z2] | (Abkürzung für
z1|...|z2) |
| . | (Abkürzung für ein beliebiges Zeichen, oft außer
\n) |
| \n, \t, \[, \. | (Ersatzsequenzen, Maskieren von
einzelnen Zeichen) |
| "..." | (Maskieren von Zeichenfolgen) |
| (...) | Prioritätenklammern |
|
|---|
| |
Beispiel
|
| R.E. | Symbol |
|---|
| if | IF |
| [a-z][a-z0-9]* | ID |
| [0-9]+ | NUM |
| ([0-9]+"."[0-9]*)|("."[0-9]+) | REAL |
| ([ \n\t]+)|("--"[a-z]*\n) | WHITESPACE |
| . | ERROR |
|
| |
Anforderungen
|
an die Beschreibung
|
| |
vollständig
|
Jedes Eingabezeichen muss zu mindestens einem R.E. passen.
|
genauer
|
Jede Zeichenfolge muss mit Hilfe der Liste der R.E.s in eine
Symbolfolge zerlegt werden können.
|
| |
|
default-Regel als letzter R.E. im Beispiel
|
| |
eindeutig
|
Jedem Textmuster muss genau ein Symbol zugeordnet werden.
|
genauer
|
Jede Zeichenfolge muss mit Hilfe der Liste der R.E.s in GENAU eine
Symbolfolge zerlegt werden können.
|
| |
1.Problem
|
|
| |
Lösung:
longest match
|
Der längste Präfix, der auf einen R.E. passt wird als nächstes Symbol verarbeitet.
|
| |
2.Problem
|
|
| |
Lösung:
Prioritäten
|
Der erste passende R.E. wird gewählt.
|
| |
Konsequenz
|
Die Reihenfolge der R.E.s in der Spezifikation ist signifikant.
|
| |
R.E.s und E.A.s
|
|
| |
Reguläre Ausdrücke
|
sind deskriptiv
|
|
beschreiben WAS gemacht werden soll
|
|---|
| |
Endliche Automaten
|
sind operational
|
|
beschreiben WIE etwas gemacht wird
|
|---|
| |
Ziel
|
Zu jedem R.E. einen gleichwertigen endlichen Automaten konstruieren.
|
| |
?
|
Was heißt gleichwertiger Automat?
|
| |
Ziel
|
für die lexikalische Analyse:
Für die Kombination aller Ausdrücke ist ein R.E. (und E.A.) gesucht.
|
| |
|
Alle R.E.s mit | zu einem zusammensetzen.
|
|
Alle Teilautomaten zu einem Automaten zusammenschalten,
die Startzustände zu einem Startzustand zusammenfassen.
|
|---|
| |
Problem
|
Es entsteht ein nichtdeterministischer endlicher Automat.
|
| |
Lösung
|
Konstruktion eines gleichwertigen deterministischen endlichen Automaten.
|
| |
Arbeitsweise
|
eines D.E.A. bei der Zerlegung der Eingabe in eine Folge von Tokens
|
|
Erkennung der längsten passenden Zeichenfolge.
|
|---|
| |
Compilerbau: Lexikalische Analyse
