// Recursive parser for the grammar of // arithmetic formulas // // S -> F $ // F -> TE // E -> +TE | -TE // E -> // T -> MG // G -> *MG | /MG // G -> // M -> C | (F) // #include #include #include #include #include #include #include double parseS(); double parseF(); double parseT(); double parseE(double v); double parseM(); double parseG(double v); double parseC(); void syntaxError(); // Tokens in input stream const int NAME_MAXLEN = 128; class LexValue { public: double value; char name[NAME_MAXLEN]; int nameLen; LexValue(): value(0.), nameLen(0) { name[0] = 0; } }; // Token types const int CONSTANT = 0; const int NAME = 1; const int LPAR = 2; const int RPAR = 3; const int PLUS = 4; const int MINUS = 5; const int MULT = 6; const int DIV = 7; const int ENDLINE = 8; const int UNDEFINED = 9; int nextToken(LexValue* v); void skipToken(); void readToken(); char line[1024]; int line_len = 0; char *curpos = line; static int next_token = UNDEFINED; static int next_token_len = 0; static LexValue next_token_value; static bool next_token_read = false; jmp_buf env; int main() { while (true) { setjmp(env); fgets(line, 1022, stdin); line_len = strlen(line); if (line_len > 0 && line[line_len-1] == '\n') { line[line_len-1] = 0; --line_len; } if (line_len > 0 && line[line_len-1] == '\r') { line[line_len-1] = 0; --line_len; } if (line_len == 0) break; line[line_len] = '$'; ++line_len; curpos = line; next_token_read = false; double v = parseS(); printf("=%lf\n", v); } return 0; } int nextToken(LexValue* v) { if (!next_token_read) readToken(); assert(next_token_read); if (v != 0) *v = next_token_value; return next_token; } void skipToken() { if (!next_token_read) readToken(); next_token_read = false; } void readToken() { next_token_read = true; // Skip spaces while (curpos - line < line_len && *curpos != 0 && isspace(*curpos)) ++curpos; if (curpos - line >= line_len || *curpos == 0) { next_token = UNDEFINED; next_token_len = 0; return; } char nextChar = *curpos; ++curpos; next_token_len = 1; switch (nextChar) { case '(': next_token = LPAR; break; case ')': next_token = RPAR; break; case '+': next_token = PLUS; break; case '-': next_token = MINUS; break; case '*': next_token = MULT; break; case '/': next_token = DIV; break; case '$': next_token = ENDLINE; break; default: if (isalpha(nextChar)) { // Name next_token = NAME; const char *nameBeg = curpos-1; while ( curpos - line < line_len && *curpos != 0 && (isalpha(*curpos) || isdigit(*curpos)) ) { ++curpos; ++next_token_len; } assert(curpos - nameBeg == next_token_len); if (next_token_len > NAME_MAXLEN - 1) next_token_len = NAME_MAXLEN - 1; strncpy(next_token_value.name, nameBeg, next_token_len); next_token_value.name[next_token_len] = 0; next_token_value.nameLen = next_token_len; } else if (isdigit(nextChar)) { // Numeric constant next_token = CONSTANT; const char *constBeg = curpos-1; while ( curpos - line < line_len && *curpos != 0 && isdigit(*curpos) ) { ++curpos; ++next_token_len; } if (curpos - line < line_len && *curpos == '.') { // Skip decimal point ++curpos; ++next_token_len; while ( curpos - line < line_len && *curpos != 0 && isdigit(*curpos) ) { ++curpos; ++next_token_len; } } assert(curpos - constBeg == next_token_len); if (next_token_len > NAME_MAXLEN - 1) { next_token_len = NAME_MAXLEN - 1; } strncpy(next_token_value.name, constBeg, next_token_len); next_token_value.name[next_token_len] = 0; next_token_value.nameLen = next_token_len; next_token_value.value = atof(next_token_value.name); } else { next_token = UNDEFINED; } break; } } double parseS() { double v = parseF(); if (nextToken(0) != ENDLINE) syntaxError(); return v; } double parseF() { double v = parseT(); double w = parseE(v); return w; } double parseE(double v) { int next = nextToken(0); if (next == PLUS) { skipToken(); double w = parseT(); double u = v + w; u = parseE(u); return u; } else if (next == MINUS) { skipToken(); double w = parseT(); double u = v - w; u = parseE(u); return u; } else if (next == RPAR || next == ENDLINE) { return v; } else { syntaxError(); } } double parseT() { double v = parseM(); double w = parseG(v); return w; } double parseG(double v) { int next = nextToken(0); if (next == MULT) { skipToken(); double w = parseM(); double u = v * w; u = parseG(u); return u; } else if (next == DIV) { skipToken(); double w = parseM(); double u = v / w; u = parseG(u); return u; } else if ( next == PLUS || next == MINUS || next == RPAR || next == ENDLINE ) { return v; } else { syntaxError(); } } double parseM() { LexValue lval; double v = 0; int next = nextToken(&lval); if (next == CONSTANT) { skipToken(); return lval.value; } else if (next == LPAR) { skipToken(); v = parseF(); if (nextToken(0) != RPAR) syntaxError(); skipToken(); } else if (next == NAME) { skipToken(); int f = (-1); if (strcmp(lval.name, "sin") == 0) f = 0; else if (strcmp(lval.name, "cos") == 0) f = 1; else if (strcmp(lval.name, "sqrt") == 0) f = 2; if (nextToken(0) != LPAR) syntaxError(); skipToken(); v = parseF(); if (nextToken(0) != RPAR) syntaxError(); skipToken(); switch(f) { case 0: v = sin(v); break; case 1: v = cos(v); break; case 2: v = sqrt(v); break; default: printf("Unknown function\n"); } } else { syntaxError(); } return v; } void syntaxError() { printf("Syntax error.\n"); longjmp(env, 0); }