-
-
Save BimManager/4068a7833accb8c346fea955c9667626 to your computer and use it in GitHub Desktop.
Pratt Parser Calculator in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // (Public domain, created by Ryan Johnson) | |
| // A simple calculator in C using Pratt parsing. | |
| // compile with `cc -lm calc.c` | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <stdarg.h> | |
| #include <inttypes.h> | |
| #include <ctype.h> | |
| #include <math.h> | |
| typedef double f64; | |
| typedef struct { | |
| int type; | |
| f64 num; | |
| } Token; | |
| // The current token. | |
| Token curr; | |
| // Exit with an error. | |
| void error(const char *fmt, ...) { | |
| va_list list; | |
| va_start(list, fmt); | |
| vfprintf(stderr, fmt, list); | |
| fputc('\n', stderr); | |
| exit(1); | |
| } | |
| // Get the next token from stdin. | |
| Token next(void) { | |
| for (;;) { | |
| int c = getchar(); | |
| if (isdigit(c)) { | |
| f64 num = 0; | |
| do num = num * 10 + (c - '0'); | |
| while (isdigit(c = getchar())); | |
| ungetc(c, stdin); | |
| curr.type = 'n'; | |
| curr.num = num; | |
| return curr; | |
| } | |
| if (isspace(c)) | |
| continue; | |
| switch (c) { | |
| case '+': | |
| case '-': | |
| case '*': | |
| case '/': | |
| case '%': | |
| case '^': | |
| case '(': | |
| case ')': | |
| case EOF: | |
| curr.type = c; | |
| return curr; | |
| } | |
| if (isprint(c)) | |
| error("Unexpected character: \"%c\"", (char)c); | |
| else | |
| error("Unexpected character: 0x%2X", (unsigned int)c); | |
| } | |
| } | |
| // Return the current Token as a string. | |
| const char *str_type(void) { | |
| switch (curr.type) { | |
| case '+': | |
| return "'+'"; | |
| case '-': | |
| return "'-'"; | |
| case '*': | |
| return "'*'"; | |
| case '/': | |
| return "'/'"; | |
| case '%': | |
| return "'%'"; | |
| case '^': | |
| return "'^'"; | |
| case 'n': | |
| return "number"; | |
| case '(': | |
| return "'('"; | |
| case ')': | |
| return "')'"; | |
| case EOF: | |
| return "EOF"; | |
| } | |
| return NULL; | |
| } | |
| // Production Rules: | |
| // add: mul (("+" | "-") mul)* ; | |
| // mul: unary (("*" | "/" | "%") unary)* ; | |
| // unary: ("+" | "-")? exp ; | |
| // exp: primary ("^" exp)? ; | |
| // primary: number | "(" add ")" ; | |
| double expr(int rbp); | |
| // Null detonate current token. | |
| // This handles prefix operators. | |
| double nud(void) { | |
| double v; | |
| switch (curr.type) { | |
| case 'n': | |
| v = curr.num; | |
| next(); // skip number | |
| return v; | |
| case '-': | |
| next(); // skip '-' | |
| return -expr(30); | |
| case '(': | |
| next(); // skip '(' | |
| v = expr(0); | |
| if (curr.type != ')') | |
| error("Expected ')', found %s", str_type()); | |
| next(); // skip ')' | |
| return v; | |
| default: | |
| error("Expected '(', '-', number, found %s", str_type()); | |
| } | |
| } | |
| // Left detonate current token. | |
| // This handles infix (and postfix) operators. | |
| double led(double left) { | |
| switch (curr.type) { | |
| case '+': | |
| next(); | |
| return left + expr(10); | |
| case '-': | |
| next(); | |
| return left - expr(10); | |
| case '*': | |
| next(); | |
| return left * expr(20); | |
| case '/': | |
| next(); | |
| return left / expr(20); | |
| case '%': | |
| next(); | |
| return fmod(left, expr(20)); | |
| case '^': | |
| next(); | |
| // This binding power prevents the expr loop from exiting immediately, which is what we | |
| // need for right associative operators. | |
| return pow(left, expr(40 - 1)); | |
| default: | |
| error("Expected operator, found %s", str_type()); | |
| } | |
| } | |
| // Binding power of current infix/postfix operator. | |
| int bp(void) { | |
| switch (curr.type) { | |
| case '+': | |
| case '-': | |
| return 10; | |
| case '*': | |
| case '/': | |
| case '%': | |
| return 20; | |
| case '^': | |
| return 40; | |
| case ')': | |
| case EOF: | |
| return 0; | |
| default: | |
| error("Unexpected token %s", str_type()); | |
| } | |
| } | |
| // Parse expression with the given binding power. | |
| // If we encounter an operator with a binding power >= the given binding | |
| // power, then exit and return the accumulated value. | |
| double expr(int rbp) { | |
| double left = nud(); | |
| while (rbp < bp()) | |
| left = led(left); | |
| return left; | |
| } | |
| int main(void) { | |
| next(); // Initialize first token | |
| printf("%.2f\n", expr(0)); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for this!! -- I found this to be much more readily understood than any of the other Pratt Parser examples I could find.