Wie Compiler und Interpreter Formeln parsen und auswerten
Ein Computer überführt einzelne Operationen in eine spezielle Struktur und rechnet damit auch komplexeste Formeln schnell aus. Wir erklären die Funktionsweise.
- Oliver Lau
Der 2019 von c't vorgestellte Arbitrary Precision Calculator (APC) ist ein Rechner für den Browser, der mit beliebig großen Ganzzahlen umgehen kann, und das nicht nur im Dezimalsystem, sondern auch im Binär-, Oktal- und Hexadezimalsystem. Er beherrscht die Grundrechenarten, bitweise Operationen, geklammerte Terme und ein paar Funktionen wie größter gemeinsamer Teiler (ggT), kleinstes gemeinsames Vielfaches (kgV) und Quadratwurzelziehen. Darüber hinaus kann er Variablen verarbeiten, sodass man wiederkehrende oder bereits berechnete Werte nicht erneut eintippen muss, sondern über Namen wie x oder theta wiederverwenden kann (Demo unter 607011.github.io/bincalc).
Was wir in dem Artikel nicht erklärten, können Sie im Folgenden lesen: wie der Arbitrary Precision Calculator die eingetippten Formeln so unter Berücksichtigung der Operatorenrangfolge (lies: Punkt vor Strich, höchste Priorität für Klammern) in ihre Bestandteile zerlegt, dass er sie bequem durchrechnen kann. Dazu bedient er sich des sogenannten Shunting-Yard-Algorithmus. Shunting Yard ist das englische Wort für Rangierbahnhof, und tatsächlich erinnert das Verfahren daran, wie Zugteile von einem Gleis zum anderen verschoben werden.
- Bevor Computer Formeln ausrechnen, überführen sie sie typischerweise in ein leichter interpretierbares Format, die sogenannte Postfix-Notation, auch als umgekehrte polnische Notation (UPN) bekannt.
- Formeln in UPN benötigen keine Rechenregeln à la "Punkt vor Strich" und auch keine Klammern mehr.
- Zum Umwandeln von Formeln nach UPN bietet sich der Shunting-Yard-Algorithmus von Edsger Dijkstra an.
Zum Verständnis hilft es, wenn Sie halbwegs fit in JavaScript sind. Kenntnisse anderer Programmiersprachen wie C/C++, Java, Python oder Rust genügen aber auch. Den Quellcode finden Sie in unserem GitHub-Repository, dort speziell in der Datei numbercruncher.js.
Das war die Leseprobe unseres heise-Plus-Artikels "Wie Compiler und Interpreter Formeln parsen und auswerten". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.Immer mehr Wissen. Das digitale Abo für IT und Technik.
Pornografische VR-Spiele im Test: Wie interaktiv sie wirklich sind
Smarte Überwachung: Füllstand von Wassertanks messen und digital abfragen
BASPi: Backup und Sync ohne Cloud mit einem Raspi einrichten
Top Ten: Apple Watch Series 10 im Test
How to: Passwortgeschützte Word- und Excel-Dateien entsperren