From 5779b80b4a378ce91295fb6bbd7e2c2f8e7fd007 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Fri, 5 Feb 2021 12:50:48 +0100 Subject: [PATCH 1/1] Initial commit --- .gitignore | 5 +++ Makefile | 15 +++++++++ ast.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ast.h | 32 ++++++++++++++++++ expr.c | 15 +++++++++ parse.y | 52 +++++++++++++++++++++++++++++ scan.l | 25 ++++++++++++++ 7 files changed, 240 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 ast.c create mode 100644 ast.h create mode 100644 expr.c create mode 100644 parse.y create mode 100644 scan.l diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..039961a --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +expr +parse.c +scan.c +*.o +y.tab.h diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..53a8ced --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +CFLAGS:=-Wall -std=c99 -D_XOPEN_SOURCE=700 +YFLAGS:=-d +LFLAGS:=-t + +OBJECTS:=scan.o parse.o expr.o ast.c + +all: expr + +scan.c: scan.l y.tab.h +y.tab.h: parse.c + +expr: $(OBJECTS) + +clean: + $(RM) $(OBJECTS) y.tab.h scan.c parse.c expr diff --git a/ast.c b/ast.c new file mode 100644 index 0000000..b220f5e --- /dev/null +++ b/ast.c @@ -0,0 +1,96 @@ +#include +#include + +#include "ast.h" + +struct ast *ast_alloc() +{ + struct ast *res = malloc(sizeof(struct ast)); + if (res == NULL) { + perror("malloc"); + exit(1); + } + return res; +} + +struct ast *ast_cons(struct ast *el, struct ast *tail) +{ + struct ast *res = ast_alloc(); + res->type = an_cons; + res->data.an_cons.el = el; + res->data.an_cons.tail = tail; + return res; +} + +struct ast *ast_binop(struct ast *l, enum binop op, struct ast *r) +{ + struct ast *res = ast_alloc(); + res->type = an_binop; + res->data.an_binop.l = l; + res->data.an_binop.op = op; + res->data.an_binop.r = r; + return res; +} + +struct ast *ast_int(int integer) +{ + struct ast *res = ast_alloc(); + res->type = an_int; + res->data.an_int = integer; + return res; +} + +static const char *binop_str[] = { + [plus] = "+", + [minus] = "+", + [times] = "+", + [divide] = "+", +}; + +void ast_print(struct ast * ast, FILE *out) +{ + if (ast == NULL) + return; + switch(ast->type) { + case an_binop: + fprintf(out, "("); + ast_print(ast->data.an_binop.l, out); + fprintf(out, "%s", binop_str[ast->data.an_binop.op]); + ast_print(ast->data.an_binop.r, out); + fprintf(out, ")"); + break; + case an_cons: + ast_print(ast->data.an_cons.el, out); + fprintf(out, ";\n"); + ast_print(ast->data.an_cons.tail, out); + break; + case an_int: + fprintf(out, "%d", ast->data.an_int); + break; + default: + fprintf(stderr, "Unsupported AST node\n"); + exit(1); + } +} + +void ast_free(struct ast *ast) +{ + if (ast == NULL) + return; + switch(ast->type) { + case an_binop: + ast_free(ast->data.an_binop.l); + ast_free(ast->data.an_binop.r); + break; + case an_cons: + ast_free(ast->data.an_cons.el); + ast_free(ast->data.an_cons.tail); + break; + case an_int: + break; + default: + fprintf(stderr, "Unsupported AST node\n"); + exit(1); + } + free(ast); +} diff --git a/ast.h b/ast.h new file mode 100644 index 0000000..758d034 --- /dev/null +++ b/ast.h @@ -0,0 +1,32 @@ +#ifndef AST_H +#define AST_H + +#include + +enum binop {plus,minus,times,divide}; +enum ast_type {an_binop, an_cons, an_int}; +struct ast { + enum ast_type type; + union { + struct { + struct ast *l; + enum binop op; + struct ast *r; + } an_binop; + struct { + struct ast *el; + struct ast *tail; + } an_cons; + int an_int; + + } data; +}; + +struct ast *ast_cons(struct ast *el, struct ast *tail); +struct ast *ast_binop(struct ast *l, enum binop op, struct ast *tail); +struct ast *ast_int(int integer); + +void ast_print(struct ast * ast, FILE *out); +void ast_free(struct ast *ast); + +#endif diff --git a/expr.c b/expr.c new file mode 100644 index 0000000..455fa71 --- /dev/null +++ b/expr.c @@ -0,0 +1,15 @@ +#include +#include +#include "ast.h" + +#include "y.tab.h" + +int main() +{ + struct ast *result = NULL; + int r = yyparse(&result); + if (r != 0) + return r; + ast_print(result, stdout); + return 0; +} diff --git a/parse.y b/parse.y new file mode 100644 index 0000000..60d4e0d --- /dev/null +++ b/parse.y @@ -0,0 +1,52 @@ +%{ +#include +#include +#include + +#include "ast.h" +#define YYSTYPE struct ast * + +#include "y.tab.h" + +int yylex(void); + +void yyerror(struct ast **result, const char *str) +{ + fprintf(stderr, "error: %s\n", str); +} + +int yywrap() +{ + return 1; +} + +%} + +%token INTEGER PLUS MINUS TIMES DIVIDE BOPEN BCLOSE SEMICOLON +%parse-param { struct ast **result } + +%% + +start : exprs { *result = $1; } ; + +exprs + : { $$ = NULL; } + | exprs expr SEMICOLON { $$ = ast_cons($2, $1); } + ; + +expr + : expr PLUS fact { $$ = ast_binop($1, plus, $3); } + | expr MINUS fact { $$ = ast_binop($1, minus, $3); } + | fact + ; + +fact + : fact TIMES basic { $$ = ast_binop($1, times, $3); } + | fact DIVIDE basic { $$ = ast_binop($1, divide, $3); } + | basic + ; + +basic + : INTEGER + | BOPEN expr BCLOSE { $$ = $2; } + ; diff --git a/scan.l b/scan.l new file mode 100644 index 0000000..bb34a5b --- /dev/null +++ b/scan.l @@ -0,0 +1,25 @@ +%option noinput +%option nounput +%{ + +#include +#include "ast.h" +#define YYSTYPE struct ast * +#include "y.tab.h" +extern YYSTYPE yylval; + +%} + +%% + +[0-9]+ { yylval = ast_int(atoi(yytext)); return INTEGER; } +\+ return PLUS; +- return MINUS; +\* return TIMES; +\/ return DIVIDE; +\( return BOPEN; +\) return BCLOSE; +\; return SEMICOLON; +[ \n\t] ; + +%% -- 2.20.1