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 $@

scan.o: parse.c

scan.c: scan.l
        $(LEX) $(LFLAGS) -o $@ $^

parse.c: parse.y
        $(YACC) $(YFLAGS) -o $@ $^

clean:
        $(RM) *.o scan.c parse.c parse.h interpreter