From 76c5e747356fea6507c1a47d5a4867e942a04c4b Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Thu, 21 May 2015 12:34:46 -0400 Subject: [PATCH] Initial commit --- Makefile | 24 +++++ source/lexer.l | 45 ++++++++++ source/main.c | 232 ++++++++++++++++++++++++++++++++++++++++++++++++ source/parser.h | 42 +++++++++ 4 files changed, 343 insertions(+) create mode 100644 Makefile create mode 100644 source/lexer.l create mode 100644 source/main.c create mode 100644 source/parser.h diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..fd404ce --- /dev/null +++ b/Makefile @@ -0,0 +1,24 @@ +LD = $(CC) +MAKEDEPEND = $(CPP) -M $(CPPFLAGS) -o $< +CCDEPGEN = -MMD -MF $*.d +CFLAGS = -Wall -Wextra -O3 --std=c99 --pedantic + +SOURCES = $(wildcard source/*.c) + +-include $(SOURCES:.c=.d) + +parser: source/lex.yy.o source/main.o + $(LD) $(LDFLAGS) -o $@ $^ + +%.o : %.c + $(CC) $(CCDEPGEN) $(CFLAGS) -c $< -o $@ + +source/lex.yy.c: source/lexer.l + $(LEX) $(LFLAGS) -o $@ $^ + +clean: + rm -f source/*.o + rm -f source/*.d + rm -f source/lex.yy.c + rm -f parser parser.exe + diff --git a/source/lexer.l b/source/lexer.l new file mode 100644 index 0000000..c2b161c --- /dev/null +++ b/source/lexer.l @@ -0,0 +1,45 @@ +%{ + +#include "parser.h" + +size_t Row = 1; +size_t Column = 1; + +int yywrap(void){ return 1; } + +#define TOKEN(type) \ + puts(#type); return type + +%} + +%% + +[\r]?[\n] Row++; Column = 1; printf(":> "); +[ \t] Column++; +#.*[\r\n]+ Row++; Column = 1; + +"." TOKEN(END); +"," TOKEN(COMMA); +"=" TOKEN(ASSIGN); +":" TOKEN(COLON); +"(" TOKEN(LPAR); +")" TOKEN(RPAR); +"[" TOKEN(LBRACK); +"]" TOKEN(RBRACK); +"{" TOKEN(LBRACE); +"}" TOKEN(RBRACE); + +"self" TOKEN(SELF); +"true"|"false" TOKEN(BOOL); +[0-9]+ TOKEN(NUM); +'[^\\]' TOKEN(CHAR); +\"[^"]*\" TOKEN(STRING); + +[+-]+ TOKEN(BINOP); +[_a-zA-Z][_a-zA-Z0-9]* TOKEN(ID); +[_a-zA-Z][_a-zA-Z0-9]*: TOKEN(KEYW); + +. fprintf(stderr, "Unrecognized Token\n"); exit(1); + +%% + diff --git a/source/main.c b/source/main.c new file mode 100644 index 0000000..fb5bcef --- /dev/null +++ b/source/main.c @@ -0,0 +1,232 @@ +#include +#include +#include +#include +#include +#include "parser.h" + +extern int yylex (void); +extern size_t Row; +extern size_t Column; + +/*****************************************************************************/ +typedef struct AST { + int type; + int num_children; + struct AST* children[]; +} AST; + +AST* Tree(int type, int num_children) { + AST* tree = (AST*)calloc(1, sizeof(AST) * (num_children * sizeof(AST*))); + tree->type = type; + tree->num_children = num_children; + return tree; +} + +void PrintTree(AST* tree, int depth) { + int indent = depth * 2; + printf("%*s(", indent, ""); + printf("%d", tree->type); + if (tree->num_children == 0) { + printf(")\n"); + } else { + printf("\n"); + for (int child = 0; child < tree->num_children; child++) { + PrintTree(tree->children[child], depth+1); + } + + printf("%*s)\n", indent, ""); + } +} + +/*****************************************************************************/ + +int Current = UNKNOWN; + +static void error(const char* msg) { + fprintf(stderr, "Error: %s\n", msg); + exit(1); +} + +static bool accept(int expected) { + if (Current == UNKNOWN) { + Current = yylex(); + } + return (Current == expected); +} + +static bool expect(int expected) { + bool accepted = accept(expected); + if (!accepted) + error("unexpected symbol"); + else + Current = UNKNOWN; + return accepted; +} + +static bool optional(int expected) { + if (accept(expected)) + return expect(expected); + else + return false; +} + +/*****************************************************************************/ + +intptr_t Token_Buffer[1024]; +intptr_t* Token_Stack = Token_Buffer-1; + +void shift(int type) { + int curr = Current; + if (expect(type)) { + *(++Token_Stack) = curr; + } +} + +void reduce(int count) { + int type = *(Token_Stack--); + AST* tree = Tree(type, count); + intptr_t* stack = Token_Stack - (count-1); + for (int i = 0; i < count; i++) { + tree->children[i] = stack[i]; + } + Token_Stack -= count ; + *(++Token_Stack) = (intptr_t)tree; +} + +void shift_reduce(int type, int nchildren) { + shift(type); + reduce(nchildren); +} + +void push_reduce(int type, int nchildren) { + *(++Token_Stack) = type; + reduce(nchildren); +} + +/*****************************************************************************/ + +static void expression(void); +static void keyword_send(void); +static void binary_send(void); +static void unary_send(void); +static void operand(void); +static void messages(void); +static void literal(void); +static void array(void); +static void hashmap(void); + +static void expression(void) { + if (accept(ID)) { + shift_reduce(ID, 0); + if (accept(ASSIGN)) { + expect(ASSIGN); + expression(); + push_reduce(ASSIGN, 2); + } + } else { + keyword_send(); + } + optional(END); +} + +static void keyword_send(void) { + int count = 0; + binary_send(); + while (accept(KEYW)) { + shift_reduce(KEYW,0); + binary_send(); + push_reduce(KEYWORD_PAIR, 2); + count++; + } + if (count > 0) { + push_reduce(KEYWORD_MSG, count); + } +} + +static void binary_send(void) { + unary_send(); + if (accept(BINOP)) { + shift_reduce(BINOP,0); + unary_send(); + push_reduce(BINARY_MSG, 3); + } +} + +static void unary_send(void) { + operand(); + while (accept(ID)) { + shift_reduce(ID, 0); + push_reduce(UNARY_MSG, 2); + } +} + +static void operand(void) { + if (accept(LPAR)) { + expect(LPAR); + expression(); + expect(RPAR); + } else { + literal(); + } +} + +static void literal(void) { + switch (Current) { + case ID: shift_reduce(ID, 0u); break; + case NUM: shift_reduce(NUM, 0u); break; + case SELF: shift_reduce(SELF, 0u); break; + case STRING: shift_reduce(STRING, 0u); break; + case BOOL: shift_reduce(BOOL, 0u); break; + case CHAR: shift_reduce(CHAR, 0u); break; + case LBRACK: array(); break; + case LBRACE: hashmap(); break; + default: error("Invalid literal"); + } +} + +static void array(void) { + int count = 0; + expect(LBRACK); + if (!accept(RBRACK)) { + do { + optional(COMMA); + expression(); + count++; + } while(accept(COMMA)); + } + expect(RBRACK); + push_reduce(ARRAY, count); +} + +static void hashmap(void) { + int count = 0; + expect(LBRACE); + if (!accept(RBRACE)) { + do { + optional(COMMA); + shift_reduce(STRING, 0); + expect(COLON); + expression(); + push_reduce(PAIR, 2); + count++; + } while(accept(COMMA)); + } + expect(RBRACE); + push_reduce(MAP, count); +} + +/*****************************************************************************/ + +int main(int argc, char** argv) { + printf(":> "); + while(true) { + expression(); + printf("stack: %du\n", (int)((Token_Stack - Token_Buffer) + 1)); + /* Print and clear */ + PrintTree((AST*)*Token_Stack, 0); + Token_Stack = Token_Buffer-1; + } + return 0; +} + diff --git a/source/parser.h b/source/parser.h new file mode 100644 index 0000000..292ea85 --- /dev/null +++ b/source/parser.h @@ -0,0 +1,42 @@ +/** + @file parser.h + @brief TODO: Describe this file + */ +#ifndef PARSER_H +#define PARSER_H + +#define UNKNOWN 0 + +#define NUM 1 +#define SELF 2 +#define STRING 3 +#define BOOL 4 +#define CHAR 5 + +#define LPAR 6 +#define RPAR 7 +#define LBRACK 8 +#define RBRACK 9 +#define LBRACE 10 +#define RBRACE 11 + +#define COMMA 12 +#define COLON 13 +#define END 14 +#define BINOP 15 + +#define RETURN 16 +#define ASSIGN 17 +#define ID 18 +#define KEYW 19 + +#define ARRAY 100 +#define MAP 101 +#define PAIR 102 +#define UNARY_MSG 103 +#define BINARY_MSG 104 +#define KEYWORD_MSG 105 +#define KEYWORD_PAIR 106 + +#endif /* PARSER_H */ + -- 2.49.0