Arithmetic evaluation/C: Difference between revisions
(Copy from main task page) |
m (Added some comments in) |
||
Line 40: | Line 40: | ||
} |
} |
||
/* Will consume a character from the input, |
|||
* (such as +, -, *, etc.) and return it. |
|||
*/ |
|||
char consume_char(const char* string, char c) { |
char consume_char(const char* string, char c) { |
||
if(string[G_STRING_ITERATOR] != c) { |
if(string[G_STRING_ITERATOR] != c) { |
||
Line 48: | Line 51: | ||
} |
} |
||
/* Same as consume_char, except for integers. |
|||
*/ |
|||
int consume_int(const char* string) { |
int consume_int(const char* string) { |
||
int i; |
int i; |
||
Line 55: | Line 60: | ||
} |
} |
||
/* I don't have to pass in the start of the string |
|||
* into atoi, but only where I want it to start |
|||
* scanning for an integer. |
|||
*/ |
|||
i = atoi(string + G_STRING_ITERATOR); |
i = atoi(string + G_STRING_ITERATOR); |
||
while(isdigit(string[G_STRING_ITERATOR])) { |
while(isdigit(string[G_STRING_ITERATOR])) { |
||
Line 156: | Line 165: | ||
} |
} |
||
/* Runs through the AST, evaluating and freeing |
|||
* the tree as it goes. |
|||
*/ |
|||
int evaluate(Expr* expr) { |
int evaluate(Expr* expr) { |
||
int ret; |
int ret; |
Revision as of 06:16, 18 September 2009
This is a LL(1) recursive descent parser. Only performs integer division. There is a function for every non-terminal in the grammar, save add_op and mult_op, which were lumped into term_tail and factor_tail respectively. <lang c>#include "stdlib.h"
- include "stdio.h"
- include "ctype.h"
unsigned int G_STRING_ITERATOR = 0;
/*
* expr := term term_tail * term_tail := add_op term term_tail | e * term := factor factor_tail * factor_tail := mult_op factor factor_tail | e * factor := ( expr ) | number * add_op := + | - * mult_op := * | / */
typedef union {
int terminal; struct expression* expr[2];
} Data;
typedef struct expression {
char op; Data data;
} Expr;
void parse_error(const char* string) {
unsigned int i; fprintf(stderr, "Unexpected symbol '%c' at position %u.\n\n", string[G_STRING_ITERATOR], G_STRING_ITERATOR); fprintf(stderr, "String: '%s'\n", string); fprintf(stderr, "Problem: "); for(i = 0; i < G_STRING_ITERATOR; ++i) { fprintf(stderr, " "); } fprintf(stderr, "^\n"); exit(1);
}
/* Will consume a character from the input,
* (such as +, -, *, etc.) and return it. */
char consume_char(const char* string, char c) {
if(string[G_STRING_ITERATOR] != c) { parse_error(string); } ++G_STRING_ITERATOR; return c;
}
/* Same as consume_char, except for integers.
*/
int consume_int(const char* string) {
int i;
if(!isdigit(string[G_STRING_ITERATOR])) { parse_error(string); }
/* I don't have to pass in the start of the string * into atoi, but only where I want it to start * scanning for an integer. */ i = atoi(string + G_STRING_ITERATOR); while(isdigit(string[G_STRING_ITERATOR])) { ++G_STRING_ITERATOR; } return i;
}
Expr* expression(const char* string);
Expr* factor(const char* string, Expr* expr) {
if(string[G_STRING_ITERATOR] == '(') { expr->op = consume_char(string, '('); expr->data.expr[0] = expression(string); consume_char(string, ')'); } else if(isdigit(string[G_STRING_ITERATOR])) { expr->op = 'd'; expr->data.terminal = consume_int(string); } return expr;
}
Expr* factor_tail(const char* string, Expr* expr) {
Expr* new_expr;
switch(string[G_STRING_ITERATOR]) { case '*': case '/': if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) { exit(1); } if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) { exit(1); } new_expr->op = consume_char(string, string[G_STRING_ITERATOR]); new_expr->data.expr[0] = expr;
new_expr->data.expr[1] = factor(string, new_expr->data.expr[1]); new_expr = factor_tail(string, new_expr); return new_expr; case '+': case '-': case ')': case 0: return expr; default: parse_error(string); }
}
Expr* term(const char* string, Expr* expr) {
if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) { expr = factor(string, expr); expr = factor_tail(string, expr); return expr; } else { parse_error(string); }
}
Expr* term_tail(const char* string, Expr* expr) {
Expr* new_expr;
switch(string[G_STRING_ITERATOR]) { case '+': case '-': if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) { exit(1); } if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) { exit(1); } new_expr->op = consume_char(string, string[G_STRING_ITERATOR]); new_expr->data.expr[0] = expr;
new_expr->data.expr[1] = term(string, new_expr->data.expr[1]); new_expr = term_tail(string, new_expr); return new_expr; case ')': case 0: return expr; default: parse_error(string); }
}
Expr* expression(const char* string) {
Expr* expr;
if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) { if(NULL == (expr = (Expr*)malloc(sizeof(Expr)))) { exit(1); }
expr = term(string, expr); expr = term_tail(string, expr); return expr; } else { parse_error(string); }
}
/* Runs through the AST, evaluating and freeing
* the tree as it goes. */
int evaluate(Expr* expr) {
int ret;
switch(expr->op) { case '(': ret = evaluate(expr->data.expr[0]); free(expr->data.expr[0]); break; case '*': ret = evaluate(expr->data.expr[0]) * evaluate(expr->data.expr[1]) ; free(expr->data.expr[0]); free(expr->data.expr[1]); break; case '/': ret = evaluate(expr->data.expr[0]) / evaluate(expr->data.expr[1]) ; free(expr->data.expr[0]); free(expr->data.expr[1]); break; case '+': ret = evaluate(expr->data.expr[0]) + evaluate(expr->data.expr[1]) ; free(expr->data.expr[0]); free(expr->data.expr[1]); break; case '-': ret = evaluate(expr->data.expr[0]) - evaluate(expr->data.expr[1]) ; free(expr->data.expr[0]); free(expr->data.expr[1]); break; case 'd': ret = expr->data.terminal; break; default: exit(1); } return ret;
}
int main(int argc, char** argv) {
Expr* expr = NULL;
if(argc > 1) { expr = expression(argv[1]); printf("%d\n", evaluate(expr)); free(expr); } return 0;
} </lang>