From c69929cc501203829082b810bafe75a22947e00c Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Tue, 19 Apr 2022 10:41:32 -0300 Subject: Add viz for symbol tables --- src/main.c | 11 ++++++++++- src/semantic.c | 44 ++++++++++++++++++++++-------------------- src/viz.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 94 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/main.c b/src/main.c index 56c36d7..fc991d2 100644 --- a/src/main.c +++ b/src/main.c @@ -17,6 +17,7 @@ typedef enum ExecMode { PRINT_LEX, PRINT_PARSE, PRINT_SEMANTIC, + PRINT_SYMTABLES, } ExecMode; static ExecMode mode = RUN_NORMAL; @@ -46,12 +47,18 @@ process_source(const StringView *source, const char *file_name) { check_errors(file_name); if (mode == PRINT_PARSE) { viz_ast(roots); + return; } // Symbol table generation and type checking. ParseTree *parse_tree = semantic_analysis(roots); if (mode == PRINT_SEMANTIC) { viz_ast(parse_tree->roots); + return; + } + if (mode == PRINT_SYMTABLES) { + viz_symtables(parse_tree->scopes); + return; } } @@ -116,7 +123,7 @@ print_usage(void) { printf("Usage: %s [options] \n", BIN_NAME); printf("\n"); printf("\t-h \t\tShow usage.\n"); - printf("\t-p [l | p | s]\tPrint mode for [l]exing, [p]arsing or [s]emantic analysis\n"); + printf("\t-p [l|p|s|t]\tPrint mode for [l]exing, [p]arsing, [s]emantic analysis, symbol [t]ables\n"); printf("\n"); } @@ -138,6 +145,8 @@ main(int argc, char *argv[]) { mode = PRINT_PARSE; } else if (optarg[0] == 's' && optarg[1] == '\0') { mode = PRINT_SEMANTIC; + } else if (optarg[0] == 't' && optarg[1] == '\0') { + mode = PRINT_SYMTABLES; } else { print_usage(); return EXIT_FAILURE; diff --git a/src/semantic.c b/src/semantic.c index 06958b9..6c9f290 100644 --- a/src/semantic.c +++ b/src/semantic.c @@ -1,6 +1,7 @@ #include "hashtable.h" typedef struct Scope { + size_t id; struct Scope *parent; HashTable *symbols; HashTable *types; @@ -8,8 +9,7 @@ typedef struct Scope { typedef struct ParseTree { Root *roots; - Scope *global_scope; - Scope *current_scope; + Scope **scopes; } ParseTree; typedef struct Type { @@ -70,6 +70,7 @@ typedef struct Symbol { }; } Symbol; +static size_t scope_gen_id = 0; Symbol * alloc_symval(Node *name, SymbolType type) { @@ -110,6 +111,7 @@ bool type_eq(void *a, void *b) { Scope * alloc_scope(Scope *parent) { Scope *scope = malloc(sizeof(Scope)); + scope->id = scope_gen_id++; scope->parent = parent; scope->symbols = ht_init(sym_hash, sym_eq); scope->types = ht_init(type_hash, type_eq); @@ -216,7 +218,7 @@ find_symbol(Scope *scope, Node *node) { } bool -resolve_type(Scope *scope, Node *node) { +resolve_type(ParseTree *ast, Scope *scope, Node *node) { if (node->expr_type != NULL) { return true; } @@ -224,7 +226,7 @@ resolve_type(Scope *scope, Node *node) { case NODE_BUILTIN: { for (size_t i = 0; i < array_size(node->builtin.args); ++i) { Node *arg = node->builtin.args[i]; - if (!resolve_type(scope, arg)) { + if (!resolve_type(ast, scope, arg)) { return false; } } @@ -311,6 +313,7 @@ resolve_type(Scope *scope, Node *node) { case NODE_FUN: { // Fill up new scope with parameters scope = alloc_scope(scope); + array_push(ast->scopes, scope); // Parameters. for (size_t i = 0; i < array_size(node->fun.param_names); ++i) { @@ -328,14 +331,14 @@ resolve_type(Scope *scope, Node *node) { if (body->type == NODE_BLOCK) { for (size_t i = 0; i < array_size(body->block.expr); ++i) { Node *expr = body->block.expr[i]; - if (!resolve_type(scope, expr)) { + if (!resolve_type(ast, scope, expr)) { return false; } } Node *last_expr = body->block.expr[array_size(body->block.expr) - 1]; node->expr_type = last_expr->expr_type; } else { - if (!resolve_type(scope, body)) { + if (!resolve_type(ast, scope, body)) { return false; } } @@ -350,9 +353,10 @@ resolve_type(Scope *scope, Node *node) { } break; case NODE_BLOCK: { scope = alloc_scope(scope); + array_push(ast->scopes, scope); for (size_t i = 0; i < array_size(node->block.expr); ++i) { Node *expr = node->block.expr[i]; - if (!resolve_type(scope, expr)) { + if (!resolve_type(ast, scope, expr)) { return false; } } @@ -360,16 +364,16 @@ resolve_type(Scope *scope, Node *node) { node->expr_type = last_expr->expr_type; } break; case NODE_IF: { - if (!resolve_type(scope, node->ifexpr.cond)) { + if (!resolve_type(ast, scope, node->ifexpr.cond)) { return false; } - if (!resolve_type(scope, node->ifexpr.expr_true)) { + if (!resolve_type(ast, scope, node->ifexpr.expr_true)) { return false; } Type *type_true = node->ifexpr.expr_true->expr_type; node->expr_type = type_true; if (node->ifexpr.expr_false != NULL) { - if (!resolve_type(scope, node->ifexpr.expr_false)) { + if (!resolve_type(ast, scope, node->ifexpr.expr_false)) { return false; } } @@ -396,10 +400,10 @@ resolve_type(Scope *scope, Node *node) { } break; case NODE_SET: { node->expr_type = &default_types[TYPE_VOID]; - if (!resolve_type(scope, node->set.symbol)) { + if (!resolve_type(ast, scope, node->set.symbol)) { return false; } - if (!resolve_type(scope, node->set.value)) { + if (!resolve_type(ast, scope, node->set.value)) { return false; } Node *symbol = node->set.symbol; @@ -426,7 +430,7 @@ resolve_type(Scope *scope, Node *node) { node->expr_type = &default_types[TYPE_VOID]; // TODO: type inference from right side when not annotated? - if (!resolve_type(scope, node->def.value)) { + if (!resolve_type(ast, scope, node->def.value)) { return false; } Node *symbol = node->def.symbol; @@ -455,7 +459,7 @@ resolve_type(Scope *scope, Node *node) { } break; case NODE_FUNCALL: { Symbol *val = find_symbol(scope, node->funcall.name); - if (!resolve_type(scope, node->funcall.name)) { + if (!resolve_type(ast, scope, node->funcall.name)) { return false; } if (val->type != SYMBOL_FUN) { @@ -470,7 +474,7 @@ resolve_type(Scope *scope, Node *node) { node->expr_type = node->funcall.name->expr_type; for (size_t i = 0; i < array_size(node->funcall.args); ++i) { Node *arg = node->funcall.args[i]; - if (!resolve_type(scope, arg)) { + if (!resolve_type(ast, scope, arg)) { return false; } Node *expected = val->fun.param_types[i]; @@ -490,18 +494,18 @@ ParseTree * semantic_analysis(Root *roots) { ParseTree *parse_tree = malloc(sizeof(ParseTree)); parse_tree->roots = roots; - parse_tree->global_scope = alloc_scope(NULL); - parse_tree->current_scope = parse_tree->global_scope; + array_init(parse_tree->scopes, 0); + Scope *scope = alloc_scope(NULL); + array_push(parse_tree->scopes, scope); // Fill global scope with default types. - HashTable *types = parse_tree->global_scope->types; + HashTable *types = scope->types; for (size_t i = 0; i < sizeof(default_types)/sizeof(Type); ++i) { Type *type = &default_types[i]; ht_insert(types, &type->name, type); } // Fill up global function symbols. - Scope *scope = parse_tree->global_scope; for (size_t i = 0; i < array_size(parse_tree->roots); ++i) { Node *root = parse_tree->roots[i]; if (root->type == NODE_FUN) { @@ -518,7 +522,7 @@ semantic_analysis(Root *roots) { for (size_t i = 0; i < array_size(parse_tree->roots); ++i) { // Fill up symbol tables in proper scope and resolve type of expression // for all elements. - if (!resolve_type(scope, parse_tree->roots[i])) { + if (!resolve_type(parse_tree, scope, parse_tree->roots[i])) { return NULL; } } diff --git a/src/viz.c b/src/viz.c index d519d2c..c3b05f9 100644 --- a/src/viz.c +++ b/src/viz.c @@ -170,3 +170,63 @@ viz_ast(Root *roots) { printf("}\n"); } +void +viz_symtables(Scope **scopes) { + printf("digraph symtables {\n"); + printf("rankdir=RL;\n"); + printf("ranksep=\"0.95 equally\";\n"); + printf("nodesep=\"0.5 equally\";\n"); + printf("overlap=scale;\n"); + for (size_t i = 0; i < array_size(scopes); ++i) { + Scope *scope = scopes[i]; + if (array_size(scope->symbols->pairs) == 0) { + continue; + } + printf("%zu [shape=none,label=<", scope->id); + printf("\n"); + printf(""); + for (size_t j = 0; j < array_cap(scope->symbols->pairs); ++j) { + HashTablePair pair = scope->symbols->pairs[j]; + if (pair.key == NULL) { + continue; + } + Symbol *sym = pair.value; + printf(""); + printf(""); + switch (sym->type) { + case SYMBOL_VAR: { + printf(""); + printf(""); + } break; + case SYMBOL_FUN: { + printf(""); + printf(""); + } break; + } + printf("\n"); + } + printf("
NAMEKINDTYPE
"); + print_node(sym->name); + printf("var"); + print_node(sym->var.type); + printf("fun"); + printf("("); + size_t n_params = array_size(sym->fun.param_types); + for (size_t k = 0; k < n_params; ++k) { + print_node(sym->fun.param_types[k]); + if (k < n_params - 1) { + printf(" "); + } + } + printf(")"); + printf(":"); + print_node(sym->fun.return_type); + printf("
\n"); + printf(">];\n"); + + if (scope->parent != NULL) { + printf("%zu -> %zu\n", scope->id, scope->parent->id); + } + } + printf("}\n"); +} -- cgit v1.2.1