1 18 19 package org.sablecc.sablecc.automaton; 20 21 import java.util.Collections ; 22 import java.util.Map ; 23 import java.util.SortedMap ; 24 import java.util.SortedSet ; 25 import java.util.TreeMap ; 26 import java.util.TreeSet ; 27 28 import org.sablecc.sablecc.alphabet.Alphabet; 29 import org.sablecc.sablecc.alphabet.Symbol; 30 import org.sablecc.sablecc.exception.InternalException; 31 import org.sablecc.sablecc.util.WorkSet; 32 33 38 public class Dfa<T extends Comparable <? super T>> { 39 40 41 private static final String lineSeparator = System 42 .getProperty("line.separator"); 43 44 45 private Alphabet<T> alphabet; 46 47 48 private SortedSet <DfaState<T>> states; 49 50 51 private DfaState<T> startState; 52 53 54 private DfaState<T> deadEndState; 55 56 57 private SortedSet <DfaState<T>> acceptStates; 58 59 60 private boolean isStable; 61 62 66 private String toString; 67 68 72 private Dfa() { 73 74 } 75 76 85 public Dfa( 86 Nfa<T> nfa) { 87 88 if (nfa == null) { 89 throw new InternalException("nfa may not be null"); 90 } 91 92 init(nfa); 93 StateMatcher<T> stateMapper = computeDfaStates(nfa); 94 95 NfaState<T> nfaAccept = nfa.getAcceptState(); 97 for (DfaState<T> dfaState : this.states) { 98 if (stateMapper.match(dfaState, nfaAccept)) { 99 this.acceptStates.add(dfaState); 100 } 101 } 102 103 stabilize(); 104 } 105 106 110 private void init( 111 Nfa<T> nfa) { 112 113 this.alphabet = nfa.getAlphabet(); 114 this.states = new TreeSet <DfaState<T>>(); 115 this.acceptStates = new TreeSet <DfaState<T>>(); 116 this.isStable = false; 117 } 118 119 127 private StateMatcher<T> computeDfaStates( 128 Nfa<T> nfa) { 129 130 StateMatcher<T> matcher = new StateMatcher<T>(this, nfa); 131 WorkSet<DfaState<T>> workSet = new WorkSet<DfaState<T>>(); 132 133 this.deadEndState = matcher.getDfaState(new TreeSet <NfaState<T>>()); 134 this.startState = matcher.getDfaState(nfa.getStartState() 135 .getEpsilonReach()); 136 workSet.add(this.startState); 137 138 while (workSet.hasNext()) { 139 DfaState<T> sourceDfaState = workSet.next(); 140 141 SortedMap <Symbol<T>, SortedSet <NfaState<T>>> directDestinationMap = new TreeMap <Symbol<T>, SortedSet <NfaState<T>>>(); 143 144 for (NfaState<T> sourceNfaState : matcher 145 .getNfaStates(sourceDfaState)) { 146 147 for (Map.Entry <Symbol<T>, SortedSet <NfaState<T>>> entry : sourceNfaState 148 .getTransitions().entrySet()) { 149 150 Symbol<T> symbol = entry.getKey(); 151 SortedSet <NfaState<T>> targets = entry.getValue(); 152 153 if (symbol != null) { 154 155 SortedSet <NfaState<T>> directDesinations = directDestinationMap 156 .get(symbol); 157 158 if (directDesinations == null) { 159 160 directDesinations = new TreeSet <NfaState<T>>(); 161 directDestinationMap.put(symbol, directDesinations); 162 } 163 164 directDesinations.addAll(targets); 165 } 166 } 167 } 168 169 for (Map.Entry <Symbol<T>, SortedSet <NfaState<T>>> entry : directDestinationMap 171 .entrySet()) { 172 173 Symbol<T> symbol = entry.getKey(); 174 SortedSet <NfaState<T>> directDestinations = entry.getValue(); 175 176 SortedSet <NfaState<T>> epsilonClosure = new TreeSet <NfaState<T>>(); 177 178 for (NfaState<T> nfaState : directDestinations) { 179 epsilonClosure.addAll(nfaState.getEpsilonReach()); 180 } 181 182 DfaState<T> destinationDfaState = matcher 183 .getDfaState(epsilonClosure); 184 185 sourceDfaState.addTransition(symbol, destinationDfaState); 186 187 workSet.add(destinationDfaState); 188 } 189 } 190 191 return matcher; 192 } 193 194 199 public Alphabet<T> getAlphabet() { 200 201 return this.alphabet; 202 } 203 204 211 public SortedSet <DfaState<T>> getStates() { 212 213 if (!this.isStable) { 214 throw new InternalException("this DFA is not stable yet"); 215 } 216 217 return this.states; 218 } 219 220 225 SortedSet <DfaState<T>> getUnstableStates() { 226 227 return this.states; 228 } 229 230 237 public DfaState<T> getStartState() { 238 239 if (!this.isStable) { 240 throw new InternalException("this DFA is not stable yet"); 241 } 242 243 return this.startState; 244 } 245 246 253 public DfaState<T> getDeadEndState() { 254 255 if (!this.isStable) { 256 throw new InternalException("this DFA is not stable yet"); 257 } 258 259 return this.deadEndState; 260 } 261 262 267 DfaState<T> getUnstableDeadEndState() { 268 269 return this.deadEndState; 270 } 271 272 279 public SortedSet <DfaState<T>> getAcceptStates() { 280 281 if (!this.isStable) { 282 throw new InternalException("this DFA is not stable yet"); 283 } 284 285 return this.acceptStates; 286 } 287 288 295 @Override 296 public String toString() { 297 298 if (this.toString == null) { 299 300 if (!this.isStable) { 301 throw new InternalException("this DFA is not stable yet"); 302 } 303 304 StringBuilder sb = new StringBuilder (); 305 306 sb.append("DFA:{"); 307 308 for (DfaState<T> state : this.states) { 309 sb.append(lineSeparator); 310 sb.append(" "); 311 sb.append(state); 312 313 if (state == this.startState) { 314 sb.append("(start)"); 315 } 316 317 if (state == this.deadEndState) { 318 sb.append("(dead-end)"); 319 } 320 321 if (this.acceptStates.contains(state)) { 322 sb.append("(accept)"); 323 } 324 325 sb.append(":"); 326 for (Map.Entry <Symbol<T>, DfaState<T>> entry : state 327 .getTransitions().entrySet()) { 328 Symbol<T> symbol = entry.getKey(); 329 DfaState<T> target = entry.getValue(); 330 331 sb.append(lineSeparator); 332 sb.append(" "); 333 sb.append(symbol); 334 sb.append(" -> "); 335 sb.append(target); 336 } 337 } 338 339 sb.append(lineSeparator); 340 sb.append("}"); 341 342 this.toString = sb.toString(); 343 } 344 345 return this.toString; 346 } 347 348 354 private void stabilize() { 355 356 if (this.isStable) { 357 throw new InternalException("this DFA is already stable"); 358 } 359 360 removeUnreachableStates(); 361 362 for (DfaState<T> state : this.states) { 363 state.stabilize(); 364 } 365 366 this.states = Collections.unmodifiableSortedSet(this.states); 367 this.acceptStates = Collections 368 .unmodifiableSortedSet(this.acceptStates); 369 370 this.isStable = true; 371 } 372 373 376 private void removeUnreachableStates() { 377 378 SortedSet <DfaState<T>> reachableStates = new TreeSet <DfaState<T>>(); 379 380 WorkSet<DfaState<T>> workSet = new WorkSet<DfaState<T>>(); 381 workSet.add(this.startState); 382 383 while (workSet.hasNext()) { 384 DfaState<T> state = workSet.next(); 385 reachableStates.add(state); 386 387 for (DfaState<T> target : state.getUnstableTransitions().values()) { 388 workSet.add(target); 389 } 390 } 391 392 reachableStates.add(this.deadEndState); 393 394 this.states = reachableStates; 395 } 396 397 407 static <T extends Comparable <? super T>> Dfa<T> shortest( 408 Nfa<T> nfa) { 409 410 if (nfa == null) { 411 throw new InternalException("nfa may not be null"); 412 } 413 414 Dfa<T> dfa = new Dfa<T>(); 415 416 dfa.init(nfa); 417 StateMatcher<T> stateMapper = dfa.computeDfaStates(nfa); 418 419 NfaState<T> nfaAccept = nfa.getAcceptState(); 421 for (DfaState<T> dfaState : dfa.states) { 422 if (stateMapper.match(dfaState, nfaAccept)) { 423 dfa.acceptStates.add(dfaState); 424 } 425 } 426 427 for (DfaState<T> state : dfa.acceptStates) { 429 state.removeTransitions(); 430 } 431 432 dfa.stabilize(); 433 return dfa; 434 } 435 436 449 static <T extends Comparable <? super T>> Dfa<T> difference( 450 Nfa<T> nfa1, 451 Nfa<T> nfa2) { 452 453 if (nfa1 == null) { 454 throw new InternalException("nfa1 may not be null"); 455 } 456 457 if (nfa2 == null) { 458 throw new InternalException("nfa2 may not be null"); 459 } 460 461 NfaCombineResult<T> nfaCombineResult = nfa1.combineWith(nfa2); 462 Nfa<T> newNfa = nfaCombineResult.getNewNfa(); 463 464 newNfa.getUnstableStartState().addTransition(null, 466 nfaCombineResult.getNewNfa1StartState()); 467 newNfa.getUnstableStartState().addTransition(null, 468 nfaCombineResult.getNewNfa2StartState()); 469 470 newNfa.stabilize(); 471 472 Dfa<T> dfa = new Dfa<T>(); 473 474 dfa.init(newNfa); 475 StateMatcher<T> stateMapper = dfa.computeDfaStates(newNfa); 476 477 NfaState<T> nfa1Accept = nfaCombineResult.getNewNfa1AcceptState(); 479 NfaState<T> nfa2Accept = nfaCombineResult.getNewNfa2AcceptState(); 480 for (DfaState<T> dfaState : dfa.states) { 481 if (stateMapper.match(dfaState, nfa1Accept) 482 && !stateMapper.match(dfaState, nfa2Accept)) { 483 dfa.acceptStates.add(dfaState); 484 } 485 } 486 487 dfa.stabilize(); 488 return dfa; 489 } 490 491 504 static <T extends Comparable <? super T>> Dfa<T> intersection( 505 Nfa<T> nfa1, 506 Nfa<T> nfa2) { 507 508 if (nfa1 == null) { 509 throw new InternalException("nfa1 may not be null"); 510 } 511 512 if (nfa2 == null) { 513 throw new InternalException("nfa2 may not be null"); 514 } 515 516 NfaCombineResult<T> nfaCombineResult = nfa1.combineWith(nfa2); 517 Nfa<T> newNfa = nfaCombineResult.getNewNfa(); 518 519 newNfa.getUnstableStartState().addTransition(null, 521 nfaCombineResult.getNewNfa1StartState()); 522 newNfa.getUnstableStartState().addTransition(null, 523 nfaCombineResult.getNewNfa2StartState()); 524 525 newNfa.stabilize(); 526 527 Dfa<T> dfa = new Dfa<T>(); 528 529 dfa.init(newNfa); 530 StateMatcher<T> stateMapper = dfa.computeDfaStates(newNfa); 531 532 NfaState<T> nfa1Accept = nfaCombineResult.getNewNfa1AcceptState(); 534 NfaState<T> nfa2Accept = nfaCombineResult.getNewNfa2AcceptState(); 535 for (DfaState<T> dfaState : dfa.states) { 536 if (stateMapper.match(dfaState, nfa1Accept) 537 && stateMapper.match(dfaState, nfa2Accept)) { 538 dfa.acceptStates.add(dfaState); 539 } 540 } 541 542 dfa.stabilize(); 543 return dfa; 544 } 545 546 553 int getNextStateId() { 554 555 if (this.isStable) { 556 throw new InternalException("a stable DFA may not be modified"); 557 } 558 559 return this.states.size(); 560 } 561 562 571 void addState( 572 DfaState<T> state) { 573 574 if (this.isStable) { 575 throw new InternalException("a stable DFA may not be modified"); 576 } 577 578 if (!this.states.add(state)) { 579 throw new InternalException("state is already in state set"); 580 } 581 } 582 } 583 | Popular Tags |