implement analyse function

anlyises the parse results to build a tree for deterministic parser
generation

4 files changed, 166 insertions, 1 deletions

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 <assert.h>
+#include <string.h>
+
+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 <stdbool.h>
+
+/* 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;
 }