diff options
| -rw-r--r-- | Makefile | 25 | ||||
| -rw-r--r-- | README.ORG | 7 | ||||
| -rw-r--r-- | lisp.c | 95 | ||||
| -rw-r--r-- | lisp.h | 37 | ||||
| -rw-r--r-- | lisp.l | 25 | ||||
| -rw-r--r-- | lisp.y | 59 |
6 files changed, 248 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..2dc8a02 --- /dev/null +++ b/Makefile @@ -0,0 +1,25 @@ +LEX = flex +YACC = bison +CC = gcc -g +CFLAGS = -DYYDEBUG=1 +LIBS = -lreadline -lfl -lm + +lisp: lisp.c lisp.tab.o lex.yy.o + $(CC) $(CFLAGS) -o $@ lisp.c lisp.tab.o lex.yy.o $(LIBS) + +lisp.tab.c lisp.tab.h: lisp.y + $(YACC) -d lisp.y + +lex.yy.c: lisp.l lisp.tab.h + $(LEX) --header-file=lex.yy.h lisp.l + +lisp.tab.o: lisp.tab.c + $(CC) $(CFLAGS) -c lisp.tab.c + +lex.yy.o: lex.yy.c + $(CC) $(CFLAGS) -c lex.yy.c + +clean: + rm -f *.o lisp lisp.tab.c lisp.tab.h lex.yy.c lex.yy.h + +.PHONY: clean diff --git a/README.ORG b/README.ORG new file mode 100644 index 0000000..500e08b --- /dev/null +++ b/README.ORG @@ -0,0 +1,7 @@ +* Lisp Interpreter +using lex and yacc + +** Resources: ++ [[https://github.com/AdhamAfis/yacc-parser-tutorial][yacc-parser-tutorial]] ++ [[https://en.wikipedia.org/wiki/S-expression][s-expressions]] ++ [[https://www.bowaggoner.com/writeups/jumpstart/flexbison/jumpstart_flexbison.pdf?utm_source][flex / bison jumpstart]] @@ -0,0 +1,95 @@ +#include <stdlib.h> +#include <stdio.h> +#include <readline/readline.h> +#include <readline/history.h> +#include "lisp.h" +#include "lex.yy.h" +#include "lisp.tab.h" + +value *make_int(int i) { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_INT; + val->as.i = i; + return val; +} + +value *make_double(double d) { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_DOUBLE; + val->as.d = d; + return val; +} + +value *make_symbol(const char *s) { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_SYMBOL; + val->as.sym = s; + return val; +} + +value *make_string(const char *s) { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_STRING; + val->as.str = s; + return val; +} + +value *make_nil() { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_NIL; + return val; +} + +value *cons(value *car, value *cdr) { + value *val = malloc(sizeof(value)); + val->type = VALTYPE_PAIR; + val->as.pair.car = car; + val->as.pair.cdr = cdr; + return val; +} + +void *print_val(value *val){ + char *str; + switch (val->type) { + case VALTYPE_INT: + printf("%d", val->as.i); + break; + + case VALTYPE_DOUBLE: + printf("%f", val->as.d); + break; + + case VALTYPE_SYMBOL: + printf("%s", val->as.sym); + break; + + case VALTYPE_STRING: + printf("\"%s\"", val->as.str); + break; + + case VALTYPE_NIL: + printf("()"); + break; + + case VALTYPE_PAIR: + printf("("); + print_val(val->as.pair.car); + printf(" . "); + print_val(val->as.pair.cdr); + printf(")"); + default: + } + + return val; +} + +int main(void) { + char* line; + while ((line = readline("λ > ")) != NULL) { + if (*line) add_history(line); + yy_scan_string(line); // feed input to Flex/Bison + yyparse(); + free(line); + } + return 0; +} @@ -0,0 +1,37 @@ +#ifndef LISP_H +#define LISP_H + +typedef enum { + VALTYPE_INT, + VALTYPE_DOUBLE, + VALTYPE_SYMBOL, + VALTYPE_STRING, + VALTYPE_NIL, + VALTYPE_PAIR +} val_type; + +typedef struct value value; +struct value { + val_type type; + union { + int i; + double d; + const char *sym; + const char *str; + struct { + value *car; + value *cdr; + } pair; + } as; +}; + +value *make_int(int i); +value *make_double(double d); +value *make_symbol(const char *sym); +value *make_string(const char *str); +value *make_nil(); +value *cons(value *car, value *cdr); + +void *print_val(value *val); + +#endif @@ -0,0 +1,25 @@ +%{ +#include <stdlib.h> +#include "lisp.h" +#include "lisp.tab.h" + +int tcnt = 0; +%} + +%% +[+-]?([0-9]+|([0-9]*\.[0-9]+))([eE][-+]?[0-9]+)? { + yylval.dval = atof(yytext); + printf("%d: NUMBER: %f\n", ++tcnt, yylval.dval); + return NUMBER; + } +[ \t\n]+ { printf("%d: WHITESPACE\n", tcnt); return WHITESPACE; } +"(" { printf("%d: LPAREN\n", ++tcnt); return LPAREN; } +")" { printf("%d: RPAREN\n", ++tcnt); return RPAREN; } +"\." { printf("%d: DOT\n", ++tcnt); return DOT; } +"+" { printf("%d: PLUS\n", ++tcnt); return PLUS; } +"-" { printf("%d: MINUS\n", ++tcnt); return MINUS; } +"*" { printf("%d: MULT\n", ++tcnt); return MULT; } +"/" { printf("%d: DIV\n", ++tcnt); return DIV; } +\".*\" { printf("%d: STRING\n", ++tcnt); return STRING; } +. ; // do nothing +%% @@ -0,0 +1,59 @@ +%{ +#include <stdio.h> +#include <stdlib.h> +#include <math.h> +#include "lisp.h" + +int yylex(void); +int yyerror(const char *s); + +static int is_integer(double x) { + return floor(x) == x && isfinite(x); +} +%} + +%union { + int ival; + double dval; + const char *strval; + value *val; +} +%token <dval> NUMBER +%token <strval> STRING +%token <ival> LPAREN RPAREN DOT WHITESPACE +%token <ival> PLUS MINUS MULT DIV + +%type <val> sexpr atom sexprs + +%start sexprs + +%% +opt_ws: /* matches no whitespace */ + | WHITESPACE; + +sexprs: sexpr + | sexprs opt_ws sexpr; + +sexpr: atom + | LPAREN opt_ws sexpr opt_ws DOT opt_ws sexpr opt_ws RPAREN + { + $$ = cons($3, $7); + print_val($$); + printf("\n"); + }; + +atom: NUMBER + { + if(is_integer($1)) { + $$ = make_int($1); + } else { + $$ = make_double($1); + } + } + | LPAREN opt_ws RPAREN { $$ = make_nil(); } + | STRING { $$ = make_string($1); }; +%% + +int yyerror(const char *s) { + printf("%s\n",s); +} |