In dieser Aufgabe sollen Sie einen kleinen Interpreter schreiben, für eine einfache Programmiersprache (LL für little language).
Die Sprache LL ist gegeben als abstrakter Syntaxbaum. Es gibt dabei folgende Ausdrücke:
- Zahlenliterale
- Variablen
- Funktionsaufrufe
- Zuweisung an eine Variable
- Binäre Operatoren
- if-else Ausdrücke
- while-Schleifen
Für alle diese stehen structs zur Verfügung. Diese werde in einer union vereinigt. Ein allgemeiner Ausdruck ist schließlich ein struct aus dieser union und einem enum Wert, der anzeigt, welche Daten in der union gerade gespeichert sind.
Ein LL Programm besteht aus einem Array von Funktionsdefinitionen.
Einer LL-Funktion stehen 100 Variablen zur Verfügung, die durchnummeriert sind und in einem Array, der die Umgebung, in der ausgewertet wird darstellt.
Der einzige Datentyp, auf dem LL arbeitet, ist long int.
Sie sollen in dieser Aufgabe zwei Dinge implementiere:
- Destruktorfunktionen für alle Datentypen.
- die Funktion eval für alle Datentypen.
Die jeweilige
eval Funktion erhält folgende Parameter:
- long int* env: einen Array der Länge 100 in dem für die 100 durchnummerierten Variablen Werte gespeichert sind.
- FunDef* funs: einen Array der Funktionsdefinition. Um eine Funktion für einen Funktionsaufruf aufzulösen, muss die Funktion mit entsprechenden Namen hier gesucht werden. Ist allerdings einmal der Index der Funktion so gefunden worden, dann kann dieser in dem FunCallExpr-Knoten als compiledNr gespeichert werden. compiledNr ist auf -1 gesetzt, wenn der Index in diesem Array noch nicht bekannt ist.
- int funsNr: die Anzahl der definierten Funktionen.
Hier die zu implementierende Header Datei.
#ifndef LL__H
#define LL__H
/** The operators of LL. Note the operator SEQ. It is a sequence of two operators. The result is
the value of the second operand. It is shall work like the comma operator in C.
**/
typedef enum{
ADD, SUB, MULT, DIV, MOD, LT, GT, LE, GE, EQ, NEQ, AND, OR, SEQ
} BinOp;
/** The different types of expressions. **/
typedef enum {
BIN_OP, VAR, LIT, IF_ELSE, WHILE, ASSIGN, FUN_CALL
} ExprType;
struct Expr;
typedef struct{
BinOp op;
struct Expr* left;
struct Expr* right;
} BinExpr;
typedef struct {
unsigned int varNr;
}VariableExpr;
typedef struct {
long int value;
} LiteralExpr;
typedef struct {
unsigned int varNr;
struct Expr* rhs;
}AssignExpr;
typedef struct{
struct Expr* cond;
struct Expr* ifCase;
struct Expr* elseCase;
} IfElseExpr;
typedef struct {
struct Expr* cond;
struct Expr* body;
} WhileExpr;
typedef struct{
char* name;
int compiledNr;
struct Expr** args;
int argsNr;
} FunCallExpr;
union ExprUnion{
BinExpr binExpr;
VariableExpr variableExpr;
LiteralExpr literalExpr;
AssignExpr assignExpr;
IfElseExpr ifElseExpr;
WhileExpr whileExpr;
FunCallExpr funCallExpr;
};
struct Expr{
ExprType type;
union ExprUnion expr;
};
typedef struct Expr Expression;
typedef struct{
char* name;
int* args;
int argsNr;
struct Expr* body;
} FunDef;
typedef struct{
FunDef* funs;
int funsNr;
} Program;
typedef union {Program prog;Expression* expr;} ParseResult;
/** constructor und destructor functions. **/
void deleteExpr(struct Expr* this);
Expression* newBinExpr(BinOp op,struct Expr* left, struct Expr* right);
void deleteBinExpr(BinExpr binExpr);
Expression* newVariableExpr(unsigned int varNr);
Expression* newLiteralExpr(long int value);
Expression* newIfElseExpr(struct Expr* cond, struct Expr* ifCase, struct Expr* elseCase);
void deleteIfElseExpr(IfElseExpr expr);
Expression* newWhileExpr(struct Expr* cond, struct Expr* body);
void deleteWhileExpr(WhileExpr expr);
Expression* newAssignExpr(unsigned int varNr,struct Expr* rhs);
void deleteAssignExpr(AssignExpr expr);
Expression* newAddExpr(struct Expr* left, struct Expr* right);
Expression* newSubExpr(struct Expr* left, struct Expr* right);
Expression* newMultExpr(struct Expr* left, struct Expr* right);
Expression* newDivExpr(struct Expr* left, struct Expr* right);
Expression* newModExpr(struct Expr* left, struct Expr* right);
Expression* newLtExpr(struct Expr* left, struct Expr* right);
Expression* newGtExpr(struct Expr* left, struct Expr* right);
Expression* newLeExpr(struct Expr* left, struct Expr* right);
Expression* newGeExpr(struct Expr* left, struct Expr* right);
Expression* newEqExpr(struct Expr* left, struct Expr* right);
Expression* newNeqExpr(struct Expr* left, struct Expr* right);
Expression* newAndExpr(struct Expr* left, struct Expr* right);
Expression* newOrExpr(struct Expr* left, struct Expr* right);
Expression* newSeqExpr(struct Expr* left, struct Expr* right);
Expression* newFunCallExpr(char* name, Expression** args, int argsNr);
void deleteFunCallExpr(FunCallExpr binExpr);
long int eval(Expression* this, long int* env, FunDef* funs, int funsNr);
long int evalBinOp(BinExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalVariableExpr(VariableExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalLiteralExpr(LiteralExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalIfElseExpr(IfElseExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalWhileExpr(WhileExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalAssignExpr(AssignExpr expr, long int* env,FunDef* funs, int funsNr);
long int evalFunCallExpr(FunCallExpr* expr, long int* env,FunDef* funs, int funsNr);
#endif
Ein kleiner Beispielaufruf der Funktionen:
#include "LL.h"
int main(){
long int env[] = {0,0,0,0,0,0,0,0,0,0,0,0,0};
struct Expr* e1 = newLiteralExpr(42);
printf("%ld\n",eval(e1,env,NULL,0));
deleteExpr(e1);
struct Expr* e5 = newIfElseExpr(newGtExpr(newLiteralExpr(4),newLiteralExpr(0)),newLiteralExpr(42),newDivExpr(newLiteralExpr(1),newLiteralExpr(0)));
printf("%ld\n",eval(e5,env,NULL,0));
deleteExpr(e5);
}
Anbei finden Sie auch einen Lexer und einem Parser, mit dem ein Quelltext gelesen und der entsprechende anstrakte Syntaxbaum erzeugt wird. Diese sind mit den Tools flex und bison (oder lex und yacc zu bauen.) Das beigelegte Makefile beschreibt, wie diese aufgerufen werden.
Zusammen mit dem Programm LLInterpreter.h erhalten Sie so einen interaktiven Interpreter für die Programmiersprache LL. (Achtung: moin in main änderrn.)
Hier ein kleines LL Programm, das die Syntax exemplarisch zeigt:
fun doppelt(X42){
2 * X42
}
fun fac(X1){
if (X1<=0){1}else{X1*fac(X1-1)}
}
fun fac2(X1){
X2 = 1;
while (X1!=0){
X2 = X2*X1;
X1 = X1 -1
};
X2
}
fun fib(X1){
if(X1<=1){
X1
}else{
fib(X1-2)+fib(X1-1)
}
}
Mit dem Kommandozeilenprogramm
LLInterpreter können Sie eine LL-Datei laden und dann dann Ausdrücke auswerten lassen. Hier eine kleine Beispielsession zur Arbeit mit dem LLInterpreter.
panitz@panitz-ThinkPad-T430:~/ll$ ./LLInterpreter test3.ll
parsing file test3.ll
Welcome. Type :? for help.
>: :?
Commands:
:q quit the programm
:l list defined functions
:? this help
1+1 evaluate expression
>: :l
doppelt
fac
>: 1+1
2
>: fac(doppelt(3))
720
>: :q
panitz@panitz-ThinkPad-T430:~/ll$
Subato
