Mit der zweiten Vorlesung, will ich die Syntaktische Analyse vollständig abdecken um möglichst schnell die Syntax als Vorhang vor der eigentlichen Bedeutung der Sprache hinter uns zu lassen. Am Anfang der Vorlesung soll der Zeichenstrom stehen und am Ende der Abstrakte Syntaxbaum. Dabei will ich vermeiden jede erdenkliche Art und Weise des Parsens zu behandeln, und nur schlaglichtartig einen Blick auf das Thema der Parser zu richten.
- Motivation
- ?
- Sprachen sind eigentlich nicht Kontextfrei
- Lexer
- Zerteilung in einen Tokenstrom
- Kombination aus endlichen Automaten
- Parser
- Wiederholung Kontextfreie Grammatiken
- Backus-Naur-Form
- Ableitungsbaum bzw. Parsebaum
- Recursive Descent Parser/Syntaxgraphen/LL(1)
- Vom Parsebaum zum Abstrakten Syntaxbaum
- LR(1) Grammatiken und Parsergeneratoren (kurz)
- C ist nur mit Symbol Table parsebar
- Parsing ist ganz weites Feld, in dem es viele Unterschiedliche Klassen und Parsetechniken gibt. Was Menschen meist verwenden ist LALR(1).
- Wiederholung Kontextfreie Grammatiken
- Regular or Context-Free!
- Man wird ganz leicht eine weird machine.
- Zusammenfassung
Was lernt man aus dieser Vorlesung für die Ziele effektiv und effizient?
- Syntax ist nur ein Vorhang vor der eigentlichen Semantik.
- Der Studierende muss irgendwann den AST sehen und nicht mehr die Zeichen.
- Man kommt ganz schnell in größere Komplexitätsklassen.
\subtitle{{{{subtitle()}}}}
\maketitleframe
\begin{frame}[t]{Einordnung in die Vorlesung: Syntaktische Analyse}
\begin{center}
\includegraphics[page=4,width=0.8\linewidth]{fig/01-overview-small}
\end{center}
\bi
\ii Die Syntaktische Analyse ist der erste Schritt in einem Übersetzer.\medskip
\ii Was sollte der \emph{effektive} und \emph{effiziente} Informatiker darüber Wissen? {
\bi
\ii Die Syntax ist die nur die Schreibweise, wie man die Konzepte notiert.
\ii Rekursiv geschachtelte Elemente und Bäume passen zueinander.
\ii Es gibt gute Formalismen und mächtige Werkzeuge zur Syntaktischen Analyse.
\ei
}
\ei
\end{frame}
\begin{frame}{Was ist das Ziel der Syntaktischen Analyse?}
\begin{center}
\includegraphics[page=1,width=0.6\linewidth]{fig/01-overview-example}
\end{center}
\bi
\ii Überprüfung der Syntaxregeln und Extraktion der Programmstruktur {
\bi
\ii Syntaktische Korrektheit ist \alert{ein} Teil der Sprachregeln.
\ii Übersetzer für Programmiersprachen müssen Zeichenketten verarbeiten.
\ii Im Weiteren benötigen wir die Programmstruktur als abstrakten Syntaxbaum.
\ei
}
\ei
\end{frame}Ein Übersetzer für (Maschinen-)Programme{{{see(01-ebenenmodell,Ebenenmodell)}}} wird meistens mit einer, oft sehr langen, Zeichenkette konfrontiert, von der der Programmierer behauptet, es wäre ein valides Programm. Da der Programmier beim Kodieren wahrscheinlich unter Zeitdruck stand, faul war, oder einfach ein anderes Verständnis von Ästhetik hat, darf der Übersetzer kreative Formatierungen und allerhöchstens die Erfüllung der minimalen Sprachregeln erwarten. Er muss also herausfinden, ob diese Zeichenkette ein valides Programm der erwarteten Sprache darstellt oder ob es fehlerhaft ist.
Der erste Schritt dieser akribischen Untersuchung des Quellprogramms ist die Syntaktische Analyse oder Syntaxanalyse. Diese ist Vergleichbar mit der Rechtschreib- und Grammatikprüfung bei normalsprachlichen Texten, bei der es zunächst auch nur darum geht, ob alle Worte richtig geschrieben und die Regeln der Satzstruktur eingehalten wurde. Dabei überprüft die Syntaxanalyse ebenso wenig den Sinn eines Satzes, welchen man auch als seine Semantik bezeichnen kann, wie dies ein Rechtschreibprogramm tut.
Ein Beispiel, im Kontext von Programmiersprachen, für den Unterschied
zwischen Syntax und Semantik ist das folgende Pythonprogramm. Es
stellt zwar ein syntaktisch korrektes Programm dar, ist also nach den
Regeln der Sprache aufgeschrieben worden, aber es ergibt keinen
Sinn, weil die Variable undef_variable nicht definiert wurde.
Versuchen Sie im interaktiven Interpreter, der wie ein Übersetzer auch eine Syntaxanalyse
durchführt, einen Syntaxfehler zu provozieren.
foo = undef_variable + 3Um zu prüfen, ob ein gegebenes Programm wirklich zum Maschinenmodell passt, wird es demnach nicht ausreichen, seine syntaktische Korrektheit zu prüfen. Aber es ist ein erster wichtiger Schritt.
Als Seiteneffekt der Syntaktischen Analyse bekommen wir auch noch den
abstrakten Syntaxbaum oder AST (engl. abstract syntax tree). Dieser
Baum, der das Rechenergebnis von Scanner und Parser ist, fängt die
Struktur des Programms ein und wird in der folgenden Übersetzung als
Datenbasis benötigt. Mit dieser Struktur des Programms meinen wir so
etwas wie die korrekte Klammerung von arithmetischen Ausdrücken
(1+2*3-4 wird verstanden als 1+(2*3)-4) oder welche Codezeile zum
then-Teil einer Bedingung gehört.
Für den Informatiker ist die Beschäftigung mit dem Thema Scannen und Parsen aus mehreren Gründen sehr lohnend: Durch den direkten Vergleich von Programmtext und AST sieht man, dass die konkrete Syntax einer Programmiersprache relativ egal ist, hauptsächlich mit Ästhetik, Klarheit und leichter Verständlichkeit zusammenhängt, und vom Übersetzer bereits im ersten Schritt weggewischt wird. Dennoch ist die Extraktion von Strukturen aus einer Zeichenkette ein immer wiederkehrendes Thema der Informatik, das nicht nur bei Programmiersprachen auftritt, sondern, zum Beispiel, auch bei Dateiformaten oder Netzwerkprotokollen.
Daher hat die Informatik auch eine Reihe von präzisen Formalismen entwickelt (reguläre und kontextfreie Sprachen), mit Hilfe derer man solche Probleme erfassen und angehen kann. Mit dieser Formalisierung kam auch die Möglichkeit Werkzeuge zu bauen, die einem dabei helfen, Werkzeuge zur Syntaxanalyse zu erstellen (Parsergeneratoren)[fn::Parsergeneratoren werden auch Compiler-Compiler genannt, da sie Übersetzer sind, die Code erzeugen, der in Übersetzern verwendet wird.].
\dividerframe{Scanner\\und\\Tokenstrom}
\begin{frame}<handout:3>[t]{Tokenstrom}
\animation[width=\linewidth]{1/1,2/2-}{fig/02-token-stream}
\bi
\ii<2-> Gruppierung von Zeichen zu sprachspezifischen Bausteinen (Token) {
\bi
\ii Token haben eine \emph{Klasse} (func) und ggf. eine \emph{Nutzlast} (\texttt{"fnord"}, 23).
\ii Der Tokenstrom enthält keine Leerzeichen oder Kommentare.
\ii Unterschiedliche Schreibweisen (0x17, 23, 027, 0b10111) sind vereinheitlicht.
\ii Gemeinsame Präfixe werden zum längsten Match aufgelöst (\texttt{fn} vs. \texttt{fnord}).
\ei
}\medskip
\ii<3-> Ziele der Abstraktion vom einzelnen Zeichen zum Token{
\bi
\ii \alert{Komplexitätsreduktion:} Es gibt immer weniger Token als Zeichen.
\ii \alert{Fokussierung} auf die Sprachelemente, nicht auf ihre Schreibweise.
\ii \alert{Vereinfachung} des Parsens durch weniger Sonderfälle (Kommentare).
\ei
}
\ei
\end{frame}
\begin{frame}<handout:1,3>[t]{Scanner (oder Lexer)}
\begin{center}
\signature{scanner\_next}{Stream[char]}{Token}
\end{center}
\bi
\ii<2-|handout:2-> Der Scanner (auch Abtaster oder Lexer) erzeugt den Tokenstrom. {
\bi
\ii \texttt{scanner\_next} konsumiert Zeichen vom Anfang bis zum Ende eines Tokens.
\ii Implementierung: \alert<3>{manuell} oder mittels regulärer Ausdrücke und Tooling
\ei
}
\ei
\begin{code}<3-|handout:3->[tag=Py]
\lstinputlisting[style=PY,style=smaller,linerange={scanner0-scanner1,scanner2-scanner3}]{lst/02-scanner.py}
\end{code}
\only<1|handout:1>{\begin{tikzpicture}[overlay,remember picture,box/.style={draw=srared,ultra thick}]
\node[fit=(sig-name),box,pin=-100:Funktionsname]{};
\node[fit=(sig-input),box,pin=-90:Parameter]{};
\node[fit=(sig-output),box,pin=-85:Rückgabewert]{};
\node[below=2 of sig-input] {\alert{Konvention}: Wir verwenden Funktionssignaturen aus Haskell};
\end{tikzpicture}}%
\end{frame}Die Eingabe unseres Übersetzers ist eine Zeichenkette, die der Programmierer mühsam auf der Tastatur eingetippt und dann in einer Datei gespeichert hat. In dem Prozess des Kodierens hat der Programmierer die Programmstruktur, die in seinem Geist entstanden ist, in diese Zeichenkette serialisiert.
Als ersten Schritt wollen wir die Zeichenkette in einen linearen
Tokenstrom aus sprachspezifischen Elementen, wie Schlüsselwörter und
Bezeichner, verwandeln. Dazu läuft der Scanner (= Lexer) einmal(!)
über die Zeichenkette und emittiert, immer wenn ein vollständiges
Sprachelement, was häufig aus mehr als einem Zeichen besteht, gelesen
wurde, ein einzelnes Token. Diese Token haben immer eine Tokenklasse
(z.B. Bezeichner oder “öffnende runde Klammer”) und manchmal eine
Nutzlast. In dieser Nutzlast transportiert der Scanner weitere
Informationen zum Token zu den nachfolgenden Übersetzerstufen. So
haben beispielsweise alle Bezeichner die gleiche Tokenklasse
(identifier) und tragen die überdeckten Zeichen aus der Eingabe
(das Lexem) als Nutzlast (z.B., Bezeichnername) mit sich herum.
Durch den Prozess des Scannens eliminieren wir Leerzeichen und jegliche Codeformatierung, wir vereinheitlichen unterschiedliche Schreibweisen des gleichen Sprachelements und wir reduzieren die Anzahl der zu verarbeitenden Objekte erheblich. Dies macht Übersetzerbauern das Leben im Folgenden erheblich einfacher, weil der Rest der Syntaxanalyse deutlich schneller ablaufen kann und wir viele Sonderfälle der Sprache bereits abgedeckt haben. So würden wir beispielsweise einen deutlich aufwendigeren Parser benötigen, wenn wir erst dort Kommentare, die überall im Quellcode auftauchen können, behandeln würden.
Um einen Scanner für eine Sprache zu erstellen, haben wir prinzipiell zwei Möglichkeiten: Entweder wir kodieren eine entsprechende Funktion manuell oder wir leiten einen Scanner von einer Menge regulärer Ausdrücke mit Hilfe eines Generators ab. Der manuelle Ansatz wird auch ad-hoc Ansatz genannt, da die Kodierung als ein normales Programm keinem Formalismus folgt. Dies hat den Nachteil, dass es schwierig ist, einen korrekten Scanner von Hand zu schreiben, aber es bringt auch den Vorteil, dass man an jeder Stelle Sonderbehandlungen einbauen kann, mit sich.
In beiden Fällen benutzt der Scanner zwei Operationen auf dem Eingabestrom: read() konsumiert ein Zeichen vom Anfang und gibt es zurück, peek() gibt dasselbe Zeichen zurück, ohne es zu konsumieren. Insbesondere letzteres, das Vorausschauen, oder look-ahead, im Zeichenstrom ist ein Konzept, welches uns beim Parser wieder begegnen wird. Eine wichtige Eigenschaft von Scannern und Parsern ist es, wie viele Zeichen der Vorausschau benötigt werden. Die meisten Sprachen kommen mit einem Scanner aus, der nur ein einzelnes Zeichen Vorschau benötigt[fn::Fortran ist ein trauriges Gegenbeispiel: http://shape-of-code.coding-guidelines.com/2009/12/20/parsing-fortran-95/ ].
Im Beispiel[fn::Vollständiger Scanner: ./lst/02-scanner.py]
liefert die Funktion scanner_next() bei jedem Aufruf eine 2-elementige
Liste, bestehend aus Tokentyp und Nutzlast, zurück. Die Funktion
überspringt zunächst alle Leer- und Tabulatorzeichen, bevor die
eigentliche Tokenerkennung startet. Dieser Beispielscanner erkennt nur
Ganzzahlen, allerdings ist es möglich diese Zahlen in binärer
(0b111), oktaler (0777), oder hexadezimaler Schreibweise zu
erkennen. Hierfür erkennt der Scanner, ob ein entsprechendes Präfix
vorliegt (z.B. 0x für hexadezimal) und liest danach entsprechend der
erkannten Notation solange Zeichen aus der entsprechenden Klasse
zulässiger Zeichen, bis ein unzulässiges Zeichen erreicht wird (stream.read_many()).
An diesem Beispiel ist es wichtig zu erkennen, dass das Zeichen 0
ein gemeinsames Präfix ist und erst mit dem zweiten Zeichen (b,
x, oder eine Oktalzahl) wirklich feststeht, welche Notation an dieser
Stelle vorliegt. Mit jedem weiteren gelesenen Zeichen, wird hier die
Menge der möglichen Notationen weiter eingeschränkt. So ist ab der
ersten gelesenen 0 klar, dass es sich nicht mehr um eine Zahl in
Dezimalnotation handeln kann.
\begin{frame}<handout:3>[t]{Wiederholung: Reguläre Sprachen und ihre Akzeptoren}
\bi
\ii Reguläre Sprachen werden von Typ-3 Grammatiken erzeugt. {
\btDefTab[4cm]
\bi
\ii (Nicht-)Terminale: \btSetTab \emph{nonterminal} $\rightarrow$ X
\ii Alternativen: \btUseTab \emph{hexdigit} $\rightarrow$ 0 $\mid$ 1 $\mid$ 2 $\mid$ 3 $\mid$ \ldots $\mid$ f
\ii Konkatenierung: \btUseTab \emph{hexprefix} $\rightarrow$ 0x
\ii Wiederholung: \btUseTab \emph{hexliteral} $\rightarrow$ \emph{hexprefix} \emph{hexdigit} \emph{hexdigit}*\hfill(Kleene Stern)
\ei
}\medskip
\ii Reguläre Ausdrücke sind eine Kurzschreibweise für diese Grammatiken. {
\bi
\ii Für hexadezimale Zahlen: 0x[0-9a-f][0-9a-f]*
\ii Verwendung zum Pattern Matching in Texten (\texttt{grep(1)}, Py: \texttt{import re}, \ldots)
\ii Effizient implementierbar in $\mathcal{O}(n)$, wenn $n$ die Eingabelänge
\ei
}
\ii<2-> Darstellung und Implementierung: (nicht-)deterministische Automaten {\medskip
\begin{center}
\animation{1/2,2/3}{fig/02-automata-hex}
\end{center}
}
\ei
\end{frame}
\begin{frame}{Scanner als Kombination von Regulären Automaten}
\animation[width=\linewidth]{1/1,2/2,3/3,4/4,5/5,6/6,7/7,8/8,9/9,10/10,11/11,12/12}{fig/02-scanner}
\bi
\ii Automaten parallel über die Eingabe ausführen{
\bi
\ii Longest Possible Match, Konfliktauflösung bei mehrfachem Match
\ii Simulation des NFA, Umwandlung in \emph{determinstic finite automata} (\texttt{flex(1)})
\ei
}
\ei
\end{frame}
Für den Schritt der Tokenerkennung aus einem Zeichenstrom hat sich herausgestellt, dass der Rückgriff auf formale Konzepte aus der theoretischen Informatik höchst lohnend ist und, dass man mit regulären Ausdrücken die Token der meisten Programmiersprachen hervorragend beschreiben kann.
Reguläre Ausdrücke beschreiben eine reguläre Sprache und haben die gleiche Ausdrucksstärke wie eine reguläre Grammatik.
Man kann sagen, dass reguläre Ausdrücke ein Formalismus ist, mit dem man reguläre Grammatiken konstruieren kann, ohne ausversehen in die nächst komplexere Sprachklasse (kontextfrei) zu rutschen.
Daher wollen wir nun der ad-hoc Implementierung scanner_next() aus dem Beispiel einen formaleren Hintergrund geben.
Zu Beginn müssen wir uns daran erinnern, was Grammatiken überhaupt
waren. Die theoretische Informatikvorlesung ist lange her, und die
Erinnerung bereits verschwommen. Zunächst ist eine (formale) Grammatik
ein Regelsatz, der beschreibt, wie man, beginnend von einem
Startsymbol, über einen iterativen Textersetzungsprozess zu einer
Zeichenkette kommt. Zu jedem Zeitpunkt besteht die Zeichenkette aus
einer Reihe von terminalen und nichtterminalen Symbolen und die
Ersetzung wird solange wiederholt, bis nur noch terminale Symbole
übrig sind. Die Ersetzung an sich erfolgt durch eine Menge von Regel,
die ein Muster erkennt und durch ein anderes Muster ersetzt. Alle
Zeichenketten, die abgeleitet werden können, nennt man die zugehörige
(formale) Sprache[fn::Verwechslungsgefahr: Formale Sprachen sind etwas
anderes als Programmiersprachen und sie haben nichts mit einem
Maschinenmodell zu tun. Das Skript unterscheidet daher strikt zwischen
formalen Sprachen und (einfach nur) Sprachen.]. Im Folgenden leiten
wir, Zeile für Zeile, die Zeichenkette 0xa2c aus dem Startsymbol
hexliteral her:
hexliteral hexprefix hexdigit hexdigit* 0x hexdigit hexdigit* 0xa hexdigit* 0xa2 hexdigit* 0xa2c hexdigit* 0xa2c
Je nachdem wie die Regeln einer Grammatik strukturiert sind, werden diese in unterschiedliche Klassen eingeteilt{{{wikipedia_de(Chomsky-Hierarchie)}}}. Die einfachste Klasse, die besonders wünschenswerte Eigenschaften hat, sind die regulären Grammatiken. Bei dieser Klasse gilt, dass alle Regeln kontextfrei sind und das man mit einem endlichen Automaten erkennen kann ob ein Wort in der Sprache ist (Wortproblem). Dabei bedeutet kontextfrei, dass auf den linken Seiten der Ersetztungsregeln immer nur ein einzelnes Nichtterminal steht, sodass jedes Nichtterminal, egal in welchem Kontext es steht, immer gleich ersetzt wird. Die Abbildbarkeit von regulären Grammatiken auf endliche Automaten führt dazu, dass man aus der Grammatik sehr leicht ein Programm ableiten kann, welches das Wortproblem lößt. Dabei drehen wir die Richtung der Grammatik um, und erzeugen keine Zeichenketten mehr, sondern konsumieren diese. Genau das, was wir für unseren Scanner brauchen.
Allerdings ist der Nachweis ob eine gegebene Grammatik wirklich regulär ist, nicht ganz leicht.
Daher gehen wir das Problem von einer anderen Seite heran und greifen auf **reguläre Ausdrücke** zurück um die Token unserer Sprache zu beschreiben.
Bei diesem Formalismus ist konstruktiv sicher gestellt, dass jeder reguläre Ausdruck eine reguläre Sprache beschreibt.
Daher kann man aus jedem regulären Ausdruck eine entsprechende reguläre Grammatik ableiten und es kann niemals geschehen, dass ein regulärer Ausdruck ausversehen nicht mehr regulär ist.
Erreicht wird diese Garantie durch das Verbot rekursiver Ersetzungen[fn::In keiner der möglichen Ersetzungen eines Nichtterminals kann das Nichtterminal noch einmal auftreten.].
Um dennoch das wiederholte Auftreten eines Nichtterminals zu erlauben, welches in regulären Grammatiken möglich ist[fn::Reguläre Grammatik: A -> xA, Regulärer Ausdruck: ~x*~] wird der Kleene-Stern eingeführt, bei dem das direkt vorangegangene Nichtterminal 0 bis N mal ersetzt werden kann.
Beim Parsen werden wir kontextfreie Grammatiken verwenden, die rekursive Ersetzungen enthalten und daher nicht mittels regulärerer Ausdrücke beschrieben werden können.
Für das Erkennen einer regulären Sprache konstruiert man aus den Grammatikregeln einen endlichen Automaten, der die Zeichenkette elementweise konsumiert.
An jeder Kante des Automaten gibt es eine Bedingung (engl.
Guard), die angibt, bei welchen gelesenen Zeichen die Transition möglich ist.
Ist die Entscheidung, welche Transition genommen wird, zu irgendeinem Zeitpunkt nicht eindeutig, so ist der Automat nicht-deterministisch.
Erreichen wir beim konsumieren einen akzeptierenden Zustand, so haben wir ein Wort der formalen Sprache erkannt.
Allerdings können akzeptierende Zustände auch wieder verlassen werden, um noch längere Worte der Sprache zu erkennen.
Im Fall der Hexadezimalzahlen dürfen am Ende noch beliebig viele Zeichen aus der Klasse [0-9a-fA-F] auftauchen.
Im Kontext eines Scanners bedeutet das Erreichen eines akzeptierenden
Zustandes, dass wir ein valides Token gefunden haben. Allerdings
könnte dieses Token auch das Präfix eines längeren Tokens sein. So ist
zwar 0xa2 eine valide hexadezimale Zahl, aber es ist auch das Präfix
für das Wort 0xa2c. Für Scanner wollen wir immer jenes Token
finden, das die maximale Länge hat (longest possible match).
Da es in einer Programmiersprache unterschiedliche Arten von Token gibt, die es zu erkennen gilt, müssen wir mehrere Automaten kombinieren; ein Automat/Grammatik/regulären Ausdruck/Sprache für jeden Tokentyp. Dazu lassen wir “einfach” alle Automaten parallel laufen und füttern jedem Automaten jedes gelesene Zeichen, sodass jeder Automat eine Transition macht. Hat ein Automat zu einem Zeitpunkt keine valide Transition, so fällt er aus (Folien: er wird grau) und wird nicht weiter mit Zeichen gefüttert. Erreicht einer der Automaten einen akzeptierenden Zustand, so merken wir uns das erkannte Wort (auch **Lexem** genannt). Wir füttern die Automaten so lange mit Zeichen, bis auch der letzte von ihnen ausgefallen ist und geben das zuletzt gefundene Wort als Token zurück.
Dieses parallele Ausführen von endlichen Automaten können wir entweder tatsächlich durchführen oder wir können, was effizienter ist, einen kombinierten Automaten konstruieren: Dazu fügt man einen weiteren Startzustand ein, der über Epsilon-Transitionen die Startzustände der einzelnen Token erreichen kann (was den kombinierten Automaten immer nicht-deterministisch macht). Mittels der Potenzmengenkonstruktion leitet man den äquivalenten deterministischen Automaten her.
Zurück zu den weniger theoretischen Aspekten des Scannens.
Im Beispiel auf den Folien ist eine Situation abgebildet, bei der das Schlüsselwort fn das Präfix für den Bezeichner fnord ist und zum gleichen Zeitpunkt (fn) zwei Automaten das Lexem als valides Wort erkennen würden.
In solchen Fällen müssen wir durch zusätzliche Regeln angeben, welcher der Tokentypen den Vorrang hat.
Für Programmiersprachen müssen Schlüsselwörter immer höhere Prioritäten als Bezeichner haben, solange der Bezeichner nicht länger ist.
Dies ist der Grund, wieso Sie Schlüsselwörter nicht als Variablennamen verwenden können und diese daher auch oft als reservierte Wörter genannt werden.
Da die manuelle Konstruktion von endlichen Automaten und deren Kombination müßig ist, gibt es Programme, die aus einer Menge von regulären Ausdrücken einen Scanner erzeugen. Ein solches Programm ist flex(1). Sollten Sie später einen Lexer brauchen, der schnell und korrekt eine Zeichenkette in Tokens zerlegt, so zögern Sie nicht und nehmen Sie einen Scannergenerator zur Hand! Mehr zu den Sicherheitsaspekten von Scannern, und auch Parsern, lernen wir in einem kleinen Exkurs am Ende dieser Vorlesung kennen.
\dividerframe{Parser\\und\\Syntaxbaum}
\begin{frame}<handout:2>{Blockstruktur und Klammerung}
\bi
\ii \textbf{Erinnerung}: Wir wollen Syntaxbaum aus Tokenstrom erzeugen.
\bigskip
\ii Programmiersprachen enthalten \emph{geschachtelte} oder \emph{rekursive} Konstrukte{%
\bi
\ii Geklammerte Ausdrücke: \btSetTab ((1*2)+(3/4)-(5*6))\hfill\emph{explizit}\\
\ii Operatorpräzedenz: \btUseTab 1*2+3/4-5*6\hfill\emph{implizit}
\ii Blockstrukturen: \btUseTab if (\ldots) \{ if (\ldots) \{ while (\ldots) \{ \ldots \} \} \} \hfill\emph{explizit}
\ii Grammatik: \btUseTab \grammarrule{\NT{expr}}{ ( \NT{expr} ) \OR \NT{expr} + \NT{expr}}
\ei
}\medskip
\ii<2-> Bäume eignen sich, diese Strukture zu erfassen!{
\includegraphics[width=0.45\linewidth,page=2]{fig/02-tree}\hfill
\includegraphics[width=0.45\linewidth,page=3]{fig/02-tree}
\bi
\ii{Token werden hierarchisch geordnet. Implizite Regeln werden explizit.}
\ii{Bäume sind \alert{rekursive} Datenstrukturen. Unterbäume sind auch Bäume!}
\ei
}
\ei
\end{frame}
\begin{frame}<handout:1-2>[t]{Wiederholung: Kontextfreie Grammatiken}
\bi
\ii Reguläre Grammatiken nicht fähig rekursive Strukturen zu erfassen\\
\enquote{Klammernzählen} ist verboten: \grammarrule{\NT{A}}{( \NT{A} ) \OR \EPSILON}
\bigskip
\ii Kontextfreie Sprachen werden von Typ-2 Grammatiken erzeugt.{
\bi
\ii Weiterhin erlaubt: Alternativen ($\mid$), Konkatenierung ($Aa$), Wiederholung ($A*$)
\ii Zusätzlich: Nichtterminale dürfen sich selbst referenzieren.{\medskip
\begin{center}
\includegraphics[width=0.3\linewidth,page=1]{fig/02-grammar}
\hspace{1cm}
\includegraphics[width=0.3\linewidth,page=2]{fig/02-grammar}
\end{center}
}
\ei
}\medskip
\ii Kontextfreie Sprachen können von Kellerautomaten erkannt werden.{
\bi
\ii Kellerautomat: Endlicher Zustandsautomat + Unendlicher Stapelspeicher
\ii Erkennung immer in $\mathcal{O}(n^3)$ möglich: Cocke-Younger-Kasami Algorithmus
\ii Für Programmiersprachen relevante Grammatiken: $\mathcal{O}(n)$
\ei
}
\ei%
\begin{tikzpicture}[remember picture,overlay,visible on=<2|handout:2>]
\node[anchor=south east,inner sep=0,xshift=1cm] at (current page.south east) (yeah) {\includegraphics[width=4.5cm]{fig/yeah}};
\node[anchor=south east,fill=safegreen!50,draw,xshift=1.2cm,yshift=6mm] at (yeah.south west) {\Huge $\mathcal{O}(n)$};
\end{tikzpicture}
\end{frame}
\begin{frame}{Determinstische Kontextfreie Grammatiken}
\bi
\ii Kontextfrei bedeutet nicht direkt, dass der Baum eindeutig ist.{
\bi
\ii Linksableitung: Das linkeste Nicht-Terminal wird zuerst abgeleitet.
\ei
\medskip
\begin{center}
\small
\fbox{\grammarrule{\NT{E}}{ \NT{E} + \NT{E} \OR Integer}\strut}
$\oplus$
\fbox{\strut 1 + 2 + 3 + 4}
$\Rightarrow$
\medskip
\includegraphics[width=0.3\linewidth,page=11]{fig/02-tree}
\includegraphics[width=0.3\linewidth,page=12]{fig/02-tree}
\includegraphics[width=0.3\linewidth,page=13]{fig/02-tree}
\end{center}
}\medskip
\ii Wir werden nur deterministische Grammatiken verwenden. {
\bi
\ii \alert<2>{LL-Grammatiken: \btDefTab \textbf{L}inks lesend, \textbf{L}inksableitend} \only<2>{\hfill $\Rightarrow$ Recursive-Descent Parser}
\ii LR-Grammatiken: \btUseTab \textbf{L}inks lesend, \textbf{R}echtsableitend \only<2>{\hfill $\Rightarrow$ Parsergeneratoren}
\ii LL($k$)/LR($k$): \btUseTab Mit $k$ Zeichen Look-Ahead Parsebar \only<2>{\hfill LL(1) $\ll$ LR(1)}
\ei
}
\ei
\end{frame}Die syntaktische Analyse hat zwei primäre Ziele: (1) Die Überprüfung der syntaktischen Regeln der Sprache, also ob das Programm richtig notiert wurde. (2) Die Befüllung einer geeigneten Datenstruktur mit der extrahierten Struktur des Programms.
Für beide Ziele stellt sich die Frage, welcher Natur die syntaktischen Konstrukte in echten Programmiersprachen sind. Hierbei fällt schnell auf, dass viele Konstrukte geschachtelt vorkommen können: Dies bedeutet, dass ein Konstrukt von einem Konstrukt anderer Art umschlossen auftreten kann. So umschließt ein Funktionsrumpf eine oder mehrere Programmanweisungen. Es ist sogar recht häufig, dass ein Konstrukt von einem Konstrukt gleicher Art umschlossen auftreten darf, und damit **rekursiv** ist. Dabei ist der arithmetische Ausdruck das Paradebeispiel, bei dem die Schachtelung entweder explizit durch Klammern oder implizit durch die Operatorpräzedenz notiert wird.
Um der geschachtelten Natur von Programmiersprachen Rechnung zu tragen, benötigen wir also eine Datenstruktur, die ebenfalls rekursiv ist. Die bedeutet, dass eine Instanz dieser Datenstruktur weitere, kleinere, Instanzen der gleichen Datenstruktur enthalten kann. Die einfachste rekursive Datenstruktur, die in Frage kommt, ist die einfach verkettete Liste:
struct list {
int value;
struct list * next;
};Bei dieser einfach verketteten Liste ist das nachfolgende Element next wiederum eine einfach verkettete Liste (oder NULL).
Allerdings enthält jedes Element einer Liste maximal eine weitere Liste.
Da wir bereits, bei den Anweisungen und dem Funktionsrumpf, erkannt haben, dass ein Sprachkonstrukt mehrere “Kinder” haben kann, ist sofort klar, dass die verkettete Liste ungeeignet für unsere Zwecke ist.
Daher müssen wir auf die nächst mächtigere Klasse von Datenstruktur, nämlich die der **Bäume**, wechseln. Bäume sind hervorragend geeignet, die syntaktische Struktur von Programmen zu erfassen: Sie sind rekursiv, da jedes Kind eines Knotens wiederum ein Unterbaum ist; dabei sind Blätter triviale Bäume.
Für unser Beispiel der arithmetischen Ausdrücke zeigt ein innerer Knoten an, welche Operation ausgeführt werden soll. Die Kinder dieses Knotens sind die Operanden, die verrechnet werden. Da Operationen in der Regel nicht kommutativ sind, ist die Reihenfolge der Kinder wichtig.
Für die Speicherung von Bäumen können wir dann doch wieder Listen verwenden, solange wir Listen als Listenelemente zulassen.
Dabei speichern wir immer im ersten Element einer Liste den aktuellen Knoten; alle weiteren Listenelemente sind die Kinder.
Der Baum für den arithmetischen Ausdruck 1*2+3/4 wäre dann[fn::In Lisp wäre es (+ (* 1 2) (/ 3 4)).
In dieser Programmiersprache, die von Studierenden aufgrund ihrer immensen Menge an Klammerung gehassten wird, werden Programme direkt in einer solchen Listennotation notiert. Es gibt nur wenige weitere syntaktische Regeln.
Dies erklärt auch ihre Beliebtheit bei Übersetzerbauern: Man kommt mit einem sehr einfachen Parser aus. Wenn Sie also über die folgenden Abschnitte stöhnen, denken Sie daran: Mit Lisp wäre das alles nicht nötig.]:
def node(tree):
return tree[0]
def children(tree):
return tree[1:]
tree = ['+', ['*', [1], [2]], ['/', [3], [4]]]
print(children(tree))Im Kapitel über Scanner haben wir bereits formale Grammatiken und formale Sprachen als eine Methode kennen gelernt, Regeln von Programmiersprachen zu notieren. Mit dieser Erfolgsgeschichte im Rücken, können wir uns nun daran machen auch die weiteren Sprachregeln formal aufzuschreiben.
Hierbei stellt allerdings die erwähnte rekursive Natur von Programmiersprachen ein Hindernis dar: Bei regulären Sprachen haben wir explizit verboten, dass Regeln sich selbst referenzieren, also rekursiv sind. Daher sind Typ-3-Grammatiken **nicht**[fn::Dies ist auch der Grund, wieso man mit Regexen kein HTML parsen kann. Versuchen Sie es nicht, es wird immer scheitern bzw. ein Hack bleiben.] geeignet, um Programme zu parsen und wir müssen auf die Typ-2 Grammatiken, also die **kontextfreien Sprachen** wechseln. Diese erlauben es, dass auf der linken Seite einer Regel ein Nicht-Terminal stehen darf, welches (direkt oder indirekt) wiederholt auf der rechten Seite auftauchen kann. Dies erlaubt es, dass eine kontextfreie Grammatik “Klammern zählen” kann und daher in der Lage ist korrekt balancierte Klammerungen zu erzeugen.
Im Allgemeinen ist die Komplexität des “Wortproblems” (Prüfung, ob ein Wort in der Sprache ist) für kontextfreie Sprachen kubisch{{{wikipedia_de(Cocke-Younger-Kasami-Algorithmus)}}}. Allerdings gibt es mit den **deterministischen kontextfreien Sprachen** eine Klasse von Sprachen, die in linearer Zeit, also viel viel schneller, erkennbar sind. Daher sind eigentlich alle Programmiersprachen in dieser Klasse zu finden, da das Lösen des Wortproblems gleichbedeutend mit dem Parsen ist.
Um zu verstehen, was deterministisch im Fall von kontextfreien Sprachen bedeutet, müssen wir uns **Ableitungsbäume** für kontextfreie Grammatiken anschauen. Bei Ableitungsbäumen entspricht jeder innere Knoten einem Nicht-Terminal, jedes Blatt entspricht einem Terminal. Die durchgeführten Ableitungen kann man von oben nach unten ablesen: Die Kinder eines Nicht-Terminals entsprechen den Elementen der rechten Seite der angewendeten Regel. Die Blätter (Terminale), wenn wir sie von links nach rechts lesen, ergeben das erzeugte Wort. Der Ableitungsbaum ist also eine Vorschrift, wie die Regel einer Grammatik anzuwenden ist, damit ein bestimmtes Wort entsteht. Umgekehrt bedeutet dies auch, dass wir beim Lösen des Wortproblems einen Ableitungsbaum angeben müssen, um zu zeigen, dass das Wort in der Sprache ist. Das rekonstruieren des Ableitungsbaums nennt man auch **parsen**.
Gibt es mehr als eine Möglichkeit einen Ableitungsbaum für ein gegebenes Wort zu rekonstruieren, ist die Grammatik mehrdeutig. In Falle einer mehrdeutigen Grammatik, versehen wir zwei der entstehenden Ableitungsbäume mit einem speziellen Namen: Die **Linksableitung** entsteht, wenn immer das linkeste Nicht-Terminal zuerst abgeleitet wird; die **Rechtsableitung** vice versa mit dem rechtesten Nicht-Terminal.
Gibt es genau einen Ableitungsbaum für jedes Wort, so ist sie **eindeutig**. Diese Eindeutigkeit ist etwas, was wir bei Programmiersprachen auf jeden Fall haben wollen. Denn der Übersetzer soll die Struktur unseres Programms ja nicht einmal so und einmal anders erkennen.
Noch strenger als “eindeutig”, ist die Eigenschaft des **deterministisch**: Bei einer deterministischen Grammatik gibt es eine allgemeine Vorschrift, wie und in welcher Reihenfolge die Regeln angewendet werden müssen, um einen Ableitungsbaum aus einem gegebenen Wort zu rekonstruieren[fn::Formaler: Deterministische kontextfreie Sprachen können mit deterministischen Kellerautomaten erkannt werden.]. Zum Beispiel kann solch eine Vorschrift sein, dass man das Wort von links nach rechts durchgeht und am jeweils nächsten Zeichen (look-ahead) entscheidet, welche Regel im Folgenden angewendet werden muss. Dies ist der Sprachklasse LL(1), mit der wir uns nun intensiver auseinander setzen werden.
\begin{frame}{Determinstische Linksableitende Grammatiken}
\textbf{Informell:} Bei einer LL(1)-Grammatik kann man am aktuellen Zeichen sicher erkennen, welche Regel als nächstes angewendet werden soll.
\bigskip\medskip
\begin{columns}
\begin{column}{0.49\textwidth}
\btDefTab[2.3cm]
\grammarrule{\NT{intAdd}\btUseTab} { Int \NT{intAddTail}}\\
\grammarrule{\NT{intAddTail}\btUseTab }{+ Int \NT{intAddTail}}\\
\grammarrule{\NT{intAddTail}\btUseTab}{ $\dashv$}\\
\end{column}\hfill
\begin{column}{0.49\textwidth}
\includegraphics[page=3]{fig/02-grammar}
\end{column}
\end{columns}
\medskip
\bi
\ii Diese Sprachklasse kann mit \emph{rekursivem Abstieg} geparst werden. {
\btUseExtraItemSep
\bi
\ii Eine Funktion für jedes Nicht-Terminal:\\\lstinline[style=PY]|def intAddTail(token_stream)|
\ii Entscheidung über angewendete Regel anhand des Look-Aheads:\\
\lstinline[style=PY]|if token_stream.peek() == TOK_PLUS: ...|
\ii Recursive-Descent Parser werden manuell erstellt oder generiert.
\ei
}
\ei
\end{frame}
\begin{frame}{Beispiel: Parser mit rekursivem Abstieg}
\lstset{
style=PY,
morekeywords={TOK\_PLUS,TOK\_INT,TOK\_EOF},
}
\begin{code}
\lstinputlisting[
linerange={parser0-parser1},
firstnumber=0,
linebackgroundcolor={%
\btLstHL<1>{2}%
\btLstHL<3>{3-4}%
\btLstHL<4>{5-6}%
\btLstHL<5>{8}%
}
]{lst/02-ll0-recursive.py}%
\end{code}
\begin{code}
\lstinputlisting[
linerange={parser2-parser3},
firstnumber=0,
linebackgroundcolor={%
\btLstHL<1>{2-3}%
\btLstHL<2>{5-6}%
\btLstHL<3>{7-8}%
\btLstHL<4>{9-10}%
\btLstHL<5>{12}%
}
]{lst/02-ll0-recursive.py}%
\end{code}
\vfill
\strut\hspace{-5mm}\only<5->{
\lstinline[style=PY]|addInt(Scanner("1+2"))| $\Rightarrow$ \lstinline[style=PY]|['intAdd',1,['intAddTail',2,['intAddTail',]]]|
}
\end{frame}
\begin{frame}{LL(1): \PREDICT-Mengen}
Für jede \textbf{Regel} enthält die \PREDICT-Menge jene Token/Terminale, die im Look-Ahead dazu führen, dass die Regel angewendet wird.
\[ \PREDICT(A \rightarrow a) \in T^n\]
\begin{center}
\begin{tabular}{ll}
\toprule
Regel & \PREDICT \\
\midrule
\grammarrule{\NT{intAdd}} { Int \NT{intAddTail}} & \{ Int \}\\
\grammarrule{\NT{intAddTail}}{+ Int \NT{intAddTail}} & \{ + \} \\
\grammarrule{\NT{intAddTail}}{ \$} & \{ \$ \}\\\midrule
\grammarrule{\NT{qualifier}}{const \OR \EPSILON} & \{ const \}\\
\grammarrule{\NT{funcDef}}{\NT{qualifier} func identifier \ldots} & \{ const, func \}\\
\bottomrule
\end{tabular}
\end{center}
\begin{alertblock}{Test: Ist eine Grammatik in LL(1)?}
Alle \PREDICT-Mengen mit der gleichen \textbf{linken} Seite müssen schnittfrei sein. Für jedes Nicht-Terminal ist Regelauswahl eindeutig.
\end{alertblock}
\end{frame}Wie bereits erwähnt, kann man bei einer LL(1)-Grammatik anhand des nächsten Zeichens **deterministisch** entscheiden, welche Regel der Grammatik angewendet werden soll. Um dies zu verstehen, müssen wir mehr darauf eingehen, wie ein Parser für eine LL(1)-Sprache aussieht. Die einfachste Form eines LL(1)-Parsers verwendet die Methode des **rekursiven Abstiegs**, um aus einem Wort den Ableitungsbaum zu rekonstruieren.
Bei einem solchen Parser wird für jedes Nicht-Terminal eine Funktion erzeugt, die genauso heißt wie das Nicht-Terminal.
Diese Funktionen haben den Tokenstrom bzw.
ein Scanner-Objekt als Argument und können vorne aus diesem Strom Zeichen entnehmen (read()).
Weiterhin können sie das erste Zeichen mittels peek() anschauen, ohne es zu entnehmen (look-ahead).
Als Rückgabewert liefern diese Funktionen (partielle) Ableitungsbäume.
Wenn wir eine solche Nicht-Terminal-Funktion aufrufen, entscheidet sie anhand des aktuellen Look-aheads, welche Regel nun angewendet werden muss und konsumiert im Folgenden solange Token aus dem Strom, bis das Teilwort, das zu dieser Regelanwendung gehört, aus dem Tokenstrom entfernt ist. Ein solcher Aufruf ist also ein Art “Rückwärtsableitung” auf der linken Seite des Tokenstroms. Die Funktion ordnet die Token so an, dass sie die Blätter des zurückgegebenen Ableitungsbaums sind.
Wird an einer Stelle auf der rechten Seite ein Nicht-Terminal erwartet, so ruft die Funktion **rekursiv** die entsprechende Parsefunktion auf und gibt den Rückgabewert als Unterbaum weiter. Es sind diese rekursiven Aufrufe, die der Klasse der Parser mit rekursivem Abstieg ihren Namen geben!
Um ein ganzes Programm zu parsen, rufen wir einfach nur die Funktion, die dem Startsymbol entspricht, auf.
Im Folgenden können Sie mit dem intAdd-Parser aus den Vorlesungsfolien herumspielen.
Parser mit rekursivem Abstieg können entweder manuell erstellt werden, oder man verwendet einen LL(1)-Parsergenerator. Ein solcher Generator bekommt eine LL(1)-Grammatik als Eingabe, analysiert die Struktur und die Eigenschaften der Grammatik und generiert ein entsprechendes Programm. Mit dieser Analyse von LL(1)-Grammatiken wollen wir uns nun genauer beschäftigen, um zu verstehen, wie ein solcher Generator genau funktioniert. Dies wird Sie nicht nur in die Lage versetzen LL(1)-Grammatiken zu formulieren, sondern auch selbst einen Parsergenerator zu schreiben. Es ist einfacher, als Sie befürchten!
Die wichtigste Information, die wir aus einer LL(1)-Grammatik extrahieren wollen, sind die **PREDICT-Mengen**: Für jede Regel der Grammatik gibt die zugehörige PREDICT-Menge, die terminale Symbole enthält, an, ob diese Regel genommen wird. Diese Mengen enthalten also genau jenen Token, anhand dessen der Parser mit rekursivem Abstieg, anhand des Look-Aheads, seine Entscheidungen trifft. Vice Versa: Haben wir die PREDICT-Mengen, so können wir daraus also einfach einen Parser konstruieren.
Zusätzlich können wir anhand der PREDICT-Mengen auch prüfen, ob eine gegebene Grammatik eine LL(1)-Grammatik ist. Überschneiden sich die PREDICT-Mengen von zwei Regeln, die das gleiche Nicht-Terminal auf der linken Seite haben, auch nur in einem Zeichen, so liegt keine LL(1)-Grammatik vor. Im Parser mit rekursivem Abstieg könnten wir keine deterministische Entscheidung über die nächste anzuwendende Regel treffen[fn::YouTube: Feuerzangebowle: Ostgoten, die wissen auch nicht ganz genau, wo sie hin müssen.].
\begin{frame}[fragile]{Parser-Generator für Parser mit rekursivem Abstieg}
\bi
\ii Mit den \PREDICT-Mengen können wir einen LL(1)-Parser generieren.{
\bi
\ii Der Parser-Generator (grau) iteriert über Nichtterminale und Regeln.
\ii Er erzeugt und emittiert, mittels Codeschablonen (gelb), den Parsercode.
\ii Innerhalb der Schablonen werden Ersetzungen (grün) vorgenommen.
\ei
}
\ei
\lstdefinestyle{meta}{
basicstyle=\ttfamily\fontsize{8}{12}\selectfont,
escapechar={`},
moredelim=**[is][{\btHL[draw,fill=safegreen!40,rounded corners=0pt,inner ysep=-2pt]}]{@@}{@@},
moredelim=**[is][{\btHL[fill=badbee!50,rounded corners=0pt]}]{!!}{!!},
}
\def\meta{\btHL[draw]}
\begin{code}[]
\begin{py}[style=meta]
# Für jedes Nicht-Terminal erzeugen wir eine Funktion.
for NT in nonterminals:
``!!def @@NT.name@@(token_stream):!!
# Die \PREDICT entscheidet, ob eine Regel genommen wird.
for rule in NT.rules:
``!! if token_stream.peek() in @@PREDICT(rule)@@:!!
for symbol in rule.righthandside:
if is_terminal(symbol):
``!! ``@@..._load@@ = token_stream.read(expect=@@symbol.name@@)!!
else:
``!! ``@@..._tree@@ = @@symbol.name@@(token_stream)!!
# Return Parse Tree
``!! return [@@NT.name@@, @@..._load@@, @@..._tree@@, @@...@@]!!
\end{py}
\end{code}
\bi
\ii Dieser Parser-Generator ist ein Übersetzer von \enquote{Grammatik} $\rightarrow$ Python.
\ei
\end{frame}Zunächst werden wir so tun, als hätten wir die PREDICT-Mengen schon und wollen uns anschauen, wie der Parsergenerator den Code für den Parser erzeugt.
Dafür hat der gezeigte Parsergenerator mehrere interne Datenstrukturen:
Die Liste nonterminals enthält ein Objekt für jedes Nicht-Terminal der Grammatik.
Jedes Nicht-Terminal NT hat einen Namen (NT.name) und eine Liste mit Regeln, auf deren linken Seite das Nicht-Terminal vorkommt (NT.rules)[fn::Diese Regeln für das Nicht-Terminal A nennt man auch A-Produktionen.].
Jede Regel hat eine linke und eine rechte Seite (rule.righthandside).
Die rechte Seite ist dabei eine Liste von Symbolen (Terminale und Nichtterminale), über die der Generator iterieren kann.
Um den gezeigten Generator zu verstehen, müssen Sie auf die Einrückungen achten. Diese sind für den Parsergenerator (grau) und den generierten Code (gelb) unterschiedlich. Die gelben Zeilen sind vollständige Zeilen, die ausgegeben werden, die Einrückungen beziehen sich also auf den gelben linken Rand.
Der Generator erzeugt für jedes Nicht-Terminal eine Funktion und benennt sie anhand des Namens des Nicht-Terminals.
Innerhalb der Funktion wird für jede Regel ein bedingter Block emittiert, der mit einem return Statement endet, das den Ableitungsbaum zurückgeben wird.
Die erzeugte Bedingung prüft, ob das nächste Zeichen in der PREDICT-Menge, die zur aktuellen Regel gehört, enthalten ist (in).
Innerhalb des bedingten Blockes werden, nacheinander, alle Symbole der rechten Seite aus dem Tokenstrom gelesen.
Ist ein Symbol ein Terminal, so lässt der Generator den Parser das Zeichen direkt in der Funktion aus dem Strom konsumieren.
Hierbei bekommt die read()-Funktion das optionale Argument expected=, sodass sie prüft, ob das vorderste Token wirklich von der entsprechenden Klasse ist. Ist dies nicht der Fall, so wird ein Parserfehler geworfen.
Ist das Symbol ein Nicht-Terminal, so delegieren wir das Parsen für diese Teil der rechten Seite an die entsprechende Funktion (rekursiver Abstieg).
Weiterhin legt der Generator für jedes Symbol eine Variable an, um das Token (Terminale) bzw. den Unterbaum (Nichtterminale) aufzufangen und zur Konstruktion des zurückgegebenen Baumes zu verwenden.
Da der Parsergenerator eine Grammatik als Eingabe und einen Parser als Ausgabe hat, können wir ihn als Übersetzer bezeichnen. Dabei akzeptiert der Generator alle Grammatiken der Klasse LL(1) und erzeugt ein Programm in der Programmiersprache Python.
\begin{frame}{\PREDICT: Berechnung von \EPS und \FIRST}
\textbf{Bisher}: Die \PREDICT-Menge fällt vom Himmel bzw. ist trivial.
\bigskip
\bi
\ii Berechnung von \PREDICT mittels \EPS, \FIRST und \FOLLOW.{\medskip
\bi
\ii $\EPS(\alpha) \equiv \textbf{ if } \alpha \Longrightarrow^* \epsilon \textbf{ then}\text{ true}\textbf{ else}\text{ false}$ \\\smallskip
Kann aus dem Wort $\alpha$, durch Ableitung(en), das leere Wort entstehen?
\medskip
\ii $\FIRST(\alpha) \equiv \{ c \mid c \in T, \alpha \Longrightarrow^* c \beta\}$ \\\smallskip
Die Menge aller Terminale, die bei den Ableitungen von $\alpha$ links auftreten.
\ei
}
\ii Beispiel für \EPS und \FIRST:\medskip{
\begin{columns}
\begin{column}{0.44\textwidth}\small%
\begin{exampleblock}{1+(3+4)+foo(2+5)}
\btDefTab[1.8cm]
\grammarrule{\NT{term} \btUseTab}{\NT{factor} \NT{factor\_tail}}\\
\grammarrule{\NT{factor\_tail}\btUseTab}{+ \NT{factor\_tail} \OR \EPSILON}\\
\grammarrule{\NT{factor} \btUseTab}{Int \OR trans ( \NT{term} ) }\\
\grammarrule{\NT{trans} \btUseTab}{Ident \OR \EPSILON}
\end{exampleblock}
\end{column}\hfill
\begin{column}{0.51\textwidth}\small%
\begin{tabular}[t]{lll}\toprule
$\alpha$ & \scriptsize$\EPS(\alpha)$ & \scriptsize$\FIRST(\alpha)$ \\\midrule
term & false & \{Int, Ident, (\}\\
factor\_tail & true & \{+\}\\
factor & false & \{Int, Ident, (\}\\
trans & true & \{ Ident \}\\
\bottomrule
\end{tabular}
\end{column}
\end{columns}
}
\ei
\end{frame}
\begin{frame}[fragile]{\PREDICT: Berechnung der \FOLLOW-Menge}
\bi
\ii $\FOLLOW(A) \equiv \{ c \mid c \in T, S \Longrightarrow^+ \alpha A c \beta \}${\smallskip
\bi
\ii Die Menge aller Terminale, die bei einer Ableitung vom Startsymbol S direkt auf A folgen können. $\alpha$ und $\beta$ sind beliebige Teilwörter.
\ei
\small
\begin{exampleblock}{Grammatik mit Endsymbol $\dashv$}
\begin{columns}
\begin{column}{0.47\textwidth}
\grammarrule{\NT{S}}{\NT{term} $\dashv$} \\
\grammarrule{\NT{term} }{\NT{factor} \NT{factor\_tail}}\\
\grammarrule{\NT{factor\_tail}}{+ \NT{factor\_tail} \OR \EPSILON}\\
\end{column}
\begin{column}{0.47\textwidth}
\grammarrule{\NT{factor} }{Int \OR trans ( \NT{term} ) }\\
\grammarrule{\NT{trans} }{Ident \OR \EPSILON}
\end{column}
\end{columns}
\end{exampleblock}
\begin{center}
\def\NT{\emph}
\def\abox#1{\fbox{\scriptsize\strut#1}}
\begin{tabular}{lll}\toprule
A & $\FOLLOW(A)$ & Beispielhafte Satzformen \\\midrule
term & \{),$\dashv$\} & \abox{(\NT{term})} \abox{\NT{term}$\dashv$ } \\\midrule
factor\_tail & \{),$\dashv$\} & \abox{(1+\NT{factor\_tail})} \abox{1+\NT{factor\_tail} \textbf{$\dashv$}} \\\midrule
factor & \{+,),$\dashv$\} & \abox{1+\NT{factor}\textbf{+}3}
\abox{(5+\NT{factor}\textbf{)}}
\abox{4+\NT{factor} \textbf{$\dashv$}}\\\midrule
trans & \{(\} & \abox{\NT{trans} \textbf{(}1+2)} \\
\bottomrule
\end{tabular}
\end{center}
}
\ei
\end{frame}
\begin{frame}[fragile]{\PREDICT $=$ \FIRST $\oplus$ \FOLLOW}
\bi
\ii {\small $PREDICT(A \rightarrow \alpha) \equiv \FIRST(\alpha) \cup (\textbf{if }\EPS(\alpha)\textbf{ then }\FOLLOW(A)\textbf{ else }\emptyset ) $}{ \\
\bigskip
\textbf{Intuition}: Ein Terminal c sagt eine Regel dann voraus, wenn:
\begin{enumerate}
\item Die Ableitung der rechten Seite mit dem Terminal c startet (\FIRST).
\item Die rechte Seite $\alpha$ kann $\epsilon$ werden, daher muss man auf die Terminal schauen, die der Regel folgen können (\FOLLOW).
\end{enumerate}
\begin{center}
\def\first{}
\def\second{}
\only<3>{\def\first{\rowcolor{badbee!50}}}
\only<2>{\def\second{\rowcolor{badbee!50}}}
\scriptsize
\mbox{}\hspace{-1cm}\begin{tabular}{ll|c|l|l}\toprule
$A \rightarrow \alpha$ & \PREDICT & $\EPS(\alpha)$ & $\FIRST(\alpha)$ & $\FOLLOW(A)$ \\\midrule
\grammarrule{\NT{S}}{\alert<3>{\NT{term}$\dashv$}} & Int, Ident, ( & 0 & Int, Ident,( & \\\midrule
\grammarrule{\alert<3>{\NT{term}}}{\alert<3>{\NT{factor} \NT{factor\_tail}}} & Int, Ident, ( & 0 & Int, Ident, ( & ), $\dashv$ \\\midrule
\grammarrule{\alert<3>{\NT{factor\_tail}}}{+ \alert<3>{\NT{factor\_tail}}} & + & 0 & + & \only<3>{\cellcolor{badbee!50}} \\
\first%
\grammarrule{\NT{factor\_tail}}{\EPSILON} & ), $\dashv$ & 1 & $\emptyset$ & \multirow{-2}{*}{), $\dashv$} \\\midrule
\grammarrule{\NT{factor}}{Int} & Int & 0 & Int & \\
\grammarrule{\NT{factor}}{\alert<2>{trans(}\alert<3>{\NT{term})}} & Ident, ( & 0 & Ident, ( & \multirow{-2}{*}{+, ), $\dashv$} \\\midrule
\grammarrule{\NT{trans}}{Ident} & Ident & 0 & Ident & \only<2>{\cellcolor{badbee!50}} \\
\second%
\grammarrule{\NT{trans}}{\EPSILON} & ( & 1 & $\emptyset$ & \multirow{-2}{*}{(} \\
\bottomrule
\end{tabular}
\end{center}
}
\ii<4>[$\Rightarrow$] \alert{ In der Übung: konkreter Algorithmus für \EPS, \FIRST, \FOLLOW}
\ei
\end{frame}Nun wollen wir uns der Berechnung der PREDICT-Mengen für die Regeln einer gegebene Grammatik zuwenden. Informell ausgedrückt stellen wir uns dabei die Frage: “Welche Regelanwendung einer Regel führt dazu, dass wir im Tokenstrom das Zeichen sehen, was wir sehen?”
Falls eine rechte Seite nur ein einziges Terminal enthält, oder mit einem Terminal startet, ist die Sache ganz klar:
Die PREDICT-Menge dieser Regel hat nur ein Element, nämlich dieses erste Terminal der rechten Seite.
Dies war zum Beispiel bei unserem intAdd~/~intAddTail-Beispiel ganz absichtlich der Fall[fn::Tatsächlich hat die Grammatikklasse, bei der alle Produktionen mit einem Terminal starten, einen eigenen Namen: Simple LL(1) oder SLL(1).].
Steht an erster Stelle der rechten Seite ein Nicht-Terminal, wird die Sache komplizierter und wir müssen zwei Hilfsmengen (FIRST und FOLLOW) und ein Hilfsprädikat (EPS) einführen, um die PREDICT-Menge zu berechnen. Das Prädikat EPS wird genau dann wahr, wenn das übergebene (teilweise abgeleitete) Wort durch beliebig viele Ableitungen zum leeren Wort werden kann. Wir werden mittels EPS prüfen, ob eine rechte Seite bzw. ein Präfix einer rechten Seite durch Ableitung “verschwinden” kann.
Die FIRST-Menge gibt an, mit welchen Zeichen die Ableitung eines (partiell abgeleiteten) Wortes anfangen kann.
Dies sieht nur auf den ersten Blick genau so aus wie die Definition der PREDICT-Menge.
Allerdings bezieht sich die FIRST-Menge nur auf ein Wort a (wie es auf der rechten Seite auftritt), die PREDICT-Menge auf eine Regel A->a.
Der Unterschied wird sichtbar, wenn das Wort a, als Ganzes, zum leeren Wort abgeleitet werden kann und quasi verschwindet:
Die PREDICT-Menge muss dann noch weitere Zeichen enthalten, die nicht in der FIRST-Menge enthalten sind, da die Regel dennoch zur Anwendung selektiert werden muss, auch wenn ihre Produktion verschwindet.
Nur so erhalten wir einen vollständigen und korrekten Ableitungsbaum.
Im Beispiel, müssen wir für trans die Epsilon-Produktion auswählen, wenn wir ( im Tokenstrom sehen.
Um diesen Schritt von FIRST(a) auf PREDICT(A->a) zu machen, müssen wir die Grammatik als Ganzes analysieren und nicht nur die Ableitungen, die aus der rechten Seite einer Regel folgen.
Hierzu führen wir die FOLLOW-Menge ein, die für jedes Nicht-Terminal A berechnet werden kann.
Neben der formalen Definition (siehe Folie), kann man FOLLOW auch informell beschreiben:
Welche Terminale können direkt **nach** einer vollständigen Ableitung von A in einem Wort folgen?
So kann, im Beispiel, dem Nicht-Terminal trans in jeder beliebigen Ableitung nur das Token ( folgen, da trans auf der rechten Seite nur in factor und vor einem ( vorkommt.
Etwas schwieriger ist factor_tail.
Man könnte zwar meinen, dass + Teil der FOLLOW-Menge ist, da mittels dieser Regel die ganzen + erzeugt werden.
Allerdings gibt es keine Satzform (partielle Ableitung), bei der bereits ein + rechts von factor_tail steht.
Wenn man sich ansieht, was in rechten Seiten rechts von factor_tail steht, kommt man dazu, dass factor_tail am Ende von seiner eigenen Regel und am Ende der term Regel steht.
In beiden Fällen können wir, weil das Wort dort endet, nichts darüber lernen, was rechts von factor_tail stehen könnte.
Daher müssen wir, bei term schauen was rechts davon stehen kann.
Dies bringt uns dann zu der Erkenntnis, dass die FOLLOW-Menge von factor_tail und term gleich ist.
Die Berechnung der FOLLOW-Mengen funktioniert also so, dass anhand der Nichtterminale die Regeln rückwärts gehen und dort immer schauen, was rechts vom aktuellen Nicht-Terminal vorkommen könnte. Erreichen wir das Ende einer rechten Seite, springen wir eine Stufe weiter zurück. Wir führen also eine Tiefensuche in den Regeln der Grammatik durch. Eine detailliertere Diskussion des Algorithmus zur Berechnung der FOLLOW-Menge (sowie FIRST und EPS) werden wir in den Übungen durchführen.
Mittels EPS, FIRST und FOLLOW können wir nun die PREDICT-Menge einer Regel A->a berechnen.
Wenn die rechte Seite nicht verschwinden kann (EPS(a) ist False), so müssen wir nur damit rechnen, die Zeichen aus FIRST(a) zu sehen, wenn wir die Regel anwenden sollen.
Verschwindet die rechte Seite (EPS(a) == True), so müssen wir zusätzlich die Zeichen aus FOLLOW(A) erwarten.
Wir verschmelzen also die FOLLOW-Menge des Nicht-Terminals mit der FIRST-Menge der Regel.
Aus dem letzten Satz können wir auch direkt lernen, dass bei LL(1)-Grammatiken immer nur eine Regel von allen A-Produktionen verschwinden darf. Sonst würden wir FOLLOW(A) zu zwei PREDICT-Mengen hinzuschlagen und die Mengen wären daher nicht mehr schnittfrei. Dies ergibt auch intuitiv Sinn: Wenn wir bei A stehen und zwei Regeln zur Auswahl haben, die dieses A verschwinden lassen, woher sollen wir wissen, welche wir auswählen sollen? Die Grammatik wäre nicht mehr deterministisch.
\begin{frame}<handout:2>{LL(1)-Probleme: Gemeinsame Präfixe}
\bi
\ii \textbf{Erinnerung:} Nur, wenn alle \PREDICT-Mengen mit der gleichen linken Seite (=A-Produktionen) schnittfrei sind, ist die Grammatik LL(1).\medskip
\ii Oft haben zwei A-Produktionen das gleiche Präfix und ein Look-Ahead von einem Token würde nicht reichen. \\{\smallskip
\btSetNamedTab[1cm]{\first}%
\btSetNamedTab[6.5cm]{\second}%
\first \grammarrule{\NT{stmt}}{\alert<1>{Ident} := \NT{expr}} \second \PREDICT=\{Ident\}\\
\first \grammarrule{\NT{stmt}}{\alert<1>{Ident} ( \NT{argument\_list} )} \second\PREDICT=\{Ident\}
}
\ii Mittels \emph{Linksfaktorisierung} kann man das Problem umgehen.\\{
\first \grammarrule{\NT{stmt}}{Ident \NT{stmt\_tail}}\\
\first \grammarrule{\NT{stmt\_tail}}{:= \NT{expr} } \second\PREDICT=\{:=\}\\
\first \grammarrule{\NT{stmt\_tail}}{( \NT{argument\_list} )} \second\PREDICT=\{(\}
}\medskip
\ii<2-> Linksfaktorisierte Grammatik ist \alert{nicht} äquivalent! (Syntaxbäume){\medskip
\begin{columns}
\begin{column}{0.49\textwidth}
\begin{tikzpicture}[small tree]
\node {\emph{stmt}}
child { node {Ident} }
child { node {:=} }
child { node {\emph{expr}}}
;
\end{tikzpicture}\
\end{column}
\begin{column}{0.49\textwidth}
\begin{tikzpicture}[small tree,level distance=8mm]
\node {\emph{stmt}}
child { node {Ident} }
child { node {\emph{stmt\_tail}}
child { node {:=} }
child { node {\emph{expr}}}}
;
\end{tikzpicture}
\end{column}
\end{columns}
}
\ei
\end{frame}
\begin{frame}[t,fragile]{LL(1)-Probleme: Linksrekursion}
\vspace{-1em}
\bi
\ii LL(1) verbietet, dass eine Regel auf der linken Seite rekursiv ist.\\{
\btSetNamedTab[1cm]{\first}%
\btSetNamedTab[6.5cm]{\second}%
\first\grammarrule{\NT{intAdd}}{Int}\second\PREDICT=\{Int\}\\
\first\grammarrule{\NT{intAdd}}{\NT{intAdd} + Int}\second\PREDICT=\{Int\}
}\medskip
\ii \textbf{Informell}: Der Parser mit rekursivem Abstieg weiß nicht, welche Regel er anwenden soll, wenn er einen Int sieht bzw. kommt in eine endlose Rekursion, wenn er die zweite Regel auswählt.{%
\begin{code}[]
\begin{py}[]
def addInt(token_stream):
if token_stream.peek() == TOK_INT:
addInt(token_stream)
...
\end{py}
\end{code}%
}
\ii<2-> \textbf{Definition}(Linksrekursiv): Mind. eine Regel hat folgende Ableitung. {
\[ A \Longrightarrow^* A \alpha \]
}
\ii<3-> \enquote{Reparatur} nur \alert{manchmal} möglich.\hfill{\scriptsize (LL(1)$\ll$LR(1))}\\{
\first\grammarrule{\NT{intAdd}}{Int + intAdd}\\
\first\grammarrule{\NT{intAddTail}}{Int} \\[3pt]
$\Rightarrow$ Umformung zur Rechtsrekursion + Linksfaktorisierung\\
}
\ei
\end{frame}
\begin{frame}[fragile]{LL(1)-Probleme: \enquote{Hässliche} Syntaxbäume}
\bi
\ii Faktorisierung und tail-Umformung zerstören Lokalität des Syntaxbaums.\\{
\begin{columns}
\begin{column}{0.49\textwidth}
\begin{center}
Mit Linksrekursion:\\[2ex]
\begin{tikzpicture}[small tree,level distance=8mm]
\node {\emph{intAdd}}
child { node {\emph{intAdd}} child { node {1} }}
child { node {+} }
child { node {2}}
;
\end{tikzpicture}
\end{center}
\vfill
\end{column}
\begin{column}{0.49\textwidth}
\begin{center}
Ohne Linksrekursion:\\[2ex]
\begin{tikzpicture}[small tree,level distance=8mm]
\node {\emph{intAdd}}
child { node {1} }
child { node {\emph{intAddTail}}
child { node {+} }
child { node {2}}}
;
\end{tikzpicture}
\end{center}
\end{column}
\end{columns}
\medskip
Mit Linksrekursion reicht oft Propagation alleinstehender Blätter.
}
\ii Parsergeneratoren können diese Probleme verstecken. ($\Rightarrow$ \texttt{antlr})
\bigskip
\ii<2> \textbf{Alternativ}: Verwendung der mächtigeren Sprachklasse LR(1). {
\bi
\ii LR(1) erlaubt gemeinsame Präfixe und Linksrekursion.
\ii Konstruktion von LR(1) Parsern ist komplexer ($\Rightarrow$ Parsergenerator)
\ii Parser sind Tabellen-gestützte Automaten mit explizitem Stapelspeicher.
\ei
}
\ei
\end{frame}
\begin{frame}{Einordnung von kontextfreien Grammatiken}
\vspace{-1em}
\begin{center}
\animation[width=\textwidth]{1/1,2/2}{fig/02-complexities}
\end{center}
\bi
\ii Theorie von kontextfreien Grammatiken und Parsern ist gut erforscht.
\ii<2> Moderne Generatoren akzeptieren beinahe jede ktfr. detr. Grammatik und liefern gute Fehlermeldungen. \textbf{Nutzen Sie diese!}
\ei
\end{frame}
Mit der Berechnung von PREDICT haben wir alles, was wir für unseren, vorher vorgestellten, Parsergenerator brauchen. Ist die Welt nun also eine bessere und wir können alles, was wir von einer Programmiersprachensyntax verlangen, in LL(1) ausdrücken?[fn::Rhetorische Frage.] Leider nicht, denn LL(1)-Grammatiken haben einige Probleme, die wir im Weiteren diskutieren wollen. Dennoch war die Beschäftigung mit LL(1) äußerst lohnend, weil wir gesehen haben, wie man an die Analyse einer Grammatik herangehen kann, wie ein Parsergenerator im Prinzip arbeitet und wie der fertige Parser schlussendlich arbeitet.
Das erste Problem sind gemeinsame Präfixe.
Wenn zwei A-Produktionen mit dem gleichen Terminal starten, so haben sie ein solches gemeinsames Präfix.
Wir könnten daher nicht mehr deterministisch entscheiden, welche der beiden Regeln wir auswählen sollen.
Im Beispiel wüssten wir mit einem Token Look-Ahead (Ident) nicht, ob wir die obere oder die untere Regel wählen sollten.
Wir könnten das Problem zwar lösen, indem wir uns ein weiteres Token Look-Ahead gönnen würden (Ident := vs. Ident (), aber dann würden wir LL(1)-Land verlassen und in LL(2) landen.
Die andere Variante ist das Umformen der Regeln mittels Linksfaktorisierung.
Dabei spalten wir die zweideutigen A-Produktionen auf, indem wir ein weiteres _tail Nicht-Terminal einführen.
Das originale Nicht-Terminal (stmt) hat nur noch eine Regel, die das gemeinsame Präfix konsumiert und mit dem _tail Symbol endet.
In den _tail-Regeln wird dann anhand der nun unterschiedlichen Präfixe entschieden, welche Regel zutrifft.
Allerdings gibt es mit der Linksfaktorisierung auch ein Problem: Die umgeformte Grammatik ist nicht äquivalent zur originalen Grammatik, die die Regel mit dem gemeinsamen Präfix enthält[fn::Man kann an diesem Beispiel auch sehen, dass Sprachklassen und Grammatikklassen etwas unterschiedliches sind. Die gezeigte Sprache ist LL(1), aber die Grammatik, die wir verwendet hatten, war in LL(2). Durch die Umformung haben wir es geschafft, eine Grammatik zu erzeugen, die näher an der eigentlichen Klasse der Sprache ist.]. Sie erzeugt zwar die gleiche formale Sprache, liefert aber andere Ableitungsbäume; etwas womit wir im Übersetzerbau umgehen müssen.
Das zweite Problem von LL(1)-Grammatiken ist, dass sie keine **Linksrekursion**[fn::Linksfaktorisierung != Linksrekursion] erlauben. Linksrekursion bedeutet, dass man durch Ableitung des Nicht-Terminals A zu einer Satzform kommt, die wieder mit A beginnt. Da LL(1)-Parser linksreduzierend sind, würde das bedeuten, dass wir immer wieder versuchen A zu reduzieren, ohne ein einziges Terminal zu konsumieren; rekursiv; für immer. Der Parser würde sich also in einer Endlosrekursion fangen.
Dass eine solche linksrekursive Grammatik nicht LL(1) sein kann, sehen wir auch an den PREDICT-Mengen.
Im Beispiel der linksrekursiven Variante von intAdd sind die PREDICT-Mengen für die beiden Regeln von int nicht schnittfrei, womit der LL(1)-Test fehlschlägt.
Allerdings sehen wir auch, dass die linksrekursive Variante deutlich intuitiver aufzuschreiben ist als die bisher diskutierte nicht-linksrekursive Variante, die zwei Nichtterminale braucht, um die gleiche Sprache abzubilden.
Wiederum können wir (manchmal) die Grammatik heilen, indem wir ein zusätzliches Nicht-Terminal einführen. Dazu machen wir zuerst aus der Linksrekursion eine Rechtsrekursion. In der rechtsrekursiven Grammatik wächst das Wort nicht mehr an der linken Seite sondern an der rechten Seite. Daher können wir beim Parsen Zeichen an der linken Seite konsumieren, bevor wir wieder zum rekursiven Nicht-Terminal kommen. Wir machen also Fortschritt (progress) und laufen nicht mehr unendlich lange. In der rechtsrekursiven Grammatik haben wir ein gemeinsames Präfix erzeugt, das wir, wie gehabt, mit Linksfaktorisierung entfernen können.
Das dritte Problem von LL(1)-Grammatiken ist, dass sie viele Nichtterminale enthalten und daher auch große Ableitungsbäume erzeugen. Noch schlimmer wird es dadurch, dass wir mit der Linksfaktorisierung Konstrukte zerreißen: Semantisch zusammengehörenden Token werden nun in unterschiedlichen Unterbäumen abgespeichert. Bei der gezeigten Addition sind die Operanden keine direkten Geschwister mehr.
Heutzutage haben wir mit den modernen Parsergeneratoren sehr gute Werkzeuge, um Parser aus formalen Grammatiken zu erzeugen, die sowohl effizient sind, als auch “schöne” Ableitungsbäume erzeugen und sich auf 50 Jahre Forschung im Bereich der Syntaxanalyse stützen.
Diese Generatoren führen, neben der reinen Analyse und Generierung, noch diverse Grammatikumformungen durch.
Ebenfalls werden entsprechende Baumtransformationen auf den Ableitungsbäumen durchgeführt, sodass es gar nicht zu diesen “hässlichen” Bäumen kommt.
So ist der antlr Parsergenerator in der Version 4 in der Lage, folgende Grammatik, inklusive der Operatorpräzedenz, richtig zu einem Parser mit rekursivem Abstieg umzuformen:
E -> E + E E -> E * E
In der Übung werden wir uns genauer mit LL(1)-Parsergeneratoren und der Extraktion der EPS-, FIRST- und FOLLOW-Mengen beschäftigen. Diese intensive Beschäftigung hat den Zweck, Sie mehr in die Denke formal notierter Grammatiken einzuführen. Später, in der Praxis, sollten Sie allerdings vermeiden ihre Parser, oder gar Parsergeneratoren, selbst zu schreiben. Mehr dazu im Exkurs über Parsing und Sicherheit.
Das andere Thema, welches wir in der Vorlesung ganz ausgelassen haben, obwohl es für viele zum Kanon der Syntaxanalyse gehört, sind die LR(1)-Grammatiken. Diese Klasse von Grammatiken hat weder das Problem der gemeinsamen Präfixe noch Schwierigkeiten mit Linksrekursion. Allerdings ist die Analyse und die Konstruktion dieser Parser deutlich aufwendiger zu verstehen als bei LL(1)-Parsern.
In a nutshell ist der Unterschied zwischen LL(k) und LR(k) in etwa folgender: Bei einem LL-Parser muss immer anhand des Look-Aheads direkt entschieden werden, welche Regel nun im Folgenden angewendet werden muss. Dies bringt eben genau die Probleme, die wir bei einem gemeinsamen Präfix haben, mit sich: Dort können wir diese eindeutige Entscheidung nicht sofort treffen. LR(k)-Parser haben die Möglichkeit, beliebige Zeit in einem Zustand des “sich noch nicht entschieden habens” (tristate) zu bleiben. Sie führen dazu (virtuell) eine Menge von möglichen Regeln mit sich, die mit jedem weiteren Token weiter eingeschränkt wird. Erst wenn diese Menge nur noch eine Regel enthält, wird sie angewendet. Wenn Sie weiteres Interesse an LR(k)-Parsern haben, sei Ihnen, neben der Lektüre des Drachenbuches, der Artikel LR(k)-Analyse für Pragmatiker von Andreas Kunert ans Herz gelegt.
\begin{frame}<handout:2>[t,fragile]{Ableitungsbäume}
\bi
\ii \textbf{Bisher:} Wir haben angenommen, dass der Parser "magisch" einen benutzbaren Syntaxbaum erzeugt. Aber nach welchen Regeln?\medskip
\ii \textbf{Ableitungsbaum}: Jede Anwendung einer Regel wird zu einem Knoten. Die Blätter überdecken alle Token.\\\medskip
\begin{columns}[T ]
\begin{column}{0.49\textwidth}
\includegraphics[width=\linewidth,page=4]{fig/02-grammar}
\end{column}\hfill
\begin{column}{0.4\textwidth}
\includegraphics[width=\linewidth,page=5]{fig/02-grammar}
\end{column}
\end{columns}
\ii<2-> Ein erzeugter Parser kann den Ableitungsbaum recht einfach liefern.\\
\begin{code}
\begin{py}
def varDef(token_stream):
if token_stream.peek() == TOK_VAR:
# varDef -> var Ident = expr
...
expr_tree = expr(token_stream)
# Ableitungsbaum als Python-Tupel
return ("varDef", t_var, t_id, t_eq, expr_tree)
\end{py}
\end{code}
\ei
\end{frame}
\begin{frame}<handout:2>{Abstrakte Syntaxbaum}
\bi
\ii Oft ist der Ableitungsbaum zu detailliert. {
\bi
\ii Viele Token sind nur für den Parser (Klammerung).
\ii Regelumformungen, um die Grammatik parsebar zu machen (Faktorisierung)
\ii Präzedenz von Operatoren wird über hierarchische Regeln ausgedrückt.
\ei
}
\ei
\medskip
\begin{center}
\animation[width=\linewidth]{6/1,7/2}{fig/02-grammar}
\end{center}
\bi
\ii<2-> Der \textbf{Abstrakte Syntaxbaum} ist kondensiert auf das \alert{Wesentliche}.{
\bi
\ii \enquote{Wesentlich} ist abhängig von den folgenden Übersetzerschritten.
\ii Zusammenfalten Unterbäumen und Erzeugung semantischer Knoten (add).
\ei
}
\ei
\end{frame}Bisher haben wir nur davon gesprochen, dass unsere Parser Ableitungsbäume erzeugen bzw. aus dem gegebenen Programmtext rekonstruieren. Diese Ableitungsbäume haben alle Token, die der Scanner erkennt, als Blätter. Über diesen Blättern wird, für jede angewendete Grammatikregel, ein innerer Knoten erzeugt: Alle Elemente der rechten Regelseite werden als Kindsknoten unter einen, mit dem Nicht-Terminal markiertem, inneren Knoten gehängt. Der Wurzelknoten des Ableitungsbaums ist immer das nichtterminale Startsymbol der Grammatik.
Während des Parsens unterscheidet man noch, ob man den Baum von den Blättern zur Wurzel (bottom-up) oder von der Wurzel zu den Blättern (top-down) hin wachsen lässt. LL(1)-Parser sind Top-Down-Parser. LR(1)-Parser sind Bottom-Up-Parser.
Allerdings sind diese Ableitungsbäume eher unpraktisch zu handhaben: Zum einen enthalten sie wirklich **alle** Token des Tokenstroms. Also auch jene Zeichen, die wir nur benutzt haben, um dem Parser zu vermitteln, was wir eigentlich wollen. Das Paradebeispiel hierfür ist explizite Klammerung. In einer perfekten Welt wüsste der Parser, wie wir einen arithmetischen Ausdruck interpretiert haben wollen; in der Realität müssen wir Klammern verwenden, wenn wir mit der impliziten Klammerung von Punkt-vor-Strich nicht zufrieden sind.
Aber es gibt in Ableitungsbäumen auch zu viele innere Knoten: Durch Regelumformungen und durch Einführung von zusätzlichen Nichtterminalen zur korrekten Erkennung der Operatorpräzedenz, kommen viele viele innere Knoten hinzu, die keinen Wert mehr im weiteren Verlauf des Übersetzungsvorgangs haben.
Daher gibt es das Konzept des Abstrakten Syntaxbaums (AST). Der AST ist ein vom Ableitungsbaum abgeleiteter Baum, der die essentielle Struktur des Programms erfasst und, wie es der Scanner auch schon gemacht hat, nur noch die wesentliche Information an die späteren Übersetzerstufen liefert. Was genau wesentlich bedeutet, hängt stark von der Sprache ab.
Um den AST zu generieren, haben wir prinzipiell zwei Möglichkeiten: Entweder falten wird den vollständig aufgebauten Ableitungsbaum mittels Baumtransformationen im Nachhinein wieder zusammen und kompaktifizieren ihn dabei, oder wir lassen den Parser den AST direkt erzeugen. Für letzteres müssen wir dem Parsergenerator mitteilen, wie diese AST-Konstruktion von statten gehen soll. Wir brauchen also zusätzliche Informationen in der Grammatik, die nicht die erkannte formale Sprache verändert, aber dem Generator zusätzliche Informationen liefert. Den Weg, den die meisten Generatoren hier gehen ist eine **Reduktionsaktion** anzugeben:
varDef -> var Ident = expr { return ("varDef", $2, $3) }
Die Aktion (in geschweiften Klammern), wird als Rückgabewert der Parsefunktionen eingesetzt, nachdem die Pattern ($1,$2,…) durch die Elemente der rechten Seite ersetzt wurden. Im Folienbeispiel würde die Funktion für varDef dann so ausehen:
def varDef(token_stream):
if token_stream.peek() == TOK_VAR:
# ...
return ("varDef", t_id, expr_tree)Noch mehr Details zu diesen Reduktionsaktionen gibt es in den Übungen.
\begin{frame}<handout:2,3,4>{Parsingprobleme mit realen Sprachen}
\bi
\ii Sprachen mit optionalem \texttt{else} können das \emph{dangling-else problem} haben.\\\medskip {
\btSetNamedTab[1cm]{\first}%
\first\grammarrule{\NT{stmt}}{\K{if} \NT{condition} \NT{then\_clause} \NT{else\_clause} \OR \K{\{} \NT{stmt\_list} \K{\}} \OR\ldots}\\
\first\grammarrule{\NT{then\_stmt}}{\K{then} \NT{stmt}}\\
\first\grammarrule{\NT{else\_stmt}}{\K{else} \NT{stmt} \OR \EPSILON}
\bi
\ii Grammatik ist \alert<1>{nicht} eindeutig! Wohin gehört bei \texttt{if-if-else} das \texttt{else}?\\
Die Sprache muss definieren, welche Variante gewählt wird.\\\medskip
\begin{center}
\only<1|handout:1>{\texttt{\tikznode[draw=white]{if A then \tikznode[draw=white]{if B then doAB();} else doX();} }}
\only<2|handout:2>{\texttt{\tikznode[draw,fill=badbee!50]{if A then \tikznode[draw,fill=safegreen!50]{if B then doAB(); else doX();}} }}
\only<3-|handout:3->{\texttt{\tikznode[draw,fill=badbee!50]{if A then \tikznode[draw,fill=safegreen!50]{if B then doAB();} else doX();} }}
\end{center}
\ei
}
\medskip
\ii<handout:4|4-> Oft reicht ein Token Look-Ahead nicht aus, um Konstrukte zu erkennen.{%
\bi
\ii Java: Felder und Methoden erlauben unterschiedliche Modifer: \\\medskip{
\btSetNamedTab[5mm]{\first}%
\btSetNamedTab[6.5cm]{\second}%
\first\texttt{\colorbox{badbee!50}{\strut public}\colorbox{srared!50}{\strut abstract} int foo = 0;} \second
Syntaxfehler lässt sich nicht\\[1ex]
\first\texttt{\colorbox{badbee!50}{\strut public}\colorbox{srared!50}{\strut abstract} int foo() \{\ldots\} } \second am \enquote{\texttt{abstract}} erkennen.
}\medskip
\ii Wir lassen beliebige Modifier zu, akzeptieren invalide Programme, und verschieben das Problem auf die semantische Analyse.
\ei
}
\ei
\end{frame}
\begin{frame}[fragile]{Parsingprobleme mit realen Sprachen: \texttt{typedef}}
\bi
\ii Die Definition von eigenen Typnamen führt zu kontextsensitivität.{\\\smallskip
\btSetNamedTab[5mm]{\first}%
\btSetNamedTab[6.5cm]{\second}%
\first\grammarrule{\NT{typedef\_decl}}{\K{typedef} \NT{type} Ident} \second$\Rightarrow$ Ident wird ein Typname\\[1ex]
\first\grammarrule{\NT{cast\_expr}}{(\NT{type\_name}) expr} \second $\Rightarrow$ Referenz von Typnamen
}\medskip
\ii Ohne Kontext können wir Aufrufe und Casts nicht unterscheiden.{\\\smallskip
\begin{columns}
\begin{column}{0.49\textwidth}
\begin{code}
\begin{C}
int bar;
int foo(int a) {};
...
// Funktionsname in Klammern
(foo)(bar); // = foo(bar)
\end{C}
\end{code}
\end{column}
\begin{column}{0.49\textwidth}
\begin{code}
\begin{C}
int bar;
typedef char foo;
...
// Typname in Klammern
(foo)(bar); // = (char)(bar)
\end{C}
\end{code}
\end{column}
\end{columns}
}\medskip
\ii<2-> \enquote{Lösung}: Der Lexer Hack vermeidet kontextsensitives Parsing.{
\bi
\ii Der Scanner führt eine Liste von bereits definierten Typnamen mit.
\ii Er emittiert unterschiedliche Token für Typname und Bezeichner.
\ii Nun ist allerdings der Scanner kontextsensitiv!
\ei
}
\medskip
\ii<3>[$\Rightarrow$]{Echte Programmiersprachen sind nur auf den ersten Blick kontextfrei!}
\ei
\end{frame}{{{wikipedia_en(The_lexer_hack)}}}
Nachdem wir sehr detailiert über Parser geredet haben, wollen wir nun wieder herauszoomen und uns auf unser eigentliches Ziel konzentrieren: Die Extraktion der Programmstruktur für eine real existierende Programmiersprache. Mit welchem Parsingalgorithmus das passiert, ist uns im Grunde egal, hauptsache es ist schnell, korrekt und eindeutig. Dabei gibt es allerdings einige Probleme, die entweder bereits in der Sprache angelegt sind oder die wir machen können, wenn wir die formale Grammatik aufschreiben.
Einen klassischen Fehler, den man beim Erstellen einer Grammatik machen kann, ist das dangling-else Problem.
Dabei wird bei einem doppelt geschachtelten if-else nicht klar, ob der else-Zweig zum inneren oder zum äußeren if gehört.
Dieses Problem kann nur auftreten, wenn die Sprache es erlaubt, die Klammerung von Codeblöcken wegzulassen, falls man nur ein einzelnes Statement hat.
Bei der angegeben Grammatik entsteht so das Problem, dass sie nicht eindeutig ist (also auch nicht LL(1)).
Konstruiert man dennoch einen Parser, so würde ein linksreduzierender Parser die eine und ein rechtsreduzierender Parser die andere Variante finden. Daher muss eine Sprache, die die Auslassung der Codeblockklammerung erlaubt, genau definieren, wie dieser Fall behandelt wird.
Historisch gesehen wurde ein dangling-else Problem zum ersten Mal bei ALGOL-60 erkannt.
Ein anderes grundsätzliches Problem der Syntaxanalyse ist, dass wir manchmal nicht alle Notationsregeln der Sprache mit nur einem Zeichen Look-Ahead prüfen können.
Beim Beispiel auf den Folien kommt das Problem zutage, dass bei Java manche Modifikatoren innerhalb einer Klassendefinition sowohl für Member als auch für Methoden (public) erlaubt sind, während dies bei anderen nicht der Fall ist (abstract macht keinen Sinn für eine Membervariable).
Da allerdings erst nach dem Bezeichner klar wird, ob ein Member oder eine Methode vorliegt, kann ein LL(1)-Parser nicht entscheiden, ob der Modifikator an dieser Stelle erlaubt ist oder nicht.
Die Lösung hierfür ist das teilweise Aufschieben der Entscheidung über die syntaktische Korrektheit in die semantische Analyse.
Der Parser erlaubt also beide gezeigten Programme, erzeugt einen AST, und eine spätere Prüfung schlägt der Memberdefinition Alarm.
Das dritte und schwerwiegendste Problem von Parsing ist, dass wir bisher die Unwahrheit über die kontextfreie Syntax von Programmiersprachen gesagt haben[fn::Stackoverflow: Which contemporary computer languages are LL(1)?]. Viele Sprachen sind nämlich nicht wirklich kontextfrei. Dies bedeutet, dass ein Unterbaum des Ableitungsbaums nicht nur von den überdeckten Token abhängt, sondern auch von der semantischen Interpretation anderer Programmteile. Oder anders gesagt: Das Parsen der meisten Sprachen ist nicht lokal machbar.
Das klassische Beispiel hierfür ist typedef aus der Programmiersprache C.
Hiermit zeigt der Programmierer an, dass ab der Stelle des typedefs ein Bezeichner nicht mehr als Variablenname, sondern als Alias für einen anderen Typen interpretiert werden soll.
So führt der Ausdruck typedef char foo dazu, dass foo der Name eines Datentyps ist, der genau ein Byte groß ist und an jeder Stelle verwendet werden kann, an der auch char verwendet werden darf.
Da aber einige Grammatikregeln anhand des Wissens, ob wir gerade auf den Namen einer Variable oder den Namen eines Typs schauen, eine Unterscheidung treffen, müssen wir an diesen Stellen wissen, welche Typnamen es gibt. Man kann dieses Problem entweder mit einer Menge Formalismus{{{wikipedia_en(Attribute_grammar)}}} erschlagen, oder man gibt die Kontextfreiheit zu einem gewissen Teil auf.
Beim Lexer Hack, lässt man Parser und Scanner miteinander reden. Der Scanner führt eine Liste mit gerade aktiven Typnamen mit und gibt unterschiedliche Token für Typnamen und für Bezeichner an den Parser. Der Parser seinerseits teilt dem Scanner beim Erkennen eines typedef mit, dass es einen neuen Typnamen gibt[fn::https://blogs.gnome.org/otte/2019/10/17/riddle-me-this/]. Dies kann in der Reduktionsregel der Grammatik erfolgen:
typedef_decl -> typedef type Ident { scanner.typenames.add($3); return ('typedef', $3, $2); }
\dividerframe{Parsing\\und\\Sicherheit}
\begin{frame}[fragile]{Parser als Einfallstore für Angreifer}
\bi
\ii Nutzer, wie auch Angreifer, schicken Anfragen als Zeichenstrom. {
\bi
\ii Parser extrahieren Typ, Argumente und strukturierte Daten.
\ii Komplexe Protokoll- und Dateiformate (ASN.1, PDF, JPEG)
\ii Die Eingaben müssen validiert und transformiert werden (XML: XSD, XSLT)
\ei
}\medskip
\ii Kleine (Programmier-)sprachen sind überall{
\bi
\ii Format Strings: \verb|printf("%3$*1$.*2$f", 10, 2, 1.11111);|
\ii Browser: HTML5, JavaScript, CSS, RDF, Embedded SVG, MathML, \ldots
\ei
}\medskip
\ii Handgeschriebene für komplexe Formate neigen zu Schwachstellen.{
\bi
\ii DNP3: Kommunikationsprotokoll im US Stromnetz ($> 100$ Seiten Standard)
\ii Untersuchung von 20 DNP3 Implementierung durch Fuzzing (2013-2014)
\ii 31 bekannte Schwachstellen in DNP3 Parsern
\ei
}\medskip
\ei
\pause
\hspace{-5mm}\Large\ALERT{(Benutzer-)Eingaben sind Lava! Parsergeneratoren!}
\end{frame}
\begin{frame}{Ungewollt Turing-Vollständig: Eingabevalidierung}
\bi
\ii Syntaktische (und semantische) Analysen validieren eine Eingabe.{
\bi
\ii Dazu wenden sie, teils komplexe, Regeln auf die Eingabedaten an.
\ii Was, wenn diese Regeln so komplex sind, dass eine virtuelle Maschine entsteht?
\ii Der Übersetzer selbst wird zum Sprachprozessor.
\ei
}\medskip
\ii \enquote{C++-Templates are Turing Complete}, Veldhuizen, 2003 {
\bi
\ii Erlauben ein flexible Definition von Datentypen; aber auch Berechnung von $\pi$.
\ii Maschinenmodell: Typen sind Objekte, Rekursive Templates die Operationen.
\ii Es gibt sogar Standardbibliotheken zur C++-Template-Programmierung.
\ei
}
\ei
\begin{code}
\lstinputlisting[style=CPP]{lst/02-factorial.cc}
\end{code}
\pause
\hspace{-5mm}\Large\ALERT{Maschinen die $\pi$ berechnen, führen auch Exploits aus.}
\end{frame}
Ein weiteres Problem, dass ganz eng mit Parsen verbunden ist, ist die Validierung von Benutzereingaben und die damit verbundenen Sicherheitsimplikationen. Jede Form von Informationsextraktion aus einer Zeichenkette ist Parsing. Daher sind Parser die ersten, die mit möglicherweise schadhaften und gefährlichen Eingaben konfrontiert sind. Hat der Parser eine Sicherheitslücke, so ist diese besonders einfach auszunutzen, da der Angreifer an keiner anderen Instanz vorbei muss.
Daher ist es nicht nur vom Programmieraufwand her korrekt gedacht einen Parsergenerator zu verwenden, sondern häufig auch vom Sicherheitsstandpunkt: Dabei hilft die genaue Spezifikation der erwartete Eingaben als formale Grammatik nicht nur einen Parser für das Austauschformat zu generieren, sondern auch das Format genau zu beschreiben. Mittels Grammatikanalysen kann man dann sogar nachweisen, dass die Grammatik deterministisch parsebar ist.
Das andere sicherheitsrelevante Thema beim Validieren von Zeichenketten ist, dass man sehr schnell an den Punkt kommt, dass die Validierung der Eingabe an sich schon eine virtuelle Maschine darstellt und vielleicht Turing-vollständig ist. Es geht also um Situationen, bei denen die Struktur eines Programms selbst ein Programm ist, dass vom Übersetzer während der Übersetzungszeit ausgeführt wird, während er versucht nachzuweisen, dass das Programm valide ist. Der Übersetzer wird also selbst zum Sprachprozessor für dieses Meta-Programm.
Das bekannteste Beispiel hierfür sind C++-Templates:
Mit C++-Templates kann der Programmierer Datentypen definieren, die parametrisch von anderen Datentypen abhängen.
Ein Beispiel für einen solchen Datentyp ist die doppelt verkettete Liste von Integern (std::deque<int>).
Jetzt muss der Übersetzer allerdings diese parametrischen Datentypen vollständig expandieren, um zu prüfen, ob alle Typen korrekt verwendet wurden.
Da aber auch Templatetypen Argumente für Templatetypen sein können, hat man alle Elemente zusammen, um ein Programm zu schreiben: Rekursion und Abbruchbedingungen.
Es wurde sogar nachgewiesen, dass C++-Templates wirklich Turing-vollständig sind, indem eine Turingmaschine mittels C++-Templates erstellt wurde.
Jetzt hat es sich im Falle von C++-Templates herausgestellt, dass eine solche Flexibilität in der Sprache viele Möglichkeiten bietet, elegante Programme zu schreiben. Allerdings möchten Sie nicht aus Versehen in die Falle tappen, dass jemand auf Ihrem Parser für Netzwerkpakete Bitcoins minen kann. Mit LANGSEC gibt es sogar eine Forschungsrichtung, die sich auf genau diese sprachlich formale Sicht der Sicherheit konzentriert. Ihre Forderung ist Context-Free or Regular!
\begin{frame}{Zusammenfassung}
\bi
\ii Die syntaktische Analyse extrahiert die Struktur eines Programms {
\bi
\ii Die rekursive Natur von Bäumen eignet sich Schachtelungen zu greifen.
\ii Syntaktische Korrektheit ist notwendig, jedoch nicht hinreichend.
\ei
}\medskip
\ii Scanner (Lexer) partitionieren den Zeichenstrom in einen Tokenstrom. {
\bi
\ii Token haben eine Klasse und eine Nutzlast: \texttt{(Int, 23)}
\ii Zerteilung mittels regulärer Ausdrücke und endlichen Zustandsautomaten
\ei
}\medskip
\ii Parser ordnen die Token, mittels Grammatikregeln, in einem Baum an. {
\bi
\ii Die Sprachklasse LL(1) kann mittels rekursivem Abstieg erkannt werden.
\ii Die PREDICT-Menge und der Look-Ahead entscheiden die nächste Regel.
\ii Im Parsebaum sind alle Token Blätter und alle Regeln Knoten.
\ei
}\medskip
\ii Strukturierte Sprachen sind allgegenwärtig und sicherheitsrelevant!{
\bi
\ii Jede Validierung von Eingabedaten erfordert strukturelles Verstehen.
\ii Formale Grammatiken und Parsergeneratoren helfen Lücken zu vermeiden.
\ei
}
\ei
\end{frame}
%\begin{frame}{Quellenverzeichnis}
% \printbibliography
%\end{frame}