// attemp to create mini c++ compiler // start coding date: 21.02 17:00 // What now available: // 1. Base types of instructions: // print ; // printing instruction // ; // declaring data instruction // or = ; // = ; // assign instruction // instead of value you can write an expression! // eg. var_a = 10 + 4 * 2; // = 18 // Blocked instructions supported! { ... } // data table deduction is correct // 2. Adequate error messages like: // expected ';' at end of declaration // different value types in assign // 3. Easy to add new type of instructions // because of program logic // 4. Two execute modes support: // you can execute compiled program single-time // or do your own actions between executing // instructions // simple instructions how to add your own token // Eg. add token that means '\t' in code // first add token tag TAB (Token::enum) // next in lexer constructor add reserve instruction // reserve (Token::TAB, "tab"); // last define data interpretation of your token // in Parser::parse_data add code like for ENDL // and that's all! Have fun) #include #include #include #include #include #include using std::string; using std::stack; using std::list; using std::cout; using std::endl; using std::cin; using std::map; using std::set; //================================================= struct Token { int tag; string lexeme; Token () : tag (ERROR), lexeme ("") {} Token (int t, string l) : tag (t), lexeme (l) {} string repr () { switch (tag) { case ERROR: return ""; case NUMBER: return ""; case WORD: return ""; case STR: return ""; //case PRINT: return ""; default: return "<" + lexeme + ">"; } } enum { ERROR, NUMBER, WORD, STR, LOGIC, SIGN, EQUAL, NEQUAL, LOWER_EQ, GREATER_EQ, PRINT, CONTEXT, INT, STRING, BOOL, ENDL, IF, ELSE, WHILE }; }; class Lexer { private: string target; string::iterator curr_pos; list reserved; void reserve (int t, string l) { reserved.insert (reserved.end (), Token (t, l)); } Token check_reserved (Token t) { for (auto iter: reserved) if (iter.lexeme == t.lexeme) return iter; return t; } bool check_sign (string l) { if (l.size () == 0) return false; for (auto iter: reserved) if (iter.lexeme.substr (0, l.size ()) == l) return true; return false; } void skip_space () { while (curr_pos != target.end () && iswspace (*curr_pos)) curr_pos++; } void skip_comment () { while (curr_pos != target.end () && *curr_pos != '\n') curr_pos++; } Token scan_num () { string lexeme = ""; while (curr_pos != target.end () && isdigit (*curr_pos)) lexeme += *(curr_pos++); return Token (Token::NUMBER, lexeme); } Token scan_word () { string lexeme = ""; while (curr_pos != target.end () && isalnum (*curr_pos)) lexeme += *(curr_pos++); return check_reserved (Token (Token::WORD, lexeme)); } Token scan_string () { string lexeme = ""; curr_pos++; while (curr_pos != target.end () && *curr_pos != '"') lexeme += *(curr_pos++); curr_pos++; return Token (Token::STR, lexeme); } Token scan_sign () { string lexeme = ""; lexeme += *curr_pos; while (++curr_pos != target.end () && check_sign (lexeme)) lexeme += *curr_pos; if (lexeme.size () > 1) { curr_pos--; lexeme = lexeme.substr (0, lexeme.size ()-1); } return check_reserved (Token (Token::SIGN, lexeme)); } public: Lexer (string t) : target (t), curr_pos (target.begin ()) { reserve (Token::PRINT, "print"); reserve (Token::CONTEXT, "context"); reserve (Token::INT, "int"); reserve (Token::STRING, "string"); reserve (Token::BOOL, "bool"); reserve (Token::LOGIC, "true"); reserve (Token::LOGIC, "false"); reserve (Token::ENDL, "endl"); reserve (Token::IF, "if"); reserve (Token::ELSE, "else"); reserve (Token::WHILE, "while"); reserve (Token::EQUAL, "=="); reserve (Token::NEQUAL, "!="); reserve (Token::LOWER_EQ, "<="); reserve (Token::GREATER_EQ, ">="); } Token scan_next () { bool any_founded = true; while (any_founded) { any_founded = false; skip_space (); if (curr_pos == target.end ()) return Token (); if (*curr_pos == '/' && *(curr_pos+1) == '/') { skip_comment (); any_founded = true; } skip_space (); } if (isdigit (*curr_pos)) return scan_num (); if (isalpha (*curr_pos)) return scan_word (); if (*curr_pos == '"') return scan_string (); return scan_sign (); } list scan () { list result; Token token; while (true) { token = scan_next (); if (token.tag == Token::ERROR) break; result.insert (result.end (), token); } return result; } }; //================================================= struct DataTable; struct DataType { int type; string name, value; DataType (int t, string n, string v = "") : type (t), name (n), value (v) {} virtual string get_value (DataTable* dt); // method extracts first number in data string // negative numbers work correct int as_int (DataTable* dt) { string val = get_value (dt); int result = 0, sign = 1; if (!val.empty ()) if (val[0] == '-') sign = -1; auto iter = val.begin (); while (!isdigit (*iter)) iter++; while (isdigit (*iter)) result = 10*result + (*(iter++) - '0'); return sign * result; } // false returns only if // data (empty = 0 = false) bool as_bool (DataTable* dt) { bool res = true; string val = get_value (dt); res = res && !val.empty (); res = res && (val != "false"); res = res && (val != "0"); return res; } virtual string repr () { string result = "{"; switch (type) { case NDEF: result += "ndef|"; break; case VOID: result += "void|"; break; case INT: result += "int|"; break; case BOOL: result += "bool|"; break; case STRING: result += "string|"; break; default: result += "???|"; break; } result += name + "|" + value + "}"; return result; } enum {NDEF, VOID, INT, BOOL, STRING}; }; class DataTable { private: list data; DataTable* parent; DataType* get (string name) { for (auto iter: data) if (iter->name == name) return iter; if (parent == nullptr) return nullptr; else return parent->get (name); } public: DataTable (DataTable* p = nullptr) : parent (p) {} DataTable (const DataTable& d) : data (d.data), parent (d.parent) {} void enter () { *this = DataTable (new DataTable (*this)); } void out () {*this = *parent;} void add (DataType* d) { data.insert (data.end (), d); } bool known (DataType* d) { return get (d->name) != nullptr; } string get_value (string name) { DataType* d = get (name); if (d == nullptr) return ""; else return d->value; } int type_of (string name) { DataType* d = get (name); if (d == nullptr) return DataType::NDEF; else return d->type; } void set_value (string name, string value) { DataType* d = get (name); if (d == nullptr) return; else d->value = value; } string context (string tab = "") { string result = tab + "DataTable {\n"; if (parent != nullptr) result += parent->context (tab + " "); for (auto iter: data) result += tab + " " + iter->repr () + "\n"; return result + tab + "}\n"; } }; string DataType::get_value (DataTable* dt) { if (value.empty ()) return dt->get_value (name); else return value; } //================================================= // here is expressions logic block // each type of expression can contain other // expressions and count itself recurrently struct Expression : DataType { Expression (int type) : DataType (type, "") {} }; struct Int_sum : Expression { DataType *lvalue, *rvalue; Int_sum (DataType* l, DataType* r) : Expression (DataType::INT), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { int sum = lvalue->as_int (dt) + rvalue->as_int (dt); string result = ""; while (sum > 0) { result = char ('0'+sum%10) + result; sum /= 10; } return result; } string repr () { return "{Int_sum|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; struct Int_sub : Expression { DataType *lvalue, *rvalue; Int_sub (DataType* l, DataType* r) : Expression (DataType::INT), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { int sum = lvalue->as_int (dt) - rvalue->as_int (dt); string result = ""; while (sum > 0) { result = char ('0'+sum%10) + result; sum /= 10; } return result; } string repr () { return "{Int_sub|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; struct Int_mult : Expression { DataType *lvalue, *rvalue; Int_mult (DataType* l, DataType* r) : Expression (DataType::INT), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { int sum = lvalue->as_int (dt) * rvalue->as_int (dt); string result = ""; while (sum > 0) { result = char ('0'+sum%10) + result; sum /= 10; } return result; } string repr () { return "{Int_mult|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; struct Int_div : Expression { DataType *lvalue, *rvalue; Int_div (DataType* l, DataType* r) : Expression (DataType::INT), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { int sum = lvalue->as_int (dt) / rvalue->as_int (dt); string result = ""; while (sum > 0) { result = char ('0'+sum%10) + result; sum /= 10; } return result; } string repr () { return "{Int_div|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; struct Bool_eq : Expression { DataType *lvalue, *rvalue; Bool_eq (DataType* l, DataType* r) : Expression (DataType::BOOL), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { bool result = lvalue->get_value (dt) == rvalue->get_value (dt); if (result) return "true"; else return "false"; } string repr () { return "{Bool_eq|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; struct Bool_neq : Expression { DataType *lvalue, *rvalue; Bool_neq (DataType* l, DataType* r) : Expression (DataType::BOOL), lvalue (l), rvalue (r) {} string get_value (DataTable* dt) { bool result = lvalue->get_value (dt) != rvalue->get_value (dt); if (result) return "true"; else return "false"; } string repr () { return "{Bool_neq|" + lvalue->repr () + "|" + rvalue->repr () + "}"; } }; //================================================= struct Instruction { virtual bool execute (DataTable* dt, bool show_info) = 0; virtual string repr () { return "instr;"; } }; struct Contex_instr : Instruction { bool execute (DataTable* dt, bool show_info) { cout << "\nContext info:\n"; cout << dt->context (); return true; } string repr () { return "show_context;"; } }; struct Print_instr : Instruction { DataType* data; Print_instr (DataType* d) : data (d) {} bool execute (DataTable* dt, bool show_info) { if (show_info) cout << "print: ("; cout << data->get_value (dt); if (show_info) cout << ")\n"; return true; } }; struct Decl_instr : Instruction { DataType *data, *value; Decl_instr (DataTable* dt, DataType* d, DataType* v = nullptr) : data (d), value (v) { dt->add (data); } bool execute (DataTable* dt, bool show_info) { if (value != nullptr) data->value = value->get_value (dt); dt->add (data); if (show_info) cout << "declared: " << data->repr () << endl; return true; } }; struct Assign_instr : Instruction { DataType* lvalue; DataType* rvalue; Assign_instr (DataType* l, DataType* r) : lvalue (l), rvalue (r) {} bool execute (DataTable* dt, bool show_info) { dt->set_value (lvalue->name, rvalue->get_value (dt)); if (show_info) cout << "assigned: '" << lvalue->name << "' to " << rvalue->repr () << endl; return true; } }; struct Block_instr : Instruction { list instrs; list::iterator iter; bool entered; Block_instr () : entered (false) {} void add_instr (Instruction* i) { instrs.push_back (i); iter = instrs.begin (); } bool execute (DataTable* dt, bool show_info) { if (iter == instrs.end ()) return true; if (!entered) { dt->enter (); entered = true; } if ((*iter)->execute (dt, show_info)) iter++; if (iter == instrs.end ()) { dt->out (); iter = instrs.begin (); entered = false; return true; } else return false; } string repr () { string result = "{"; for (auto i: instrs) result += i->repr (); return result + "}"; } }; struct If_instr : Instruction { DataType* cond; Instruction *instr, *else_instr; bool running; bool checked; If_instr (DataType* d, Instruction* i, Instruction* e) : cond (d), instr (i), else_instr (e), checked (false) {} bool execute (DataTable* dt, bool show_info) { if (!checked) { running = cond->as_bool (dt); checked = true; } if (running) { if (instr->execute (dt, show_info)) { running = false; return true; } else return false; } else if (else_instr != nullptr) { if (else_instr->execute (dt, show_info)) { running = false; return true; } } else return false; } string repr () { return "if("+cond->repr()+")"+instr->repr(); } }; struct While_instr : Instruction { DataType* cond; Instruction* instr; bool running; While_instr (DataType* d, Instruction* i) : cond (d), instr (i), running (false) {} bool execute (DataTable* dt, bool show_info) { if (!running) running = cond->as_bool (dt); if (!running) return true; if (instr->execute (dt, show_info)) running = cond->as_bool (dt); return !running; } string repr () { return "while(" + cond->repr () + ")" + instr->repr (); } }; struct Program { list instrs; DataTable dtable; void add_instr (Instruction* i) { instrs.insert (instrs.end (), i); } bool run_instr (bool show_info = false) { static auto iter = instrs.begin (); if (iter == instrs.end ()) return true; if ((*iter)->execute (&dtable, show_info)) iter++; return iter == instrs.end (); } void run (bool show_info = false) { while (!run_instr (show_info)); } string repr () { string result = "program{"; for (auto i: instrs) result += i->repr (); return result + "}"; } }; //================================================= class Parser { private: list target; list::iterator curr_pos; string error_msg; void error (string msg) { if (error_msg.empty ()) error_msg += msg; else error_msg += "\n" + msg; } DataType* parse_basic_data (DataTable* dt) { switch (curr_pos->tag) { case Token::WORD: if (!dt->known (new DataType (DataType::NDEF, curr_pos->lexeme))) error ("value '" + curr_pos->lexeme + "' is not declared"); return new DataType (dt->type_of (curr_pos->lexeme), curr_pos++->lexeme); case Token::STR: return new DataType (DataType::STRING, "", curr_pos++->lexeme); case Token::NUMBER: return new DataType (DataType::INT, "", curr_pos++->lexeme); case Token::LOGIC: return new DataType (DataType::BOOL, "", curr_pos++->lexeme); case Token::ENDL: curr_pos++; return new DataType (DataType::STRING, "", "\n"); default: return new DataType (DataType::NDEF, "ndef"); } } void _set_lops (list ops, string& l, string& p) { l = ops.front (); if (ops.size () > 1) p = *++ops.begin (); else p = l; } void _set_d (list data, DataType*& l, DataType*& r) { r = data.front (); l = *++data.begin (); //cout << "setted data:" << endl; //cout << "l = " << l->repr () << endl; //cout << "r = " << r->repr () << endl; } // returns true if A has higher priority than B bool _h_prior (string a, string b) { // a > b static const map prior = { {"==", 1}, {"!=", 1}, {"+", 2}, {"-", 2}, {"*", 3}, {"/", 3} }; return prior.at (a) >= prior.at (b); } // returns true if token can`t be part of expression bool _is_expr_end (Token t) { static const set lexemes = {";", "=", ")", "}", "]"}; return lexemes.count (t.lexeme); } DataType* parse_data (DataTable* dt) { list data; list operators; DataType *l, *r, *res; string plop, lop = ""; // pre-last op, last op while (!_is_expr_end (*curr_pos)) { if (curr_pos->lexeme == "(") { curr_pos++; data.push_front (parse_data (dt)); curr_pos++; } else data.push_front (parse_basic_data (dt)); if (!_is_expr_end (*curr_pos)) { operators.push_front (curr_pos++->lexeme); } while (data.size () > 1) { _set_lops (operators, lop, plop); _set_d (data, l, r); if (_h_prior (plop, lop)) { if (plop == "+") res = new Int_sum (l, r); else if (plop == "-") res = new Int_sub (l, r); else if (plop == "*") res = new Int_mult(l, r); else if (plop == "/") res = new Int_div (l, r); else if (plop == "==") res = new Bool_eq (l, r); else if (plop == "!=") res = new Bool_neq(l, r); data.pop_front (); data.pop_front (); data.push_front (res); //cout << "data crafted: " << res->repr () << endl; if (operators.size () == 1) operators.erase (operators.begin ()); else operators.erase (++operators.begin ()); } else if (_is_expr_end (*curr_pos)) { if (lop == "+") res = new Int_sum (l, r); else if (lop == "-") res = new Int_sub (l, r); else if (lop == "*") res = new Int_mult(l, r); else if (lop == "/") res = new Int_div (l, r); else if (lop == "==") res = new Bool_eq (l, r); else if (lop == "!=") res = new Bool_neq (l, r); data.pop_front (); data.pop_front (); data.push_front (res); //cout << "last data crafting: " << res->repr () << endl; operators.erase (operators.begin ()); } else break; } } //cout << "parsed data: " << data.front ()->repr () << endl; return data.front (); } // print 'data' ; Print_instr* parse_print (DataTable* dt) { curr_pos++; Print_instr* result = new Print_instr (parse_data (dt)); if (curr_pos->lexeme != ";") { error ("expected ';' at end of print"); return nullptr; } curr_pos++; return result; } // context ; Contex_instr* parse_context (DataTable* dt) { curr_pos++; // skip curr_pos++; // skip ; return new Contex_instr (); } // 'id' ; // OR // 'id' = 'value' ; Decl_instr* parse_decl (DataTable* dt) { int data_type; string data_name; DataType *data, *value; switch (curr_pos++->tag) { case Token::INT: data_type = DataType::INT; break; case Token::STRING: data_type = DataType::STRING; break; case Token::BOOL: data_type = DataType::BOOL; break; } if (curr_pos->tag != Token::WORD) { error ("expected 'id' in declaring"); return nullptr; } data_name = curr_pos++->lexeme; if (curr_pos->lexeme == ";") { curr_pos++; return new Decl_instr (dt, new DataType (data_type, data_name)); } else if (curr_pos->lexeme == "=") { curr_pos++; data = new DataType(data_type, data_name); value = parse_data (dt); curr_pos++; return new Decl_instr (dt, data, value); } else { error ("expected ';' or '=' in declaration of variable '" + data_name + "'"); return nullptr; } } // 'id' = 'value' ; Assign_instr* parse_assign (DataTable* dt) { // 'id' = 'data' ; DataType* lvalue = parse_data (dt); if (!error_msg.empty ()) return nullptr; curr_pos++; DataType* rvalue = parse_data (dt); if (dt->type_of (lvalue->name) != rvalue->type) { error ("different types in assign"); return nullptr; } Assign_instr* result = new Assign_instr (lvalue, rvalue); if (curr_pos++->lexeme != ";") { error ("expected ';' at end of assign"); return nullptr; } return result; } // { } Block_instr* parse_block (DataTable* dt) { //cout << "entering in block" << endl; curr_pos++; dt->enter (); Block_instr* result = new Block_instr (); while (curr_pos->lexeme != "}") { //cout << "added instr" << endl; result->add_instr (parse_next (dt)); } curr_pos++; dt->out (); //cout << "leaving block" << endl; return result; } // if ( 'value' ) If_instr* parse_if (DataTable* dt) { curr_pos++; // skip curr_pos++; // skip ( DataType* cond = parse_data (dt); curr_pos++; // skip ) Instruction* instr = parse_next (dt); Instruction* else_instr; if (curr_pos->tag == Token::ELSE) { curr_pos++; // skip else_instr = parse_next (dt); return new If_instr (cond, instr, else_instr); } else return new If_instr (cond, instr, nullptr); } // while ( 'value' ) While_instr* parse_while (DataTable* dt) { curr_pos++; // skip curr_pos++; // skip ( DataType* cond = parse_data (dt); curr_pos++; // skip ) Instruction* instr = parse_next (dt); return new While_instr (cond, instr); } public: Parser (list t) : error_msg (""), target (t), curr_pos (target.begin ()) {} Instruction* parse_next (DataTable* dt) { if (curr_pos->lexeme == "{") return parse_block (dt); switch (curr_pos->tag) { case Token::PRINT: return parse_print (dt); case Token::CONTEXT: return parse_context (dt); case Token::INT: case Token::STRING: case Token::BOOL: return parse_decl (dt); case Token::WORD: return parse_assign (dt); case Token::IF: return parse_if (dt); case Token::WHILE: return parse_while (dt); default: error ("unknown instr type"); return nullptr; } } Program parse () { Program result; DataTable temp_dtable; Instruction* instr; while (curr_pos != target.end ()) { instr = parse_next (&temp_dtable); if (!error_msg.empty () || instr == nullptr) { cout << "error happened:\n " << error_msg << endl; return Program (); } else result.add_instr (instr); } cout << "parse completed" << endl; return result; } }; //method for IDE executing:======================== //#include //string load_from_file (const string &fname) { // std::ifstream ifile (fname); // string result = ""; // char temp; // // while (!ifile.eof ()) { // ifile.get (temp); // if (ifile.eof ()) break; // result += temp; // } // // return result; //} int main () { string test_code; // try to write your code here! test_code = "int f1 = 1; int f2 = 1;\n" "int n = 6; int temp;\n" "while (n != 2) {\n" " temp = f2+1-1;\n" " f2 = f2 + f1;\n" " f1 = temp+1-1;\n" " print 9-n;\n" " print \"th fib num = \";\n" " print f2;\n" " print endl;\n" " n = n-1;\n" "}"; //test_code = load_from_file ("temp_prog.cpp"); list tokens = Lexer (test_code).scan (); cout << "source code:==============\n"; cout << test_code << endl; /* cout << "tokenized:================\n"; auto iter = tokens.begin (); for (int i = 1; i <= tokens.size (); i++, iter++) { cout << iter->repr () << " "; if (i % 3 == 0 || i == tokens.size ()) cout << endl; } // */ cout << "parsing:==================\n"; Program prog = Parser (tokens).parse (); //cout << "reproduction:=============\n"; //cout << prog.repr () << endl; cout << "executing:================\n"; prog.run (false); // switch to true if you want to see process return 0; }

mini c++ compiler part 1