calc

Simple math expression parser.
git clone git://git.amin.space/calc.git
Log | Files | Refs | LICENSE

calc.c (12545B)

      1 #include <assert.h>
      2 #include <ctype.h>
      3 #include <inttypes.h>
      4 #include <stdbool.h>
      5 #include <stddef.h>
      6 #include <stdint.h>
      7 #include <stdio.h>
      8 #include <stdlib.h>
      9 
     10 #define global_variable static
     11 
     12 struct BufHdr {
     13     size_t cap;
     14     size_t len;
     15     uint8_t buf[];
     16 };
     17 
     18 void *cmalloc(size_t num_bytes) {
     19     void *ptr = malloc(num_bytes);
     20     if (!ptr) {
     21         fprintf(stderr, "cmalloc failed\n");
     22         exit(1);
     23     }
     24     return ptr;
     25 }
     26 
     27 void *crealloc(void *ptr, size_t num_bytes) {
     28     ptr = realloc(ptr, num_bytes);
     29     if (!ptr) {
     30         fprintf(stderr, "crealloc failed\n");
     31         exit(1);
     32     }
     33     return ptr;
     34 }
     35 
     36 #define buf__hdr(b) ((struct BufHdr *)(void *)((uint8_t *)(b) - offsetof(struct BufHdr, buf)))
     37 #define buf_cap(b) ((b) ? buf__hdr(b)->cap : 0)
     38 #define buf_len(b) ((b) ? buf__hdr(b)->len : 0)
     39 
     40 #define buf__must_grow(b, n) (buf_len(b) + (n) >= buf_cap(b))
     41 #define buf__maybe_grow(b, n) (buf__must_grow((b), (n)) ? (b) = buf__grow((b), buf_len(b) + (n), sizeof(*(b))) : 0)
     42 #define buf_push(b, x) (buf__maybe_grow((b), 1), (b)[buf__hdr(b)->len++] = (x))
     43 
     44 #define MAX(x, y) ((x) >= (y) ? (x) : (y))
     45 
     46 void *buf__grow(void *buf, size_t new_length, size_t element_size) {
     47     size_t new_cap = MAX(1 + (2 * buf_cap(buf)), new_length);
     48     assert(new_cap >= new_length);
     49     size_t new_size = offsetof(struct BufHdr, buf) + (new_cap * element_size);
     50     struct BufHdr *new_hdr = NULL;
     51     if (buf) {
     52         new_hdr = crealloc(buf__hdr(buf), new_size);
     53     } else {
     54         new_hdr = cmalloc(new_size);
     55         new_hdr->len = 0;
     56     }
     57     new_hdr->cap = new_cap;
     58     return new_hdr->buf;
     59 }
     60 
     61 void buf_test(void) {
     62     int *buf = NULL;
     63     assert(buf_len(buf) == 0);
     64     for (size_t i = 0; i < 1000; ++i) {
     65         buf_push(buf, i);
     66     }
     67     assert(buf_len(buf) == 1000);
     68     for (size_t i = 0; i < buf_len(buf); ++i) {
     69         //printf("%d, ", buf[i]);
     70     }
     71     //printf("\n");
     72 }
     73 
     74 #define TOKEN_LIST            \
     75     X(TOKEN_NONE,       "")   \
     76     X(TOKEN_OP_ADD,     "+")  \
     77     X(TOKEN_OP_SUB,     "-")  \
     78     X(TOKEN_OP_BIN_OR,  "|")  \
     79     X(TOKEN_OP_BIN_XOR, "^")  \
     80     X(TOKEN_OP_MUL,     "*")  \
     81     X(TOKEN_OP_DIV,     "/")  \
     82     X(TOKEN_OP_MOD,     "%")  \
     83     X(TOKEN_OP_SHIFT_L, "<<") \
     84     X(TOKEN_OP_SHIFT_R, ">>") \
     85     X(TOKEN_OP_BIN_AND, "&")  \
     86     X(TOKEN_OP_BIN_NOT, "~")  \
     87     X(TOKEN_PAREN_L,    "(")  \
     88     X(TOKEN_PAREN_R,    ")")  \
     89     X(TOKEN_INT,        "")   \
     90                               \
     91     X(TOKEN__KIND_COUNT, "")
     92 
     93 enum TokenKind {
     94 #define X(kind, glyph) kind,
     95     TOKEN_LIST
     96 #undef X
     97 };
     98 
     99 char *TokenKindNames[] = {
    100 #define X(kind, glyph) [kind] = #kind,
    101     TOKEN_LIST
    102 #undef X
    103 };
    104 
    105 char *TokenKindGlyphs[] = {
    106 #define X(kind, glyph) [kind] = glyph,
    107     TOKEN_LIST
    108 #undef X
    109 };
    110 
    111 #undef TOKEN_LIST
    112 
    113 char *token_kind_glyph(enum TokenKind k) {
    114     assert(k >= TOKEN_NONE && k < TOKEN_INT);
    115     assert((size_t)k <= (sizeof TokenKindGlyphs / sizeof TokenKindGlyphs[0]));
    116     return TokenKindGlyphs[k];
    117 }
    118 
    119 char *token_kind_name(enum TokenKind k) {
    120     assert(k >= TOKEN_NONE && k < TOKEN__KIND_COUNT);
    121     assert((size_t)k <= (sizeof TokenKindNames / sizeof TokenKindNames[0]));
    122     return TokenKindNames[k];
    123 }
    124 
    125 typedef struct Token {
    126     enum TokenKind kind;
    127     uint64_t val;
    128 } Token;
    129 
    130 global_variable char *g_stream;
    131 
    132 #define ERROR() assert(false && "error")
    133 
    134 void print_token(struct Token token) {
    135     bool has_val = token.kind == TOKEN_INT;
    136     if (has_val) {
    137         printf("T: %s: %" PRIu64 "\n", token_kind_name(token.kind), token.val);
    138     } else {
    139         printf("T: %s\n", token_kind_name(token.kind));
    140     }
    141 }
    142 
    143 char *lex_next_token(Token *out_t) {
    144     assert(out_t);
    145 
    146     // TODO: bounds check cursor advances
    147     char *cursor = g_stream;
    148 
    149     while (*cursor == ' ') {
    150         cursor++;
    151     }
    152 
    153     switch(*cursor) {
    154         case '0':
    155         case '1':
    156         case '2':
    157         case '3':
    158         case '4':
    159         case '5':
    160         case '6':
    161         case '7':
    162         case '8':
    163         case '9': {
    164             uint64_t val = 0;
    165             while (isdigit(*cursor)) {
    166                 val *= 10;
    167                 val += *cursor++ - '0';
    168             }
    169             out_t->kind = TOKEN_INT;
    170             out_t->val = val;
    171             break;
    172         }
    173         case '<':
    174             cursor++;
    175             if (*cursor == '<') {
    176                 out_t->kind = TOKEN_OP_SHIFT_L;
    177                 cursor++;
    178             } else {
    179                 ERROR();
    180             }
    181             break;
    182         case '>':
    183             cursor++;
    184             if (*cursor == '>') {
    185                 out_t->kind = TOKEN_OP_SHIFT_R;
    186                 cursor++;
    187             } else {
    188                 ERROR();
    189             }
    190             break;
    191         case '+': out_t->kind = TOKEN_OP_ADD;     cursor++; break;
    192         case '-': out_t->kind = TOKEN_OP_SUB;     cursor++; break;
    193         case '|': out_t->kind = TOKEN_OP_BIN_OR;  cursor++; break;
    194         case '^': out_t->kind = TOKEN_OP_BIN_XOR; cursor++; break;
    195         case '*': out_t->kind = TOKEN_OP_MUL;     cursor++; break;
    196         case '/': out_t->kind = TOKEN_OP_DIV;     cursor++; break;
    197         case '%': out_t->kind = TOKEN_OP_MOD;     cursor++; break;
    198         case '&': out_t->kind = TOKEN_OP_BIN_AND; cursor++; break;
    199         case '~': out_t->kind = TOKEN_OP_BIN_NOT; cursor++; break;
    200         case '(': out_t->kind = TOKEN_PAREN_L;    cursor++; break;
    201         case ')': out_t->kind = TOKEN_PAREN_R;    cursor++; break;
    202         case '\0':
    203             out_t->kind = TOKEN_NONE;
    204             break;
    205         default:
    206             printf("ERROR: '%c' %i\n", *cursor, (int)*cursor);
    207             ERROR();
    208             break;
    209     }
    210 
    211     return cursor;
    212 }
    213 
    214 bool token_is_kind(Token t, enum TokenKind kind) {
    215     return t.kind == kind;
    216 }
    217 
    218 Token token_peek(void) {
    219     Token t = {0};
    220     lex_next_token(&t);
    221     return t;
    222 }
    223 
    224 Token token_consume(void) {
    225     Token t = {0};
    226     g_stream = lex_next_token(&t);
    227     return t;
    228 }
    229 
    230 bool token_consume_kind(enum TokenKind kind) {
    231     Token t = token_peek();
    232     if (token_is_kind(t, kind)) {
    233         token_consume();
    234         return true;
    235     } else {
    236         return false;
    237     }
    238 }
    239 
    240 Token token_require_kind(enum TokenKind kind) {
    241     Token t = token_consume();
    242     if (!token_is_kind(t, kind)) {
    243         ERROR();
    244     }
    245     return t;
    246 }
    247 
    248 void lex_test(void) {
    249     char *source = "+123<<>>4+   ~994";
    250     printf("lex_test: '%s'\n", source);
    251     g_stream = source;
    252     Token t = token_consume();
    253     while (t.kind) {
    254         print_token(t);
    255         t = token_consume();
    256     }
    257 }
    258 
    259 enum ExprKind {
    260     EXPR_NONE,
    261     EXPR_OPERAND,
    262     EXPR_UNARY,
    263     EXPR_BINARY,
    264 };
    265 
    266 bool is_unary_op(enum TokenKind o) {
    267     return o == TOKEN_OP_SUB || o == TOKEN_OP_BIN_NOT;
    268 }
    269 
    270 bool is_mul_op(enum TokenKind o) {
    271     return o == TOKEN_OP_MUL || o == TOKEN_OP_DIV || o == TOKEN_OP_MOD || o == TOKEN_OP_SHIFT_L || o == TOKEN_OP_SHIFT_R || o == TOKEN_OP_BIN_AND;
    272 }
    273 
    274 bool is_add_op(enum TokenKind o) {
    275     return o == TOKEN_OP_ADD || o == TOKEN_OP_SUB || o == TOKEN_OP_BIN_OR || o == TOKEN_OP_BIN_XOR;
    276 }
    277 
    278 typedef struct Expr Expr;
    279 
    280 struct Expr {
    281     enum ExprKind kind;
    282     enum TokenKind op;
    283     Expr *left;
    284     Expr *right;
    285     int32_t operand;
    286 };
    287 
    288 Expr *expr_alloc(void) {
    289     Expr *e = malloc(sizeof(Expr));
    290     *e = (Expr) {0};
    291     return e;
    292 }
    293 
    294 Expr *expr_unary(enum TokenKind o, Expr *u) {
    295     assert(is_unary_op(o));
    296     Expr *e = expr_alloc();
    297     *e = (Expr) {
    298         .kind = EXPR_UNARY,
    299         .op = o,
    300         .left = u,
    301     };
    302     return e;
    303 }
    304 
    305 Expr *expr_binary(enum TokenKind o, Expr *l, Expr *r) {
    306     assert(is_mul_op(o) || is_add_op(o));
    307     Expr *e = expr_alloc();
    308     *e = (Expr) {
    309         .kind = EXPR_BINARY,
    310         .op = o,
    311         .left = l,
    312         .right = r,
    313     };
    314     return e;
    315 }
    316 
    317 void print_expr(Expr *e) {
    318     assert(e);
    319 
    320     char *op = token_kind_glyph(e->op);
    321 
    322     if (e->kind != EXPR_OPERAND) {
    323         printf("(");
    324     }
    325 
    326     switch (e->kind) {
    327         case EXPR_OPERAND:
    328             printf("%i", e->operand);
    329             break;
    330         case EXPR_UNARY:
    331             printf("%s ", op);
    332             print_expr(e->left);
    333             break;
    334         case EXPR_BINARY:
    335             printf("%s ", op);
    336             print_expr(e->left);
    337             printf(" ");
    338             print_expr(e->right);
    339             break;
    340         case EXPR_NONE: // fallthrough
    341         default:
    342             ERROR();
    343             break;
    344     }
    345 
    346     if (e->kind != EXPR_OPERAND) {
    347         printf(")");
    348     }
    349 }
    350 
    351 int32_t parse_number(void) {
    352     Token t = token_require_kind(TOKEN_INT);
    353     return t.val;
    354 }
    355 
    356 Expr *parse_expr_operand(void) {
    357     Expr *e = expr_alloc();
    358     *e = (Expr) {
    359         .operand = parse_number(),
    360         .kind = EXPR_OPERAND,
    361     };
    362     return e;
    363 }
    364 
    365 Expr *parse_expr(void);
    366 
    367 Expr *parse_expr_grouping(void) {
    368     if (token_consume_kind(TOKEN_PAREN_L)) {
    369         Expr *e = parse_expr();
    370         token_require_kind(TOKEN_PAREN_R);
    371         return e;
    372     } else {
    373         return parse_expr_operand();
    374     }
    375 }
    376 
    377 Expr *parse_expr_unary(void) {
    378     if (is_unary_op(token_peek().kind)) {
    379         enum TokenKind op = token_consume().kind;
    380         return expr_unary(op, parse_expr_unary());
    381     } else {
    382         return parse_expr_grouping();
    383     }
    384 }
    385 
    386 Expr *parse_expr_mul(void) {
    387     Expr *e = parse_expr_unary();
    388     while (is_mul_op(token_peek().kind)) {
    389         enum TokenKind op = token_consume().kind;
    390         e = expr_binary(op, e, parse_expr_unary());
    391     }
    392     return e;
    393 }
    394 
    395 Expr *parse_expr_add(void) {
    396     Expr *e = parse_expr_mul();
    397     while (is_add_op(token_peek().kind)) {
    398         enum TokenKind op = token_consume().kind;
    399         e = expr_binary(op, e, parse_expr_mul());
    400     }
    401 
    402     return e;
    403 }
    404 
    405 Expr *parse_expr(void) {
    406     return parse_expr_add();
    407 }
    408 
    409 int32_t eval_expr(Expr *e) {
    410     assert(e);
    411 
    412     switch (e->kind) {
    413         case EXPR_OPERAND:
    414             return e->operand;
    415             break;
    416         case EXPR_UNARY: {
    417             int32_t val = eval_expr(e->left);
    418             switch (e->op) {
    419                 case TOKEN_OP_SUB:
    420                     return -val;
    421                     break;
    422                 case TOKEN_OP_BIN_NOT:
    423                     return ~val;
    424                     break;
    425                 default:
    426                     ERROR();
    427                     break;
    428             }
    429         } break;
    430         case EXPR_BINARY: {
    431             int32_t val1 = eval_expr(e->left);
    432             int32_t val2 = eval_expr(e->right);
    433 
    434             switch (e->op) {
    435                 case TOKEN_OP_ADD:
    436                     return val1 + val2;
    437                     break;
    438                 case TOKEN_OP_SUB:
    439                     return val1 - val2;
    440                     break;
    441                 case TOKEN_OP_BIN_OR:
    442                     return val1 | val2;
    443                     break;
    444                 case TOKEN_OP_BIN_XOR:
    445                     return val1 ^ val2;
    446                     break;
    447                 case TOKEN_OP_MUL:
    448                     return val1 * val2;
    449                     break;
    450                 case TOKEN_OP_DIV:
    451                     if (val2 == 0) {
    452                         ERROR();
    453                     }
    454                     return val1 / val2;
    455                     break;
    456                 case TOKEN_OP_MOD:
    457                     return val1 % val2;
    458                     break;
    459                 case TOKEN_OP_SHIFT_L:
    460                     return val1 << val2;
    461                     break;
    462                 case TOKEN_OP_SHIFT_R:
    463                     return val1 >> val2;
    464                     break;
    465                 case TOKEN_OP_BIN_AND:
    466                     return val1 & val2;
    467                     break;
    468                 default:
    469                     ERROR();
    470                     break;
    471             }
    472         } break;
    473         case EXPR_NONE: // fallthrough
    474         default:
    475             ERROR();
    476             break;
    477     }
    478     return 0;
    479 }
    480 
    481 // Precedence Climbing
    482 // op_unary = "-" | "~".
    483 // op_mul = "*" | "/" | "%" | "<<" | ">>" | "&".
    484 // op_add = "+" | "-" | "|" | "^".
    485 // expr_operand = number.
    486 // expr_grouping = "(" expr ") | expr_operand."
    487 // expr_unary = ([op_unary] expr_unary) | expr_grouping.
    488 // expr_mul = expr_unary {op_mul expr_unary}.
    489 // expr_add = expr_mul {op_add expr_mul}.
    490 // expr = expr_add.
    491 // number = "0" .. "9" {"0" .. "9"}.
    492 Expr *parse_test(void) {
    493     char *source = "12*34 + 45/56 + ~-25 + ((4+6) / (6+4))";
    494     printf("parse_test: '%s'\n", source);
    495     g_stream = source;
    496     Expr *e = parse_expr();
    497     print_expr(e);
    498     printf("\n");
    499     return e;
    500 }
    501 
    502 void eval_test(Expr *e) {
    503     printf("Result: %i\n", eval_expr(e));
    504 }
    505 
    506 int main(void) {
    507     buf_test();
    508     lex_test();
    509     Expr *e = parse_test();
    510     eval_test(e);
    511     return 0;
    512 }