archetype | title | author | readings | outcomes | attachments | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
lecture-bc |
LL-Parser |
BC George (HSBI) |
|
|
|
- Warum reichen uns DFAs nicht zum Matchen von Eingabezeichen?
- Wie könnnen wir sie minimal erweitern?
- Sind PDAs deterministisch?
- Wie sind kontextfreie Grammatiken definiert?
- Sind kontextfreie Grammatiken eindeutig?
- einen Grammatiktypen, aus dem sich manuell oder automatisiert ein Programm zur deterministischen Syntaxanalyse erstellen lässt
- einen Algorithmus zum sog. Parsen von Programmen mit Hilfe einer solchen Grammatik
- Syntaxanlyse
- Top-down-Analyse
- rekursiver Abstieg
- LL(k)-Analyse
Die Syntax bezieht sich auf die Struktur der zu analysierenden Eingabe, z. B. einem Computerprogramm in einer Hochsprache. Diese Struktur wird mit formalen Grammatiken beschrieben. Einsetzbar sind Grammatiken, die deterministisch kontextfreie Sprachen erzeugen.
- Top-Down-Analyse: Aufbau des Parse trees von oben nach unten
- Parsen durch rekursiven Abstieg
- tabellengesteuertes LL-Parsing
- Bottom-Up-Analyse: LR-Parsing
Def.: Ein Nichtterminal A einer kontextfreien Grammatik G heißt unerreichbar, falls es kein
Def.: Eine kontextfreie Grammatik
Bevor mit einer Grammatik weitergearbeitet wird, müssen erst alle nutzlosen und dann alle unerreichbaren Symbole eliminiert werden. Wir betrachten ab jetzt nur reduzierte Grammatiken.
Hier ist ein einfacher Algorithmus, der (indeterministisch) top-down Ableitungen vom Nonterminal X aufbaut:
Eingabe: Ein Nichtterminal
Welche Produktion nehmen?
Wir brauchen die "terminalen k-Anfänge" von Ableitungen von Nichtterminalen, um eindeutig die nächste zu benutzende Produktion festzulegen.
Def.: Wir definieren
-
$a \in T^\ast, |a| \leq k: {First}_k (a) = \lbrace a\rbrace$ -
$a \in T^\ast, |a| > k: {First}_k (a) = \lbrace v \in T^\ast \mid a = vw, |v| = k\rbrace$ -
$\alpha \in (N \cup T)^\ast \backslash T^\ast: {First}_k (\alpha) = \lbrace v \in T^\ast \mid \alpha \overset{\ast}{\Rightarrow} w,\text{mit}\ w \in T^\ast, First_k(w) = \lbrace v \rbrace \rbrace$
Def.: Bei einer kontextfreien Grammatik
Man schreibt
Manchmal müssen wir wissen, welche terminalen Zeichen hinter einem Nichtterminal stehen können.
Def. Wir definieren Follow - Mengen einer Grammatik wie folgt:
Def.: Eine kontextfreie Grammatik G = (N, T, P, S) ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form:
und
mit
Das hilft manchmal:
Für
-
$\lnot \exists a \in T: \alpha \overset{\ast}{\Rightarrow}_l a\alpha_1$ und$\beta \overset{\ast}{\Rightarrow}_l a\beta_1$ -
$((\alpha \overset{\ast}{\Rightarrow}_l \epsilon) \Rightarrow (\lnot (\beta \overset{\ast}{\Rightarrow}_l \epsilon)))$ und$((\beta \overset{\ast}{\Rightarrow}_l \epsilon) \Rightarrow (\lnot (\alpha\overset{\ast}{\Rightarrow}_l \epsilon)))$ -
$((\beta \overset{\ast}{\Rightarrow}_l \epsilon)$ und$(\alpha \overset{\ast}{\Rightarrow}_l a\alpha_1)) \Rightarrow a \notin Follow(A)$ -
$((\alpha \overset{\ast}{\Rightarrow}_l \epsilon)$ und$(\beta \overset{\ast}{\Rightarrow}_l a\beta_1)) \Rightarrow a \notin Follow(A)$
\bigskip
Die ersten beiden Zeilen bedeuten:
Die dritte und vierte Zeile bedeuten:
Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der deterministisch parsbaren Sprachen.
Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der von LL(k+1)-Grammatiken erzeugten Sprachen.
Für eine kontextfreie Grammatik G ist nicht entscheidbar, ob es eine LL(1) - Grammatik G' gibt mit
In der Praxis reichen
Eingabe: Eine Grammatik G = (N, T, P, S) mit
Ausgabe: Eine Parsertabelle P
\medskip
Statt
Rekursive Programmierung bedeutet, dass das Laufzeitsystem einen Stack benutzt (bei einem Recursive-Descent-Parser, aber auch bei der Parsertabelle). Diesen Stack kann man auch "selbst programmieren", d. h. einen PDA implementieren. Dabei wird ebenfalls die oben genannte Tabelle zur Bestimmung der nächsten anzuwendenden Produktion benutzt. Der Stack enthält die zu erwartenden Eingabezeichen, wenn immer eine Linksableitung gebildet wird. Diese Zeichen im Stack werden mit dem Input gematcht.
Eingabe: Eine Grammatik G = (N, T, P, S), eine Parsertabelle P mit
Ausgabe: Wenn
- Syntaxanalyse wird mit deterministisch kontextfreien Grammatiken durchgeführt.
- Eine Teilmenge der dazu gehörigen Sprachen lässt sich top-down parsen.
- Ein einfacher Recursive-Descent-Parser arbeitet mit Backtracking.
- Ein effizienter LL(k)-Parser realisiert einen DPDA und kann automatisch aus einer LL(k)-Grammatik generiert werden.
- Der Parser liefert in der Regel einen abstrakten Syntaxbaum (AST).
::: slides
Unless otherwise noted, this work is licensed under CC BY-SA 4.0. :::