From 24eeb2825c9f755c92812ec3a257e6709ccb6576 Mon Sep 17 00:00:00 2001 From: katherine Date: Mon, 20 May 2019 19:23:47 -0700 Subject: implement analyse function anlyises the parse results to build a tree for deterministic parser generation --- src/analyse.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/analyse.h | 29 +++++++++++++++++++ src/main.c | 30 +++++++++++++++++++ src/parse.c | 16 ++++++++++- 4 files changed, 166 insertions(+), 1 deletion(-) create mode 100644 src/analyse.c create mode 100644 src/analyse.h diff --git a/src/analyse.c b/src/analyse.c new file mode 100644 index 0000000..9510f5a --- /dev/null +++ b/src/analyse.c @@ -0,0 +1,92 @@ +#include "err.h" +#include "analyse.h" + +#include +#include + +struct analyse_result_s analyse(struct parse_result_s pr) +{ + struct analyse_result_s ar; + struct parse_deftype_s *dtp, *tmp_dtp; + struct parse_var_s *vtp, *tmp_vtp; + struct analyse_tree_s *cur; + unsigned i; + + ar.deftype_tree.branch_count = 0; + ar.deftype_tree.is_terminal = false; + + if (pr.deftypes != NULL) { + HASH_ITER(hh, pr.deftypes, dtp, tmp_dtp) { + cur = &(ar.deftype_tree); + + /* walk down the tree, creating nodes when necessary */ + for (i = 0; dtp->name[i] != '\0'; i++) { + if (cur->branch_count == 0 + || cur->branch_chars[cur->branch_count - 1] + != dtp->name[i] + ) { + cur->branch_count++; + cur->branch_chars[cur->branch_count - 1] = dtp->name[i]; + TRYALLOC(cur->branches[cur->branch_count - 1], 1); + cur = cur->branches[cur->branch_count - 1]; + cur->branch_count = 0; + cur->is_terminal = false; + } else { + cur = cur->branches[cur->branch_count - 1]; + } + } + + cur->is_terminal = true; + strcpy(cur->name, dtp->name); + } + } + + ar.var_tree.branch_count = 0; + ar.var_tree.is_terminal = false; + + if (pr.vars != NULL) { + HASH_ITER(hh, pr.vars, vtp, tmp_vtp) { + cur = &(ar.var_tree); + + /* walk down the tree, creating nodes when necessary */ + for (i = 0; vtp->name[i] != '\0'; i++) { + if (cur->branch_count == 0 + || cur->branch_chars[cur->branch_count - 1] + != vtp->name[i] + ) { + cur->branch_count++; + cur->branch_chars[cur->branch_count - 1] = vtp->name[i]; + TRYALLOC(cur->branches[cur->branch_count - 1], 1); + cur = cur->branches[cur->branch_count - 1]; + cur->branch_count = 0; + cur->is_terminal = false; + } else { + cur = cur->branches[cur->branch_count - 1]; + } + } + + cur->is_terminal = true; + strcpy(cur->name, vtp->name); + } + } + + return ar; +} + +static void sub_recurse_free(struct analyse_tree_s *t) +{ + unsigned i; + + for (i = 0; i < t->branch_count; i++) { + sub_recurse_free(t->branches[i]); + free(t->branches[i]); + } +} + +void analyse_result_wipe(struct analyse_result_s *r) +{ + assert(r != NULL); + + sub_recurse_free(&(r->deftype_tree)); + sub_recurse_free(&(r->var_tree)); +} diff --git a/src/analyse.h b/src/analyse.h new file mode 100644 index 0000000..8e21db7 --- /dev/null +++ b/src/analyse.h @@ -0,0 +1,29 @@ +#ifndef CONFCONF_ANALYSE_H +#define CONFCONF_ANALYSE_H + +#include "tok.h" +#include "parse.h" + +#include + +/* 26 letters * 2 for case + 1 for '_' */ +#define ANALYSE_MAX_BRANCH (26 * 2 + 1) + +struct analyse_tree_s { + bool is_terminal; + char name[TOK_MAX_LEN]; + unsigned branch_count; + char branch_chars[ANALYSE_MAX_BRANCH]; + struct analyse_tree_s *branches[ANALYSE_MAX_BRANCH]; +}; + +struct analyse_result_s { + struct analyse_tree_s deftype_tree; + struct analyse_tree_s var_tree; +}; + +struct analyse_result_s analyse(struct parse_result_s pr); + +void analyse_result_wipe(struct analyse_result_s *r); + +#endif diff --git a/src/main.c b/src/main.c index a101849..0c0e510 100644 --- a/src/main.c +++ b/src/main.c @@ -1,12 +1,34 @@ #include "err.h" #include "opt.h" #include "parse.h" +#include "analyse.h" + +static void print_tree(struct analyse_tree_s *t) +{ + unsigned i; + if (t->is_terminal) + printf("!"); + + if (t->branch_count > 1) + printf("("); + + for (i = 0; i < t->branch_count; i++) { + printf("%c", t->branch_chars[i]); + print_tree(t->branches[i]); + if (t->branch_count > 1 && i < t->branch_count - 1) + printf("|"); + } + + if (t->branch_count > 1) + printf(")"); +} int main(int argc, char **argv) { FILE *fi = stdin; const char *finame = "stdin"; struct parse_result_s pr; + struct analyse_result_s ar; opt_parse(argc, argv); @@ -21,7 +43,15 @@ int main(int argc, char **argv) if (fi != stdin) fclose(fi); + ar = analyse(pr); + + print_tree(&ar.deftype_tree); + puts(""); + print_tree(&ar.var_tree); + puts(""); + parse_result_wipe(&pr); + analyse_result_wipe(&ar); return 0; } diff --git a/src/parse.c b/src/parse.c index ce255bb..16f6355 100644 --- a/src/parse.c +++ b/src/parse.c @@ -338,6 +338,17 @@ static bool sub_parse_rule(void) return true; } +static int sub_sort_deftypes(struct parse_deftype_s *d1, + struct parse_deftype_s *d2) +{ + return strcmp(d1->name, d2->name); +} + +static int sub_sort_vars(struct parse_var_s *v1, struct parse_var_s *v2) +{ + return strcmp(v1->name, v2->name); +} + struct parse_result_s parse(FILE *f, const char *fname) { size_t i, j; @@ -399,7 +410,7 @@ struct parse_result_s parse(FILE *f, const char *fname) for (i = j; fname[i] != '\0' && fname[i] != '.' && i - j < r.hkey_size; i++) { - if (!isalnum(fname[i])) { + if (!isalnum(fname[i]) && fname[i] != '_') { fprintf(stderr, "\e[1m%s:\e[0m ", fname); ERR("no function suffix specified, and could not generate one"); } @@ -417,6 +428,9 @@ struct parse_result_s parse(FILE *f, const char *fname) WARN("no function suffix specified. using `%s`...", r.fun_suf); } + HASH_SORT(r.deftypes, sub_sort_deftypes); + HASH_SORT(r.vars, sub_sort_vars); + return r; } -- cgit v1.2.3