02 - Syntaktische Analyse

Previous Next

Ein Übersetzer für (Maschinen-)ProgrammeSiehe 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 + 3

Um 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)Parsergeneratoren werden auch Compiler-Compiler genannt, da sie Übersetzer sind, die Code erzeugen, der in Übersetzern verwendet wird..

Previous Next

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ötigtFortran ist ein trauriges Gegenbeispiel: http://shape-of-code.coding-guidelines.com/2009/12/20/parsing-fortran-95/.

Im BeispielVollstä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()).

class Stream:
    """Eine (ineffiziente) Abstraktion fuer einen Eingabestrom aus Zeichen,
       die es erlaubt ein einzelnes Zeichen in die Zukunft zu blicken
       (look-ahead).
    """
    def __init__(self, data):
        self.data = list(data)

    def peek(self):
        if len(stream.data) == 0:
            return '\0'
        return stream.data[0]

    def read(self):
        if len(self.data) == 0:
            return '\0'
        return self.data.pop(0)

    def read_many(self, allowed_characters):
        ret = ""
        while self.peek() in allowed_characters:
            ret += self.read()
        return ret


#scanner0
def scanner_next(stream):
    # Leerzeichen vom Anfang wegwerfen
    while stream.peek() in " \t":
        stream.read()

    ch = stream.read()
    if ch == '0': # literal: hex, oktal, oder binär
        ch = stream.read()
        if ch == 'x':
            hexdigits = "0123456789abcdefABCDEF"
            chars = stream.read_many(hexdigits)
            value = int(chars, base=16)
            return ["literal", value]
        # ....
#scanner1
        elif ch == 'b':
            chars = stream.read_many('01')
            value = int(chars, base=2)
            return ['literal', value]
        elif ch in '01234567':
            chars  = ch + stream.read_many('01234567')
            value = int(chars, 8)
            return ['literal', value]
#scanner2
        else:
            raise ScannerError("invalid character")
#scanner3

stream = Stream("0x17 027 0b10111 0777")

while True:
    token = scanner_next(stream)
    if token is None:
        break
    print(repr(token))

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.

Previous Next

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) SpracheVerwechslungsgefahr: 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 eingeteiltWikipedia: 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 ErsetzungenIn 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 istRegulä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.

Previous Next

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 dannIn 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 nichtDies 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 kubischWikipedia: 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 rekonstruierenFormaler: 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.

Previous Next

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!