Zwei Ergebnisse für dieselbe Rechnung
Ein Skript eines Paketdienstes berechnet Versandkosten als 4 + 5 * 2. Eine Testerin erwartet 14 Euro, ein Kollege 18 Euro.
Beide lesen dieselben Tokens in derselben Reihenfolge. Sie fassen sie nur verschieden zusammen. Ein Compiler muss Tokens immer auf genau eine Weise zusammenfassen. Diese Weise steht in einer Grammatik.
Am Ende dieser Lektion
Notiz
Ich kann aus Tokens einen Syntaxbaum bauen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Grammatik | die Regeln, welche Folgen von Tokens erlaubt sind | |
| Syntaxbaum | ein Baum, der zeigt, wie die Tokens zusammengehören | |
| Parser | der Teil eines Compilers, der den Baum baut | |
| Vorrang | welcher Operator zuerst zusammenfasst | * vor + |
| Assoziativität | welche Seite bei gleichrangigen Operatoren zuerst zusammenfasst | links |
| Rekursiver Abstieg | ein Parser mit einer Funktion je Regel |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Grammatik sagt, wie Tokens zusammengehören
Eine Grammatik ist eine kurze Liste von Regeln. Jede Regel nennt einen Teil eines Satzes und sagt, woraus er besteht.
Die drei Regeln unten geben * und / einen höheren Vorrang als + und -. Eine Summe besteht aus Produkten, also werden Produkte zuerst zusammengefasst. Klammern beginnen wieder oben. So setzen sie die Reihenfolge außer Kraft.
Beispiel: drei Regeln für Rechnungen
| Regel | Besteht aus | Beispiel |
|---|---|---|
| ausdruck | Einem term, dann beliebig oft + oder - und noch ein term | 4 + 5 * 2 |
| term | Einem faktor, dann beliebig oft * oder / und noch ein faktor | 5 * 2 |
| faktor | Einer Zahl oder einem ausdruck in Klammern | 2 oder (4 + 5) |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Funktion für jede Regel
Ein Parser mit rekursivem Abstieg hat für jede Regel eine Funktion. ausdruck ruft term auf, und term ruft faktor auf. Bei einer Klammer ruft faktor wieder ausdruck auf: Das ist die Rekursion.
Jede Runde der Schleife in ausdruck nimmt den bisherigen Baum als linke Seite. Deshalb lehnt sich - nach links. Das Beispiel zeigt nur diese Schleife, mit einfachen Zahlen als Terme.
Die Schleife, die Minus nach links lehnt
# Ein Parser fuer Summen wie 20 - 5 - 3: Zahlen mit + und - dazwischen.
tokens = ["20", "-", "5", "-", "3"]
pos = 0
# Die erste Zahl ist der Anfang des Baums.
baum = int(tokens[pos])
pos = pos + 1
while pos < len(tokens):
op = tokens[pos]
rechts = int(tokens[pos + 1])
# Der bisherige Baum wird zur linken Seite: So lehnt sich - nach links.
baum = [op, baum, rechts]
pos = pos + 2
print(baum)
# Aendern Sie tokens in ["8", "+", "1", "-", "4", "+", "2"] und fuehren Sie erneut aus.
bison baut den Parser aus einer Grammatik
Ein Parsergenerator wie bison liest eine Grammatik und schreibt den Parser in C. In calc.y hat die Regel expr eine Zeile für jeden Operator. Das allein ist mehrdeutig: 4 + 5 * 2 ließe sich auf beide Arten zusammenfassen.
Zwei Zeilen mit %left klären das. Jede sagt, dass sich ihre Operatoren nach links lehnen. Die spätere Zeile bindet stärker, also gehen * und / vor + und -.
In den Ordner compiler wechseln
cd ~/compilerHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Sicherstellen, dass der Rechner gebaut ist
makeHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die zwei Zeilen zum Vorrang
grep -n "%left" calc.yHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Minus lehnt sich nach links
echo "20 - 5 - 3" | ./calcHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ganzzahliges Teilen ebenso
echo "60 / 4 / 3" | ./calcHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zwei Klammern ändern den Baum
echo "(1 + 2) * (3 + 4)" | ./calcHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zwei Zeichen hintereinander
echo "5 * + 2" | ./calcHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Klammer, die offen bleibt
echo "(4 + 2" | ./calcHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, ein Parser arbeitet einfach von links nach rechts. Dann wäre 4 + 5 * 2 gleich 18. Die Grammatik bestimmt den Baum, und der Baum bestimmt die Reihenfolge. Durch den Vorrang steht 5 * 2 tiefer im Baum und wird zuerst gerechnet. Links nach rechts gilt nur für Operatoren mit gleichem Vorrang.
Den Vorrang wegnehmen
Der nächste Befehl kopiert calc.y ohne die zwei Zeilen mit %left. Dann liest bison die Kopie.
Ohne Vorrang hat bison oft zwei mögliche Schritte und keine Regel, einen zu wählen. Jede solche Stelle heißt Shift/Reduce-Konflikt. Der letzte Befehl bittet bison um ein Beispiel für den ersten Konflikt.
Die Grammatik ohne Vorrang kopieren
sed "/%left/d" calc.y > ohnevorrang.yHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
bison die Kopie bauen lassen
bison ohnevorrang.yHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Einen Konflikt zeigen
bison -Wcounterexamples ohnevorrang.y 2>&1 | head -n 3Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend
Ergänzen Sie Ihren Parser um einen Potenzoperator ^. Er bindet stärker als * und lehnt sich nach rechts: 2 ^ 3 ^ 2 bedeutet 2 ^ (3 ^ 2).
Fügen Sie dafür eine neue Regel zwischen term und faktor ein. Erklären Sie, warum eine Schleife wie in ausdruck hier den falschen Baum baut und was Sie stattdessen schreiben.