1 2 package java_cup; 3 4 import java.io.PrintStream; 5 import java.util.Stack; 6 import java.util.Enumeration; 7 import java.util.Date; 8 9 /** 10 * This class handles emitting generated code for the resulting parser. 11 * The various parse tables must be constructed, etc. before calling any 12 * routines in this class.<p> 13 * 14 * Three classes are produced by this code: 15 * <dl> 16 * <dt> symbol constant class 17 * <dd> this contains constant declarations for each terminal (and 18 * optionally each non-terminal). 19 * <dt> action class 20 * <dd> this non-public class contains code to invoke all the user actions 21 * that were embedded in the parser specification. 22 * <dt> parser class 23 * <dd> the specialized parser class consisting primarily of some user 24 * supplied general and initialization code, and the parse tables. 25 * </dl><p> 26 * 27 * Three parse tables are created as part of the parser class: 28 * <dl> 29 * <dt> production table 30 * <dd> lists the LHS non terminal number, and the length of the RHS of 31 * each production. 32 * <dt> action table 33 * <dd> for each state of the parse machine, gives the action to be taken 34 * (shift, reduce, or error) under each lookahead symbol.<br> 35 * <dt> reduce-goto table 36 * <dd> when a reduce on a given production is taken, the parse stack is 37 * popped back a number of elements corresponding to the RHS of the 38 * production. This reveals a prior state, which we transition out 39 * of under the LHS non terminal symbol for the production (as if we 40 * had seen the LHS symbol rather than all the symbols matching the 41 * RHS). This table is indexed by non terminal numbers and indicates 42 * how to make these transitions. 43 * </dl><p> 44 * 45 * In addition to the method interface, this class maintains a series of 46 * public global variables and flags indicating how misc. parts of the code 47 * and other output is to be produced, and counting things such as number of 48 * conflicts detected (see the source code and public variables below for 49 * more details).<p> 50 * 51 * This class is "static" (contains only static data and methods).<p> 52 * 53 * @see java_cup.main 54 * @version last update: 11/25/95 55 * @author Scott Hudson 56 */ 57 58 /* Major externally callable routines here include: 59 symbols - emit the symbol constant class 60 parser - emit the parser class 61 62 In addition the following major internal routines are provided: 63 emit_package - emit a package declaration 64 emit_action_code - emit the class containing the user's actions 65 emit_production_table - emit declaration and init for the production table 66 do_action_table - emit declaration and init for the action table 67 do_reduce_table - emit declaration and init for the reduce-goto table 68 69 Finally, this class uses a number of public instance variables to communicate 70 optional parameters and flags used to control how code is generated, 71 as well as to report counts of various things (such as number of conflicts 72 detected). These include: 73 74 prefix - a prefix string used to prefix names that would 75 otherwise "pollute" someone else's name space. 76 package_name - name of the package emitted code is placed in 77 (or null for an unnamed package. 78 symbol_const_class_name - name of the class containing symbol constants. 79 parser_class_name - name of the class for the resulting parser. 80 action_code - user supplied declarations and other code to be 81 placed in action class. 82 parser_code - user supplied declarations and other code to be 83 placed in parser class. 84 init_code - user supplied code to be executed as the parser 85 is being initialized. 86 scan_code - user supplied code to get the next token. 87 start_production - the start production for the grammar. 88 import_list - list of imports for use with action class. 89 num_conflicts - number of conflicts detected. 90 nowarn - true if we are not to issue warning messages. 91 not_reduced - count of number of productions that never reduce. 92 unused_term - count of unused terminal symbols. 93 unused_non_term - count of unused non terminal symbols. 94 *_time - a series of symbols indicating how long various 95 sub-parts of code generation took (used to produce 96 optional time reports in main). 97 */ 98 99 public class emit { 100 101 /*-----------------------------------------------------------*/ 102 /*--- Constructor(s) ----------------------------------------*/ 103 /*-----------------------------------------------------------*/ 104 105 /** Only constructor is private so no instances can be created. */ emit()106 private emit() { } 107 108 /*-----------------------------------------------------------*/ 109 /*--- Static (Class) Variables ------------------------------*/ 110 /*-----------------------------------------------------------*/ 111 112 public static String input_file_name; 113 114 /** The prefix placed on names that pollute someone else's name space. */ 115 public static String prefix = "CUP$"; 116 117 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 118 119 /** Package that the resulting code goes into (null is used for unnamed). */ 120 public static String package_name = null; 121 122 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 123 124 /** Name of the generated class for symbol constants. */ 125 public static String symbol_const_class_name = "sym"; 126 127 128 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 129 130 /** Name of the generated parser class. */ 131 public static String parser_class_name = "parser"; 132 133 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 134 135 /** User declarations for direct inclusion in user action class. */ 136 public static String action_code = null; 137 138 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 139 140 /** User declarations for direct inclusion in parser class. */ 141 public static String parser_code = null; 142 143 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 144 145 /** User code for user_init() which is called during parser initialization. */ 146 public static String init_code = null; 147 148 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 149 150 /** User code for scan() which is called to get the next token. */ 151 public static String scan_code = null; 152 153 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 154 155 /** The start production of the grammar. */ 156 public static production start_production = null; 157 158 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 159 160 /** List of imports (Strings containing class names) to go with actions. */ 161 public static Stack import_list = new Stack(); 162 163 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 164 165 /** Number of conflict found while building tables. */ 166 public static int num_conflicts = 0; 167 168 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 169 170 /** Do we skip warnings? */ 171 public static boolean nowarn = false; 172 173 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 174 175 /** Count of the number on non-reduced productions found. */ 176 public static int not_reduced = 0; 177 178 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 179 180 /** Count of unused terminals. */ 181 public static int unused_term = 0; 182 183 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 184 185 /** Count of unused non terminals. */ 186 public static int unused_non_term = 0; 187 188 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 189 190 /* Timing values used to produce timing report in main.*/ 191 192 /** Time to produce symbol constant class. */ 193 public static long symbols_time = 0; 194 195 /** Time to produce parser class. */ 196 public static long parser_time = 0; 197 198 /** Time to produce action code class. */ 199 public static long action_code_time = 0; 200 201 /** Time to produce the production table. */ 202 public static long production_table_time = 0; 203 204 /** Time to produce the action table. */ 205 public static long action_table_time = 0; 206 207 /** Time to produce the reduce-goto table. */ 208 public static long goto_table_time = 0; 209 210 /** Do we produce calls debug_gammar in generated parser? */ 211 public static String debug_grammar = null; 212 213 /*-----------------------------------------------------------*/ 214 /*--- General Methods ---------------------------------------*/ 215 /*-----------------------------------------------------------*/ 216 217 /** Build a string with the standard prefix. 218 * @param str string to prefix. 219 */ pre(String str)220 protected static String pre(String str) {return prefix + str;} 221 222 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 223 224 /** Emit a package spec if the user wants one. 225 * @param out stream to produce output on. 226 */ emit_package(PrintStream out)227 protected static void emit_package(PrintStream out) 228 { 229 /* generate a package spec if we have a name for one */ 230 if (package_name != null) 231 out.println("package " + package_name + ";\n"); 232 233 } 234 235 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 236 237 /** Emit code for the symbol constant class, optionally including non terms, 238 * if they have been requested. 239 * @param out stream to produce output on. 240 * @param emit_non_terms do we emit constants for non terminals? 241 */ symbols(PrintStream out, boolean emit_non_terms)242 public static void symbols(PrintStream out, boolean emit_non_terms) 243 { 244 terminal term; 245 non_terminal nt; 246 247 long start_time = System.currentTimeMillis(); 248 249 /* top of file */ 250 out.println(); 251 out.println("//----------------------------------------------------"); 252 out.println("// The following code was generated by " + 253 version.title_str); 254 out.println("// " + new Date()); 255 out.println("//----------------------------------------------------"); 256 out.println(); 257 emit_package(out); 258 259 /* class header */ 260 out.println( 261 "/** JavaCup generated class containing symbol constants. */"); 262 out.println("public class " + symbol_const_class_name + " {"); 263 264 out.println(" /* terminals */"); 265 266 /* walk over the terminals */ /* later might sort these */ 267 for (Enumeration e = terminal.all(); e.hasMoreElements(); ) 268 { 269 term = (terminal)e.nextElement(); 270 271 /* output a constant decl for the terminal */ 272 out.println(" static final int " + term.name() + " = " + 273 term.index() + ";"); 274 } 275 276 /* do the non terminals if they want them (parser doesn't need them) */ 277 if (emit_non_terms) 278 { 279 out.println("\n /* non terminals */"); 280 281 /* walk over the non terminals */ /* later might sort these */ 282 for (Enumeration e = non_terminal.all(); e.hasMoreElements(); ) 283 { 284 nt = (non_terminal)e.nextElement(); 285 286 /* output a constant decl for the terminal */ 287 out.println(" static final int " + nt.name() + " = " + 288 nt.index() + ";"); 289 } 290 } 291 292 /* end of class */ 293 out.println("};\n"); 294 295 symbols_time = System.currentTimeMillis() - start_time; 296 } 297 298 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 299 300 /** Emit code for the non-public class holding the actual action code. 301 * @param out stream to produce output on. 302 * @param start_prod the start production of the grammar. 303 */ emit_action_code(PrintStream out, production start_prod)304 protected static void emit_action_code(PrintStream out, production start_prod) 305 throws internal_error 306 { 307 production prod; 308 309 long start_time = System.currentTimeMillis(); 310 311 /* class header */ 312 out.println(); 313 out.println( 314 "/** JavaCup generated class to encapsulate user supplied action code.*/" 315 ); 316 out.println("class " + pre("actions") + " {"); 317 318 /* user supplied code */ 319 if (action_code != null) 320 { 321 out.println(); 322 out.println(action_code); 323 } 324 325 /* constructor */ 326 out.println(); 327 out.println(" /** Constructor */"); 328 out.println(" " + pre("actions") + "() { }"); 329 330 /* action method head */ 331 out.println(); 332 out.println(" /** Method with the actual generated action code. */"); 333 out.println(" public final java_cup.runtime.symbol " + 334 pre("do_action") + "("); 335 out.println(" int " + pre("act_num,")); 336 out.println(" java_cup.runtime.lr_parser " + pre("parser,")); 337 out.println(" java.util.Stack " + pre("stack,")); 338 out.println(" int " + pre("top)")); 339 out.println(" throws java.lang.Exception"); 340 out.println(" {"); 341 342 /* declaration of result symbol */ 343 out.println(" /* object for return from actions */"); 344 out.println(" java_cup.runtime.symbol " + pre("result") + ";"); 345 out.println(); 346 347 /* switch top */ 348 out.println(" /* select the action based on the action number */"); 349 out.println(" switch (" + pre("act_num") + ")"); 350 out.println(" {"); 351 352 /* emit action code for each production as a separate case */ 353 for (Enumeration p = production.all(); p.hasMoreElements(); ) 354 { 355 prod = (production)p.nextElement(); 356 357 /* case label */ 358 out.println(" /*. . . . . . . . . . . . . . . . . . . .*/"); 359 out.println(" case " + prod.index() + ": // " + 360 prod.to_simple_string()); 361 362 /* give them their own block to work in */ 363 out.println(" {"); 364 365 /* user supplied code for debug_grammar() */ 366 if (debug_grammar != null) 367 out.println(" " +debug_grammar+ "(\"" + 368 prod.to_simple_string() + "\");"); 369 370 /* create the result symbol */ 371 out.println(" " + pre("result") + " = new " + 372 prod.lhs().the_symbol().stack_type() + "(/*" + 373 prod.lhs().the_symbol().name() + "*/" + 374 prod.lhs().the_symbol().index() + ");"); 375 376 /* if there is an action string, emit it */ 377 if (prod.action() != null && prod.action().code_string() != null && 378 !prod.action().equals("")) 379 out.println(" " + prod.action().code_string()); 380 381 /* end of their block */ 382 out.println(" }"); 383 384 /* if this was the start production, do action for accept */ 385 if (prod == start_prod) 386 { 387 out.println(" /* ACCEPT */"); 388 out.println(" " + pre("parser") + ".done_parsing();"); 389 } 390 391 /* code to return lhs symbol */ 392 out.println(" return " + pre("result") + ";"); 393 out.println(); 394 } 395 396 /* end of switch */ 397 out.println(" /* . . . . . .*/"); 398 out.println(" default:"); 399 out.println(" throw new Exception("); 400 out.println(" \"Invalid action number found in " + 401 "internal parse table\");"); 402 out.println(); 403 out.println(" }"); 404 405 /* end of method */ 406 out.println(" }"); 407 408 /* end of class */ 409 out.println("};\n"); 410 411 action_code_time = System.currentTimeMillis() - start_time; 412 } 413 414 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 415 416 /** Emit the production table. 417 * @param out stream to produce output on. 418 */ emit_production_table(PrintStream out)419 protected static void emit_production_table(PrintStream out) 420 { 421 production all_prods[]; 422 production prod; 423 424 long start_time = System.currentTimeMillis(); 425 426 /* do the top of the table */ 427 out.println(); 428 out.println(" /** production table */"); 429 out.println(" protected static final short _production_table[][] = {"); 430 431 /* collect up the productions in order */ 432 all_prods = new production[production.number()]; 433 for (Enumeration p = production.all(); p.hasMoreElements(); ) 434 { 435 prod = (production)p.nextElement(); 436 all_prods[prod.index()] = prod; 437 } 438 439 /* do one entry per production */ 440 out.print(" "); 441 for (int i = 0; i<production.number(); i++) 442 { 443 prod = all_prods[i]; 444 445 /* make the table entry */ 446 out.print(" {"); 447 out.print(/* lhs symbol # */ prod.lhs().the_symbol().index() + ", "); 448 out.print(/* rhs size */ prod.rhs_length() + "}"); 449 450 /* put in a comma if we aren't at the end */ 451 if (i < production.number()-1) out.print(", "); 452 453 /* 5 entries per line */ 454 if ((i+1) % 5 == 0) 455 { 456 out.println(); 457 out.print(" "); 458 } 459 } 460 461 /* finish off the table initializer */ 462 out.println(" };"); 463 464 /* do the public accessor method */ 465 out.println(); 466 out.println(" /** access to production table */"); 467 out.println(" public short[][] production_table() " + 468 "{return _production_table;}"); 469 470 production_table_time = System.currentTimeMillis() - start_time; 471 } 472 473 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 474 475 /** Emit the action table. 476 * @param out stream to produce output on. 477 * @param act_tab the internal representation of the action table. 478 * @param compact_reduces do we use the most frequent reduce as default? 479 */ do_action_table( PrintStream out, parse_action_table act_tab, boolean compact_reduces)480 protected static void do_action_table( 481 PrintStream out, 482 parse_action_table act_tab, 483 boolean compact_reduces) 484 throws internal_error 485 { 486 parse_action_row row; 487 parse_action act; 488 int red; 489 490 long start_time = System.currentTimeMillis(); 491 492 out.println(); 493 out.println(" /** parse action table */"); 494 out.println(" protected static final short[][] _action_table = {"); 495 496 /* do each state (row) of the action table */ 497 for (int i = 0; i < act_tab.num_states(); i++) 498 { 499 /* get the row */ 500 row = act_tab.under_state[i]; 501 502 /* determine the default for the row */ 503 if (compact_reduces) 504 row.compute_default(); 505 else 506 row.default_reduce = -1; 507 508 out.print(" /*" + i + "*/{"); 509 510 /* do each column */ 511 for (int j = 0; j < row.size(); j++) 512 { 513 /* extract the action from the table */ 514 act = row.under_term[j]; 515 516 /* skip error entries these are all defaulted out */ 517 if (act.kind() != parse_action.ERROR) 518 { 519 /* first put in the symbol index, then the actual entry */ 520 521 /* shifts get positive entries of state number + 1 */ 522 if (act.kind() == parse_action.SHIFT) 523 { 524 out.print(j + "," + 525 (((shift_action)act).shift_to().index() + 1) + ","); 526 } 527 528 /* reduce actions get negated entries of production# + 1 */ 529 else if (act.kind() == parse_action.REDUCE) 530 { 531 /* if its the default entry let it get defaulted out */ 532 red = ((reduce_action)act).reduce_with().index(); 533 if (red != row.default_reduce) 534 out.print(j + "," + (-(red+1)) + ","); 535 } 536 537 /* shouldn't be anything else */ 538 else 539 throw new internal_error("Unrecognized action code " + 540 act.kind() + " found in parse table"); 541 } 542 } 543 544 /* finish off the row with a default entry */ 545 if (row.default_reduce != -1) 546 out.println("-1," + (-(row.default_reduce+1)) + "},"); 547 else 548 out.println("-1,0},"); 549 } 550 551 /* finish off the init of the table */ 552 out.println(" };"); 553 554 /* do the public accessor method */ 555 out.println(); 556 out.println(" /** access to parse action table */"); 557 out.println(" public short[][] action_table() {return _action_table;}"); 558 559 action_table_time = System.currentTimeMillis() - start_time; 560 } 561 562 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 563 564 /** Emit the reduce-goto table. 565 * @param out stream to produce output on. 566 * @param red_tab the internal representation of the reduce-goto table. 567 */ do_reduce_table( PrintStream out, parse_reduce_table red_tab)568 protected static void do_reduce_table( 569 PrintStream out, 570 parse_reduce_table red_tab) 571 { 572 lalr_state goto_st; 573 parse_action act; 574 575 long start_time = System.currentTimeMillis(); 576 577 out.println(); 578 out.println(" /** reduce_goto table */"); 579 out.println(" protected static final short[][] _reduce_table = {"); 580 581 /* do each row of the reduce-goto table */ 582 for (int i=0; i<red_tab.num_states(); i++) 583 { 584 out.print(" /*" + i + "*/{"); 585 586 /* do each entry in the row */ 587 for (int j=0; j<red_tab.under_state[i].size(); j++) 588 { 589 /* get the entry */ 590 goto_st = red_tab.under_state[i].under_non_term[j]; 591 592 /* if we have none, skip it */ 593 if (goto_st != null) 594 { 595 /* make entries for the index and the value */ 596 out.print(j + "," + goto_st.index() + ","); 597 } 598 } 599 600 /* end row with default value */ 601 out.println("-1,-1},"); 602 } 603 604 /* finish off the init of the table */ 605 out.println(" };"); 606 607 /* do the public accessor method */ 608 out.println(); 609 out.println(" /** access to reduce_goto table */"); 610 out.println(" public short[][] reduce_table() {return _reduce_table;}"); 611 out.println(); 612 613 goto_table_time = System.currentTimeMillis() - start_time; 614 } 615 616 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 617 618 /** Emit the parser subclass with embedded tables. 619 * @param out stream to produce output on. 620 * @param action_table internal representation of the action table. 621 * @param reduce_table internal representation of the reduce-goto table. 622 * @param start_st start state of the parse machine. 623 * @param start_prod start production of the grammar. 624 * @param compact_reduces do we use most frequent reduce as default? 625 */ parser( PrintStream out, parse_action_table action_table, parse_reduce_table reduce_table, int start_st, production start_prod, boolean compact_reduces)626 public static void parser( 627 PrintStream out, 628 parse_action_table action_table, 629 parse_reduce_table reduce_table, 630 int start_st, 631 production start_prod, 632 boolean compact_reduces) 633 throws internal_error 634 { 635 long start_time = System.currentTimeMillis(); 636 637 /* top of file */ 638 out.println(); 639 out.println("//----------------------------------------------------"); 640 out.println("// The following code was generated by " + 641 version.title_str); 642 out.println("// " + new Date()); 643 out.println("//----------------------------------------------------"); 644 out.println(); 645 emit_package(out); 646 647 /* user supplied imports */ 648 for (int i = 0; i < import_list.size(); i++) 649 out.println("import " + import_list.elementAt(i) + ";"); 650 651 /* class header */ 652 out.println(); 653 out.println("public class " + parser_class_name + 654 " extends java_cup.runtime.lr_parser {"); 655 656 /* constructor */ 657 out.println(); 658 out.println(" /** constructor */"); 659 out.println(" public " + parser_class_name + "() {super();}"); 660 661 /* emit the various tables */ 662 emit_production_table(out); 663 do_action_table(out, action_table, compact_reduces); 664 do_reduce_table(out, reduce_table); 665 666 /* instance of the action encapsulation class */ 667 out.println(" /** instance of action encapsulation class */"); 668 out.println(" protected " + pre("actions") + " action_obj;"); 669 out.println(); 670 671 /* action object initializer */ 672 out.println(" /** action encapsulation object initializer */"); 673 out.println(" protected void init_actions()"); 674 out.println(" {"); 675 out.println(" action_obj = new " + pre("actions") + "();"); 676 out.println(" }"); 677 out.println(); 678 679 /* access to action code */ 680 out.println(" /** invoke a user supplied parse action */"); 681 out.println(" public java_cup.runtime.symbol do_action("); 682 out.println(" int act_num,"); 683 out.println(" java_cup.runtime.lr_parser parser,"); 684 out.println(" java.util.Stack stack,"); 685 out.println(" int top)"); 686 out.println(" throws java.lang.Exception"); 687 out.println(" {"); 688 out.println(" /* call code in generated class */"); 689 out.println(" return action_obj." + pre("do_action(") + 690 "act_num, parser, stack, top);"); 691 out.println(" }"); 692 out.println(""); 693 694 695 /* method to tell the parser about the start state */ 696 out.println(" /** start state */"); 697 out.println(" public int start_state() {return " + start_st + ";}"); 698 699 /* method to indicate start production */ 700 out.println(" /** start production */"); 701 out.println(" public int start_production() {return " + 702 start_production.index() + ";}"); 703 out.println(); 704 705 /* methods to indicate EOF and error symbol indexes */ 706 out.println(" /** EOF symbol index */"); 707 out.println(" public int EOF_sym() {return " + terminal.EOF.index() + 708 ";}"); 709 out.println(); 710 out.println(" /** error symbol index */"); 711 out.println(" public int error_sym() {return " + terminal.error.index() + 712 ";}"); 713 out.println(); 714 715 /* user supplied code for user_init() */ 716 if (init_code != null) 717 { 718 out.println(); 719 out.println(" /** user initialization */"); 720 out.println(" public void user_init() throws java.lang.Exception"); 721 out.println(" {"); 722 out.println(init_code); 723 out.println(" }"); 724 } 725 726 /* user supplied code for scan */ 727 if (scan_code != null) 728 { 729 out.println(); 730 out.println(" /** scan to get the next token */"); 731 out.println(" public java_cup.runtime.token scan()"); 732 out.println(" throws java.lang.Exception"); 733 out.println(" {"); 734 out.println(scan_code); 735 out.println(" }"); 736 } 737 738 /* user supplied code */ 739 if (parser_code != null) 740 { 741 out.println(); 742 out.println(parser_code); 743 } 744 745 /* end of class */ 746 out.println("};"); 747 748 /* put out the action code class */ 749 emit_action_code(out, start_prod); 750 751 parser_time = System.currentTimeMillis() - start_time; 752 } 753 754 /*-----------------------------------------------------------*/ 755 }; 756