1 8 9 package beaver.comp; 10 11 import java.util.Arrays ; 12 import java.util.Comparator ; 13 14 import beaver.comp.util.BitSet; 15 import beaver.comp.util.Log; 16 import beaver.spec.Grammar; 17 import beaver.spec.GrammarSymbol; 18 import beaver.spec.NonTerminal; 19 import beaver.spec.Production; 20 import beaver.spec.Terminal; 21 22 26 class Action 27 { 28 static final Comparator LOOKAHEAD_ID_COMPARATOR = new Comparator () 29 { 30 public int compare(Object o1, Object o2) 31 { 32 return ((Action) o1).lookahead.id - ((Action) o2).lookahead.id; 33 } 34 }; 35 36 39 static class Type 40 { 41 static class Conflict extends Type 42 { 43 static class ShiftReduce extends Conflict 44 { 45 ShiftReduce(Shift shift_act, Reduce reduce_act, State state, String reason) 46 { 47 super("shift-reduce", makeDescription(shift_act, reduce_act, state, reason)); 48 } 49 50 static private String makeDescription(Shift shift_act, Reduce reduce_act, State state, String reason) 51 { 52 StringBuffer text = new StringBuffer (256) 53 .append("\n\tshift ") 54 .append(shift_act.lookahead.name) 55 .append(" in:"); 56 for (Configuration conf = state.conf_set.first_conf; conf != null; conf = conf.next) 57 { 58 if (conf.dot < conf.rule.rhs.items.length && conf.rule.rhs.items[conf.dot].symbol == shift_act.lookahead) 59 { 60 text.append("\n\t\t").append(conf); 61 } 62 } 63 text.append("\n\tor reduce:\n\t\t") 64 .append(reduce_act.rule.toString()); 65 int line = reduce_act.rule.getFirstLine(); 66 if (line > 0) 67 { 68 text.append(" @ ").append(line); 69 } 70 text.append("\n\t- ") 71 .append(reason); 72 73 return text.toString(); 74 } 75 } 76 77 static class ReduceReduce extends Conflict 78 { 79 ReduceReduce(Reduce act1, Reduce act2, State state, String reason) 80 { 81 super("reduce-reduce", makeDescription(act1, act2, state, reason)); 82 } 83 84 static private String makeDescription(Reduce act1, Reduce act2, State state, String reason) 85 { 86 StringBuffer text = new StringBuffer (256) 87 .append("\n\treduce\t") 88 .append(act1.rule); 89 int line; 90 if ((line = act1.rule.getFirstLine()) > 0) 91 text.append(" @ ").append(line); 92 text.append("\n\tor\t") 93 .append(act2.rule); 94 if ((line = act2.rule.getFirstLine()) > 0) 95 text.append(" @ ").append(line); 96 text.append("\n\ton ") 97 .append(act1.lookahead.name) 98 .append(" - ") 99 .append(reason); 100 return text.toString(); 101 } 102 } 103 104 private String descr; 105 106 Conflict(String type, String details) 107 { 108 super(0, type + " conflict"); 109 descr = details; 110 } 111 112 public String toString() 113 { 114 return new StringBuffer (super.toString().length() + 2 + descr.length()) 115 .append(super.toString()) 116 .append(": ") 117 .append(descr) 118 .toString(); 119 } 120 } 121 122 static final Type SHIFT = new Type(1, "SHIFT"); 123 static final Type REDUCE = new Type(2, "REDUCE"); 124 static final Type ACCEPT = new Type(3, "ACCEPT"); 125 static final Type RESOLVED = new Type(-1, "RESOLVED"); 126 static final Type NOT_USED = new Type(-2, "NOT USED"); 127 128 private int id; 129 private String name; 130 131 Type(int id, String name) 132 { 133 this.id = id; 134 this.name = name; 135 } 136 137 boolean isRemovable() 138 { 139 return id < 0; 140 } 141 142 boolean isResolved() 143 { 144 return id <= 0; 145 } 146 147 public String toString() 148 { 149 return name; 150 } 151 } 152 153 156 static class Shift extends Action 157 { 158 State state; 159 160 Shift(GrammarSymbol lookahead, State state) 161 { 162 super(Type.SHIFT, lookahead); 163 this.state = state; 164 } 165 166 172 boolean resolveConflict(Action act, State act_state, Log log) 173 { 174 if (!(act instanceof Reduce)) 175 throw new IllegalArgumentException ("shift-reduce expected, \"" + act + "\" found"); 176 177 Reduce reduce_act = (Reduce) act; 178 Terminal reduce_prec_sym = reduce_act.rule.prec_sym; 179 180 if (this.lookahead instanceof NonTerminal) 181 { 182 act.type = new Type.Conflict.ShiftReduce(this, reduce_act, act_state, lookahead.name + " is a non-terminal"); 183 return false; 184 } 185 Terminal shift_prec_sym = (Terminal) this.lookahead; 186 187 if (shift_prec_sym.prec > reduce_prec_sym.prec) 188 { 189 if (reduce_prec_sym.prec < 0) 190 { 191 log.warning("Resolved Shift-Reduce conflict by selecting (" + this.toString() + ") over (" + act.toString() + ") using precedence."); 192 } 193 act.type = Type.RESOLVED; 194 return true; 195 } 196 if (shift_prec_sym.prec < reduce_prec_sym.prec) 197 { 198 if (shift_prec_sym.prec < 0) 199 { 200 log.warning("Resolved Shift-Reduce conflict by selecting (" + act.toString() + ") over (" + this.toString() + ") using precedence."); 201 } 202 this.type = Type.RESOLVED; 203 return true; 204 } 205 if (shift_prec_sym.assoc == Terminal.Associativity.RIGHT) 209 { 210 act.type = Type.RESOLVED; 211 return true; 212 } 213 if (shift_prec_sym.assoc == Terminal.Associativity.LEFT) 214 { 215 this.type = Type.RESOLVED; 216 return true; 217 } 218 219 act.type = new Type.Conflict.ShiftReduce(this, reduce_act, act_state, shift_prec_sym.prec > 0 ? lookahead.name + " is nonassociative" : "insufficient precedence information"); 220 return false; 221 } 222 223 226 short getId() 227 { 228 return (short) state.id; 229 } 230 231 public String toString() 232 { 233 return lookahead + ": " + type + "; goto " + state.id; 234 } 235 } 236 237 240 static class Reduce extends Action 241 { 242 246 static class Maker extends BitSet.Processor 247 { 248 Terminal[] terminals; 249 State state; 250 Production rule; 251 252 Maker(Terminal[] terminals, State first_state) 253 { 254 this.terminals = terminals; 255 this.state = first_state; 256 } 257 258 264 void buildReduceActions() 265 { 266 for (; state != null; state = state.next) 267 { 268 for (Configuration conf = state.conf_set.first_conf; conf != null; conf = conf.next) 269 { 270 if (conf.dot == conf.rule.rhs.items.length) 271 { 272 rule = conf.rule; 273 conf.lookaheads.forEachElementRun(this); 274 } 275 } 276 } 277 } 278 279 284 protected void process(int index) 285 { 286 state.actions.add(new Reduce(terminals[index], rule)); 287 } 288 } 289 290 Production rule; 291 292 Reduce(Terminal lookahead, Production rule) 293 { 294 super(Type.REDUCE, lookahead); 295 this.rule = rule; 296 } 297 298 304 boolean resolveConflict(Action act, State act_state, Log log) 305 { 306 if (!(act instanceof Reduce)) 307 throw new IllegalArgumentException ("reduce-reduce expected"); 308 309 Terminal my_prec_sym = rule.prec_sym; 310 Reduce reduce_act = (Reduce) act; 311 Terminal act_prec_sym = reduce_act.rule.prec_sym; 312 313 if (my_prec_sym.prec > act_prec_sym.prec) 314 { 315 act.type = Type.RESOLVED; 316 return true; 317 } 318 if (my_prec_sym.prec < act_prec_sym.prec) 319 { 320 this.type = Type.RESOLVED; 321 return true; 322 } 323 act.type = new Type.Conflict.ReduceReduce(this, reduce_act, act_state, "equal precedence"); 325 return false; 326 } 327 328 331 short getId() 332 { 333 return (short) ~rule.id; 334 } 335 336 public String toString() 337 { 338 return lookahead != null ? lookahead + ": " + type + " " + rule : "[any]: REDUCE " + rule; 339 } 340 } 341 342 345 static class Accept extends Action 346 { 347 private short id; 348 349 Accept(Grammar grammar) 350 { 351 super(Type.ACCEPT, grammar.goal_symbol); 352 id = (short) ~ grammar.rules.length; 353 } 354 355 358 short getId() 359 { 360 return id; 361 } 362 } 363 364 367 static class List 368 { 369 static final Comparator NUM_ACTIONS_CMP = new Comparator () 370 { 371 public int compare(Object o1, Object o2) 372 { 373 return ((Action.List) o2).num_actions - ((Action.List) o1).num_actions; 374 } 375 }; 376 377 State state; 378 Action first; 379 Action last; 380 int num_actions; 381 382 List(State state) 383 { 384 this.state = state; 385 } 386 387 void add(Action act) 388 { 389 if (last == null) 390 last = first = act; 391 else 392 last = last.next = act; 393 num_actions++; 394 } 395 396 408 int resolveConflicts(Log log) 409 { 410 int num_conflicts = 0; 411 if (first != null && num_actions > 1) 412 { 413 for (Action act = first; act != last; act = act.next) 414 { 415 if (!act.type.isResolved()) 416 { 417 for (Action cmp = act.next; cmp != null; cmp = cmp.next) 418 { 419 if (cmp.lookahead == act.lookahead && !act.resolveConflict(cmp, state, log)) 420 { 421 num_conflicts++; 422 } 423 } 424 } 425 } 426 removeResolvedActions(); 427 } 428 return num_conflicts; 429 } 430 431 void reportConflicts(Log log) 432 { 433 if (first != null && num_actions > 1) 434 { 435 for (Action act = first; act != null; act = act.next) 436 { 437 if (act.type instanceof Type.Conflict) 438 { 439 log.error(act.type.toString()); 440 } 441 } 442 } 443 } 444 445 private void removeResolvedActions() 446 { 447 while (first != null && first.type.isRemovable()) 448 { 449 first = first.next; 450 num_actions--; 451 } 452 last = first; 453 for (Action next = first.next; next != null; next = next.next) 454 { 455 if (next.type.isRemovable()) 456 { 457 num_actions--; 458 } 459 else 460 { 461 last = last.next = next; 462 } 463 } 464 last.next = null; 465 } 466 467 471 void markReducibleProductions() 472 { 473 for (Action act = first; act != null; act = act.next) 474 { 475 if (act.type == Type.REDUCE) 476 { 477 ((Reduce) act).rule.is_reducible = true; 478 } 479 } 480 } 481 482 492 void compress() 493 { 494 Production maxrule = null; 495 int maxcnt = 0; 496 497 for (Action act = first; act != null; act = act.next) 498 { 499 if (act.type == Type.REDUCE) 500 { 501 Production rule = ((Reduce) act).rule; 502 if (rule == maxrule) continue; 503 int cnt = 1; 504 for (Action cmp = act.next; cmp != null; cmp = cmp.next) 505 { 506 if (cmp.type == Type.REDUCE && ((Reduce) cmp).rule == rule) 507 { 508 cnt++; 509 } 510 } 511 if (cnt > maxcnt) 512 { 513 maxrule = rule; 514 maxcnt = cnt; 515 } 516 } 517 } 518 519 if (maxcnt > 1) 520 { 521 Action act = first; 522 while (act.type != Type.REDUCE || ((Reduce) act).rule != maxrule) 523 { 524 act = act.next; 525 } 526 act.lookahead = null; 527 for (act = act.next; act != null; act = act.next) 528 { 529 if (act.type == Type.REDUCE && ((Reduce) act).rule == maxrule) 530 { 531 act.type = Type.NOT_USED; 532 } 533 } 534 } 535 } 536 537 546 Action split(List terminal_actions, List nonterminal_actions) 547 { 548 Action default_act = null, first_not_used = null, last_not_used = null; 549 this.num_actions = 0; 550 for (Action act = first; act != null; act = act.next) 551 { 552 if (act.type.isRemovable()) 553 { 554 if (last_not_used == null) 555 last_not_used = first_not_used = act; 556 else 557 last_not_used = last_not_used.next = act; 558 num_actions++; 559 } 560 else 561 { 562 if (act.lookahead instanceof NonTerminal) 563 nonterminal_actions.add(act); 564 else if (act.lookahead instanceof Terminal) 565 terminal_actions.add(act); 566 else { 568 if (default_act != null) 569 throw new IllegalStateException ("multiple default actions in state " + state.id + " actions list"); 570 default_act = act; 571 } 572 } 573 } 574 first = first_not_used; 575 last = last_not_used; 576 577 if (last_not_used != null) 578 last_not_used.next = null; 579 580 if (default_act != null) 581 default_act.next = null; 582 583 if (terminal_actions.last != null) 584 terminal_actions.last.next = null; 585 586 if (nonterminal_actions.last != null) 587 nonterminal_actions.last.next = null; 588 589 terminal_actions.sort(); 590 nonterminal_actions.sort(); 591 592 return default_act; 593 } 594 595 598 void sort() 599 { 600 if (num_actions > 1) 601 { 602 Action[] actions = new Action[num_actions]; 603 int i = 0; 604 for (Action act = first; act != null; act = act.next) 605 { 606 actions[i++] = act; 607 } 608 Arrays.sort(actions, LOOKAHEAD_ID_COMPARATOR); 609 610 Action act = first = actions[i = 0]; 611 while (++i < num_actions) 612 { 613 act = act.next = actions[i]; 614 } 615 (last = act).next = null; 616 } 617 } 618 } 619 620 621 Action next; 622 623 624 Type type; 625 626 627 GrammarSymbol lookahead; 628 629 Action(Type type, GrammarSymbol lookahead) 630 { 631 this.type = type; 632 this.lookahead = lookahead; 633 } 634 635 short getId() 636 { 637 return 0; 638 } 639 640 boolean resolveConflict(Action act, State state, Log log) 641 { 642 throw new IllegalStateException ("only shift-reduce or reduce-reduce conflicts are expected"); 643 } 644 645 public String toString() 646 { 647 return lookahead + ": " + type; 648 } 649 } 650 | Popular Tags |