1 package fri.patterns.interpreter.parsergenerator.parsertables; 2 3 import java.util.*; 4 import fri.patterns.interpreter.parsergenerator.Token; 5 import fri.patterns.interpreter.parsergenerator.ParserTables; 6 import fri.patterns.interpreter.parsergenerator.syntax.*; 7 8 25 26 class SLRSyntaxNode 27 { 28 29 protected Hashtable entries = new Hashtable(); 30 31 private int kernels = 0; 32 private Integer hashCache = null; 33 34 35 36 public SLRSyntaxNode() { 37 } 38 39 40 protected SLRSyntaxNode createSyntaxNode() { 41 return new SLRSyntaxNode(); 42 } 43 44 45 protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) { 46 return new RuleStateItem(ruleIndex, rule); 47 } 48 49 50 58 public List build(Syntax syntax, List syntaxNodes, Hashtable kernels) { 59 RuleStateItem item = createRuleStateItem(0, syntax.getRule(0)); 61 entries.put(item, item); 62 closure(syntax); 64 syntaxNodes.add(this); 66 generateSyntaxNodes(syntaxNodes, syntax, kernels); 68 return syntaxNodes; 70 } 71 72 73 79 protected void generateSyntaxNodes(List syntaxNodes, Syntax syntax, Hashtable kernels) { 80 for (int i = 0; i < syntaxNodes.size(); i++) { 82 SLRSyntaxNode node = (SLRSyntaxNode)syntaxNodes.get(i); 83 node.generateSyntaxNodesFromItems(syntaxNodes, syntax, kernels); 84 } 85 } 86 87 93 protected void generateSyntaxNodesFromItems(List syntaxNodes, Syntax syntax, Hashtable kernels) { 94 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) { 95 RuleStateItem item = (RuleStateItem)e.nextElement(); 96 String pending = item.getPendingSymbol(); 97 98 if (item.followNodeIndex < 0 && pending != null) { SLRSyntaxNode node = createSyntaxNode(); 101 List tmp = node.addShiftedItems(pending, entries); 103 Integer kernelIndex = (Integer )kernels.get(node); 105 int index = kernelIndex != null ? kernelIndex.intValue() : -1; 106 107 if (index < 0) { 109 index = syntaxNodes.size(); 110 kernels.put(node, new Integer (index)); 111 syntaxNodes.add(node); 112 node.closure(syntax); 113 } 114 115 for (int i = 0; i < tmp.size(); i++) { 117 Tuple t = (Tuple)tmp.get(i); 118 linkParentItemToChild(t.o1, index, syntaxNodes, t.o2); 119 } 120 } 121 } 122 } 123 124 125 136 protected List addShiftedItems(String symbol, Hashtable originatorEntries) { 137 List list = new ArrayList(); 138 for (Enumeration e = originatorEntries.elements(); e.hasMoreElements(); ) { 139 RuleStateItem item = (RuleStateItem) e.nextElement(); 140 String pending = item.getPendingSymbol(); 141 142 if (pending != null && symbol.equals(pending)) { 143 RuleStateItem newitem = item.shift(); 144 this.entries.put(newitem, newitem); 145 list.add(new Tuple(item, newitem)); } 147 } 148 149 kernels = list.size(); 151 return list; } 153 154 155 159 protected void linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child) { 160 parent.followNodeIndex = newIndex; 161 } 162 163 164 165 172 protected void closure(Syntax syntax) { 173 List todo = new ArrayList(entries.size() * 2); 175 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) 176 todo.add(e.nextElement()); 177 178 for (int i = 0; i < todo.size(); i++) { 180 RuleStateItem rsi = (RuleStateItem)todo.get(i); 181 String nonterm = rsi.getPendingNonTerminal(); 182 if (nonterm != null) 183 addRulesDerivingPendingNonTerminal(rsi, nonterm, syntax, todo); 184 } 185 } 186 187 191 protected void addRulesDerivingPendingNonTerminal(RuleStateItem item, String nonterm, Syntax syntax, List todo) { 192 for (int i = 0; i < syntax.size(); i++) { 195 Rule rule = syntax.getRule(i); 196 197 if (rule.getNonterminal().equals(nonterm)) { 198 RuleStateItem rsi = createRuleStateItem(i, rule); 199 200 if (entries.containsKey(rsi) == false) { 201 entries.put(rsi, rsi); todo.add(rsi); } 204 } 205 } 206 } 207 208 209 210 215 public Hashtable fillGotoLine(int state) { 216 Hashtable h = new Hashtable(entries.size() * 3 / 2); 218 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) { 220 RuleStateItem item = (RuleStateItem)e.nextElement(); 222 String symbol = item.getPendingSymbol(); 223 224 if (symbol != null) { setTableLine("GOTO", state, h, item, new Integer (item.followNodeIndex), symbol); 227 } 228 } 229 return h; 230 } 231 232 233 240 public Hashtable fillParseActionLine(int state, FirstSets firstSets, FollowSets followSets) { 241 Hashtable h = new Hashtable(entries.size() * 10); 243 244 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) { 245 RuleStateItem item = (RuleStateItem)e.nextElement(); 247 String symbol = item.getPendingSymbol(); 248 249 if (symbol != null) { if (Token.isTerminal(symbol)) { setParseTableLine(state, h, item, ParserTables.SHIFT, symbol); 253 } 254 else { List firstSet = getNontermShiftSymbols(firstSets, item.getNonterminal()); 256 257 if (firstSet != null) { for (int i = 0; i < firstSet.size(); i++) { 259 String terminal = (String ) firstSet.get(i); 260 setParseTableLine(state, h, item, ParserTables.SHIFT, terminal); 261 } 262 } 263 } 264 } 265 else { for (Iterator reduceSymbols = getReduceSymbols(followSets, item); reduceSymbols.hasNext(); ) { 267 String terminal = (String ) reduceSymbols.next(); 268 269 if (item.ruleIndex == 0) setParseTableLine(state, h, item, ParserTables.ACCEPT, terminal); 271 else setParseTableLine(state, h, item, new Integer (item.ruleIndex), terminal); 273 } 274 } 275 } 276 return h; 277 } 278 279 283 protected List getNontermShiftSymbols(FirstSets firstSets, String nonterm) { 284 return (List) firstSets.get(nonterm); 285 } 286 287 291 protected Iterator getReduceSymbols(FollowSets followSets, RuleStateItem item) { 292 return ((List) followSets.get(item.getNonterminal())).iterator(); 293 } 294 295 296 297 298 302 protected void setParseTableLine(int state, Hashtable line, RuleStateItem item, Integer action, String terminal) { 303 305 if (setTableLine("PARSE-ACTION", state, line, item, action, terminal) == false) { 306 Object o = line.get(terminal); 308 309 if (action.equals(ParserTables.SHIFT) || o.equals(ParserTables.SHIFT)) { 310 line.put(terminal, ParserTables.SHIFT); 312 System.err.println("WARNING: shift/reduce conflict, SHIFT is preferred."); 313 } 314 else { 315 System.err.println("WARNING: reduce/reduce conflict, rule with smaller index is preferred."); 316 if (((Integer )o).intValue() > action.intValue()) 318 line.put(terminal, action); 319 } 320 } 321 } 322 323 324 329 protected boolean setTableLine(String table, int state, Hashtable line, RuleStateItem item, Integer action, String terminal) { 330 Object o = line.get(terminal); 332 if (o == null) { line.put(terminal, action); 334 } 335 else { if (o.equals(action) == false) { System.err.println("========================================================"); 338 System.err.println("WARNING: "+table+" state "+state+", terminal "+ 339 terminal+" is "+ 340 displayAction(o)+" and was overwritten by action "+ 341 displayAction(action)); 342 System.err.println("... from rule state: "+item); 343 System.err.println("... current state:\n"+this); 344 System.err.println("========================================================"); 345 return false; 346 } 347 } 348 return true; 349 } 350 351 private String displayAction(Object action) { 352 if (action.equals(ParserTables.SHIFT)) 353 return "SHIFT"; 354 return "REDUCE("+action.toString()+")"; 355 } 356 357 358 362 public boolean equals(Object o) { 363 SLRSyntaxNode node = (SLRSyntaxNode)o; 365 366 if (node.kernels != kernels) 367 return false; 368 369 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) { 371 RuleStateItem item = (RuleStateItem)e.nextElement(); 372 if (item.pointerPosition > 1 && node.entries.containsKey(item) == false) 374 return false; 375 } 376 return true; 377 } 378 379 380 public int hashCode() { 381 if (hashCache == null) { 382 int result = 0; 383 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) 384 result ^= e.nextElement().hashCode(); 385 hashCache = new Integer (result); 386 } 387 return hashCache.intValue(); 388 } 389 390 391 392 public String toString() { 393 StringBuffer sb = new StringBuffer (); 394 List list = new ArrayList(entries.size()); 396 for (Enumeration e = entries.elements(); e.hasMoreElements(); ) { 397 RuleStateItem rsi = (RuleStateItem)e.nextElement(); 398 int index = -1; 399 for (int i = 0; index == -1 && i < list.size(); i++) { 400 RuleStateItem rsi1 = (RuleStateItem) list.get(i); 401 if (rsi1.ruleIndex > rsi.ruleIndex || rsi1.ruleIndex == rsi.ruleIndex && rsi.pointerPosition > 1) 402 index = i; 403 } 404 if (index < 0) 405 list.add(rsi); 406 else 407 list.add(index, rsi); 408 } 409 for (int i = 0; i < list.size(); i++) { 410 sb.append(" "); 411 sb.append(list.get(i).toString()); 412 sb.append("\n"); 413 } 414 return sb.toString(); 415 } 416 417 418 419 private class Tuple 421 { 422 RuleStateItem o1, o2; 423 424 Tuple(RuleStateItem o1, RuleStateItem o2) { 425 this.o1 = o1; 426 this.o2 = o2; 427 } 428 } 429 430 431 432 435 protected class RuleStateItem 436 { 437 Rule rule; 438 int pointerPosition = 1; 439 int ruleIndex; 440 int followNodeIndex = -1; 441 protected Integer hashCache = null; 442 443 444 445 public RuleStateItem(int ruleIndex, Rule rule) { 446 this.rule = rule; 447 this.ruleIndex = ruleIndex; 448 } 449 450 451 protected RuleStateItem(RuleStateItem orig) { 452 this.rule = orig.rule; 453 this.pointerPosition = orig.pointerPosition; 454 this.ruleIndex = orig.ruleIndex; 455 } 456 457 458 459 protected RuleStateItem createRuleStateItem(RuleStateItem orig) { 460 return new RuleStateItem(orig); 461 } 462 463 464 String getNonterminal() { 465 return rule.getNonterminal(); 466 } 467 468 469 RuleStateItem shift() { 470 RuleStateItem clone = createRuleStateItem(this); 471 clone.pointerPosition++; 472 return clone; 473 } 474 475 476 String getPendingNonTerminal() { 477 if (pointerPosition > rule.rightSize()) 478 return null; 479 480 String symbol = getPendingSymbol(); 481 if (Token.isTerminal(symbol)) 482 return null; 484 return symbol; 485 } 486 487 488 String getPendingSymbol() { 489 if (pointerPosition > rule.rightSize()) 490 return null; 491 492 return rule.getRightSymbol(pointerPosition - 1); 493 } 494 495 496 public boolean equals(Object o) { 497 RuleStateItem item = (RuleStateItem)o; 498 return ruleIndex == item.ruleIndex && pointerPosition == item.pointerPosition; 499 } 500 501 502 public int hashCode() { 503 if (hashCache == null) 504 hashCache = new Integer (ruleIndex * 13 + pointerPosition); 505 return hashCache.intValue(); 506 } 507 508 509 public String toString() { 510 StringBuffer sb = new StringBuffer ("(Rule "+ruleIndex+") "+getNonterminal()+" : "); 511 int i = 0; 512 for (; i < rule.rightSize(); i++) { 513 if (i == pointerPosition - 1) 514 sb.append("."); 515 sb.append(rule.getRightSymbol(i)); 516 sb.append(" "); 517 } 518 if (i == pointerPosition - 1) 519 sb.append("."); 520 if (followNodeIndex >= 0) 521 sb.append(" -> State "+followNodeIndex); 522 return sb.toString(); 523 } 524 525 } 526 527 } | Popular Tags |