diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lexer.l | 34 | ||||
| -rw-r--r-- | src/main.c | 206 | ||||
| -rw-r--r-- | src/parser.y | 111 | ||||
| -rw-r--r-- | src/pinocchio.h | 24 |
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 */ |