Initial commit

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
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 (file)
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 (file)
index 0000000..b220f5e
--- /dev/null
+++ b/ast.c
@@ -0,0 +1,96 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#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 (file)
index 0000000..758d034
--- /dev/null
+++ b/ast.h
@@ -0,0 +1,32 @@
+#ifndef AST_H
+#define AST_H
+
+#include <stdio.h>
+
+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 (file)
index 0000000..455fa71
--- /dev/null
+++ b/expr.c
@@ -0,0 +1,15 @@
+#include <stdlib.h>
+#include <stdio.h>
+#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 (file)
index 0000000..60d4e0d
--- /dev/null
+++ b/parse.y
@@ -0,0 +1,52 @@
+%{
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#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 (file)
index 0000000..bb34a5b
--- /dev/null
+++ b/scan.l
@@ -0,0 +1,25 @@
+%option noinput
+%option nounput
+%{
+
+#include <stdio.h>
+#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]  ;
+
+%%