1 /*============================================================================= 2 Copyright (c) 2001-2011 Joel de Guzman 3 4 Distributed under the Boost Software License, Version 1.0. (See accompanying 5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 =============================================================================*/ 7 #include "config.hpp" 8 #include "compiler.hpp" 9 #include "vm.hpp" 10 #include <boost/foreach.hpp> 11 #include <boost/variant/apply_visitor.hpp> 12 #include <boost/assert.hpp> 13 #include <boost/lexical_cast.hpp> 14 #include <set> 15 16 namespace client { namespace code_gen 17 { op(int a)18 void function::op(int a) 19 { 20 code.push_back(a); 21 size_ += 1; 22 } 23 op(int a,int b)24 void function::op(int a, int b) 25 { 26 code.push_back(a); 27 code.push_back(b); 28 size_ += 2; 29 } 30 op(int a,int b,int c)31 void function::op(int a, int b, int c) 32 { 33 code.push_back(a); 34 code.push_back(b); 35 code.push_back(c); 36 size_ += 3; 37 } 38 find_var(std::string const & name) const39 int const* function::find_var(std::string const& name) const 40 { 41 std::map<std::string, int>::const_iterator i = variables.find(name); 42 if (i == variables.end()) 43 return 0; 44 return &i->second; 45 } 46 add_var(std::string const & name)47 void function::add_var(std::string const& name) 48 { 49 std::size_t n = variables.size(); 50 variables[name] = n; 51 } 52 link_to(std::string const & name,std::size_t address)53 void function::link_to(std::string const& name, std::size_t address) 54 { 55 function_calls[address] = name; 56 } 57 print_assembler() const58 void function::print_assembler() const 59 { 60 std::vector<int>::const_iterator pc = code.begin() + address; 61 62 std::vector<std::string> locals(variables.size()); 63 typedef std::pair<std::string, int> pair; 64 BOOST_FOREACH(pair const& p, variables) 65 { 66 locals[p.second] = p.first; 67 std::cout << " local " 68 << p.first << ", @" << p.second << std::endl; 69 } 70 71 std::map<std::size_t, std::string> lines; 72 std::set<std::size_t> jumps; 73 74 while (pc != (code.begin() + address + size_)) 75 { 76 std::string line; 77 std::size_t address = pc - code.begin(); 78 79 switch (*pc++) 80 { 81 case op_neg: 82 line += " op_neg"; 83 break; 84 85 case op_not: 86 line += " op_not"; 87 break; 88 89 case op_add: 90 line += " op_add"; 91 break; 92 93 case op_sub: 94 line += " op_sub"; 95 break; 96 97 case op_mul: 98 line += " op_mul"; 99 break; 100 101 case op_div: 102 line += " op_div"; 103 break; 104 105 case op_eq: 106 line += " op_eq"; 107 break; 108 109 case op_neq: 110 line += " op_neq"; 111 break; 112 113 case op_lt: 114 line += " op_lt"; 115 break; 116 117 case op_lte: 118 line += " op_lte"; 119 break; 120 121 case op_gt: 122 line += " op_gt"; 123 break; 124 125 case op_gte: 126 line += " op_gte"; 127 break; 128 129 case op_and: 130 line += " op_and"; 131 break; 132 133 case op_or: 134 line += " op_or"; 135 break; 136 137 case op_load: 138 line += " op_load "; 139 line += locals[*pc++]; 140 break; 141 142 case op_store: 143 line += " op_store "; 144 line += locals[*pc++]; 145 break; 146 147 case op_int: 148 line += " op_int "; 149 line += boost::lexical_cast<std::string>(*pc++); 150 break; 151 152 case op_true: 153 line += " op_true"; 154 break; 155 156 case op_false: 157 line += " op_false"; 158 break; 159 160 case op_jump: 161 { 162 line += " op_jump "; 163 std::size_t pos = (pc - code.begin()) + *pc++; 164 if (pos == code.size()) 165 line += "end"; 166 else 167 line += boost::lexical_cast<std::string>(pos); 168 jumps.insert(pos); 169 } 170 break; 171 172 case op_jump_if: 173 { 174 line += " op_jump_if "; 175 std::size_t pos = (pc - code.begin()) + *pc++; 176 if (pos == code.size()) 177 line += "end"; 178 else 179 line += boost::lexical_cast<std::string>(pos); 180 jumps.insert(pos); 181 } 182 break; 183 184 case op_call: 185 { 186 line += " op_call "; 187 int nargs = *pc++; 188 std::size_t jump = *pc++; 189 line += boost::lexical_cast<std::string>(nargs) + ", "; 190 BOOST_ASSERT(function_calls.find(jump) != function_calls.end()); 191 line += function_calls.find(jump)->second; 192 } 193 break; 194 195 case op_stk_adj: 196 line += " op_stk_adj "; 197 line += boost::lexical_cast<std::string>(*pc++); 198 break; 199 200 201 case op_return: 202 line += " op_return"; 203 break; 204 } 205 lines[address] = line; 206 } 207 208 std::cout << "start:" << std::endl; 209 typedef std::pair<std::size_t, std::string> line_info; 210 BOOST_FOREACH(line_info const& l, lines) 211 { 212 std::size_t pos = l.first; 213 if (jumps.find(pos) != jumps.end()) 214 std::cout << pos << ':' << std::endl; 215 std::cout << l.second << std::endl; 216 } 217 218 std::cout << "end:" << std::endl << std::endl; 219 } 220 operator ()(unsigned int x)221 bool compiler::operator()(unsigned int x) 222 { 223 BOOST_ASSERT(current != 0); 224 current->op(op_int, x); 225 return true; 226 } 227 operator ()(bool x)228 bool compiler::operator()(bool x) 229 { 230 BOOST_ASSERT(current != 0); 231 current->op(x ? op_true : op_false); 232 return true; 233 } 234 operator ()(ast::identifier const & x)235 bool compiler::operator()(ast::identifier const& x) 236 { 237 BOOST_ASSERT(current != 0); 238 int const* p = current->find_var(x.name); 239 if (p == 0) 240 { 241 error_handler(x.id, "Undeclared variable: " + x.name); 242 return false; 243 } 244 current->op(op_load, *p); 245 return true; 246 } 247 operator ()(token_ids::type const & x)248 bool compiler::operator()(token_ids::type const& x) 249 { 250 BOOST_ASSERT(current != 0); 251 switch (x) 252 { 253 case token_ids::plus: current->op(op_add); break; 254 case token_ids::minus: current->op(op_sub); break; 255 case token_ids::times: current->op(op_mul); break; 256 case token_ids::divide: current->op(op_div); break; 257 258 case token_ids::equal: current->op(op_eq); break; 259 case token_ids::not_equal: current->op(op_neq); break; 260 case token_ids::less: current->op(op_lt); break; 261 case token_ids::less_equal: current->op(op_lte); break; 262 case token_ids::greater: current->op(op_gt); break; 263 case token_ids::greater_equal: current->op(op_gte); break; 264 265 case token_ids::logical_or: current->op(op_or); break; 266 case token_ids::logical_and: current->op(op_and); break; 267 default: BOOST_ASSERT(0); return false; 268 } 269 return true; 270 } 271 operator ()(ast::unary const & x)272 bool compiler::operator()(ast::unary const& x) 273 { 274 BOOST_ASSERT(current != 0); 275 if (!boost::apply_visitor(*this, x.operand_)) 276 return false; 277 switch (x.operator_) 278 { 279 case token_ids::minus: current->op(op_neg); break; 280 case token_ids::not_: current->op(op_not); break; 281 case token_ids::plus: break; 282 default: BOOST_ASSERT(0); return false; 283 } 284 return true; 285 } 286 operator ()(ast::function_call const & x)287 bool compiler::operator()(ast::function_call const& x) 288 { 289 BOOST_ASSERT(current != 0); 290 291 if (functions.find(x.function_name.name) == functions.end()) 292 { 293 error_handler(x.function_name.id, "Function not found: " + x.function_name.name); 294 return false; 295 } 296 297 boost::shared_ptr<code_gen::function> p = functions[x.function_name.name]; 298 299 if (p->nargs() != x.args.size()) 300 { 301 error_handler(x.function_name.id, "Wrong number of arguments: " + x.function_name.name); 302 return false; 303 } 304 305 BOOST_FOREACH(ast::expression const& expr, x.args) 306 { 307 if (!(*this)(expr)) 308 return false; 309 } 310 311 current->op( 312 op_call, 313 p->nargs(), 314 p->get_address()); 315 current->link_to(x.function_name.name, p->get_address()); 316 317 return true; 318 } 319 320 namespace 321 { 322 int precedence[] = { 323 // precedence 1 324 1, // op_comma 325 326 // precedence 2 327 2, // op_assign 328 2, // op_plus_assign 329 2, // op_minus_assign 330 2, // op_times_assign 331 2, // op_divide_assign 332 2, // op_mod_assign 333 2, // op_bit_and_assign 334 2, // op_bit_xor_assign 335 2, // op_bitor_assign 336 2, // op_shift_left_assign 337 2, // op_shift_right_assign 338 339 // precedence 3 340 3, // op_logical_or 341 342 // precedence 4 343 4, // op_logical_and 344 345 // precedence 5 346 5, // op_bit_or 347 348 // precedence 6 349 6, // op_bit_xor 350 351 // precedence 7 352 7, // op_bit_and 353 354 // precedence 8 355 8, // op_equal 356 8, // op_not_equal 357 358 // precedence 9 359 9, // op_less 360 9, // op_less_equal 361 9, // op_greater 362 9, // op_greater_equal 363 364 // precedence 10 365 10, // op_shift_left 366 10, // op_shift_right 367 368 // precedence 11 369 11, // op_plus 370 11, // op_minus 371 372 // precedence 12 373 12, // op_times 374 12, // op_divide 375 12 // op_mod 376 }; 377 } 378 precedence_of(token_ids::type op)379 inline int precedence_of(token_ids::type op) 380 { 381 return precedence[op & 0xFF]; 382 } 383 384 // The Shunting-yard algorithm compile_expression(int min_precedence,std::list<ast::operation>::const_iterator & rbegin,std::list<ast::operation>::const_iterator rend)385 bool compiler::compile_expression( 386 int min_precedence, 387 std::list<ast::operation>::const_iterator& rbegin, 388 std::list<ast::operation>::const_iterator rend) 389 { 390 while ((rbegin != rend) && (precedence_of(rbegin->operator_) >= min_precedence)) 391 { 392 token_ids::type op = rbegin->operator_; 393 if (!boost::apply_visitor(*this, rbegin->operand_)) 394 return false; 395 ++rbegin; 396 397 while ((rbegin != rend) && (precedence_of(rbegin->operator_) > precedence_of(op))) 398 { 399 token_ids::type next_op = rbegin->operator_; 400 compile_expression(precedence_of(next_op), rbegin, rend); 401 } 402 (*this)(op); 403 } 404 return true; 405 } 406 operator ()(ast::expression const & x)407 bool compiler::operator()(ast::expression const& x) 408 { 409 BOOST_ASSERT(current != 0); 410 if (!boost::apply_visitor(*this, x.first)) 411 return false; 412 std::list<ast::operation>::const_iterator rbegin = x.rest.begin(); 413 if (!compile_expression(0, rbegin, x.rest.end())) 414 return false; 415 return true; 416 } 417 operator ()(ast::assignment const & x)418 bool compiler::operator()(ast::assignment const& x) 419 { 420 BOOST_ASSERT(current != 0); 421 if (!(*this)(x.rhs)) 422 return false; 423 int const* p = current->find_var(x.lhs.name); 424 if (p == 0) 425 { 426 error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name); 427 return false; 428 } 429 current->op(op_store, *p); 430 return true; 431 } 432 operator ()(ast::variable_declaration const & x)433 bool compiler::operator()(ast::variable_declaration const& x) 434 { 435 BOOST_ASSERT(current != 0); 436 int const* p = current->find_var(x.lhs.name); 437 if (p != 0) 438 { 439 error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name); 440 return false; 441 } 442 if (x.rhs) // if there's an RHS initializer 443 { 444 bool r = (*this)(*x.rhs); 445 if (r) // don't add the variable if the RHS fails 446 { 447 current->add_var(x.lhs.name); 448 current->op(op_store, *current->find_var(x.lhs.name)); 449 } 450 return r; 451 } 452 else 453 { 454 current->add_var(x.lhs.name); 455 } 456 return true; 457 } 458 operator ()(ast::statement const & x)459 bool compiler::operator()(ast::statement const& x) 460 { 461 BOOST_ASSERT(current != 0); 462 return boost::apply_visitor(*this, x); 463 } 464 operator ()(ast::statement_list const & x)465 bool compiler::operator()(ast::statement_list const& x) 466 { 467 BOOST_ASSERT(current != 0); 468 BOOST_FOREACH(ast::statement const& s, x) 469 { 470 if (!(*this)(s)) 471 return false; 472 } 473 return true; 474 } 475 operator ()(ast::if_statement const & x)476 bool compiler::operator()(ast::if_statement const& x) 477 { 478 BOOST_ASSERT(current != 0); 479 if (!(*this)(x.condition)) 480 return false; 481 current->op(op_jump_if, 0); // we shall fill this (0) in later 482 std::size_t skip = current->size()-1; // mark its position 483 if (!(*this)(x.then)) 484 return false; 485 (*current)[skip] = current->size()-skip; // now we know where to jump to (after the if branch) 486 487 if (x.else_) // We got an alse 488 { 489 (*current)[skip] += 2; // adjust for the "else" jump 490 current->op(op_jump, 0); // we shall fill this (0) in later 491 std::size_t exit = current->size()-1; // mark its position 492 if (!(*this)(*x.else_)) 493 return false; 494 (*current)[exit] = current->size()-exit;// now we know where to jump to (after the else branch) 495 } 496 497 return true; 498 } 499 operator ()(ast::while_statement const & x)500 bool compiler::operator()(ast::while_statement const& x) 501 { 502 BOOST_ASSERT(current != 0); 503 std::size_t loop = current->size(); // mark our position 504 if (!(*this)(x.condition)) 505 return false; 506 current->op(op_jump_if, 0); // we shall fill this (0) in later 507 std::size_t exit = current->size()-1; // mark its position 508 if (!(*this)(x.body)) 509 return false; 510 current->op(op_jump, 511 int(loop-1) - int(current->size())); // loop back 512 (*current)[exit] = current->size()-exit; // now we know where to jump to (to exit the loop) 513 return true; 514 } 515 operator ()(ast::return_statement const & x)516 bool compiler::operator()(ast::return_statement const& x) 517 { 518 if (void_return) 519 { 520 if (x.expr) 521 { 522 error_handler(x.id, "'void' function returning a value: "); 523 return false; 524 } 525 } 526 else 527 { 528 if (!x.expr) 529 { 530 error_handler(x.id, current_function_name + " function must return a value: "); 531 return false; 532 } 533 } 534 535 if (x.expr) 536 { 537 if (!(*this)(*x.expr)) 538 return false; 539 } 540 current->op(op_return); 541 return true; 542 } 543 operator ()(ast::function const & x)544 bool compiler::operator()(ast::function const& x) 545 { 546 void_return = x.return_type == "void"; 547 if (functions.find(x.function_name.name) != functions.end()) 548 { 549 error_handler(x.function_name.id, "Duplicate function: " + x.function_name.name); 550 return false; 551 } 552 boost::shared_ptr<code_gen::function>& p = functions[x.function_name.name]; 553 p.reset(new code_gen::function(code, x.args.size())); 554 current = p.get(); 555 current_function_name = x.function_name.name; 556 557 // op_stk_adj 0 for now. we'll know how many variables 558 // we'll have later and add them 559 current->op(op_stk_adj, 0); 560 BOOST_FOREACH(ast::identifier const& arg, x.args) 561 { 562 current->add_var(arg.name); 563 } 564 565 if (!(*this)(x.body)) 566 return false; 567 (*current)[1] = current->nvars(); // now store the actual number of variables 568 // this includes the arguments 569 return true; 570 } 571 operator ()(ast::function_list const & x)572 bool compiler::operator()(ast::function_list const& x) 573 { 574 // Jump to the main function 575 code.push_back(op_jump); 576 code.push_back(0); // we will fill this in later when we finish compiling 577 // and we know where the main function is 578 579 BOOST_FOREACH(ast::function const& f, x) 580 { 581 if (!(*this)(f)) 582 { 583 code.clear(); 584 return false; 585 } 586 } 587 // find the main function 588 boost::shared_ptr<code_gen::function> p = 589 find_function("main"); 590 591 if (!p) // main function not found 592 { 593 std::cerr << "Error: main function not defined" << std::endl; 594 return false; 595 } 596 code[1] = p->get_address()-1; // jump to this (main function) address 597 598 return true; 599 } 600 print_assembler() const601 void compiler::print_assembler() const 602 { 603 typedef std::pair<std::string, boost::shared_ptr<code_gen::function> > pair; 604 BOOST_FOREACH(pair const& p, functions) 605 { 606 std::cout << ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;" << std::endl; 607 std::cout << p.second->get_address() << ": function " << p.first << std::endl; 608 p.second->print_assembler(); 609 } 610 } 611 612 boost::shared_ptr<code_gen::function> find_function(std::string const & name) const613 compiler::find_function(std::string const& name) const 614 { 615 function_table::const_iterator i = functions.find(name); 616 if (i == functions.end()) 617 return boost::shared_ptr<code_gen::function>(); 618 else 619 return i->second; 620 } 621 }} 622 623