From 30a03f759ec3b34b118237c12f8804e475eac984 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Mon, 3 Jun 2019 22:07:16 -0400 Subject: [PATCH] attempted to implement TDOP --- Makefile | 4 +- example.src | 31 +++++---- src/parser.c | 179 +++++++++++++++++++++++++++----------------------- test/parser.c | 25 ++++++- 4 files changed, 137 insertions(+), 102 deletions(-) diff --git a/Makefile b/Makefile index 2f25fb5..66a11f5 100644 --- a/Makefile +++ b/Makefile @@ -16,8 +16,8 @@ ARFLAGS = rcs MAKEFLAGS = -j # GCC - Enable Sanitizers -CFLAGS += -g -fsanitize=address,undefined -LDFLAGS += -g -fsanitize=address,undefined +#CFLAGS += -g -fsanitize=address,undefined +#LDFLAGS += -g -fsanitize=address,undefined #------------------------------------------------------------------------------ # Build Targets and Rules diff --git a/example.src b/example.src index d52d547..22a606e 100644 --- a/example.src +++ b/example.src @@ -29,23 +29,26 @@ var var_string string = "" var var_intary int[] = [123,321] fun main(args string[]) int { - let foo int = 123 - var bar int = 123 - {123 321} - 123 (123) +# let foo int = 123 +# var bar int = 123 +# {123 321} +# 123 +# ( +# 123 +# ) # foo() # bar(1) # baz(1,2) - if (1) {1} - if 2 {2} - if (3) {3} else {4} - if (4) {5} else if (5) {6} - if (6) {7} else if (7) {8} else {9} - if 123 {10} else if 123 {11} else {12} - fun submain(args string[]) int { - 123 - } - # UFCS call (call regular function like a method) +# if (1) {1} +# if 2 {2} +# if (3) {3} else {4} +# if (4) {5} else if (5) {6} +# if (6) {7} else if (7) {8} else {9} +# if 123 {10} else if 123 {11} else {12} +# fun submain(args string[]) int { +# 123 +# } +# # UFCS call (call regular function like a method) # foo.bar() # foo.bar.baz() # # Struct/Union field access diff --git a/src/parser.c b/src/parser.c index 56828ad..ded14db 100644 --- a/src/parser.c +++ b/src/parser.c @@ -7,7 +7,6 @@ static void definition_list(Parser* p); static AST* definition(Parser* p); static AST* type_definition(Parser* p); static AST* func_definition(Parser* p); -static AST* expression(Parser* p, int level); static AST* constant(Parser* p); static AST* type_expression(Parser* p); static AST* struct_fields(Parser* p); @@ -15,9 +14,14 @@ static AST* expression_block(Parser* p); static AST* if_expression(Parser* p); static AST* identifier(Parser* p); static AST* expr_list(Parser* p, int firstc, int endc); -static AST* prefix_expr(Parser* p); static AST* binary_expr(Parser* p, AST* left); +static AST* expression(Parser* p); +static AST* literal(Parser* p); +static AST* grouping(Parser* p); +static AST* func_call(Parser* p, AST* left); +static AST* dot_call(Parser* p, AST* left); + //#define TRACE #ifdef TRACE static int Indent = 0; @@ -30,15 +34,43 @@ static int Indent = 0; #define parse_exit() #endif -int8_t PrefixOps[T_COUNT] = { - [T_IF] = 1, - ['{'] = 1, - ['('] = 1, +/* Precedence Table + *****************************************************************************/ +enum { /* Define precedence levels(based on C) */ + LVL_NONE, + LVL_LITERAL, + LVL_COMMA, + LVL_ASSIGN, + LVL_TERNARY, + LVL_BOOL_OR, + LVL_BOOL_AND, + LVL_BITWISE_OR, + LVL_BITWISE_XOR, + LVL_BITWISE_AND, + LVL_EQUALITY, + LVL_RELATIONAL, + LVL_BITSHIFT, + LVL_ADD_SUB, + LVL_MUL_DIV, + LVL_PREFIX, + LVL_POSTFIX, }; -int8_t BinaryOps[T_COUNT] = { - ['.'] = 1, - ['('] = 1, +typedef struct { + int level; + AST* (*prefixfn)(Parser* p); + AST* (*infixfn)(Parser* p, AST* left); +} OpRule; + +OpRule PrecedenceTable[T_COUNT] = { + [T_BOOL] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + [T_CHAR] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + [T_STRING] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + [T_INT] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + [T_FLOAT] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + [T_ID] = { .level = LVL_LITERAL, .prefixfn = literal, .infixfn = NULL }, + ['('] = { .level = LVL_POSTFIX, .prefixfn = grouping, .infixfn = func_call }, + ['.'] = { .level = LVL_POSTFIX, .prefixfn = NULL, .infixfn = dot_call }, }; /* Parsing Routines @@ -90,6 +122,13 @@ static Tok* expect_val(Parser* p, TokType type) { return &token; } +static int consume(Parser* p) { + int type = peek(p)->type; + if (!accept(p, type)) + error(p, "Unexpected token"); + return type; +} + /* Grammar Definition *****************************************************************************/ void toplevel(Parser* p) { @@ -154,7 +193,7 @@ static AST* definition(Parser* p) { char* str = strdup(expect_val(p, T_ID)->text); AST* type = type_expression(p); expect(p, '='); - AST* val = expression(p, 1); + AST* val = expression(p); parse_exit(); return Var(str, val, type, SF_CONSTANT); } @@ -191,68 +230,39 @@ static AST* func_definition(Parser* p) { return Var(name, func, type, SF_CONSTANT); } -/* -function parseExpressionAtPrecedence(currentPrecedence) { - expr = parseExpressionAtom() - while op = parseOperator() && op.precedence < currentPrecedence { - if op.rightAssociative { - b = parseExpressionAtPrecedence(op.precedence) - } else { - b = parseExpressionAtPrecedence(op.precedence + 1) - } - expr = OperatorExpression(op, expr, b) - } - return expr + + +static OpRule* get_rule(Parser* p, int toktype) { + return &PrecedenceTable[toktype < 0 ? 0 : toktype]; } -*/ - -static AST* expression(Parser* p, int level) { - AST* left = prefix_expr(p); - int oper = peek(p)->type; - while (BinaryOps[oper] && abs(BinaryOps[oper]) < level) { - AST* right; - expect(p, oper); // consume the operator - if (BinaryOps[oper] < 0) - right = expression(p, level+1); - else - right = expression(p, level); - left = OpCall(oper, left, right); - oper = peek(p)->type; // get next operator + +static AST* parse_precedence(Parser* p, int level) { + /* lookup the rule we're starting with */ + OpRule* rule = get_rule(p, peek(p)->type); + if (!(rule->prefixfn)) + error(p, "expected an expression"); + + /* parse the left operand */ + AST* left = rule->prefixfn(p); + + /* parse infix or postfix operators according to precedence */ + while (level <= get_rule(p, peek(p)->type)->level) { + OpRule* rule = get_rule(p, peek(p)->type); + left = rule->infixfn(p, left); } + return left; } -//static AST* expression(Parser* p) { -// parse_enter(); -// int precedence = PrefixOps[peek(p)->type]; -// AST* left = prefix_expr(p); -// int next = peek(p)->type; -// while (BinaryOps[next] && BinaryOps[next] >= precedence) { -// left = binary_expr(p, left); -// next = peek(p)->type; -// } -// parse_exit(); -// return left; -//} - -static AST* prefix_expr(Parser* p) { +static AST* expression(Parser* p) { + /* start parsing at the lowest possible precedence */ + return parse_precedence(p, LVL_LITERAL); +} + +static AST* literal(Parser* p) { AST* tree = NULL; Tok* tok = peek(p); switch ((int)tok->type) { - case '(': - expect(p, '('); - tree = expression(p, 1); - expect(p, ')'); - break; - case '[': - tree = expr_list(p, '[', ']'); - break; - case '{': - tree = expression_block(p); - break; - case T_IF: - tree = if_expression(p); - break; case T_BOOL: tree = Bool(tok->value.integer); accept(p, tok->type); @@ -277,25 +287,26 @@ static AST* prefix_expr(Parser* p) { accept(p, tok->type); break; default: - error(p, "expected an expression"); + error(p, "expected a primary expression"); } return tree; } -static AST* binary_expr(Parser* p, AST* left) { - AST* exp = NULL; - Tok* tok = peek(p); - switch ((int)tok->type) { - case '(': - exp = Apply(left, expr_list(p, '(', ')')); - break; - case '.': - expect(p, '.'); - AST* field = identifier(p); - exp = left; - break; - } - return exp; +static AST* grouping(Parser* p) { + expect(p, '('); + AST* expr = expression(p); + expect(p, ')'); + return expr; +} + +static AST* func_call(Parser* p, AST* left) { + error(p, "unimplemented"); + return NULL; +} + +static AST* dot_call(Parser* p, AST* left) { + error(p, "unimplemented"); + return NULL; } /* Type Expressions @@ -344,7 +355,7 @@ static AST* expression_block(Parser* p) { } else if (matches(p, T_FUN)) { expr = func_definition(p); } else { - expr = expression(p, 1); + expr = expression(p); } explist_append(list, expr); } @@ -355,10 +366,10 @@ static AST* expression_block(Parser* p) { static AST* if_expression(Parser* p) { AST *cond = 0, *b1 = 0, *b2 = 0; expect(p, T_IF); - cond = expression(p, 1); // condition - b1 = expression(p, 1); // true branch + cond = expression(p); // condition + b1 = expression(p); // true branch if (accept(p, T_ELSE)) { - b2 = expression(p, 1); // false branch + b2 = expression(p); // false branch } return If(cond, b1, b2); } @@ -379,7 +390,7 @@ static AST* expr_list(Parser* p, int firstc, int endc) { expect(p, firstc); AST* list = ExpList(); while (!matches(p, endc)) { - explist_append(list, expression(p, 1)); + explist_append(list, expression(p)); if (!matches(p, endc)) { expect(p, ','); if (matches(p, endc)) diff --git a/test/parser.c b/test/parser.c index 0b1ab76..b0c861b 100644 --- a/test/parser.c +++ b/test/parser.c @@ -3,7 +3,6 @@ Parser TestCtx = {0}; - static int astcmp(AST* a, AST* b) { int result = a->nodetype - b->nodetype; if (result) return result; @@ -12,6 +11,8 @@ static int astcmp(AST* a, AST* b) { case AST_CHAR: case AST_INT: return (a->value.integer - b->value.integer); + case AST_STRING: + return strcmp(a->value.text, b->value.text); } } @@ -33,7 +34,27 @@ int parse(char* text, AST* expect) { } TEST_SUITE(ParserTests) { - TEST(should parse some stuff) { + TEST(should parse an int) { CHECK(!parse("123", Integer(123))); } + + TEST(should parse an bool) { + CHECK(!parse("false", Bool(0))); + } + + TEST(should parse an bool) { + CHECK(!parse("true", Bool(1))); + } + + TEST(should parse a string) { + CHECK(!parse("\"\"", String(""))); + } + + TEST(should parse a grouped expression) { + CHECK(!parse("(123)", Integer(123))); + } + +// TEST(should parse a function call) { +// CHECK(!parse("foo()", Integer(123))); +// } } -- 2.52.0