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