Predictive Parser
// Build with: | |
// gcc calc.c -o calc -lm -Wall | |
// | |
// Run with: | |
// ./calc 'ln((1+2)(3+4))' | |
#include <ctype.h> | |
#include <math.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
// Grammar: | |
// | |
// Expression = Terms { ( '+' | '-' ) Terms } | |
// Terms = Primary { '(' Expression ')' } | |
// Primary = 'ln' Primary | |
// | '(' Expression ')' | |
// | CONST | |
enum NodeType { LN, ADD, SUB, MUL, CONST }; | |
struct AstNode { | |
enum NodeType type; | |
double value; | |
struct AstNode *children[2]; | |
}; | |
double eval(struct AstNode *node) { | |
struct AstNode **c = node->children; | |
switch (node->type) { | |
case LN: return log(eval(c[0])); | |
case ADD: return eval(c[0]) + eval(c[1]); | |
case SUB: return eval(c[0]) - eval(c[1]); | |
case MUL: return eval(c[0]) * eval(c[1]); | |
case CONST: return node->value; | |
default: abort(); | |
} | |
} | |
void freeAst(struct AstNode *node) { | |
struct AstNode **c = node->children; | |
switch (node->type) { | |
case ADD: case SUB: case MUL: freeAst(c[1]); | |
case LN: freeAst(c[0]); | |
default: free(node); | |
} | |
} | |
// Tokens: LN, '(', ')', ADD, SUB, CONST, END | |
typedef int Token; | |
const Token END = -1; | |
Token next(const char **s) { | |
while (isspace(**s)) (*s)++; // Skip spaces | |
if (**s == 0) return END; // End of input | |
if (isdigit(**s)) { // Real numbers | |
while (isdigit(**s)) (*s)++; | |
if (**s == '.') (*s)++; | |
while (isdigit(**s)) (*s)++; | |
return CONST; | |
} | |
// Fixed tokens | |
struct { const char *s; int t; } fixed[] = { | |
{"ln", LN}, {"(", '('}, {")", ')'}, | |
{"+", ADD}, {"-", SUB}, | |
}; | |
for (int i = 0; i < sizeof(fixed)/sizeof(fixed[0]); i++) { | |
if (strncmp(*s, fixed[i].s, strlen(fixed[i].s)) == 0) { | |
*s += strlen(fixed[i].s); | |
return fixed[i].t; | |
} | |
} | |
fprintf(stderr, "Unexpected '%c'\n", **s); | |
exit(1); | |
} | |
Token peek(const char **s) { | |
while (isspace(**s)) (*s)++; // Skip spaces | |
const char *initial = *s; | |
Token t = next(s); | |
*s = initial; // Rollback | |
return t; | |
} | |
void expect(const char **s, Token t) { | |
if (peek(s) != t) { | |
if (**s == 0) | |
fprintf(stderr, "Unexpected EOF\n"); | |
else | |
fprintf(stderr, "Unexpected '%c'\n", **s); | |
exit(1); | |
} | |
next(s); | |
} | |
struct AstNode* parseExpression(const char **s); | |
struct AstNode* parsePrimary(const char **s) { | |
struct AstNode *n = malloc(sizeof(*n)); | |
switch (peek(s)) { | |
case LN: | |
n->type = next(s); | |
n->children[0] = parsePrimary(s); | |
break; | |
case '(': | |
expect(s, '('); | |
n = parseExpression(s); | |
expect(s, ')'); | |
break; | |
case CONST: | |
n->value = atof(*s); | |
n->type = next(s); | |
break; | |
default: | |
expect(s, CONST); // Exits | |
} | |
return n; | |
} | |
struct AstNode* parseTerms(const char **s) { | |
struct AstNode *n = parsePrimary(s); | |
while (peek(s) == '(') { | |
struct AstNode *rhs = malloc(sizeof(*rhs)); | |
rhs->children[0] = n; | |
rhs->type = MUL; | |
expect(s, '('); | |
rhs->children[1] = parseExpression(s); | |
expect(s, ')'); | |
n = rhs; | |
} | |
return n; | |
} | |
struct AstNode* parseExpression(const char **s) { | |
struct AstNode *n = parseTerms(s); | |
while (peek(s) == ADD || peek(s) == SUB) { | |
struct AstNode *rhs = malloc(sizeof(*rhs)); | |
rhs->children[0] = n; | |
rhs->type = next(s); | |
rhs->children[1] = parseTerms(s); | |
n = rhs; | |
} | |
return n; | |
} | |
int main(int argc, const char **argv) { | |
if (argc != 2) { | |
printf("Usage: %s EXPRESSION", argv[0]); | |
exit(1); | |
} | |
const char **s = &(argv[1]); | |
struct AstNode *ast = parseExpression(s); | |
expect(s, END); | |
printf("%lf\n", eval(ast)); | |
freeAst(ast); | |
} |
Copyright 2018 Ryan O'Leary | |
Permission is hereby granted, free of charge, to any person obtaining a copy of | |
this software and associated documentation files (the "Software"), to deal in | |
the Software without restriction, including without limitation the rights to | |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies | |
of the Software, and to permit persons to whom the Software is furnished to do | |
so, subject to the following conditions: | |
The above copyright notice and this permission notice shall be included in all | |
copies or substantial portions of the Software. | |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
SOFTWARE. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment