Powoli nadchodzi czas aby rozbudować nasz interpreter o obsługę instrukcji. Zanim jednak to zrobimy wprowadzimy do naszego interpretera drzewo składniowe.
Drzewo składniowe
Definiowane przez nas drzewo składniowe będzie mogło mieć wierzchołki 3 różnych typów – typeCon (osbługa stałych), typeId (obsługa identyfikatorów, zmiennych, funkcji wbudowanych), typeOpr (obsługa operatorów, instrukcji sterujących itp.). W celu dodawania i usuwania wierzchołków z drzewa wykorzystamy cztery funkcje: add_operator, add_identifier, add_constant oraz freeNode. Dodamy również jedną funkcję execute, która będzie odpowiadała za wykonywanie programu zapisanego w drzewie składniowym.
Zapiszmy następujący plik ast.h.
#include "symbol.h" #ifndef AST_H #define AST_H typedef enum { typeCon, typeId, typeOpr } nodeEnum; typedef struct { double value; } conNodeType; typedef struct { Symbol *symbol; } idNodeType; typedef struct { int oper; int nops; struct nodeTypeTag **op; } oprNodeType; typedef struct nodeTypeTag { nodeEnum type; union { conNodeType con; idNodeType id; oprNodeType opr; }; } nodeType; extern void yyerror(char *s); nodeType *add_operator(int oper, int nops, ...); /* operator */ nodeType *add_identifier(Symbol *symbol); /* identifiers */ nodeType *add_constant(double value); /* constants */ void freeNode(nodeType *p); double execute(nodeType *p); #endif
W pliku ast.c wprowadzimy definicje poszczególnych funkcji.
#include <stdlib.h>; #include <stdarg.h>; #include "symbol.h" #include "ast.h" #include "parse.h" nodeType *add_constant(double value) { nodeType *p; if ((p = malloc(sizeof(nodeType))) == NULL) yyerror("out of memory"); p->type = typeCon; p->con.value = value; return p; } nodeType *add_identifier(Symbol *symbol) { nodeType *p; Symbol *s; if ((p = malloc(sizeof(nodeType))) == NULL) yyerror("out of memory"); p->type = typeId; p->id.symbol = symbol; return p; } nodeType *add_operator(int oper, int nops, ...) { va_list ap; nodeType *p; int i; if ((p = malloc(sizeof(nodeType))) == NULL) yyerror("out of memory"); if ((p->opr.op = malloc(nops * sizeof(nodeType))) == NULL) yyerror("out of memory"); p->type = typeOpr; p->opr.oper = oper; p->opr.nops = nops; va_start(ap,nops); for (i=0; i<nops; i++) p->opr.op[i] = va_arg(ap, nodeType*); va_end(ap); return p; } void freeNode(nodeType *p) { int i; if(!p) return; if (p->type == typeOpr) { for (i = 0; i<p->opr.nops; i++) freeNode(p->opr.op[i]); free(p->opr.op); } free(p); } double execute(nodeType *p) { if (!p) return 0; switch(p->type) { case typeCon: return p->con.value; case typeId: return p->id.symbol->u.val; case typeOpr: switch(p->opr.oper) { case '=': p->opr.op[0]->id.symbol->type = symbolVar; return p->op[0]->id.symbol->u.val = execute(p->opr.op[1]); case UMINUS: return -execute(p->opr.op[0]); case '+': return execute(p->opr.op[0]) + execute(p->opr.op[1]); case '-': return execute(p->opr.op[0]) - execute(p->opr.op[1]); case '*': return execute(p->opr.op[0]) * execute(p->opr.op[1]); case '/': return execute(p->opr.op[0]) / execute(p->opr.op[1]); case '@': return (*(p->opr.op[0].id.symbol->u.ptr))(execute(p->opr.op[1])); } } return 0; }
Parser
Wprowadźmy w pliku parse.y zmiany do parsera tak aby wykorzystywał drzewo składniowe.
%{ #include <stdio.h> #include <math.h> #include "symbol.h" #include "ast.h" int yylex(void); void yyerror(char *s ); %} %union { double val; Symbol *sym; nodeType *nPtr; } %start expression_list %token <val> NUM %token <sym> VARIABLE CONST UNDEF BLTIN %type <nPtr> statement expression %left '-' '+' %left '*' '/' %nonassoc UMINUS %% expression_list: expression_list statement '\n' { printf("Result: %f\n",execute($2)); freeNode($2); } | expression_list '\n' { /* allow blank lines */ } | { /* empty string */ } ; statement: expression | VARIABLE '=' expression { $$=add_operator('=', 2, add_identifier($1), $3); } expression: NUM { $$ = add_constant($1); } | VARIABLE { $$ = add_constant($1); } | CONST { $$=add_identifier($1); } | BLTIN '(' expression ')' { $$ = add_operator('@', 2, add_identifier($1), $3);} | '-' expression %prec UMINUS { $$ = add_operator(UMINUS, 1, $2); } | '(' expression ')' { $$=$2; } | expression '+' expression { $$ = add_operator('+',2,$1,$3); } | expression '-' expression { $$ = add_operator('-',2,$1,$3); } | expression '*' expression { $$ = add_operator('*',2,$1,$3); } | expression '/' expression { $$ = add_operator('/',2,$1,$3); } ; %% void yyerror(char *s ) { fprintf (stderr, "%s\n", s); } int yywrap() { return 1; } double sinx(double x) { return sin(x); } double cosx(double x) { return cos(x); } int main (int argc, char **argv) { Symbol *s; add("PI", symbolConst, 3.14159265359); s=add("sin", symbolBltin, 0); s->u.ptr = sinx; s=add("cos", symbolBltin, 0); s->u.ptr = cosx; return yyparse(); }
Lekser
Wprowadźmy też odpowiednie zmiany do pliku scan.l.
%{ #include <stdio.h> #include "symbol.h" #include "ast.h" #include "parse.h" void yyerror(char *s); %} %% [a-zA-Z_][a-zA-Z_0-9]* { Symbol *s; if ( (s = find(yytext)) == NULL ) s = add( yytext, symbolUndef, 0); yylval.sym = s; switch(s->type){ case symbolUndef: return VARIABLE; case symbolConst: return CONST; case symbolBltin: return BLTIN; default: return VARIABLE; } } [0-9]+ { yylval = atof (yytext); return NUM; } (([0-9]+(\.[0-9]*)?)|([0-9]*\.[0-9]+)) { yylval = atof (yytext); return NUM; } [-+()=/*\n] return *yytext; [ \t] ; /* skip whitespace */ . yyerror("invalid character"); %%
Makefile
Ponieważ dodaliśmy do naszego projektu plik ast.c musimy jeszcze zmienić plik Makefile tak aby plik ast.c brał udział w kompilacji.
LEX = flex LFLAGS = YACC = yacc YFLAGS = -d LDFLAGS = -ll OBJ = scan.o parse.o symbol.o ast.o SRC = scan.l parse.y symbol.c ast.c all: interpreter interpreter: $(OBJ) $(CC) $(LDFLAGS) $(CPPFLAGS) $(CFLAGS) $(OBJ) -o [email protected] scan.o: parse.c scan.c: scan.l $(LEX) $(LFLAGS) -o [email protected] $^ parse.c: parse.y $(YACC) $(YFLAGS) -o [email protected] $^ clean: $(RM) *.o scan.c parse.c parse.h interpreter