#include <cctype>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <sstream>
#include <vector>
namespace TinyCalc {
// storage of variables
class Var {
private:
double _value;
public:
Var(): _value() { }
~Var() = default;
double get() const { return _value; }
void set(double value) { _value = value; }
};
typedef std::map<std::string, Var> VarTable;
// abstract syntax tree -> storage of "executable"
namespace AST {
class Expr {
protected:
Expr() = default;
public:
virtual ~Expr() = default;
public:
virtual double solve() const = 0;
};
class ExprConst: public Expr {
private:
double _value;
public:
ExprConst(double value): Expr(), _value(value) { }
virtual ~ExprConst() = default;
virtual double solve() const { return _value; }
};
class ExprVar: public Expr {
private:
Var *_pVar;
public:
ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
virtual ~ExprVar() = default;
virtual double solve() const { return _pVar->get(); }
};
class ExprUnOp: public Expr {
protected:
Expr *_pArg1;
protected:
ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
virtual ~ExprUnOp() { delete _pArg1; }
};
class ExprUnOpNeg: public ExprUnOp {
public:
ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
virtual ~ExprUnOpNeg() = default;
virtual double solve() const
{
return -_pArg1->solve();
}
};
class ExprBinOp: public Expr {
protected:
Expr *_pArg1, *_pArg2;
protected:
ExprBinOp(Expr *pArg1, Expr *pArg2):
Expr(), _pArg1(pArg1), _pArg2(pArg2)
{ }
virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
};
class ExprBinOpAdd: public ExprBinOp {
public:
ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpAdd() = default;
virtual double solve() const
{
return _pArg1->solve() + _pArg2->solve();
}
};
class ExprBinOpSub: public ExprBinOp {
public:
ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpSub() = default;
virtual double solve() const
{
return _pArg1->solve() - _pArg2->solve();
}
};
class ExprBinOpMul: public ExprBinOp {
public:
ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpMul() = default;
virtual double solve() const
{
return _pArg1->solve() * _pArg2->solve();
}
};
class ExprBinOpDiv: public ExprBinOp {
public:
ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpDiv() = default;
virtual double solve() const
{
return _pArg1->solve() / _pArg2->solve();
}
};
} // namespace AST
// token class - produced in scanner, consumed in parser
struct Token {
// tokens
enum Tk {
Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
Number, Id,
EOT, Error
};
// token number
Tk tk;
// lexem as floating point number
double number;
// lexem as identifier
std::string id;
// constructors.
explicit Token(Tk tk): tk(tk), number() { }
explicit Token(double number): tk(Number), number(number) { }
explicit Token(const std::string &id): tk(Id), number(), id(id) { }
};
// the scanner - groups characters to tokens
class Scanner {
private:
std::istream &_in;
public:
// constructor.
Scanner(std::istream &in): _in(in) { }
/* groups characters to next token until the first character
* which does not match (or end-of-file is reached).
*/
Token scan()
{
char c;
// skip white space
do {
if (!(_in >> c)) return Token(Token::EOT);
} while (isspace(c));
// classify character and build token
switch (c) {
case '+': return Token(Token::Plus);
case '-': return Token(Token::Minus);
case '*': return Token(Token::Star);
case '/': return Token(Token::Slash);
case '(': return Token(Token::LParen);
case ')': return Token(Token::RParen);
case ';': return Token(Token::Semicolon);
default:
if (isdigit(c)) {
_in.unget(); double value; _in >> value;
return Token(value);
} else if (isalpha(c) || c == '_') {
std::string id(1, c);
while (_in >> c) {
if (isalnum(c) || c == '_') id += c;
else { _in.unget(); break; }
}
return Token(id);
} else {
_in.unget();
return Token(Token::Error);
}
}
}
};
/* parser
*
* This is a recursive descent parser with a look-ahead of one symbol
* and without back-tracking.
* The parser implements the following grammar:
*
* program
* : expr Semicolon program
* | <empty>
* ;
*
* expr
* : addExpr
* ;
*
* addExpr
* : mulExpr addExprRest
* ;
*
* addExprRest
* : addOp mulExpr addExprRest
* | <empty>
* ;
*
* mulExpr
* : unaryExpr mulExprRest
* ;
*
* mulExprRest
* : mulOp unaryExpr mulExprRest
* | <empty>
* ;
*
* mulOp
* : Star | Slash
* ;
*
* unaryExpr
* : unOp unaryExpr
* | primExpr
* ;
*
* unOp
* : Plus | Minus
* ;
*
* primExpr
* : Number
* | Id
* | LParen expr RParen
* ;
*/
class Parser {
private:
Scanner _scanner;
VarTable &_varTable;
Token _lookAhead;
private:
// constructor.
Parser(std::istream &in, VarTable &varTable):
_scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
{
scan(); // load look ahead initially
}
// calls the scanner to read the next look ahead token.
void scan() { _lookAhead = _scanner.scan(); }
// consumes a specific token.
bool match(Token::Tk tk)
{
if (_lookAhead.tk != tk) {
std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
return false;
}
scan();
return true;
}
// the rules:
std::vector<AST::Expr*> parseProgram()
{
// right recursive rule
// -> can be done as iteration
std::vector<AST::Expr*> pExprs;
for (;;) {
if (AST::Expr *pExpr = parseExpr()) {
pExprs.push_back(pExpr);
} else break;
// special error checking for missing ';' (usual error)
if (_lookAhead.tk != Token::Semicolon) {
std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
break;
}
scan(); // consume semicolon
if (_lookAhead.tk == Token::EOT) return pExprs;
}
// error handling
for (AST::Expr *pExpr : pExprs) delete pExpr;
pExprs.clear();
return pExprs;
}
AST::Expr* parseExpr()
{
return parseAddExpr();
}
AST::Expr* parseAddExpr()
{
if (AST::Expr *pExpr1 = parseMulExpr()) {
return parseAddExprRest(pExpr1);
} else return nullptr; // ERROR!
}
AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
{
// right recursive rule for left associative operators
// -> can be done as iteration
for (;;) {
switch (_lookAhead.tk) {
case Token::Plus:
scan(); // consume token
if (AST::Expr *pExpr2 = parseMulExpr()) {
pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Minus:
scan(); // consume token
if (AST::Expr *pExpr2 = parseMulExpr()) {
pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
delete pExpr1;
return nullptr;
default: return pExpr1;
}
}
}
AST::Expr* parseMulExpr()
{
if (AST::Expr *pExpr1 = parseUnExpr()) {
return parseMulExprRest(pExpr1);
} else return nullptr; // ERROR!
}
AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
{
// right recursive rule for left associative operators
// -> can be done as iteration
for (;;) {
switch (_lookAhead.tk) {
case Token::Star:
scan(); // consume token
if (AST::Expr *pExpr2 = parseUnExpr()) {
pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Slash:
scan(); // consume token
if (AST::Expr *pExpr2 = parseUnExpr()) {
pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
delete pExpr1;
return nullptr;
default: return pExpr1;
}
}
}
AST::Expr* parseUnExpr()
{
// right recursive rule right recursive operators
// -> must be done as recursion
switch (_lookAhead.tk) {
case Token::Plus:
scan(); // consume token
// as a unary plus has no effect it is simply ignored
return parseUnExpr();
case Token::Minus:
scan();
if (AST::Expr *pExpr = parseUnExpr()) {
return new AST::ExprUnOpNeg(pExpr);
} else return nullptr; // ERROR!
default:
return parsePrimExpr();
}
}
AST::Expr* parsePrimExpr()
{
AST::Expr *pExpr = nullptr;
switch (_lookAhead.tk) {
case Token::Number:
pExpr = new AST::ExprConst(_lookAhead.number);
scan(); // consume token
break;
case Token::Id: {
Var &var = _varTable[_lookAhead.id]; // find or create
pExpr = new AST::ExprVar(&var);
scan(); // consume token
} break;
case Token::LParen:
scan(); // consume token
if (!(pExpr = parseExpr())) return nullptr; // ERROR!
if (!match(Token::RParen)) {
delete pExpr; return nullptr; // ERROR!
}
break;
case Token::EOT:
std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
break;
default:
std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
}
return pExpr;
}
public:
// the parser function
static std::vector<AST::Expr*> parse(
std::istream &in, VarTable &varTable)
{
Parser parser(in, varTable);
return parser.parseProgram();
}
};
} // namespace TinyCalc
// a sample application
using namespace std;
using namespace TinyCalc;
int main()
{
// the program:
const char *sourceCode =
"1 + 2 * 3 / 4 - 5;\n"
"a + b;\n"
"a - b;\n"
"a * b;\n"
"a / b;\n"
"a * (b + 3);\n";
// the variables
const char *vars[] = { "a", "b" };
enum { nVars = sizeof vars / sizeof *vars };
// the data
const double data[][nVars] = {
{ 4.0, 2.0 },
{ 2.0, 4.0 },
{ 10.0, 5.0 },
{ 42, 6 * 7 }
};
// compile program
stringstream in(sourceCode);
VarTable varTable;
vector<AST::Expr*> program = Parser::parse(in, varTable);
if (program.empty()) {
cerr << "ERROR: Compile failed!" << endl;
string line;
if (getline(in, line)) {
cerr << "Text at error: '" << line << "'" << endl;
}
return 1;
}
// apply program to the data
enum { nDataSets = sizeof data / sizeof *data };
for (size_t i = 0; i < nDataSets; ++i) {
const char *sep = "";
cout << "Data Set:" << endl;
for (size_t j = 0; j < nVars; ++j, sep = ", ") {
cout << sep << vars[j] << ": " << data[i][j];
}
cout << endl;
// load data
for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
// perform program
cout << "Compute:" << endl;
istringstream in(sourceCode);
for (const AST::Expr *pExpr : program) {
string line; getline(in, line);
cout << line << ": " << pExpr->solve() << endl;
}
cout << endl;
}
// clear the program
for (AST::Expr *pExpr : program) delete pExpr;
program.clear();
// done
return 0;
}