From 60493a315417e996238f24f4375ecef945898fea Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 4 Sep 2024 01:37:29 +0200 Subject: Genesis commit --- src/lexer.l | 34 ++++++++++ src/main.c | 206 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/parser.y | 111 ++++++++++++++++++++++++++++++ src/pinocchio.h | 24 +++++++ 4 files changed, 375 insertions(+) create mode 100644 src/lexer.l create mode 100644 src/main.c create mode 100644 src/parser.y create mode 100644 src/pinocchio.h (limited to 'src') 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 + +#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 +#include +#include +#include +#include +#include +#include +#include +#include + +#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)< 0;) { + bool bit = msk & 1<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)<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 +#include +#include +#include + +#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 line exp +%token NOT AND OR XOR IMPL EQUIV OPAR CPAR +%token 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 +#include + +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 */ -- cgit v1.2.3