fork(2) download
  1. #include <cctype>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <map>
  5. #include <string>
  6. #include <sstream>
  7. #include <vector>
  8.  
  9. namespace TinyCalc {
  10.  
  11. // storage of variables
  12.  
  13. class Var {
  14. private:
  15. double _value;
  16. public:
  17. Var(): _value() { }
  18. ~Var() = default;
  19. double get() const { return _value; }
  20. void set(double value) { _value = value; }
  21. };
  22.  
  23. typedef std::map<std::string, Var> VarTable;
  24.  
  25. // abstract syntax tree -> storage of "executable"
  26.  
  27. namespace AST {
  28.  
  29. class Expr {
  30. protected:
  31. Expr() = default;
  32. public:
  33. virtual ~Expr() = default;
  34. public:
  35. virtual double solve() const = 0;
  36. };
  37.  
  38. class ExprConst: public Expr {
  39. private:
  40. double _value;
  41. public:
  42. ExprConst(double value): Expr(), _value(value) { }
  43. virtual ~ExprConst() = default;
  44. virtual double solve() const { return _value; }
  45. };
  46.  
  47. class ExprVar: public Expr {
  48. private:
  49. Var *_pVar;
  50. public:
  51. ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
  52. virtual ~ExprVar() = default;
  53. virtual double solve() const { return _pVar->get(); }
  54. };
  55.  
  56. class ExprUnOp: public Expr {
  57. protected:
  58. Expr *_pArg1;
  59. protected:
  60. ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
  61. virtual ~ExprUnOp() { delete _pArg1; }
  62. };
  63.  
  64. class ExprUnOpNeg: public ExprUnOp {
  65. public:
  66. ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
  67. virtual ~ExprUnOpNeg() = default;
  68. virtual double solve() const
  69. {
  70. return -_pArg1->solve();
  71. }
  72. };
  73.  
  74. class ExprBinOp: public Expr {
  75. protected:
  76. Expr *_pArg1, *_pArg2;
  77. protected:
  78. ExprBinOp(Expr *pArg1, Expr *pArg2):
  79. Expr(), _pArg1(pArg1), _pArg2(pArg2)
  80. { }
  81. virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
  82. };
  83.  
  84. class ExprBinOpAdd: public ExprBinOp {
  85. public:
  86. ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  87. virtual ~ExprBinOpAdd() = default;
  88. virtual double solve() const
  89. {
  90. return _pArg1->solve() + _pArg2->solve();
  91. }
  92. };
  93.  
  94. class ExprBinOpSub: public ExprBinOp {
  95. public:
  96. ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  97. virtual ~ExprBinOpSub() = default;
  98. virtual double solve() const
  99. {
  100. return _pArg1->solve() - _pArg2->solve();
  101. }
  102. };
  103.  
  104. class ExprBinOpMul: public ExprBinOp {
  105. public:
  106. ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  107. virtual ~ExprBinOpMul() = default;
  108. virtual double solve() const
  109. {
  110. return _pArg1->solve() * _pArg2->solve();
  111. }
  112. };
  113.  
  114. class ExprBinOpDiv: public ExprBinOp {
  115. public:
  116. ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
  117. virtual ~ExprBinOpDiv() = default;
  118. virtual double solve() const
  119. {
  120. return _pArg1->solve() / _pArg2->solve();
  121. }
  122. };
  123.  
  124. } // namespace AST
  125.  
  126. // token class - produced in scanner, consumed in parser
  127. struct Token {
  128. // tokens
  129. enum Tk {
  130. Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
  131. Number, Id,
  132. EOT, Error
  133. };
  134. // token number
  135. Tk tk;
  136. // lexem as floating point number
  137. double number;
  138. // lexem as identifier
  139. std::string id;
  140.  
  141. // constructors.
  142. explicit Token(Tk tk): tk(tk), number() { }
  143. explicit Token(double number): tk(Number), number(number) { }
  144. explicit Token(const std::string &id): tk(Id), number(), id(id) { }
  145. };
  146.  
  147. // the scanner - groups characters to tokens
  148. class Scanner {
  149. private:
  150. std::istream &_in;
  151.  
  152. public:
  153. // constructor.
  154. Scanner(std::istream &in): _in(in) { }
  155.  
  156. /* groups characters to next token until the first character
  157.   * which does not match (or end-of-file is reached).
  158.   */
  159. Token scan()
  160. {
  161. char c;
  162. // skip white space
  163. do {
  164. if (!(_in >> c)) return Token(Token::EOT);
  165. } while (isspace(c));
  166. // classify character and build token
  167. switch (c) {
  168. case '+': return Token(Token::Plus);
  169. case '-': return Token(Token::Minus);
  170. case '*': return Token(Token::Star);
  171. case '/': return Token(Token::Slash);
  172. case '(': return Token(Token::LParen);
  173. case ')': return Token(Token::RParen);
  174. case ';': return Token(Token::Semicolon);
  175. default:
  176. if (isdigit(c)) {
  177. _in.unget(); double value; _in >> value;
  178. return Token(value);
  179. } else if (isalpha(c) || c == '_') {
  180. std::string id(1, c);
  181. while (_in >> c) {
  182. if (isalnum(c) || c == '_') id += c;
  183. else { _in.unget(); break; }
  184. }
  185. return Token(id);
  186. } else {
  187. _in.unget();
  188. return Token(Token::Error);
  189. }
  190. }
  191. }
  192. };
  193.  
  194. /* parser
  195.  *
  196.  * This is a recursive descent parser with a look-ahead of one symbol
  197.  * and without back-tracking.
  198.  * The parser implements the following grammar:
  199.  *
  200.  * program
  201.  * : expr Semicolon program
  202.  * | <empty>
  203.  * ;
  204.  *
  205.  * expr
  206.  * : addExpr
  207.  * ;
  208.  *
  209.  * addExpr
  210.  * : mulExpr addExprRest
  211.  * ;
  212.  *
  213.  * addExprRest
  214.  * : addOp mulExpr addExprRest
  215.  * | <empty>
  216.  * ;
  217.  *
  218.  * mulExpr
  219.  * : unaryExpr mulExprRest
  220.  * ;
  221.  *
  222.  * mulExprRest
  223.  * : mulOp unaryExpr mulExprRest
  224.  * | <empty>
  225.  * ;
  226.  *
  227.  * mulOp
  228.  * : Star | Slash
  229.  * ;
  230.  *
  231.  * unaryExpr
  232.  * : unOp unaryExpr
  233.  * | primExpr
  234.  * ;
  235.  *
  236.  * unOp
  237.  * : Plus | Minus
  238.  * ;
  239.  *
  240.  * primExpr
  241.  * : Number
  242.  * | Id
  243.  * | LParen expr RParen
  244.  * ;
  245.  */
  246. class Parser {
  247. private:
  248. Scanner _scanner;
  249. VarTable &_varTable;
  250. Token _lookAhead;
  251.  
  252. private:
  253. // constructor.
  254. Parser(std::istream &in, VarTable &varTable):
  255. _scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
  256. {
  257. scan(); // load look ahead initially
  258. }
  259.  
  260. // calls the scanner to read the next look ahead token.
  261. void scan() { _lookAhead = _scanner.scan(); }
  262.  
  263. // consumes a specific token.
  264. bool match(Token::Tk tk)
  265. {
  266. if (_lookAhead.tk != tk) {
  267. std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
  268. return false;
  269. }
  270. scan();
  271. return true;
  272. }
  273.  
  274. // the rules:
  275.  
  276. std::vector<AST::Expr*> parseProgram()
  277. {
  278. // right recursive rule
  279. // -> can be done as iteration
  280. std::vector<AST::Expr*> pExprs;
  281. for (;;) {
  282. if (AST::Expr *pExpr = parseExpr()) {
  283. pExprs.push_back(pExpr);
  284. } else break;
  285. // special error checking for missing ';' (usual error)
  286. if (_lookAhead.tk != Token::Semicolon) {
  287. std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
  288. break;
  289. }
  290. scan(); // consume semicolon
  291. if (_lookAhead.tk == Token::EOT) return pExprs;
  292. }
  293. // error handling
  294. for (AST::Expr *pExpr : pExprs) delete pExpr;
  295. pExprs.clear();
  296. return pExprs;
  297. }
  298.  
  299. AST::Expr* parseExpr()
  300. {
  301. return parseAddExpr();
  302. }
  303.  
  304. AST::Expr* parseAddExpr()
  305. {
  306. if (AST::Expr *pExpr1 = parseMulExpr()) {
  307. return parseAddExprRest(pExpr1);
  308. } else return nullptr; // ERROR!
  309. }
  310.  
  311. AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
  312. {
  313. // right recursive rule for left associative operators
  314. // -> can be done as iteration
  315. for (;;) {
  316. switch (_lookAhead.tk) {
  317. case Token::Plus:
  318. scan(); // consume token
  319. if (AST::Expr *pExpr2 = parseMulExpr()) {
  320. pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
  321. } else {
  322. delete pExpr1;
  323. return nullptr; // ERROR!
  324. }
  325. break;
  326. case Token::Minus:
  327. scan(); // consume token
  328. if (AST::Expr *pExpr2 = parseMulExpr()) {
  329. pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
  330. } else {
  331. delete pExpr1;
  332. return nullptr; // ERROR!
  333. }
  334. break;
  335. case Token::Error:
  336. std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  337. delete pExpr1;
  338. return nullptr;
  339. default: return pExpr1;
  340. }
  341. }
  342. }
  343.  
  344. AST::Expr* parseMulExpr()
  345. {
  346. if (AST::Expr *pExpr1 = parseUnExpr()) {
  347. return parseMulExprRest(pExpr1);
  348. } else return nullptr; // ERROR!
  349. }
  350.  
  351. AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
  352. {
  353. // right recursive rule for left associative operators
  354. // -> can be done as iteration
  355. for (;;) {
  356. switch (_lookAhead.tk) {
  357. case Token::Star:
  358. scan(); // consume token
  359. if (AST::Expr *pExpr2 = parseUnExpr()) {
  360. pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
  361. } else {
  362. delete pExpr1;
  363. return nullptr; // ERROR!
  364. }
  365. break;
  366. case Token::Slash:
  367. scan(); // consume token
  368. if (AST::Expr *pExpr2 = parseUnExpr()) {
  369. pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
  370. } else {
  371. delete pExpr1;
  372. return nullptr; // ERROR!
  373. }
  374. break;
  375. case Token::Error:
  376. std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  377. delete pExpr1;
  378. return nullptr;
  379. default: return pExpr1;
  380. }
  381. }
  382. }
  383.  
  384. AST::Expr* parseUnExpr()
  385. {
  386. // right recursive rule right recursive operators
  387. // -> must be done as recursion
  388. switch (_lookAhead.tk) {
  389. case Token::Plus:
  390. scan(); // consume token
  391. // as a unary plus has no effect it is simply ignored
  392. return parseUnExpr();
  393. case Token::Minus:
  394. scan();
  395. if (AST::Expr *pExpr = parseUnExpr()) {
  396. return new AST::ExprUnOpNeg(pExpr);
  397. } else return nullptr; // ERROR!
  398. default:
  399. return parsePrimExpr();
  400. }
  401. }
  402.  
  403. AST::Expr* parsePrimExpr()
  404. {
  405. AST::Expr *pExpr = nullptr;
  406. switch (_lookAhead.tk) {
  407. case Token::Number:
  408. pExpr = new AST::ExprConst(_lookAhead.number);
  409. scan(); // consume token
  410. break;
  411. case Token::Id: {
  412. Var &var = _varTable[_lookAhead.id]; // find or create
  413. pExpr = new AST::ExprVar(&var);
  414. scan(); // consume token
  415. } break;
  416. case Token::LParen:
  417. scan(); // consume token
  418. if (!(pExpr = parseExpr())) return nullptr; // ERROR!
  419. if (!match(Token::RParen)) {
  420. delete pExpr; return nullptr; // ERROR!
  421. }
  422. break;
  423. case Token::EOT:
  424. std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
  425. break;
  426. case Token::Error:
  427. std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
  428. break;
  429. default:
  430. std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
  431. }
  432. return pExpr;
  433. }
  434.  
  435. public:
  436.  
  437. // the parser function
  438. static std::vector<AST::Expr*> parse(
  439. std::istream &in, VarTable &varTable)
  440. {
  441. Parser parser(in, varTable);
  442. return parser.parseProgram();
  443. }
  444. };
  445.  
  446. } // namespace TinyCalc
  447.  
  448. // a sample application
  449.  
  450. using namespace std;
  451. using namespace TinyCalc;
  452.  
  453. int main()
  454. {
  455. // the program:
  456. const char *sourceCode =
  457. "1 + 2 * 3 / 4 - 5;\n"
  458. "a + b;\n"
  459. "a - b;\n"
  460. "a * b;\n"
  461. "a / b;\n"
  462. "a * (b + 3);\n";
  463. // the variables
  464. const char *vars[] = { "a", "b" };
  465. enum { nVars = sizeof vars / sizeof *vars };
  466. // the data
  467. const double data[][nVars] = {
  468. { 4.0, 2.0 },
  469. { 2.0, 4.0 },
  470. { 10.0, 5.0 },
  471. { 42, 6 * 7 }
  472. };
  473. // compile program
  474. stringstream in(sourceCode);
  475. VarTable varTable;
  476. vector<AST::Expr*> program = Parser::parse(in, varTable);
  477. if (program.empty()) {
  478. cerr << "ERROR: Compile failed!" << endl;
  479. string line;
  480. if (getline(in, line)) {
  481. cerr << "Text at error: '" << line << "'" << endl;
  482. }
  483. return 1;
  484. }
  485. // apply program to the data
  486. enum { nDataSets = sizeof data / sizeof *data };
  487. for (size_t i = 0; i < nDataSets; ++i) {
  488. const char *sep = "";
  489. cout << "Data Set:" << endl;
  490. for (size_t j = 0; j < nVars; ++j, sep = ", ") {
  491. cout << sep << vars[j] << ": " << data[i][j];
  492. }
  493. cout << endl;
  494. // load data
  495. for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
  496. // perform program
  497. cout << "Compute:" << endl;
  498. istringstream in(sourceCode);
  499. for (const AST::Expr *pExpr : program) {
  500. string line; getline(in, line);
  501. cout << line << ": " << pExpr->solve() << endl;
  502. }
  503. cout << endl;
  504. }
  505. // clear the program
  506. for (AST::Expr *pExpr : program) delete pExpr;
  507. program.clear();
  508. // done
  509. return 0;
  510. }
  511.  
Success #stdin #stdout 0s 16112KB
stdin
Standard input is empty
stdout
Data Set:
a: 4, b: 2
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: 2
a * b;: 8
a / b;: 2
a * (b + 3);: 20

Data Set:
a: 2, b: 4
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: -2
a * b;: 8
a / b;: 0.5
a * (b + 3);: 14

Data Set:
a: 10, b: 5
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 15
a - b;: 5
a * b;: 50
a / b;: 2
a * (b + 3);: 80

Data Set:
a: 42, b: 42
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 84
a - b;: 0
a * b;: 1764
a / b;: 1
a * (b + 3);: 1890