First commitHEADmaster

Signed-off-by: Mattias Andrée <m@maandree.se>

6 files changed, 248 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..7296458
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,18 @@
+*\#*
+*~
+*.o
+*.a
+*.t
+*.lo
+*.to
+*.su
+*.so
+*.so.*
+*.dll
+*.dylib
+*.gch
+*.gcov
+*.gcno
+*.gcda
+/binary-tree
+/nary-tree
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..1634eae
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,15 @@
+ISC License
+
+© 2026 Mattias Andrée <m@maandree.se>
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..17e29de
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,21 @@
+.POSIX:
+
+CONFIGFILE = config.mk
+include $(CONFIGFILE)
+
+all: binary-tree
+
+.c.o:
+	$(CC) -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+.o:
+	$(CC) -o $@ $< $(LDFLAGS)
+
+clean:
+	-rm -f -- *.o *.a *.lo *.su *.so *.so.* *.gch *.gcov *.gcno *.gcda
+	-rm -f -- binary-tree
+
+.SUFFIXES:
+.SUFFIXES: .o .c
+
+.PHONY: all clean
diff --git a/README b/README
new file mode 100644
index 0000000..25e2559
--- /dev/null
+++ b/README
@@ -0,0 +1,6 @@
+Example code demonstrating how to do operator-precedence
+parsing directly to an abstract syntax tree (rather than
+to prefix or postfix like the shunting yard algorithm,
+which is better for you want to perform the operations
+immediately) with dynamic operator, precedence, and
+associativity definitions.
diff --git a/binary-tree.c b/binary-tree.c
new file mode 100644
index 0000000..c43f59e
--- /dev/null
+++ b/binary-tree.c
@@ -0,0 +1,180 @@
+/* See LICENSE file for copyright and license details. */
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#if defined(__GNUC__)
+# pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
+# pragma GCC diagnostic ignored "-Wsuggest-attribute=pure"
+#endif
+
+
+static char **tokens;
+static size_t ntokens;
+
+
+struct node {
+	int is_operand;
+	const char *symbol;
+	struct node *left;
+	struct node *right;
+};
+
+
+static struct node *
+operand_node(const char *token)
+{
+	struct node *ret = malloc(sizeof(*ret));
+	ret->is_operand = 1;
+	ret->symbol = token;
+	ret->left = NULL;
+	ret->right = NULL;
+	return ret;
+}
+
+
+static struct node *
+operator_node(struct node *left, const char *operator, struct node *right)
+{
+	struct node *ret = malloc(sizeof(*ret));
+	ret->is_operand = 0;
+	ret->symbol = operator;
+	ret->left = left;
+	ret->right = right;
+	return ret;
+}
+
+
+static void
+print_node(struct node *node)
+{
+	if (node->is_operand) {
+		printf("%s", node->symbol);
+	} else {
+		printf("(");
+		print_node(node->left);
+		printf(" %s ", node->symbol);
+		print_node(node->right);
+		printf(")");
+	}
+}
+
+
+static const char *
+next_token(void)
+{
+	static size_t token_i = 0;
+	return token_i == ntokens ? NULL : tokens[token_i++];
+}
+
+
+static struct node *
+parse_operand(void)
+{
+	const char *token = next_token();
+	if (!token)
+		exit(2); /* syntax error */
+	return operand_node(token);
+}
+
+
+static int
+get_precedence(const char *token, int *ltr)
+{
+	int prec = 0;
+	*ltr = 1;
+	if (!strcmp(token, ","))
+		return prec;
+	prec++;
+	*ltr = 0;
+	if (!strcmp(token, "=") || !strcmp(token, "+=") || !strcmp(token, "-=") || !strcmp(token, "*=") ||
+	    !strcmp(token, "%=")  || !strcmp(token, "<<=") || !strcmp(token, ">>=") || !strcmp(token, "&=") ||
+	    !strcmp(token, "^=")  || !strcmp(token, "|="))
+		return prec;
+	prec++;
+	*ltr = 1;
+	if (!strcmp(token, "||"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "&&"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "|"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "^"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "&"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "==") || !strcmp(token, "!="))
+		return prec;
+	prec++;
+	if (!strcmp(token, "<=") || !strcmp(token, "<") || !strcmp(token, ">=") || !strcmp(token, ">"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "<<") || !strcmp(token, ">>"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "+") || !strcmp(token, "-"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "*") || !strcmp(token, "/") || !strcmp(token, "%"))
+		return prec;
+	prec++;
+	*ltr = 0;
+	if (!strcmp(token, "**"))
+		return prec;
+	exit(2);
+}
+
+
+
+static struct node *
+parse_expression_(int min_prec, const char **tokenp)
+{
+	struct node *left, *right;
+	const char *operator;
+	int prec, ltr;
+
+	left = parse_operand();
+	*tokenp = next_token();
+
+	while (*tokenp) {
+		prec = get_precedence(*tokenp, &ltr);
+		if (ltr ? prec <= min_prec : prec < min_prec)
+			break;
+		operator = *tokenp;
+		*tokenp = NULL;
+		right = parse_expression_(prec, tokenp);
+		left = operator_node(left, operator, right);
+		*tokenp = *tokenp ? *tokenp : next_token();
+	}
+
+	return left;
+}
+
+static struct node *
+parse_expression(void)
+{
+	return parse_expression_(-1, &(const char *){NULL});
+}
+
+
+int
+main(int argc, char *argv[])
+{
+	struct node *node;
+	tokens = &argv[1];
+	ntokens = (size_t)argc - 1u;
+
+	if (!(node = parse_expression()))
+		return 1;
+
+	print_node(node);
+	printf("\n");
+	return 0;
+}
diff --git a/config.mk b/config.mk
new file mode 100644
index 0000000..f4adf12
--- /dev/null
+++ b/config.mk
@@ -0,0 +1,8 @@
+PREFIX    = /usr
+MANPREFIX = $(PREFIX)/share/man
+
+CC = c99
+
+CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_GNU_SOURCE
+CFLAGS   =
+LDFLAGS  =