Parser sind Programme, die helfen, Text zu verarbeiten. Compiler und Interpreter verwenden Parser, um Programme zu analysieren, bevor sie weiter verarbeitet werden, und Parser für Formate wie JSON und YAML verarbeiten Text in die nativen Datenstrukturen der Programmiersprache.
In diesem Artikel werden wir uns ansehen, wie man „rekursive Abstiegs-Parser“ erstellt. Rekursiv absteigende Parser sind eine einfache, aber leistungsstarke Methode zum Erstellen von Parsern – für jede „Entität“ im Text, die Sie verarbeiten möchten, definieren Sie eine Funktion.
Zuerst werden wir uns einige der Theorien ansehen, die dem Parsen zugrunde liegen. Dann verwenden wir Python, wir werden einen Taschenrechner und einen JSON-Parser erstellen, der Kommentare, nachgestellte Kommas und Zeichenfolgen ohne Anführungszeichen unterstützt. Abschließend besprechen wir, wie Sie Parser für andere Arten von Sprachen erstellen können, die sich anders verhalten als die oben genannten Beispiele.
Wenn Sie bereits mit der Theorie vertraut sind, können Sie direkt zu den Teilen springen, in denen wir den Parser erstellen.
Inhalt
- 1 Wie funktioniert Parsing?
- 2 Produktionsregeln schreiben
- 3 Überlegungen beim Erstellen von Parsern
- 3.1 Umgang mit Vorrang in Grammatiken
- 3.2 Linke Rekursion vermeiden
- 3.3 Vermeidung von Backtracking
- 4 Aufbau einer Basis für den Recursive Descent Parser in Python
- 4.1 Die Ausnahmeklasse
- 4.2 Die Parser-Basisklasse
- 4.3 Zeichenbereiche verarbeiten
- 4.4 Zeichen aus dem Text extrahieren
- 4.5 Schlüsselwörter und Symbole extrahieren
- 4.6 Ein Helfer zum Abgleich mehrerer Produktionen
- 4.7 Ausblick auf die Zukunft – Hilfsfunktionen
- 5 Erstes Parser-Beispiel:ein Taschenrechner
- 5.1 Produktionsregeln für die Rechnergrammatik
- 5.2 Implementierung des Parsers
- 5.3 Zahlen erkennen
- 5.4 Eine Schnittstelle für unseren Parser
- 6 Zweites Parser-Beispiel:ein „erweiterter“ JSON-Parser
- 6.1 Produktionsregeln für die JSON-Grammatik
- 6.2 Den Parser implementieren und mit Kommentaren umgehen
- 6.3 Analysieren von Listen und Karten
- 6.4 Erkennen von null und booleschen Werten
- 6.5 Zeichenketten und Zahlen ohne Anführungszeichen erkennen
- 6.6 Strings in Anführungszeichen erkennen
- 6.7 Eine Schnittstelle für unseren JSON-Parser
- 7 Andere Arten von Parsern bauen
- 7.1 Whitespace-sensitive Sprachen
- 7.2 Whitespace-basierte Einrückung
Wie funktioniert Parsing?
Um einen Text zu verarbeiten, führt ein Programm drei Aufgaben aus. In einem Prozess, der „Lexing“ oder „Tokenisierung“ genannt wird, geht das Programm Zeichen im Text durch und extrahiert logische Gruppen, die „Token“ genannt werden. Beispielsweise könnte in einem Ausdruck wie „3 + 5 – 10“ ein Programm zur Verarbeitung arithmetischer Ausdrücke die folgenden Token extrahieren:
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Das Programm verwendet dann Regeln, um sinnvolle Sequenzen von Token zu identifizieren, und dies wird „Parsing“ genannt. Die dafür verwendeten Regeln werden „Grammatiken“ genannt – ähnlich wie Wörter einer natürlichen Sprache wie Englisch mithilfe der englischen Grammatik zu sinnvollen Sequenzen aneinandergereiht werden. Einzelne Regeln einer Grammatik werden als „Produktionen“ bezeichnet.
Stellen Sie sich vor, wir bauen ein Programm zur Verarbeitung mathematischer Ausdrücke und interessieren uns nur für Addition und Subtraktion. Ein Ausdruck muss eine Zahl (z. B. „3“) enthalten, gefolgt von einer beliebigen Anzahl von Operatoren und Zahlen (z. B. „+ 5“) . Die Parsing-Regel kann wie folgt visualisiert werden:
Das zeigt an, dass die Gruppe beliebig oft wiederholt werden kann (einschließlich null).
Schließlich führt das Programm eine Reihe von Aktionen für eine Grammatikregel durch. Zum Beispiel müsste unser mathematisches Programm nach dem Parsen den Wert des Ausdrucks berechnen.
Obwohl wir dies als separate Schritte beschrieben haben, kann ein Programm all dies gleichzeitig ausführen. Alle Schritte auf einmal zu machen bringt ein paar Vorteile mit sich, und das ist der Ansatz, den wir in diesem Artikel verfolgen werden.
Produktionsregeln schreiben
Im weiteren Verlauf dieses Artikels werden wir Produktionsregeln verwenden, um Grammatiken zu visualisieren. Daher haben wir in diesem Artikel erklärt, wie wir die Produktionsregeln schreiben. Wenn Sie zuvor ein Lehrbuch zum Thema Parsing gelesen haben, ist die Notation, die wir hier verwendet haben, etwas anders.
Weiter oben haben wir ein Beispiel für eine einfache Produktion gesehen. Wenn die Grammatikregel den Namen eines Tokens enthält und das Token ziemlich einfach ist, ist es üblich, den Text des Tokens in die Grammatik zu schreiben. Wenn wir das vorherige Beispiel betrachten, ergibt sich ein + oder eine - , also könnten wir die Regel folgendermaßen umschreiben:
Wir haben auch gesehen, wie wir angeben können, dass sich etwas beliebig oft wiederholt. In ähnlicher Weise zeigt a an, dass sich etwas wiederholt, aber mindestens einmal vorkommen sollte. A weist auf etwas hin, das optional ist.
Angenommen, wir bauen einen Parser, um eine Liste von Bedingungen zu verarbeiten, wie „x> 10 und y> 30“. Angenommen, der and ist optional, also könnten wir diese Bedingung umschreiben als „x> 10 y> 30“. Sie könnten eine Grammatik für das obige wie folgt entwerfen:
Bei mehreren Alternativen spielt die Reihenfolge der Alternativen eine Rolle. Für eine Regel wie sollten wir versuchen, zuerst ein „+“ und dann ein „-“ zu finden. Obwohl es in diesem trivialen Beispiel den Anschein haben mag, dass die Reihenfolge keine Rolle spielt, werden wir später Beispiele sehen, bei denen die Reihenfolge wichtig wird.
Schließlich konzentriert sich eine Produktionsregel nur auf Tokens und andere Grammatiksymbole – sie ignoriert Leerzeichen und Kommentare.
Überlegungen beim Erstellen von Parsern
Zuvor haben wir ein paar einfache Grammatiken gesehen. Wenn Sie jedoch versuchen, etwas Komplexeres zu analysieren, können eine Reihe von Problemen auftreten. Wir werden sie hier besprechen.
Umgang mit Vorrang in Grammatiken
Zuvor haben wir eine Grammatik gesehen, die einen mathematischen Ausdruck verarbeiten kann, der aus Additionen und Subtraktionen besteht. Leider können Sie dieselbe Grammatik nicht für Multiplikationen (und Divisionen) erweitern, da diese Operationen Vorrang vor Additionen (und Subtraktionen) haben.
Um mit diesem Szenario fertig zu werden, müssen wir unsere Grammatik so gestalten, dass der Parser alle Additionen aufschiebt, aber Multiplikationen ausführt, sobald sie angetroffen werden. Um dies zu erreichen, teilen wir die Grammatik in zwei separate Regeln auf, wie unten gezeigt:
Nehmen wir einen Ausdruck (z. B. „3 + 2 * 5“), um sicherzustellen, dass dies wirklich funktioniert. Wir gehen davon aus, dass unser Parser den Ausdruck automatisch berechnet, sobald er mit dem Abgleich einer Grammatikregel fertig ist. Wir verwenden auch unterstrichenen Text, um anzuzeigen, wonach der Parser sucht. Außerdem haben wir die Anführungszeichen der Übersichtlichkeit halber weggelassen.
Wenn 2 * 5 geparst wird, gibt der Parser sofort das Ergebnis 10 zurück. Dieses Ergebnis wird im Schritt empfangen, und die Addition wird am Ende ausgeführt, was 13 als Ergebnis ergibt.
Zusammenfassend sollten Sie Ihre Regeln so anordnen, dass die Operatoren mit der niedrigsten Priorität ganz oben stehen, während die mit der höchsten Priorität ganz unten stehen.
Linke Rekursion vermeiden
Wir haben bereits erwähnt, dass ein rekursiver Abstiegsparser aus Funktionen besteht, die „Entitäten“ im Text verarbeiten. Nachdem wir nun über Token und Produktionsregeln Bescheid wissen, wollen wir dies etwas formaler neu definieren:Jede Funktion im Parser extrahiert ein Token oder implementiert die Logik einer Produktionsregel.
Nehmen wir eine einfache Grammatik, um zu sehen, was das wirklich bedeutet. Wenn Sie den Pseudocode für diese Grammatik geschrieben haben, würde er etwa so aussehen:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
Betrachten Sie als Nächstes eine Grammatik, die eine Liste von durch Kommas getrennten Zahlen analysiert. Sie würden es im Allgemeinen wie folgt schreiben:
Stellen Sie sich nun vor, Sie wollten aus irgendeinem Grund den Platzhalter vermeiden und schreiben Sie ihn folgendermaßen um:
Diese Grammatik ist theoretisch korrekt – sie wählt entweder eine einzelne Zahl aus dem Text aus oder sie erweitert sich zu einer Liste mit einer Zahl am Ende. Die zweite Liste wiederum kann auf eine weitere Zahl oder eine Liste erweitert werden, bis der Parser den Text beendet hat.
Bei diesem Ansatz gibt es jedoch ein Problem – Sie würden eine unendliche Rekursion eingeben! Wenn Sie versuchen, list() anzurufen einmal funktionieren, rufen Sie sie am Ende erneut auf und so weiter. Sie könnten denken, dass es hilfreich sein könnte, die Grammatik umzuschreiben. Wenn Sie jedoch versuchten, eine Funktion zu schreiben, würden Sie eine einzelne Zahl lesen und das Parsen beenden. Die Zahl, die Sie lesen, ist möglicherweise Teil einer Liste wie „2, 4, 6“, und Sie können die anderen Zahlen nicht lesen.
Beim Parsen wird dies als linke Rekursion bezeichnet. Der Fall, den wir oben gesehen haben, beinhaltet eine „direkte Linksrekursion“, aber es gibt auch eine „indirekte Linksrekursion“, bei der A B anruft, B A anruft und so weiter. In jedem Fall sollten Sie die Grammatik anders schreiben, um dieses Problem zu vermeiden.
Rückverfolgung vermeiden
Angenommen, Sie versuchen, einen Parser zu erstellen, der eine Operation mit zwei Zahlen analysiert, z. B. „2 + 4“, und schreiben auf diese Weise eine Grammatik:
Diese Grammatik ist korrekt und wird sich auch so verhalten, wie Sie es erwarten, und korrekte Ergebnisse liefern. Diese Grammatik ist jedoch nicht das, was Sie verwenden möchten.
Um zu sehen, warum dies der Fall ist, betrachten Sie die Eingabezeichenfolge „5 – 2“. Wir gehen zuerst mit der Additionsregel vor und parsen eine Zahl. Dann würden wir ein „+“ erwarten, aber beim Lesen der Zeichenfolge erhalten wir ein „-“, was bedeutet, dass wir zurückgehen und die Subtraktionsregel anwenden müssen. Dabei haben wir Zeit und CPU-Zyklen mit dem Parsen einer Zahl verschwendet, nur um sie zu verwerfen und als Teil der Subtraktionsregel erneut zu parsen.
Darüber hinaus ist das Zurückspulen des Streams beim Erstellen von Parsern, die direkt mit Datenströmen arbeiten, wie z. B. ein Netzwerk-Socket, häufig keine Option. In diesem Artikel behandeln wir nur Parser, die den gesamten Text im Speicher haben. Nichtsdestotrotz ist es eine gute Praxis, Backtracking zu vermeiden, und um dies zu tun, sollten Sie die gemeinsamen Teile von links ausklammern. So würde unsere Regel nach dem Factoring aussehen:
Der Factoring-Schritt ist abgeschlossen und vermeidet Backtracking. Aus ästhetischen Gründen schreiben wir es jedoch einfach wie folgt:
Aufbau einer Basis für den Recursive Descent Parser in Python
Nachdem wir nun die verschiedenen Überlegungen zum Parsen besprochen haben, bauen wir den Taschenrechner und den JSON-Parser aus. Bevor wir das tun, schreiben wir jedoch eine grundlegende „Parser“-Klasse, die einige Methoden für allgemeine Funktionen hat, wie das Erkennen von Zeichen und das Behandeln von Fehlern.
Dieser Abschnitt mag etwas zu lang erscheinen, aber die Geduld lohnt sich. Sobald Sie diesen Abschnitt abgeschlossen haben, verfügen Sie über alle Tools, um komplexe Parser mit sehr wenig Code zu erstellen, der zum Erkennen von Token und Implementieren von Produktionsregeln erforderlich ist.
Die Ausnahmeklasse
Da dies bei weitem die einfachste Aufgabe ist, werden wir uns zuerst damit befassen. Wir definieren unsere eigene Ausnahmeklasse namens ParseError so:
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
Die Klasse akzeptiert die Textposition, an der der Fehler aufgetreten ist, eine Fehlermeldung (als Formatzeichenfolge) und die Argumente für die Formatzeichenfolge. Sehen wir uns an, wie Sie diesen Ausnahmetyp verwenden könnten:
e = ParseError(13, 'Expected "{" but found "%s"', "[") Wenn Sie versuchen, die Ausnahme zu drucken, erhalten Sie eine formatierte Nachricht wie diese:
Expected "{" but found "[" at position 13
Beachten Sie, dass wir keinen % verwendet haben Symbol innerhalb des Formatstrings und seiner Argumente (wie '"Expected "{" but found "%s"' % "[" ). Dies wird in __str__ gehandhabt Methode der Klasse, wo wir self.msg formatiert haben mit Elementen in self.pos .
Nun fragen Sie sich vielleicht, warum wir es im __str__ formatieren wollen Methode, anstatt sie mit einem % zu schreiben ? Es stellt sich heraus, dass die Verwendung von % Operator zum Formatieren eines Strings nimmt einige Zeit in Anspruch. Beim Parsen einer Zeichenfolge werden viele Ausnahmen ausgelöst, da der Parser versucht, verschiedene Regeln anzuwenden. Daher haben wir die Zeichenfolgenformatierung verschoben, wenn sie wirklich benötigt wird.
Die Parser-Basisklasse
Nachdem wir nun eine Fehlerklasse eingerichtet haben, besteht der nächste Schritt darin, die Parser-Klasse zu schreiben. Wir definieren es wie folgt:
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
Hier sehen Sie einen cache Mitglied im __init__ -Methode – wir werden darauf zurückkommen, warum dies erforderlich ist, wenn wir über das Erkennen von Zeichen sprechen.
Die parse Die Methode ist ziemlich einfach – zuerst speichert sie den String. Da wir noch keinen Teil der Zeichenfolge gescannt haben, setzen wir die Position auf -1. Außerdem speichern wir den maximalen Index des Strings in self.len . (Der maximale Index ist immer um eins kleiner als die Länge des Strings.)
Als nächstes beginnen wir mit dem Parsen der Zeichenfolge und prüfen, ob wir das Ende der Zeichenfolge erreicht haben. Damit soll sichergestellt werden, dass unser Parser den gesamten Text verarbeiten konnte, ohne dass am Ende etwas übrig bleibt. Danach geben wir das Ergebnis zurück.
Die assert_end Die Methode ist einfach:Wir prüfen, ob die aktuelle Position kleiner als der maximale Index ist. Denken Sie daran, dass sich diese Methoden innerhalb der Klasse befinden, obwohl wir der Einfachheit halber die Einrückung weggelassen haben.
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
In unserem gesamten Parser betrachten wir das Zeichen, das eins mehr ist als der aktuelle Index (self.pos ). Um zu sehen, warum dies der Fall ist, bedenken Sie, dass wir mit self.pos = -1 beginnen , also sehen wir uns den Index 0 an. Sobald wir ein Zeichen erfolgreich erkannt haben, self.pos geht auf 0 und wir würden uns das Zeichen bei Index 1 ansehen und so weiter. Aus diesem Grund verwendet der Fehler self.pos + 1 .
Bei den meisten Sprachen können Leerzeichen zwischen Token sicher verworfen werden. Daher erscheint es logisch, eine Methode einzufügen, die prüft, ob das nächste Zeichen ein Leerzeichen ist, und es dann „verwirft“, indem es zur nächsten Position vorrückt.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Zeichenbereiche verarbeiten
Jetzt schreiben wir eine Funktion, die uns hilft, Zeichen im Text zu erkennen. Bevor wir das tun, betrachten wir unsere Funktion jedoch aus der Perspektive eines Benutzers – wir geben ihr eine Reihe von Zeichen, die aus dem Text übereinstimmen. Wenn Sie beispielsweise ein Alphabet oder einen Unterstrich erkennen möchten, könnten Sie Folgendes schreiben:
self.char('A-Za-z_')
Wir geben den char Methode, die eine Liste von Zeichen oder Bereichen enthält (z. B. A-Z im obigen Beispiel). Bereiche werden durch zwei Zeichen gekennzeichnet, die durch - getrennt sind . Das erste Zeichen hat einen numerisch kleineren Wert als das rechte.
Wenn nun das Zeichen bei self.text[self.pos + 1] stimmt mit etwas im Argument von self.char überein , wir schicken es zurück. Andernfalls lösen wir eine Ausnahme aus.
Intern verarbeiten wir die Zeichenfolge zu etwas, das einfacher zu handhaben ist – eine Liste mit separaten Zeichen oder Bereichen wie ['A-Z', 'a-z', '_'] . Also schreiben wir eine Funktion, um die Bereiche aufzuteilen:
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
Hier durchlaufen wir den chars Zeichenfolge und suchen Sie nach einem - gefolgt von einem anderen Zeichen. Wenn diese Bedingung zutrifft und das erste Zeichen kleiner als das letzte ist, fügen wir den gesamten Bereich hinzu (z. B. A-Z ) in die Liste rv . Andernfalls fügen wir das Zeichen bei chars[index] hinzu bis rv .
Dann fügen wir die Liste in rv hinzu es in den Cache. Wenn wir diesen String ein zweites Mal sehen, geben wir ihn mit dem try ... except KeyError: ... aus dem Cache zurück oben blockieren.
Zugegeben, wir hätten einfach eine Liste wie ['A-Z', 'a-z', '_'] bereitstellen können zum char Methode. Unserer Meinung nach führt dies jedoch zu Aufrufen von char() etwas sauberer aussehen.
Zeichen aus dem Text extrahieren
Da wir nun eine Methode haben, die eine Liste mit Bereichen und Zeichen liefert, können wir unsere Funktion schreiben, um ein Zeichen aus dem Text zu extrahieren. Hier ist der Code für char Methode:
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
Konzentrieren wir uns zunächst auf das Argument chars=None . Damit können Sie self.char() anrufen ohne ihm eine Reihe von Zeichen zu geben. Dies ist nützlich, wenn Sie einfach ein Zeichen extrahieren möchten, ohne es auf einen bestimmten Satz zu beschränken. Andernfalls können Sie es mit einer Reihe von Zeichen aufrufen, wie wir im vorherigen Abschnitt gesehen haben.
Diese Funktion ist ziemlich einfach – zuerst prüfen wir, ob uns der Text ausgegangen ist. Dann wählen wir das nächste Zeichen und prüfen, ob chars None ist , in diesem Fall können wir die Position erhöhen und das Zeichen sofort zurückgeben.
Wenn es jedoch eine Reihe von Zeichen in chars gibt , teilen wir es in eine Liste einzelner Zeichen und Bereiche auf, z. B. ['A-Z', 'a-z', '_'] . In dieser Liste ist eine Zeichenfolge der Länge 1 ein Zeichen, und alles andere ist ein Bereich. Es prüft, ob das nächste Zeichen mit dem Zeichen oder dem Bereich übereinstimmt, und wenn ja, geben wir es zurück. Wenn wir es nicht mit irgendetwas vergleichen konnten, verlässt es die Schleife, die ParseError auslöst , die besagt, dass wir das erwartete Zeichen nicht erhalten konnten.
Der 'character' if chars is None else '[%s]' % chars ist nur eine Möglichkeit, eine besser lesbare Ausnahme bereitzustellen. Wenn chars ist None , würde die Ausnahmenachricht Expected character but got ... lauten , aber wenn char auf etwas wie A-Za-z_ gesetzt war , würden wir Expected [A-Za-z_] but got ... erhalten .
Später werden wir sehen, wie man diese Funktion verwendet, um Token zu erkennen.
Schlüsselwörter und Symbole extrahieren
Neben dem Extrahieren einzelner Zeichen ist das Erkennen von Schlüsselwörtern eine häufige Aufgabe beim Erstellen eines Parsers. Wir verwenden „Schlüsselwörter“, um lose auf jede zusammenhängende Zeichenfolge zu verweisen, die ihre „eigene Entität“ ist und möglicherweise Leerzeichen davor und danach hat. Zum Beispiel in JSON { könnte ein Schlüsselwort sein, und in einer Programmiersprache if , else könnte ein Schlüsselwort sein usw.
Dies ist der Code zum Erkennen von Schlüsselwörtern:
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
Diese Methode verwendet Schlüsselwörter wie self.keyword('if', 'and', 'or') . Die Methode entfernt Leerzeichen und prüft dann, ob uns der zu analysierende Text ausgegangen ist. Dann iteriert es durch jedes Schlüsselwort und prüft, ob das Schlüsselwort im Text vorhanden ist. Wenn etwas gefunden wird, entfernen wir den Leerraum nach dem Schlüsselwort und geben dann das Schlüsselwort zurück.
Wenn es jedoch nichts findet, verlässt es die Schleife, die ParseError auslöst , die besagt, dass die Keywords nicht gefunden werden konnten.
Ein Helfer zum Abgleichen mehrerer Produktionen
In den vorherigen Abschnitten haben Sie bemerkt, dass wir Ausnahmen verwenden, um Fehler zu melden. Wir wissen auch, dass Sie zum Schreiben eines rekursiven Abstiegsparsers Funktionen schreiben, die ein Token oder eine Produktionsregel erkennen. Stellen Sie sich nun vor, Sie wollten einen einfachen Text parsen, in dem Sie eine Zahl oder ein Wort erwarten. Die Produktionsregel könnte folgendermaßen aussehen:
Wir gehen außerdem davon aus, dass der Text ein Wort enthält. Wenn der Parser versucht, nach einer Ziffer zu suchen (etwa mit char() ), es wird es nicht finden, und dies führt dazu, dass es eine Ausnahme auslöst. Außerdem müssen Sie den Leerraum vor und nach dem Abgleich einer Produktionsregel entfernen. Also der Code für item() könnte so aussehen:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
Das sieht schon nach viel aus, um eine einfache Regel umzusetzen! Stellen Sie sich vor, wie es wäre, eine komplexe Regel zu implementieren – Sie müssten try...except verwenden Blöcke überall.
Also schreiben wir einen match() Funktion, die den Leerraum entfernt und versucht, mehrere Regeln zu erfüllen. Die Funktion ist wie folgt:
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
Bevor wir diskutieren, wie es funktioniert, sehen wir uns an, wie einfach es ist, unser vorheriges Beispiel mit match() umzuschreiben :
def item(self):
return self.match('number', 'word')
Also, wie funktioniert das? match() nimmt einen Methodennamen zum Ausführen (z. B. number). oder word im obigen Beispiel). Zuerst werden die Leerzeichen am Anfang entfernt. Dann iteriert es über alle Methodennamen und ruft jede Methode unter Verwendung ihres Namens über getattr() ab . Es versucht dann, die Methode aufzurufen, und wenn alles gut geht, entfernt es auch Leerzeichen nach dem Text. Schließlich gibt es den Wert zurück, den es durch den Aufruf der Methode
Wenn jedoch ein Fehler auftritt, wird self.pos zurückgesetzt auf den Wert, der dort war, bevor versucht wurde, eine Regel zuzuordnen. Dann versucht es, eine gute Fehlermeldung auszuwählen, indem es die folgenden Regeln anwendet:
- Wenn mehrere Regeln abgeglichen werden, erzeugen viele von ihnen möglicherweise einen Fehler. Der Fehler, der nach dem Parsen des größten Teils des Textes generiert wurde, ist wahrscheinlich die gewünschte Fehlermeldung.
Um zu sehen, warum das so ist, betrachten Sie die Zeichenfolge „abc1“. Versuch, number() anzurufen würde an Position 0 scheitern, während word() würde an Position 2 scheitern. Wenn man sich die Zeichenfolge ansieht, ist es ziemlich wahrscheinlich, dass der Benutzer ein Wort eingeben wollte, aber einen Tippfehler gemacht hat.
- Wenn zwei oder mehr fehlerhafte Regeln in einem „Unentschieden“ enden, teilen wir dem Benutzer lieber alle fehlgeschlagenen Regeln mit.
Die last_error_pos und last_exception verfolgt die Position des letzten Fehlers bzw. die Ausnahme. Außerdem führen wir eine Liste last_error_rules damit wir dem Benutzer im Falle eines Unentschiedens alle Regeln mitteilen können, die wir zu erfüllen versucht haben.
Im except ParseError Block vergleichen wir die Position des letzten Fehlers und den aktuellen Fehler. Wenn der aktuelle Fehler gleich ist, betrachten wir ihn als Unentschieden und hängen ihn an die Liste an. Andernfalls aktualisieren wir die Fehlerposition, die Ausnahme und die Liste der fehlerhaften Regeln.
Am Ende prüfen wir, wie viele Regeln fehlgeschlagen sind. Wenn es nur einen gibt, last_exception hätte die beste Fehlermeldung. Andernfalls gibt es ein Unentschieden, und wir teilen dem Benutzer dies mit einer Nachricht wie Expected number,word but found ... mit .
Nach vorne schauen – Helferfunktionen
An diesem Punkt haben wir alle notwendigen Dinge in unserem Parser, und alle Fehler lösen Ausnahmen aus. Manchmal möchten wir jedoch nur ein Zeichen, ein Schlüsselwort oder eine Regel abgleichen, wenn es vorhanden ist, ohne die Unannehmlichkeiten der Behandlung von Ausnahmen.
Dafür stellen wir Ihnen drei kleine Helfer vor. Im Falle einer Ausnahme bei der Suche nach Inhalten geben diese None zurück :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
Die Verwendung dieser Funktionen ist einfach. So können Sie sie verwenden:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Erstes Parser-Beispiel:ein Taschenrechner
Nachdem wir nun die Grundlage für das Schreiben eines Parsers geschaffen haben, bauen wir unseren ersten Parser. Es kann mathematische Ausdrücke mit Additionen, Subtraktionen, Multiplikationen, Divisionen analysieren und auch Ausdrücke in Klammern wie „(2 + 3) * 5“ verarbeiten.
Wir beginnen mit der Visualisierung der Grammatik in Form von Produktionsregeln.
Produktionsregeln für die Rechnergrammatik
Wir haben zuvor eine Grammatik gesehen, die alles außer Ausdrücken in Klammern behandelt:
Lassen Sie uns nun darüber nachdenken, wie Ausdrücke in Klammern in diese Grammatik passen. Bei der Auswertung von „(2 + 3) * 5“ müssten wir „(2 + 3)“ berechnen und auf eine Zahl reduzieren. Das bedeutet, dass sich der Begriff „Zahl“ in der obigen Grammatik entweder auf einen Ausdruck in Klammern oder auf etwas beziehen kann, das wirklich eine Zahl ist, wie „5“.
Also werden wir unsere Regeln anpassen, um beides zu berücksichtigen. In der Regel für „Begriff“ ersetzen wir „Zahl“ durch einen passenderen Begriff wie „Faktor“. „Faktor“ kann sich dann entweder auf einen eingeklammerten Ausdruck oder eine „Zahl“ beziehen. Die modifizierte Grammatik sieht folgendermaßen aus:
Wenn das aus dem Weg ist, lasst uns die Produktionsregeln umsetzen!
Implementierung des Parsers
Wir implementieren unseren Calculator-Parser, indem wir die Basis-Parser-Klasse erweitern. Wir beginnen mit der Definition der Klasse wie folgt:
class CalcParser(Parser):
def start(self):
return self.expression()
Früher hatten wir bei der Implementierung der Basis-Parser-Klasse einen start() Methode zum Starten des Parsens. Wir nennen einfach expression() Methode hier, die wir wie folgt definieren werden:
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
Die Grammatikregel für . Also beginnen wir damit, einen Begriff aus dem Text zu lesen. Dann richten wir eine Endlosschleife ein und suchen nach einem „+“ oder „-“. Wenn wir beides nicht finden, bedeutet dies, dass wir die Liste der zusätzlichen Begriffe, die durch angegeben ist, zu Ende gelesen haben, sodass wir aus der Schleife ausbrechen können.
Ansonsten lesen wir einen anderen Begriff aus dem Text. Dann addieren oder subtrahieren wir ihn je nach Operator zum Anfangswert. Wir fahren mit diesem Vorgang fort, bis wir kein „+“ oder „-“ erhalten, und geben den Wert am Ende zurück.
Wir implementieren term() genauso:
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv Als nächstes implementieren wir „Factor“. Wir versuchen zuerst, eine linke Klammer zu lesen, was bedeutet, dass es einen eingeklammerten Ausdruck gibt. Wenn wir eine Klammer finden, lesen wir einen Ausdruck und die schließende Klammer und geben den Wert des Ausdrucks zurück. Andernfalls lesen wir einfach eine Zahl und geben sie zurück.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
Im nächsten Abschnitt werden wir unseren Parser dazu bringen, eine Zahl zu erkennen.
Zahlen erkennen
Um eine Zahl zu erkennen, müssen wir uns die einzelnen Zeichen in unserem Text anschauen. Zahlen bestehen aus einer oder mehreren Ziffern, optional gefolgt von einem Dezimalteil. Der Dezimalteil hat einen Punkt (.) gefolgt von mindestens einer Ziffer. Außerdem können Zahlen ein Vorzeichen wie „+“ oder „-“ vorangestellt haben, z. B. „-124,33“.
Wir implementieren den number() Methode wie folgt:
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
Obwohl die Funktion lang ist, ist sie ziemlich einfach. Wir haben einen chars Liste, in die wir die Zeichen der Zahl einfügen. Zuerst sehen wir uns alle „+“- oder „-“-Symbole an, die vor der Zahl vorhanden sein können. Wenn es vorhanden ist, fügen wir es der Liste hinzu. Dann suchen wir nach der ersten obligatorischen Ziffer der Nummer und suchen mit maybe_char() nach weiteren Ziffern Methode. Sobald wir None erhalten bis maybe_char , wissen wir, dass wir den Ziffernsatz überschritten haben, und beenden die Schleife.
Ebenso suchen wir nach dem Dezimalteil und seinen Ziffern. Schließlich wandeln wir alle Zeichen in einen String um, den wir wiederum in eine Fließkommazahl umwandeln.
Eine Schnittstelle für unseren Parser
Wir sind mit dem Erstellen unseres Parsers fertig. Als letzten Schritt fügen wir ein wenig Code im globalen Bereich hinzu, der es uns ermöglicht, Ausdrücke einzugeben und Ergebnisse anzuzeigen:
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
Wenn Sie bis jetzt mitverfolgt haben, herzlichen Glückwunsch! Sie haben Ihren ersten rekursiven Abstiegsparser gebaut!
Wenn Sie in einer lokalen IDE folgen, können Sie Ihren Code an dieser Stelle ausführen. Alternativ können Sie den unten stehenden Playground verwenden, um den Parser auszuführen. Sie können Ausdrücke über die Registerkarte "Eingabe" unten eingeben:
Den vollständigen Code finden Sie auch hier.
Zweites Parser-Beispiel:ein „erweiterter“ JSON-Parser
JSON ist ein Datenaustauschformat, das grundlegende Datenstrukturen wie Zahlen, Zeichenfolgen und Listen unterstützt. Es ist ein sehr weit verbreitetes Format, obwohl seine Einfachheit bedeutet, dass es Dinge wie Kommentare und strenge Dinge, die es akzeptiert, fehlt. Sie können beispielsweise kein nachgestelltes Komma in einer Liste haben oder ein explizites „+“ vor einer Zahl haben, um ihr Vorzeichen anzuzeigen.
Da Python bereits über ein JSON-Modul verfügt, streben wir etwas höher an und bauen einen JSON-Parser, der Kommentare, nachgestellte Kommas und Zeichenfolgen ohne Anführungszeichen unterstützt.
Durch die Implementierung dieses Parsers lernen Sie, wie Sie mit Kommentaren umgehen. Es wird auch veranschaulichen, wie eine einfach zu verwendende Sprache das Parsing kompliziert machen kann und wie Sie mit solchen Situationen umgehen können.
Bevor wir unsere Grammatik implementieren, lassen Sie uns ein Gefühl für unser erweitertes JSON-Format bekommen:
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} Produktionsregeln für die JSON-Grammatik
Unser erweitertes JSON hält sich an die gleichen Datentypen, die JSON unterstützt. JSON hat vier primitive Datentypen – Null, boolesche Werte, Zahlen und Zeichenfolgen und zwei komplexe Datentypen – Listen (oder Arrays) und Karten (auch Hashes oder Wörterbücher genannt). Listen und Hashes sehen ähnlich aus wie in Python.
Da JSON-Daten aus einem dieser Typen bestehen würden, könnten Sie die Produktionsregeln folgendermaßen schreiben:
Anschließend können Sie diese beiden Typen in JSON-Typen aufteilen:
Diese Grammatik eignet sich gut zum Parsen von regulärem JSON, muss jedoch für unseren Fall etwas angepasst werden. Da wir Zeichenfolgen ohne Anführungszeichen unterstützen werden, was bedeutet, dass „1,5“ (ohne Anführungszeichen) eine Zahl ist, aber „1,5x“ (wieder ohne Anführungszeichen) eine Zeichenfolge ist. Unsere aktuelle Grammatik würde „1.5“ aus „1.5x“ lesen und dann einen Fehler verursachen, weil „x“ nach einer Zahl nicht erwartet wurde.
Das bedeutet, dass wir zuerst den vollständigen Satz von Zeichen ohne Anführungszeichen erhalten müssten. Als Nächstes analysieren wir die Zeichen und stellen fest, ob es sich um eine Zahl oder eine Zeichenfolge handelt. Also kombinieren wir Zahlen und Strings ohne Anführungszeichen in einer einzigen Kategorie, „Ohne Anführungszeichen“. Die Zeichenfolgen in Anführungszeichen sind in Ordnung, also trennen wir sie in eine andere Kategorie, „QuotedString“. Unsere modifizierte Produktionsregel für „PrimitiveType“ sieht nun so aus:
Außerdem ist die Reihenfolge der Regeln wichtig. Da wir Schlüssel ohne Anführungszeichen haben, müssen wir zuerst versuchen, den Text als Null oder Boolean zu analysieren. Andernfalls erkennen wir möglicherweise „null“ oder „true“ als Zeichenfolge ohne Anführungszeichen.
Implementierung des Parsers und Umgang mit Kommentaren
Um den JSON-Parser zu implementieren, beginnen wir damit, die Basis-Parser-Klasse wie folgt zu erweitern:
class JSONParser(Parser): # ...
Wir werden uns zunächst mit dem Problem des Umgangs mit Kommentaren befassen. Wenn Sie darüber nachdenken, sind Kommentare Whitespace wirklich ähnlich – sie treten an denselben Stellen auf, an denen Whitespaces auftreten können, und sie können genau wie Whitespace verworfen werden. Also werden wir eat_whitespace() neu implementieren um mit den Kommentaren umzugehen, so:
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
Hier müssen wir im Auge behalten, ob wir Leerzeichen oder einen Kommentar verarbeiten. Wir durchlaufen den Text Zeichen für Zeichen und prüfen, ob wir Leerzeichen oder ein # haben . Wenn es einen # gibt , aktualisieren wir is_processing_comment bis True und in den nächsten Iterationen des while Schleife können wir alle Zeichen sicher verwerfen, bis wir das Ende der Zeile erreichen. Bei der Verarbeitung von Whitespace-Zeichen müssen wir jedoch aufhören, sobald ein Nicht-Whitespace-Zeichen erscheint.
Als Nächstes implementieren wir die Produktionsregeln und den start() Methode. Der Eingabetext enthält einen JSON-Typ, also rufen wir einfach any_type() auf im start() Methode:
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
Parsen von Listen und Karten
Zuvor haben wir gesehen, wie kommagetrennte Listen analysiert werden. Die Listen von JSON sind nur eine durch Kommas getrennte Liste mit angehängten eckigen Klammern, und die Liste kann null oder mehr Elemente enthalten. Mal sehen, wie Sie das Parsen einer Liste implementieren würden:
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
Wir beginnen mit dem Ablesen der einleitenden eckigen Klammer gefolgt von einem Eintrag aus der Liste mit self.maybe_match('any_type') . Wenn wir einen Gegenstand nicht bekommen haben, bedeutet dies, dass wir wahrscheinlich alle Gegenstände durchgegangen sind, also brechen wir aus der Schleife aus. Andernfalls fügen wir das Element der Liste hinzu. Wir versuchen dann, ein Komma aus der Liste zu lesen, und das Fehlen eines Kommas zeigt auch an, dass wir mit der Liste fertig sind.
In ähnlicher Weise sind Maps nur durch Kommas getrennte Listen von „Paaren“ mit geschweiften Klammern, wobei ein Paar ein Zeichenfolgenschlüssel ist, gefolgt von einem Doppelpunkt (:) und einem Wert. Im Gegensatz zu Pythons dict s, die einen beliebigen „hashfähigen“ Typ als Schlüssel haben können (einschließlich int s und tuple s) unterstützt JSON nur Zeichenfolgenschlüssel.
So würden Sie die Regeln für Karten und Paare implementieren:
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
In pair() , versuchen wir, einen „QuotedString“ oder „Unquoted“ für den Schlüssel zu lesen. Wie wir bereits erwähnt haben, kann „Unquoted“ entweder eine Zahl oder einen String zurückgeben, also prüfen wir explizit, ob der von uns gelesene Schlüssel ein String ist. pair() gibt dann ein Tupel mit einem Schlüssel und Wert und map() zurück ruft pair() auf und fügt diese einem Python-Diktat hinzu.
Null und Boolean erkennen
Nachdem die Hauptteile unseres Parsers implementiert sind, beginnen wir damit, einfache Token wie null und boolesche Werte zu erkennen:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
Pythons None ist das nächste Analogon zu null von JSON . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() can run. In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.