Compilerbau

Ein Parser für arithmetische Ausdrücke

Ziel ist es, anhand von arithmetischen Ausdrücken beispielhaft zu zeigen, wie ein Compiler im Prinzip aufgebaut ist. Dazu definiert man zuerst eine entsprechende Grammatik und bastelt dazu einen Parser.

EBNF Grammatik für arithmetische Ausdrücke: 

expression = term { + | - term }
term       = factor { * | / factor }
factor     = value | ( "(" expression ")" )
value      = <decimal number>

Man beachte: die EBNF Regeln für arithmetische Ausdrücke sind rekursiv, d.h. ein Ausdruck kann in Klammern wieder einen Ausdruck enthalten, der wiederum kann einen weiteren geklammerten Ausdruck enthalten usw. Der entsprechende Parser gehört damit auch zur Klasse der rekursiven Funktionen.

Man setzt nun voraus, dass eine Methode gettoken() vorhanden ist, welche das nächste Wort (Token) liefert und den dazwischen liegenden Zwischenraum bzw. white space (CR LF TAB SPC) überliest. Diesen Vorgang nennt man lexikalische Analyse. Es wird vereinbart, dass die globale Variable token das jeweils aktuell gelesene Wort enthält, d.h. das nächste Wort wird mittels token=gettoken() eingelesen.

Die Umsetzung der EBNF-Regeln in einen Parser geschieht nun derart, dass eine dedizierte Parser-Funktion für jede EBNF-Regel konstruiert wird.

Jede Parser-Funktion überprüft die Ableitbarkeit, indem sie Schritt für Schritt den nächsten Token einliest und auf Übereinstimmung mit der dazugehörigen Regel überprüft. Es gelten dabei folgende Konventionen:

  • Für jedes Schlüsselwört einer Regel wird ein Wort gelesen.
  • Wenn ein gelesenes Wort nicht mit dem Schlüsselwort übereinstimmt, gilt der Satz als nicht ableitbar. Es wird eine Fehlermeldung ausgegeben.
  • Ein Regelname wird in den entsprechenden Funktionsaufruf übersetzt.
  • Bei jedem Funktionsaufruf enthält token das nächste Schlüsselwort. Selbiges gilt nach einem Funktionsruf.

Der Beispiel-Parser für arithmetische Ausdrücke lautet damit in Pseudo-Code:

void expression()
{
   term();

   while (token=="+" || token=="-") {
      token=gettoken();

      term();
   }

   exit(0); // sentence is correct
}

void term()
{
   factor();

   while (token=="*" || token=="/") {
      token=gettoken();

      factor();
   }
}

void factor()
{
   if (token=="(") {
      token=gettoken();

      expression();

      if (token!=")") error(1); // error encountered

      token=gettoken();
   }
   else {
      value();
   }
}

void value()
{
   if (!is_value(token)) error(2);

   token=gettoken();
}

void error(int code) {
   exit(code); // sentence is not correct
}
[Get Code]

Die obigen Funktionen sind nicht direkt rekursiv, aber indirekt rekursiv über 3 Ebenen.

Q Wie kann man die Ausdrücke um die mathematischen Funktionen sqrt() und pow() sowie die trigonometrischen Funktionen sin(), cos() und tan() erweitern?


← Arithmetische Ausdrücke | ● | Arithmetische Auswertung →

Options: