1 8 9 package beaver.comp; 10 11 import java.util.Arrays ; 12 import java.util.HashMap ; 13 import java.util.Map ; 14 15 import beaver.comp.util.BitSet; 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 23 27 class Configuration implements Comparable 28 { 29 static class Set 30 { 31 static class Factory 32 { 33 private Map configurations; 34 private Configuration probe; 35 private Grammar grammar; 36 37 38 Configuration first_conf; 39 40 41 Configuration last_conf; 42 43 44 int num_conf; 45 46 Factory(Grammar grammar) 47 { 48 this.configurations = new HashMap (89); 49 this.probe = new Configuration(); 50 this.grammar = grammar; 51 } 52 53 void reset() 54 { 55 first_conf = last_conf = null; 56 num_conf = 0; 57 58 configurations = new HashMap (89); 60 } 61 62 Configuration addConfiguration(Production rule, int mark) 63 { 64 probe.rule = rule; 65 probe.dot = mark; 66 67 Configuration conf = (Configuration) configurations.get(probe); 68 if (conf == null) 69 { 70 conf = new Configuration(probe, grammar); 71 configurations.put(conf, conf); 72 73 if (last_conf == null) 74 last_conf = first_conf = conf; 75 else 76 last_conf = last_conf.next = conf; 77 num_conf++; 78 } 79 return conf; 80 } 81 82 Set getCore() 83 { 84 Configuration[] core = new Configuration[num_conf]; 85 int j = 0; 86 for (Configuration conf = first_conf; conf != null; conf = conf.next) 87 { 88 core[j++] = conf; 89 } 90 Arrays.sort(core); 91 92 Configuration conf = first_conf = core[0]; 93 int core_hash_code = conf.hashCode(); 94 for (j = 1; j < num_conf; j++) 95 { 96 conf = conf.next = core[j]; 97 core_hash_code = core_hash_code * 571 + conf.hashCode(); 98 } 99 last_conf = conf; 100 conf.next = null; 101 102 return new Set(this, core_hash_code); 103 } 104 } 105 106 107 Configuration.Set.Factory conf_set_factory; 108 109 110 Configuration first_conf; 111 112 113 Configuration last_core_conf; 114 115 116 int core_size; 117 118 119 int core_hash_code; 120 121 private Set(Configuration.Set.Factory conf_set_factory, int hash_code) 122 { 123 this.conf_set_factory = conf_set_factory; 124 this.first_conf = conf_set_factory.first_conf; 125 this.last_core_conf = conf_set_factory.last_conf; 126 this.core_hash_code = hash_code; 127 this.core_size = conf_set_factory.num_conf; 128 } 129 130 void appendReversePropagation(Set conf_set) 131 { 132 Configuration stop = last_core_conf.next; 133 for (Configuration my_conf = first_conf, cp_conf = conf_set.first_conf; my_conf != stop; my_conf = my_conf.next, cp_conf = cp_conf.next) 134 { 135 my_conf.appendReversePropagation(cp_conf); 136 } 137 } 138 139 void buildClosure() 140 { 141 for (Configuration conf = first_conf; conf != null; conf = conf.next) 142 { 143 if (conf.isDotAfterLastSymbol()) 144 continue; 145 146 GrammarSymbol sym = conf.getSymbolAfterDot(); 147 if (sym instanceof NonTerminal) 148 { 149 NonTerminal nt = (NonTerminal) sym; 150 for (Production rule = nt.definitions.start(); rule != null; rule = rule.next_definition) 151 { 152 Configuration new_conf = conf_set_factory.addConfiguration(rule, 0); 153 if (new_conf.addLookaheads(conf)) 154 { 155 conf.addForwardPropagation(new_conf); 156 } 157 } 158 } 159 } 160 } 161 162 void reverseReversePropagation() 163 { 164 for (Configuration conf = first_conf; conf != null; conf = conf.next) 165 { 166 conf.reverseReversePropagation(); 167 } 168 } 169 170 void resetContributionFlags() 171 { 172 for (Configuration conf = first_conf; conf != null; conf = conf.next) 173 { 174 conf.has_contributed = false; 175 } 176 } 177 178 private boolean equals(Set conf_set) 179 { 180 if (conf_set == this) 181 return true; 182 183 if (conf_set.core_size != this.core_size) 184 return false; 185 186 Configuration my_conf = first_conf; 187 Configuration cmp_conf = conf_set.first_conf; 188 Configuration stop = last_core_conf.next; 189 while (my_conf != stop && my_conf.equals(cmp_conf)) 190 { 191 my_conf = my_conf.next; 192 cmp_conf = cmp_conf.next; 193 } 194 return my_conf == stop; 195 } 196 197 public boolean equals(Object obj) 198 { 199 return obj instanceof Set && this.equals((Set) obj); 200 } 201 202 public int hashCode() 203 { 204 return core_hash_code; 205 } 206 207 public String toString() 208 { 209 StringBuffer str = new StringBuffer (1000); 210 Configuration conf = first_conf; 211 for (; conf != last_core_conf.next; conf = conf.next) 212 { 213 str.append('+').append(conf).append('\n'); 214 } 215 for (; conf != null; conf = conf.next) 216 { 217 str.append(' ').append(conf).append('\n'); 218 } 219 return str.toString(); 220 } 221 } 222 223 static class PropagationLink 224 { 225 226 PropagationLink next; 227 228 229 Configuration conf; 230 231 PropagationLink(Configuration conf) 232 { 233 this.conf = conf; 234 } 235 } 236 237 238 Configuration next; 239 240 Production rule; 241 int dot; 242 BitSet lookaheads; 243 244 PropagationLink fwd_propagation; 248 PropagationLink bck_propagation, last_bck_propagation; 249 250 254 boolean has_contributed; 255 256 259 private Configuration() 260 { 261 } 262 263 Configuration(Configuration factory_probe, Grammar grammar) 264 { 265 this.rule = factory_probe.rule; 266 this.dot = factory_probe.dot; 267 this.lookaheads = new BitSet(grammar.terminals.length); 268 } 269 270 GrammarSymbol getSymbolAfterDot() 271 { 272 return rule.rhs.items[dot].symbol; 273 } 274 275 boolean isDotAfterLastSymbol() 276 { 277 return dot == rule.rhs.items.length; 278 } 279 280 void addLookahead(Terminal term) 281 { 282 lookaheads.add(term.id); 283 } 284 285 292 boolean addLookaheads(Configuration conf) 293 { 294 for (int i = conf.dot + 1; i < conf.rule.rhs.items.length; i++) 295 { 296 GrammarSymbol sym = conf.rule.rhs.items[i].symbol; 297 if (sym instanceof Terminal) 298 { 299 lookaheads.add(sym.id); 300 return false; 301 } 302 else 303 { 304 NonTerminal nt = (NonTerminal) sym; 305 lookaheads.add(nt.first_set); 306 if (!nt.is_nullable) 307 return false; 308 } 309 } 310 return true; 311 } 312 313 void addForwardPropagation(Configuration conf) 314 { 315 PropagationLink link = new PropagationLink(conf); 316 link.next = fwd_propagation; 317 fwd_propagation = link; 318 } 319 320 void addReversePropagation(Configuration conf) 321 { 322 PropagationLink link = new PropagationLink(conf); 323 if (last_bck_propagation == null) 324 last_bck_propagation = bck_propagation = link; 325 else 326 last_bck_propagation = last_bck_propagation.next = link; 327 } 328 329 void appendReversePropagation(Configuration conf) 330 { 331 if (last_bck_propagation == null) 332 bck_propagation = conf.bck_propagation; 333 else 334 last_bck_propagation.next = conf.bck_propagation; 335 last_bck_propagation = conf.last_bck_propagation; 336 } 337 338 void reverseReversePropagation() 339 { 340 PropagationLink link = bck_propagation; 341 while (link != null) 342 { 343 PropagationLink next_link = link.next; 344 Configuration conf = link.conf; 345 346 link.conf = this; 347 link.next = conf.fwd_propagation; 348 conf.fwd_propagation = link; 349 350 link = next_link; 351 } 352 bck_propagation = null; 353 } 354 355 boolean findLookaheads() 356 { 357 boolean more_found = false; 358 for (PropagationLink link = fwd_propagation; link != null; link = link.next) 359 { 360 if (link.conf.lookaheads.add(this.lookaheads)) 361 { 362 more_found = true; 363 link.conf.has_contributed = false; 364 } 365 } 366 return more_found; 367 } 368 369 boolean equals(Configuration conf) 370 { 371 return this.rule == conf.rule && this.dot == conf.dot; 372 } 373 374 public boolean equals(Object obj) 375 { 376 return obj instanceof Configuration && this.equals((Configuration) obj); 377 } 378 379 public int hashCode() 380 { 381 return rule.id * 37 + dot; 382 } 383 384 392 public int compareTo(Object o) 393 { 394 if (o == this) 395 return 0; 396 397 Configuration conf = (Configuration) o; 398 int cmp = this.rule.id - conf.rule.id; 399 if (cmp == 0) 400 { 401 cmp = this.dot - conf.dot; 402 } 403 return cmp; 404 } 405 406 public String toString() 407 { 408 StringBuffer str = new StringBuffer (100); 409 str.append(rule.lhs).append(" ="); 410 for (int i = 0; i < rule.rhs.items.length; i++) 411 { 412 Production.RHS.Item rhs_item = rule.rhs.items[i]; 413 str.append(' '); 414 if (i == dot) 415 str.append('*'); 416 str.append(rhs_item); 417 } 418 if (dot == rule.rhs.items.length) 419 str.append(" *"); 420 int line; 421 if ((line = rule.getFirstLine()) > 0) 422 { 423 str.append(" @ ").append(line); 424 } 425 return str.toString(); 426 } 427 } 428 | Popular Tags |