Kontextfreie Grammatik
Die kontextfreie Grammatik beschreibt die Sprache, die interpretiert werden kann. Eine Grammatik kann direkt in die Programmierung umgesetzt werden.expression -> expression + term expression -> expression - term expression -> term term -> term * primary term -> term / primary term -> primery primary -> NUMBER primary -> -primary primary -> ( expression ) |
Diese Grammatik enthält bereits die Regeln der Priorität der Operatoren. Da vor der Auflösung der Expression mit seiner "Strichrechnung" der Term mit seiner "Punktrechnung" ausgeführt wird, gilt Punktrechnung vor Strichrechnung.
Rekursiver Abstieg
Die Auswertung der Grammatik erfolgt durch den rekursiven Abstieg. Das Programm ruft expression, dies ruft term, welches primary ruft. Hier wird das erste Zeichen gefunden, das mit dem vorliegenden Token verglichen wird.Handelt es sich um eine NUMBER, ist Primary beendet und kehrt zu Term zurück. Findet sich hier ein * oder ein /, wird erneut Primary gerufen. Andernfalls wird zu Expression, das wiederum auf + oder - prüft.
Findet Primary aber eine linke Klammer ruft es (rekursiv!) Expression auf, das wieder den ganzen Stapel durchläuft. Kehrt Expression wieder zurück, prüft Primary an der korrekten Stelle, ob die Klammer wieder geschlossen wird.
Listing des Parsers
Zugunsten der Übersichtlichkeit wird die Verbindung zur lexikalischen Analyse über globale Variablen erreicht.Die Headerdatei parser.h enthält die Prototypen für die Funktionen.
double Expression(); double Term(); double Primary();Die Datei parser.cpp enthält alle Funktionen. Wir beginnen mit der Funktion Expression().
#include "lex.h"
#include "parser.h"
double Expression()
{
double Value;
Value = Term();
while (CurrentToken==PLUS || CurrentToken==MINUS) {
if (CurrentToken==PLUS) {
GetToken();
Value += Term();
} else if (CurrentToken==MINUS) {
GetToken();
Value -= Term();
}
}
return Value;
}
|
Wie in der Grammatik beschrieben, wird zunächst zu Term hinabgestiegen. Ist Term ausgewertet, prüft die Funktion auf die Tokens PLUS und MINUS. In diesem Fall ist die Expression noch nicht abgearbeitet, sondern ruft erneut Term. Durch die while-Schleife kann dies beliebig oft passieren. Erst wenn ein Zeichen erscheint, das weder PLUS noch MINUS ist, endet die Funktion und kehrt zurück.
double Term()
{
double Value;
Value = Primary();
while (CurrentToken==MUL || CurrentToken==DIV) {
if (CurrentToken==MUL) {
GetToken();
Value *= Primary();
} else if (CurrentToken==DIV) {
GetToken();
Value /= Primary();
}
}
return Value;
}
|
In Term passiert im Grunde das gleiche wie in Expression. Hier wird allerdings MUL und DIV abgearbeitet.
double Primary()
{
double Value;
switch(CurrentToken) {
case NUMBER:
GetToken();
return TokenNumberValue;
case MINUS:
GetToken();
return -Primary();
case LPAR:
GetToken();
Value = Expression();
if (CurrentToken != RPAR)
return Error(") expected");
GetToken();
return Value;
case END:
return 1;
}
return Error("primary expected");
}
|
Primary liefert im einfachsten Fall eine Zahl, wenn das erste Zeichen eine Ziffer ist. Ist es ein Minuszeichen, wird die Zahl negiert. Das "Negier-Minus" unterscheidet sich durch seine Position von dem Operatoren Minus.
Listing des Scanners
Das Token ist ein Aufzählungstyp. Ein solcher einfacher Typ ist per case einfacher zu verarbeiten als Strings. Er befindet sich in der Headerdatei lex.h.
enum tToken {
PLUS, MINUS, MUL, DIV, LPAR, RPAR, NUMBER, END, ERROR };
extern tToken CurrentToken;
extern double TokenNumberValue;
void SetSource(char *s);
tToken GetToken();
double Error(const char *s);
|
Die lexikalische Analyse ist aus Anschaulichkeitsgründen extrem knapp ausgefallen. Es fehlt das Übergehen von Leerzeichen und Leerzeilen. Auch die Auswertung der Zahl ist auf ganzzahlige Werte beschränkt. Aber zum Testen der Funktion ist er ausreichend.
Der Inhalt von lex.cpp sieht so aus:
#include <stdio.h>
#include "parser.h"
#include "lex.h"
tToken CurrentToken;
double TokenNumberValue;
char *pSource;
char *PP;
tToken GetToken()
{
CurrentToken = ERROR;
if (*PP==0) {
CurrentToken = END;
} else {
switch (*PP) {
case '(': CurrentToken=LPAR; break;
case ')': CurrentToken=RPAR; break;
case '*': CurrentToken=MUL; break;
case '/': CurrentToken=DIV; break;
case '+': CurrentToken=PLUS; break;
case '-': CurrentToken=MINUS; break;
}
if (*PP>='0' && *PP<='9') {
CurrentToken=NUMBER;
TokenNumberValue = 0.0;
}
while (*PP>='0' && *PP<='9') {
TokenNumberValue *= 10;
TokenNumberValue += *PP-'0';
PP++;
}
if (CurrentToken != NUMBER) PP++;
}
return CurrentToken;
}
void SetSource(char *s)
{
pSource = s;
PP = pSource;
GetToken(); // bestimme schon einmal das erste Token vorweg
}
double Error(const char *s)
{
return puts(s);
}
|
Aufruf
Extrem vereinfacht auch der Aufruf. Der erste Parameter ist der zu interpretierende String. Das Ergebnis wird einfach nach per printf ausgegeben. Der Inhalt der Datei main.cpp sieht so aus:
#include <stdio.h>
#include "parser.h"
#include "lex.h"
int main(int argc, char* argv[])
{
double Wert;
SetSource(argv[1]);
Wert = Expression();
printf("%f\n", Wert);
return 0;
}
|
Übersetzt wurde das Ganze durch den Aufruf:
gcc main.cpp parser.cpp lex.cppBeim Aufruf ist darauf zu achten, dass der Ausdruck in Anführungszeichen steht. Sonst könnte sich die Shell für die Sterne interessieren.
./a.out "12+3*2" 18.000000