Calculator

Der in Abschnitt 4.5.1 beschriebene Scanner-Generator flex(1) und der in Abschnitt 7.3.3 beschriebene Parser-Generator bison(1) können verwendet werden, um mit wenig Aufwand einen Interpreter für arithmetische Ausdrücke zu konstruieren. Das ebenfalls im Abschnitt 7.3.3 in mehr Detail beschriebene Codeprojekt lässt einen solchen in elf Phasen entstehen, so dass man verfolgen kann, wie die einzelnen Komponenten schrittweise zusammenkommen um die angestrebte Funktionalität zu realisieren.

Ganzes Paket: calculator.tar.gz herunterladen. Instruktionen zur Kompilation finden sich im README file im Paket.

Von Phase zu Phase ändern sich jeweils nur wenige Files, die durch Anklicken angezeigt werden können.

  1. Grundstruktur: Aus den regulären Ausdrüken im File tokens.l wird der Scanner erzeugt, aus den Grammatikregeln der Expression-Term-Factor-Grammatik im File grammar.y wird der Parser erzeugt. Die Main-Funktion calculator.c ruft den Parser in der Funktion yyparse() auf. Diese Phase kompiliert, aber es passiert nichts, weil im Scanner nicht spezifiziert ist, was mit den Tokens gemacht werden soll, und weil in der Grammatik kein Code zur Auswertung gegeben ist.
  2. Aktionen im Scanner: im File tokens.l steht jetzt bei jedem regulären Ausdruck ein Codeblock der festlegt, was der Scanner mit gefunenen Token machen soll. Für Zahlen wird dem Parser ein NUMBER-Token zurückgegeben, alle anderen Zeichen werden unverändert übergeben. In dieser Phase erwacht der Parser zum Leben und kann einen arithmetischen Ausdruck parsen, aber noch nicht evaluieren.
  3. Auswertung in der Grammatik: im File grammar.y ist zu jeder Grammatikregel angegeben, wie der Wert des Knotens des Syntaxbaumes zu ermitteln ist. Am Ende einer Zeile wird der Wert ausgegeben. Damit kann der Calculator jetzt einen arithmetischen Ausdruck auswerten.
  4. Iteration: Die Grammatik der Phasen 1-3 akzeptiert nur eine einzelnen arithmetischen Ausdruck. Durch Iterationsregeln mit Hilfe von Linksrekursion in grammar.y können in Phase 4 beliebig viele arithmetische Ausdrücke ausgewertet werden.
  5. Funktionen der C-Bibliothek: Alle Funktionen der C-Bibliothek werden verfügbar gemacht durch zwei Änderungen: Im File tokens.l werden die Namen der Funktionen als reservierte Wörter definiert und in grammar.y wird für jede Funktion eine Grammatikregel ergänzt, die die Syntax für den Funktionsaufruf und die Auswertung der Funktion implementiert.
  6. Potenzen: In der Expression-Term-Factor-Grammatik gibt es keine Potenzen. In Phase 5 wird in tokens.l der Operator ^ hinzugefügt und in grammar.y eine Grammatikregel, die factor ^ factor als Potenz interpretiert.
  7. Register: Kompliziertere Berechnungen sind nur möglich, wenn man Zwischenresultate speichern kann. Phase 7 führt führt in tokens.l eine regulären Ausdruck für Register hinzu, die Namen von der Form r0 bis r99 haben. In grammar.y werden Regeln hinzugefügt, um den Wert eines Ausdrucks einem Register zuzuweisen und Regsiter als factor in arithmetischen Ausdrücken zu verwenden.
  8. Konstanten: : Häufig verwendete Konstanten sollten einfach zugreifbar sein. Phase 8 fügt tokens.l einen regulären Ausdruck für Konstantennamen hinzu, die von der Form %konstante sind. Im Parser grammar.y werden Regel hinzugefügt, die erlauben, Konstanten als factor zu verwenden und sie mit einer Lookup-Funktion in constants.c mit Header constants.h auszuwerten.
  9. History: Eine einfache History-Funktion erlaubt, mit %% auf das letzte Resultat zurückzugreifen. In Änderung in tokens.l erlaubt die Zeichenkette %% als Token und neue Regeln in grammar.y legen die Auswertung fest.
  10. monadisches Minus, Faktormultiplikation: Die klassische Expression-Term-Factor-Grammatik erlaubt kein monadisches Minus, der Ausdruck -(1+2) wird nicht akzeptiert. In Phase 10 wird eine Regel dafür in grammar.y ergänzt. Ausserdem wird ein Multiplikation factor factor ohne Operationszeichen hinzugefügt, deren Problematik in Abschnitt 7.3.3 erörtert wird.
  11. Vollausbau der Anwendung: In Phase 11 wird der Calculator wesentlich ausgebaut. In den Files tree.h und tree.c werden Funktionen zur Konstruktion eines Syntaxbaumer bereitgestellt. In functions.h und functions.c werden weitere Funktionen hinzugefügt. In tokens.l wird die History-Funktion erweitert und es werden neue reserviert Wörter hinzugefügt, mit denen man auf die History und auf die Syntaxbäume zugreifen kann. Die neuen Regeln in grammar.y realisieren die zusätzlichen Funktionen für die History und die Syntaxbäume. Außerdem wurde in den Files help.c und help.h eine Hilfefunktion hinzugefügt.