From f32c7682d6fa5f2e794a9819354037658849fb61 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Tue, 6 Oct 2015 14:59:45 -0400 Subject: [PATCH] Started reworking the grammar to use an item stack to build the syntax trees --- source/libparse/ast.c | 203 +++++++++++++++++++++++++++++++++++++ source/libparse/grammar.c | 20 ++-- source/libparse/lexer.c | 17 ++-- source/libparse/libparse.h | 156 ++++++++++++++++++++++------ source/libparse/parser.c | 64 ++++++------ source/libparse/tree.c | 9 +- source/sclpl/codegen.c | 19 ++-- source/sclpl/main.c | 6 +- source/sclpl/ops.c | 39 +++---- source/sclpl/pprint.c | 30 +++--- 10 files changed, 423 insertions(+), 140 deletions(-) create mode 100644 source/libparse/ast.c diff --git a/source/libparse/ast.c b/source/libparse/ast.c new file mode 100644 index 0000000..b27eb3f --- /dev/null +++ b/source/libparse/ast.c @@ -0,0 +1,203 @@ +#include + +AST* Require(char* name) +{ + (void)name; + return NULL; +} + +char* require_name(AST* req) +{ + (void)req; + return NULL; +} + +AST* Def(char* name, AST* value) +{ + (void)name; + (void)value; + return NULL; +} + +char* def_name(AST* def) +{ + (void)def; + return NULL; +} + +AST* def_value(AST* def) +{ + (void)def; + return NULL; +} + +AST* Ann(char* name, AST* value) +{ + (void)name; + (void)value; + return NULL; +} + +char* ann_name(AST* ann) +{ + (void)ann; + return NULL; +} + +AST* ann_value(AST* ann) +{ + (void)ann; + return NULL; +} + +AST* IfExpr(AST* cond, AST* bthen, AST* belse) +{ + (void)cond; + (void)bthen; + (void)belse; + return NULL; +} + +AST* ifexpr_condition(AST* ifexpr) +{ + (void)ifexpr; + return NULL; +} + +AST* ifexpr_branch_then(AST* ifexpr) +{ + (void)ifexpr; + return NULL; +} + +AST* ifexpr_branch_else(AST* ifexpr) +{ + (void)ifexpr; + return NULL; +} + +AST* Func(AST* args, AST* body) +{ + (void)args; + (void)body; + return NULL; +} + +AST* func_args(AST* func) +{ + (void)func; + return NULL; +} + +AST* func_body(AST* func) +{ + (void)func; + return NULL; +} + +AST* Block(void) +{ + return NULL; +} + +void block_append(AST* expr) +{ + (void)expr; +} + +size_t block_size(AST* block) +{ + (void)block; + return NULL; +} + +AST* block_get(size_t index) +{ + (void)index; + return NULL; +} + +AST* String(char* val) +{ + (void)val; + return NULL; +} + +char* string_value(AST* val) +{ + (void)val; + return NULL; +} + +AST* Symbol(char* val) +{ + (void)val; + return NULL; +} + +char* symbol_value(AST* val) +{ + (void)val; + return NULL; +} + +AST* Char(uint32_t val) +{ + (void)val; + return NULL; +} + +uint32_t char_value(AST* val) +{ + (void)val; + return 0; +} + +AST* Integer(intptr_t val) +{ + (void)val; + return NULL; +} + +intptr_t integer_value(AST* val) +{ + (void)val; + return 0; +} + +AST* Float(double val) +{ + (void)val; + return NULL; +} + +double float_value(AST* val) +{ + (void)val; + return 0.0; +} + +AST* Bool(bool val) +{ + (void)val; + return NULL; +} + +bool bool_value(AST* val) +{ + (void)val; + return false; +} + +AST* Ident(char* val) +{ + (void)val; + return NULL; +} + +char ident_value(AST* val) +{ + (void)val; + return 0; +} + diff --git a/source/libparse/grammar.c b/source/libparse/grammar.c index d718048..5b48b0f 100644 --- a/source/libparse/grammar.c +++ b/source/libparse/grammar.c @@ -21,7 +21,7 @@ static void fn_stmnt(Parser* p); AST* toplevel(Parser* p) { - AST* p_tree = NULL; + AST* tree = NULL; try { if (accept_str(p, T_ID, "require")) require(p); @@ -33,38 +33,36 @@ AST* toplevel(Parser* p) definition(p); else expression(p); - //p_tree = get_tree(p); + //tree = get_tree(p); } catch(ParseException) { /* Do nothing, the tree is bad */ } - return p_tree; + return tree; } static void require(Parser* p) { - //size_t mrk = mark(p); - expect(p, T_STRING); + shifttok(p, T_STRING); expect(p, T_END); - //reduce(p, mrk); + //reduce(Require); } static void type_annotation(Parser* p) { - //size_t mrk = mark(p); - expect(p, T_ID); + shifttok(p, T_ID); type(p); expect(p, T_END); - //reduce(p, mrk); + //reduce(Annotation); } +/*****************************************************************************/ + static void type_definition(Parser* p) { - //size_t mrk = mark(p); expect(p, T_ID); expect_str(p, T_ID, "is"); type(p); expect(p, T_END); - //reduce(p, mrk); } static void type(Parser* p) { diff --git a/source/libparse/lexer.c b/source/libparse/lexer.c index 07aea58..1392e28 100644 --- a/source/libparse/lexer.c +++ b/source/libparse/lexer.c @@ -34,35 +34,35 @@ static Tok* Token(TokType type) return tok; } -Tok* TextTok(TokType type, char* text) +static Tok* TextTok(TokType type, char* text) { Tok* tok = Token(type); tok->value.text = dupstring(text); return tok; } -Tok* CharTok(uint32_t val) +static Tok* CharTok(uint32_t val) { Tok* tok = Token(T_CHAR); tok->value.character = val; return tok; } -Tok* IntTok(intptr_t val) +static Tok* IntTok(intptr_t val) { Tok* tok = Token(T_INT); tok->value.integer = val; return tok; } -Tok* FloatTok(double val) +static Tok* FloatTok(double val) { Tok* tok = Token(T_FLOAT); tok->value.floating = val; return tok; } -Tok* BoolTok(bool val) +static Tok* BoolTok(bool val) { Tok* tok = Token(T_BOOL); tok->value.boolean = val; @@ -114,7 +114,7 @@ static char* dup(Parser* ctx, size_t start_idx, size_t len) { return str; } -static void fetchline(Parser* ctx) { +void fetchline(Parser* ctx) { int c; size_t capacity = 8; size_t index = 0; @@ -142,11 +142,6 @@ static void fetchline(Parser* ctx) { } } -void skipline(Parser* ctx) -{ - fetchline(ctx); -} - static char* read_string(Parser* ctx) { size_t capacity = 8; size_t index = 0; diff --git a/source/libparse/libparse.h b/source/libparse/libparse.h index 05f41b7..3499d43 100644 --- a/source/libparse/libparse.h +++ b/source/libparse/libparse.h @@ -18,8 +18,6 @@ /* Token Types *****************************************************************************/ -#if 1 - typedef enum { T_ID, T_CHAR, T_INT, T_FLOAT, T_BOOL, T_STRING, T_LBRACE, T_RBRACE, T_LBRACK, T_RBRACK, T_LPAR, T_RPAR, T_COMMA, T_SQUOTE, T_DQUOTE, T_END, T_END_FILE @@ -39,26 +37,121 @@ typedef struct { } value; } Tok; -#endif - /* AST Types *****************************************************************************/ +typedef enum ASTType { + AST_REQ, AST_DEF, AST_ANN, AST_IF, AST_FUNC, AST_STRING, AST_SYMBOL, + AST_CHAR, AST_INT, AST_FLOAT, AST_BOOL, AST_IDENT +} ASTType; + +typedef struct AST { + ASTType type; + union { + /* Require Node */ + struct { + char* name; + } req; + /* Definition Node */ + struct { + char* name; + struct AST* value; + } def; + /* Annotation Node */ + struct { + char* name; + struct AST* value; + } ann; + /* If Expression */ + struct { + struct AST* cond; + struct AST* bthen; + struct AST* belse; + } ifexpr; + /* Function */ + struct { + struct AST* args; + struct AST* body; + } func; + /* Code Block */ + vec_t block; + /* String */ + char* stringval; + /* Symbol */ + char* symbolval; + /* Character */ + uint32_t charval; + /* Integer */ + intptr_t intval; + /* Float */ + double floatval; + /* Bool */ + bool boolval; + /* Ident */ + char* idval; + } data; +} AST; + +/* Require */ +AST* Require(char* name); +char* require_name(AST* req); + +/* Definition */ +AST* Def(char* name, AST* value); +char* def_name(AST* def); +AST* def_value(AST* def); + +/* Annotation */ +AST* Ann(char* name, AST* value); +char* ann_name(AST* def); +AST* ann_value(AST* def); + +/* If Expression */ +AST* IfExpr(AST* cond, AST* bthen, AST* belse); +AST* ifexpr_condition(AST* ifexpr); +AST* ifexpr_branch_then(AST* ifexpr); +AST* ifexpr_branch_else(AST* ifexpr); + +/* Function */ +AST* Func(AST* args, AST* body); +AST* func_args(AST* func); +AST* func_body(AST* func); + +/* Code Block */ +AST* Block(void); +void block_append(AST* expr); +size_t block_size(AST* block); +AST* block_get(size_t index); + +/* String */ +AST* String(char* val); +char* string_value(AST* val); + +/* Symbol */ +AST* Symbol(char* val); +char* symbol_value(AST* val); + +/* Character */ +AST* Char(uint32_t val); +uint32_t char_value(AST* val); + +/* Integer */ +AST* Integer(intptr_t val); +intptr_t integer_value(AST* val); + +/* Float */ +AST* Float(double val); +double float_value(AST* val); + +/* Bool */ +AST* Bool(bool val); +bool bool_value(AST* val); + +/* Ident */ +AST* Ident(char* val); +char ident_value(AST* val); /* Lexer and Parser Types *****************************************************************************/ -//typedef enum { -// T_ID, T_CHAR, T_INT, T_FLOAT, T_BOOL, T_STRING, T_LBRACE, T_RBRACE, T_LBRACK, -// T_RBRACK, T_LPAR, T_RPAR, T_COMMA, T_SQUOTE, T_DQUOTE, T_END, T_END_FILE -//} TokenType; -// -//typedef struct { -// TokenType type; -// const char* file; -// size_t line; -// size_t col; -// void* value; -//} Token; - DECLARE_EXCEPTION(ParseException); typedef struct { @@ -68,25 +161,12 @@ typedef struct { FILE* input; char* prompt; Tok* tok; - vec_t* tokbuf; + vec_t* stack; } Parser; -typedef enum { - ATOM, - TREE -} ASTTag; - -typedef struct { - ASTTag tag; - union { - Tok* tok; - vec_t* vec; - } ptr; -} AST; - // Lexer routines Tok* gettoken(Parser* ctx); -void skipline(Parser* ctx); +void fetchline(Parser* ctx); // Parser routines Parser* parser_new(char* p_prompt, FILE* input); @@ -99,18 +179,28 @@ bool accept(Parser* p_parser, TokType type); bool accept_str(Parser* p_parser, TokType type, const char* p_text); bool expect(Parser* p_parser, TokType type); bool expect_str(Parser* p_parser, TokType type, const char* p_text); +Tok* shifttok(Parser* parser, TokType type); + +//size_t stack_push(Parser* ctx, AST* node); +//AST* stack_pop(Parser* ctx); +//AST* stack_get(Parser* ctx, int index); + + + //size_t mark(Parser* p_parser); //void reduce(Parser* p_parser, size_t mark); //AST* get_tree(Parser* p_parser); //void insert(Parser* p_parser, TokType type, char* value); +#if 0 // AST Routines AST* tree_convert(AST* p_tree); -AST* tree_new(ASTTag tag, void* p_obj); +AST* tree_new(ASTType tag, void* p_obj); AST* tree_get_child(AST* p_tree, size_t idx); void* tree_get_val(AST* p_tree); void* tree_get_child_val(AST* p_tree, size_t idx); bool tree_is_formtype(AST* p_tree, const char* val); +#endif // Grammar Routines AST* toplevel(Parser* p); diff --git a/source/libparse/parser.c b/source/libparse/parser.c index fedff91..ba81c40 100644 --- a/source/libparse/parser.c +++ b/source/libparse/parser.c @@ -15,7 +15,7 @@ static void parser_free(void* obj) { if ((NULL != parser->tok) && (&tok_eof != parser->tok)) { mem_release(parser->tok); } - mem_release(parser->tokbuf); + mem_release(parser->stack); } Parser* parser_new(char* prompt, FILE* input) @@ -27,7 +27,7 @@ Parser* parser_new(char* prompt, FILE* input) parser->input = input; parser->prompt = prompt; parser->tok = NULL; - parser->tokbuf = vec_new(0); + parser->stack = vec_new(0); return parser; } @@ -54,8 +54,10 @@ void parser_resume(Parser* parser) { mem_release(parser->tok); parser->tok = NULL; } - vec_clear(parser->tokbuf); - skipline(parser); + vec_clear(parser->stack); + /* We ignore the rest of the current line and attempt to start parsing + * again on the next line */ + fetchline(parser); } void error(Parser* parser, const char* text) @@ -66,12 +68,23 @@ void error(Parser* parser, const char* text) throw_msg(ParseException, text); } +Tok* shifttok(Parser* parser, TokType type) +{ + Tok* tok = NULL; + if (peek(parser)->type == type) { + vec_push_back(parser->stack, parser->tok); + parser->tok = NULL; + } else { + error(parser, "Unexpected token"); + } + return tok; +} + bool accept(Parser* parser, TokType type) { bool ret = false; if (peek(parser)->type == type) { - vec_push_back(parser->tokbuf, tree_new(ATOM, parser->tok)); - parser->tok = NULL; + mem_swap((void**)&(parser->tok), NULL); ret = true; } return ret; @@ -81,8 +94,7 @@ bool accept_str(Parser* parser, TokType type, const char* text) { bool ret = false; if ((peek(parser)->type == type) && (0 == strcmp((char*)(parser->tok->value.text), text))) { - vec_push_back(parser->tokbuf, tree_new(ATOM, parser->tok)); - parser->tok = NULL; + mem_swap((void**)&(parser->tok), NULL); ret = true; } return ret; @@ -110,38 +122,20 @@ bool expect_str(Parser* parser, TokType type, const char* text) return ret; } -size_t mark(Parser* parser) +size_t stack_push(Parser* ctx, AST* node) { - return (vec_size(parser->tokbuf) - 1); + vec_push_back(ctx->stack, node); + return vec_size(ctx->stack)-1; } -void reduce(Parser* parser, size_t mark) +AST* stack_pop(Parser* ctx) { - vec_t* buf = parser->tokbuf; - vec_t* form = vec_new(0); - for(size_t idx = mark; idx < vec_size(buf); idx++) { - AST* tree = mem_retain(vec_at(buf, idx)); - vec_push_back(form, tree); - } - vec_erase(buf, mark, vec_size(buf)-1); - vec_push_back(buf, tree_new(TREE, form)); + return (AST*)vec_pop_back(ctx->stack); } -AST* get_tree(Parser* parser) { - AST* tree = NULL; - if (1 == vec_size(parser->tokbuf)) { - tree = mem_retain(vec_at(parser->tokbuf, 0)); - vec_clear(parser->tokbuf); - } else { - tree = tree_new(TREE, parser->tokbuf); - parser->tokbuf = vec_new(0); - } - return tree; +AST* stack_get(Parser* ctx, int index) +{ + index = (index < 0) ? (vec_size(ctx->stack)+index) : index; + return (AST*)vec_at(ctx->stack, (size_t)index); } -//void insert(Parser* parser, TokType type, char* value) { -// Tok* tok = token(type, strdup(value)); -// AST* tree = tree_new(ATOM, tok); -// vec_push_back(parser->tokbuf, tree); -//} - diff --git a/source/libparse/tree.c b/source/libparse/tree.c index 0bfd375..598dea1 100644 --- a/source/libparse/tree.c +++ b/source/libparse/tree.c @@ -6,6 +6,7 @@ */ #include +#if 0 static void tree_free(void* p_obj) { AST* p_tree = ((AST*)p_obj); if (NULL != p_tree->ptr.tok) { @@ -49,10 +50,10 @@ AST* tree_convert(AST* p_tree) { return p_newtree; } -AST* tree_new(ASTTag tag, void* p_obj) { +AST* tree_new(ASTType tag, void* p_obj) { AST* p_tree = (AST*)mem_allocate(sizeof(AST), &tree_free); - p_tree->tag = tag; - p_tree->ptr.tok = (Tok*)p_obj; + //p_tree->tag = tag; + //p_tree->ptr.tok = (Tok*)p_obj; return p_tree; } @@ -95,4 +96,4 @@ bool tree_is_formtype(AST* p_tree, const char* val) { } return ret; } - +#endif diff --git a/source/sclpl/codegen.c b/source/sclpl/codegen.c index d4d8aae..6968d20 100644 --- a/source/sclpl/codegen.c +++ b/source/sclpl/codegen.c @@ -2,6 +2,7 @@ #include "codegen.h" #include "pprint.h" +#if 0 static void lift_funcs(vec_t* fnlst, AST* tree) { if (tree_is_formtype(tree, "fn")) vec_push_back(fnlst, mem_retain(tree)); @@ -208,16 +209,16 @@ static void emit_footer(FILE* file) { file ); } - +#endif void codegen_csource(FILE* file, vec_t* program) { (void)file; - emit_header(file); - emit_def_placeholders(file, program); - vec_t* funcs = find_fn_literals(program); - emit_fn_declarations(file, funcs); - emit_fn_definitions(file, funcs); - emit_toplevel(file, funcs, program); - mem_release(funcs); - emit_footer(file); + //emit_header(file); + //emit_def_placeholders(file, program); + //vec_t* funcs = find_fn_literals(program); + //emit_fn_declarations(file, funcs); + //emit_fn_definitions(file, funcs); + //emit_toplevel(file, funcs, program); + //mem_release(funcs); + //emit_footer(file); } diff --git a/source/sclpl/main.c b/source/sclpl/main.c index a9a393f..51d3815 100644 --- a/source/sclpl/main.c +++ b/source/sclpl/main.c @@ -120,10 +120,10 @@ static int exec_repl(void) { while(!parser_eof(p_parser)) { AST* p_tree = toplevel(p_parser); if (NULL != p_tree) { - AST* p_ast = tree_convert(p_tree); - pprint_tree(stdout, p_ast, 0); + //AST* p_ast = tree_convert(p_tree); + //pprint_tree(stdout, p_ast, 0); mem_release(p_tree); - mem_release(p_ast); + //mem_release(p_ast); puts("OK."); } else { parser_resume(p_parser); diff --git a/source/sclpl/ops.c b/source/sclpl/ops.c index 30d64ff..4cc4700 100644 --- a/source/sclpl/ops.c +++ b/source/sclpl/ops.c @@ -12,24 +12,25 @@ #include vec_t* ops_parse_file(str_t* in) { - bool failed = false; - FILE* input = (NULL == in) ? stdin : fopen(str_cstr(in), "r"); - Parser* p_parser = parser_new(NULL, input); - vec_t* p_vec = vec_new(0); - while(!parser_eof(p_parser)) { - AST* p_tree = toplevel(p_parser); - if (NULL != p_tree) { - AST* p_ast = tree_convert(p_tree); - mem_release(p_tree); - vec_push_back(p_vec, p_ast); - } else { - parser_resume(p_parser); - failed = true; - } - } - mem_release(p_parser); - if (failed) mem_release(p_vec); - return ((failed) ? NULL : p_vec); + //bool failed = false; + //FILE* input = (NULL == in) ? stdin : fopen(str_cstr(in), "r"); + //Parser* p_parser = parser_new(NULL, input); + //vec_t* p_vec = vec_new(0); + //while(!parser_eof(p_parser)) { + // AST* p_tree = toplevel(p_parser); + // if (NULL != p_tree) { + // AST* p_ast = tree_convert(p_tree); + // mem_release(p_tree); + // vec_push_back(p_vec, p_ast); + // } else { + // parser_resume(p_parser); + // failed = true; + // } + //} + //mem_release(p_parser); + //if (failed) mem_release(p_vec); + //return ((failed) ? NULL : p_vec); + return NULL; } vec_t* ops_deps_file(vec_t* program) { @@ -72,7 +73,7 @@ str_t* ops_syntax_file(str_t* in) { vec_t* program = ops_parse_file(in); if (NULL != program) { for (size_t idx = 0; idx < vec_size(program); idx++) { - pprint_tree(output, (AST*)vec_at(program, idx), 0); + //pprint_tree(output, (AST*)vec_at(program, idx), 0); } mem_release(program); fclose(output); diff --git a/source/sclpl/pprint.c b/source/sclpl/pprint.c index b54cce9..236d685 100644 --- a/source/sclpl/pprint.c +++ b/source/sclpl/pprint.c @@ -83,19 +83,19 @@ void pprint_token(FILE* file, Tok* token, bool print_loc) } -void pprint_tree(FILE* file, AST* tree, int depth) -{ - print_indent(file, depth); - if (tree->tag == ATOM) { - pprint_token(file, tree->ptr.tok, false); - } else { - fputs("(tree", file); - vec_t* p_vec = tree->ptr.vec; - for(size_t idx = 0; idx < vec_size(p_vec); idx++) { - pprint_tree(file, (AST*)vec_at(p_vec, idx), depth+1); - } - print_indent(file, depth); - fputs(")\n", file); - } -} +//void pprint_tree(FILE* file, AST* tree, int depth) +//{ +// print_indent(file, depth); +// if (tree->tag == ATOM) { +// pprint_token(file, tree->ptr.tok, false); +// } else { +// fputs("(tree", file); +// vec_t* p_vec = tree->ptr.vec; +// for(size_t idx = 0; idx < vec_size(p_vec); idx++) { +// pprint_tree(file, (AST*)vec_at(p_vec, idx), depth+1); +// } +// print_indent(file, depth); +// fputs(")\n", file); +// } +//} -- 2.52.0