Genesis commit

4 files changed, 375 insertions, 0 deletions

diff --git a/src/lexer.l b/src/lexer.l
new file mode 100644
index 0000000..3bbfd12
--- /dev/null
+++ b/src/lexer.l
@@ -0,0 +1,34 @@
+%option noinput
+%option nounput
+%option noyywrap
+
+%{
+#include <err.h>
+
+#include "parser.h"
+
+#define YY_USER_ACTION yylloc.first_line = yylloc.last_line = yylineno;
+%}
+
+%%
+
+¬|!     { return NOT;   }
+∧|&&    { return AND;   }
+∨|\|\|  { return OR;    }
+⊻|⊕|XOR { return XOR;   }
+⇒|=>    { return IMPL;  }
+\<=>|⇔  { return EQUIV; }
+\(      { return OPAR;  }
+\)      { return CPAR;  }
+\n      { return EOL;   } /* Only eat one NL for better interactive usage */
+[a-zA-Z] {
+	yylval.ch = *yytext;
+	return IDENT;
+}
+
+[ \t]+ ;
+
+	/* TODO: Swap ‘-’ for name of the input file */
+. { errx(1, "%s:%d: Unrecognized character ‘%c’", "-", yylineno, *yytext); }
+
+%%
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..1457c75
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,206 @@
+#include <ctype.h>
+#include <err.h>
+#include <langinfo.h>
+#include <locale.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "lexer.h"
+#include "parser.h"
+
+#define MAXVARS (26 * 2)
+
+#ifndef __has_builtin
+#	define __has_builtin(x) (0)
+#endif
+
+static bool utf8;
+
+static bool eqnsolve(eqn_t *, uint64_t, uint64_t);
+static int  eqnprint(eqn_t *);
+static void eqnfree(eqn_t *);
+
+static uint64_t
+popcnt(uint64_t n)
+{
+#if __has_builtin(__builtin_popcount)
+	return __builtin_popcount(n);
+#else
+    uint64_t c;
+    for (c = 0; n > 0; n &= n - 1)
+		c++; 
+    return c; 
+#endif
+}
+
+int
+main(int argc, char **argv)
+{
+	setlocale(LC_ALL, "");
+	utf8 = strcmp(nl_langinfo(CODESET), "UTF-8") == 0;
+	if (argc > 1) {
+		if ((yyin = fopen(argv[1], "r")) == NULL)
+			err(1, "fopen: %s", argv[1]);
+	}
+	return yyparse();
+}
+
+void
+astprocess(ast_t a)
+{
+	if (a.eqn == NULL)
+		return;
+
+	enum {
+		TBLVBAR,
+		TBLHBAR,
+		TBLCROS,
+	};
+
+	static const char *symbols_utf8[] = {
+		[TBLVBAR] = "│",
+		[TBLHBAR] = "─",
+		[TBLCROS] = "┼",
+	};
+	static const char *symbols_ascii[] = {
+		[TBLVBAR] = "|",
+		[TBLHBAR] = "-",
+		[TBLCROS] = "+",
+	};
+
+	const char **symtab = utf8 ? symbols_utf8 : symbols_ascii;
+
+	for (int i = 0; i < MAXVARS; i++) {
+		bool set = a.vars & UINT64_C(1)<<i;
+		if (set)
+			printf("%c ", i < 26 ? i + 'A' : i + 'a' - 26);
+	}
+	printf("%s ", symtab[TBLVBAR]);
+	int eqnw = eqnprint(a.eqn);
+	putchar('\n');
+
+	int varcnt = popcnt(a.vars);
+
+	for (int i = 0; i < varcnt*2; i++)
+		fputs(symtab[TBLHBAR], stdout);
+	fputs(symtab[TBLCROS], stdout);
+	for (int i = 0; i <= eqnw; i++)
+		fputs(symtab[TBLHBAR], stdout);
+	putchar('\n');
+
+	for (uint64_t msk = 0; msk < (UINT64_C(1) << varcnt); msk++) {
+		for (int i = varcnt; i --> 0;) {
+			bool bit = msk & 1<<i;
+			printf("%d ", bit);
+		}
+		printf("%s ", symtab[TBLVBAR]);
+		int w = (eqnw & 1) == 0 ? eqnw / 2 : eqnw/2 + 1;
+		printf("% *d\n", w, eqnsolve(a.eqn, a.vars, msk));
+	}
+
+	eqnfree(a.eqn);
+}
+
+
+bool
+eqnsolve(eqn_t *e, uint64_t vars, uint64_t msk)
+{
+	switch (e->type) {
+	case IDENT: {
+		int i = 0, bitnr = islower(e->ch) ? e->ch-'a'+26 : e->ch-'A';
+		for (int j = 0; j < bitnr; j++)
+			i += (bool)(vars & UINT64_C(1)<<j);
+		return msk & UINT64_C(1)<<i;
+	}
+	case OPAR:
+		return eqnsolve(e->rhs, vars, msk);
+	case NOT:
+		return !eqnsolve(e->rhs, vars, msk);
+	case AND:
+		return eqnsolve(e->lhs, vars, msk) && eqnsolve(e->rhs, vars, msk);
+	case OR:
+		return eqnsolve(e->lhs, vars, msk) || eqnsolve(e->rhs, vars, msk);
+	case XOR:
+		return eqnsolve(e->lhs, vars, msk) ^ eqnsolve(e->rhs, vars, msk);
+	case IMPL:
+		return !eqnsolve(e->lhs, vars, msk) || eqnsolve(e->rhs, vars, msk);
+	case EQUIV:
+		return !(eqnsolve(e->lhs, vars, msk) ^ eqnsolve(e->rhs, vars, msk));
+	}
+
+#if __has_builtin(__builtin_unreachable)
+	__builtin_unreachable();
+#else
+	abort();
+#endif
+}
+
+int
+eqnprint(eqn_t *a)
+{
+	typedef struct {
+		const char *s;
+		int w;
+	} sym_t;
+
+	static const sym_t symbols_utf8[] = {
+		[NOT   - NOT] = {"¬", 1},
+		[OR    - NOT] = {"∨", 1},
+		[AND   - NOT] = {"∧", 1},
+		[XOR   - NOT] = {"⊻", 1},
+		[IMPL  - NOT] = {"⇒", 1},
+		[EQUIV - NOT] = {"⇔", 1},
+	};
+	static const sym_t symbols_ascii[] = {
+		[NOT   - NOT] = {"!",   1},
+		[OR    - NOT] = {"||",  2},
+		[AND   - NOT] = {"&&",  2},
+		[XOR   - NOT] = {"^",   1},
+		[IMPL  - NOT] = {"=>",  2},
+		[EQUIV - NOT] = {"<=>", 3},
+	};
+
+	const sym_t *symtab = utf8 ? symbols_utf8 : symbols_ascii;
+
+	switch (a->type) {
+	case IDENT:
+		putchar(a->ch);
+		return 1;
+	case NOT:
+		fputs(symtab[NOT - NOT].s, stdout);
+		return eqnprint(a->rhs) + symtab[NOT - NOT].w;
+	case OPAR: {
+		putchar('(');
+		int w = eqnprint(a->rhs);
+		putchar(')');
+		return w + 2;
+	}
+	}
+
+	sym_t sym = symtab[a->type - NOT];
+	int w = sym.w + 2;
+	w += eqnprint(a->lhs);
+	printf(" %s ", sym.s);
+	w += eqnprint(a->rhs);
+	return w;
+}
+
+void
+eqnfree(eqn_t *e)
+{
+	switch (e->type) {
+	case IDENT:
+		break;
+	case NOT:
+	case OPAR:
+		eqnfree(e->rhs);
+		break;
+	default:
+		eqnfree(e->lhs);
+		eqnfree(e->rhs);
+	}
+	free(e);
+}
diff --git a/src/parser.y b/src/parser.y
new file mode 100644
index 0000000..878a9a5
--- /dev/null
+++ b/src/parser.y
@@ -0,0 +1,111 @@
+%{
+#include <ctype.h>
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "lexer.h"
+#include "parser.h"
+
+static ast_t astmerge(int, ast_t, ast_t);
+static void *xmalloc(size_t);
+static void yyerror(const char *);
+%}
+
+%code requires {
+#include "pinocchio.h"
+}
+
+%union {
+	char  ch;
+	ast_t ast;
+}
+
+%define parse.error verbose
+%locations
+
+/* Very important that NOT is the first token declared!  Code depends on it. */
+
+%start input
+%type  <ast> line exp
+%token <ast> NOT AND OR XOR IMPL EQUIV OPAR CPAR
+%token <ch>  IDENT
+%token EOL
+
+%left OR
+%left AND
+%left XOR
+%left IMPL EQUIV
+%nonassoc NOT
+
+%%
+
+input
+	: %empty
+	| input line { astprocess($2); }
+	;
+
+line
+	:     EOL { $$.eqn = NULL; }
+	| exp EOL { $$ = $1; }
+	;
+
+exp
+	: IDENT {
+		$$.eqn = xmalloc(sizeof(eqn_t));
+		$$.eqn->type = IDENT;
+		$$.eqn->ch  = $1;
+		$$.vars = 1 << (islower($1) ? $1-'a'+26 : $1-'A');
+	}
+	| NOT exp {
+		eqn_t *node = xmalloc(sizeof(eqn_t));
+		node->type = NOT;
+		node->rhs  = $2.eqn;
+		$$.eqn = node;
+		$$.vars = $2.vars;
+	}
+	| OPAR exp CPAR {
+		eqn_t *node = xmalloc(sizeof(eqn_t));
+		node->type = OPAR;
+		node->rhs  = $2.eqn;
+		$$.eqn = node;
+		$$.vars = $2.vars;
+	}
+	| exp AND   exp { $$ = astmerge(AND,   $1, $3); }
+	| exp OR    exp { $$ = astmerge(OR,    $1, $3); }
+	| exp XOR   exp { $$ = astmerge(XOR,   $1, $3); }
+	| exp IMPL  exp { $$ = astmerge(IMPL,  $1, $3); }
+	| exp EQUIV exp { $$ = astmerge(EQUIV, $1, $3); }
+	;
+
+%%
+
+ast_t
+astmerge(int op, ast_t lhs, ast_t rhs)
+{
+	ast_t a = {
+		.eqn  = xmalloc(sizeof(eqn_t)),
+		.vars = lhs.vars | rhs.vars,
+	};
+	a.eqn->type = op;
+	a.eqn->lhs = lhs.eqn;
+	a.eqn->rhs = rhs.eqn;
+	return a;
+}
+
+void *
+xmalloc(size_t n)
+{
+	void *p = malloc(n);
+	if (p == NULL)
+		err(1, "malloc");
+	return p;
+}
+
+void
+yyerror(const char *s)
+{
+	/* TODO: Get filename */
+	fprintf(stderr, "pinocchio: -:%d: %s\n", yylloc.first_line, s);
+	exit(EXIT_FAILURE);
+}
diff --git a/src/pinocchio.h b/src/pinocchio.h
new file mode 100644
index 0000000..0c19def
--- /dev/null
+++ b/src/pinocchio.h
@@ -0,0 +1,24 @@
+#ifndef PINOCCIO_H
+#define PINOCCIO_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+typedef struct eqn {
+	int type;
+	union {
+		struct {
+			struct eqn *lhs, *rhs;
+		};
+		char ch;
+	};
+} eqn_t;
+
+typedef struct {
+	eqn_t    *eqn;
+	uint64_t vars;
+} ast_t;
+
+void astprocess(ast_t);
+
+#endif /* !PINOCCIO_H */