1 18 19 package org.sablecc.sablecc.automaton; 20 21 import java.util.Collections ; 22 import java.util.Comparator ; 23 import java.util.Map ; 24 import java.util.SortedMap ; 25 import java.util.SortedSet ; 26 import java.util.TreeMap ; 27 import java.util.TreeSet ; 28 29 import org.sablecc.sablecc.alphabet.Alphabet; 30 import org.sablecc.sablecc.alphabet.AlphabetMergeResult; 31 import org.sablecc.sablecc.alphabet.Interval; 32 import org.sablecc.sablecc.alphabet.Symbol; 33 import org.sablecc.sablecc.exception.InternalException; 34 35 40 public final class Nfa<T extends Comparable <? super T>> { 41 42 43 private static final String lineSeparator = System 44 .getProperty("line.separator"); 45 46 47 private Alphabet<T> alphabet; 48 49 50 private SortedSet <NfaState<T>> states; 51 52 53 private NfaState<T> startState; 54 55 56 private NfaState<T> acceptState; 57 58 59 private boolean isStable; 60 61 65 private String toString; 66 67 68 private final Comparator <Symbol<T>> symbolComparator = new Comparator <Symbol<T>>() { 69 70 public int compare( 72 Symbol<T> symbol1, 73 Symbol<T> symbol2) { 74 75 if (symbol1 == null) { 76 return symbol2 == null ? 0 : -1; 77 } 78 79 if (symbol2 == null) { 80 return 1; 81 } 82 83 return symbol1.compareTo(symbol2); 84 } 85 }; 86 87 91 public Nfa() { 92 93 init(); 94 95 this.alphabet = new Alphabet<T>(); 97 98 this.startState.addTransition(null, this.acceptState); 100 101 stabilize(); 102 } 103 104 113 public Nfa( 114 Interval<T> interval) { 115 116 if (interval == null) { 117 throw new InternalException("interval may not be null"); 118 } 119 120 init(); 121 122 Symbol<T> symbol = new Symbol<T>(interval); 123 this.alphabet = new Alphabet<T>(symbol); 124 125 this.startState.addTransition(symbol, this.acceptState); 127 128 stabilize(); 129 } 130 131 140 public Nfa( 141 Symbol<T> symbol) { 142 143 if (symbol == null) { 144 throw new InternalException("symbol may not be null"); 145 } 146 147 init(); 148 149 this.alphabet = new Alphabet<T>(symbol); 150 151 this.startState.addTransition(symbol, this.acceptState); 153 154 stabilize(); 155 } 156 157 166 public Nfa( 167 Dfa<T> dfa) { 168 169 if (dfa == null) { 170 throw new InternalException("dfa may not be null"); 171 } 172 173 init(); 174 175 this.alphabet = dfa.getAlphabet(); 176 177 SortedMap <DfaState<T>, NfaState<T>> dfaToNfaStateMap = new TreeMap <DfaState<T>, NfaState<T>>(); 178 179 dfaToNfaStateMap.put(dfa.getStartState(), this.startState); 181 182 for (DfaState<T> dfaState : dfa.getStates()) { 184 185 if (dfaState == dfa.getDeadEndState() 186 || dfaState == dfa.getStartState()) { 187 continue; 188 } 189 190 dfaToNfaStateMap.put(dfaState, new NfaState<T>(this)); 192 } 193 194 for (Map.Entry <DfaState<T>, NfaState<T>> stateEntry : dfaToNfaStateMap 196 .entrySet()) { 197 DfaState<T> startDfaState = stateEntry.getKey(); 198 NfaState<T> startNfaState = stateEntry.getValue(); 199 200 for (Map.Entry <Symbol<T>, DfaState<T>> transitionEntry : startDfaState 201 .getTransitions().entrySet()) { 202 Symbol<T> symbol = transitionEntry.getKey(); 203 DfaState<T> destinationDfaState = transitionEntry.getValue(); 204 NfaState<T> destinationNfaState = dfaToNfaStateMap 205 .get(destinationDfaState); 206 207 startNfaState.addTransition(symbol, destinationNfaState); 208 } 209 } 210 211 for (DfaState<T> dfaState : dfa.getAcceptStates()) { 213 NfaState<T> nfaState = dfaToNfaStateMap.get(dfaState); 214 215 nfaState.addTransition(null, this.acceptState); 216 } 217 218 stabilize(); 219 } 220 221 229 public Nfa( 230 MinimalDfa<T> minimalDfa) { 231 232 if (minimalDfa == null) { 233 throw new InternalException("minimalDfa may not be null"); 234 } 235 236 init(); 237 238 this.alphabet = minimalDfa.getAlphabet(); 239 240 SortedMap <MinimalDfaState<T>, NfaState<T>> minimalDfaToNfaStateMap = new TreeMap <MinimalDfaState<T>, NfaState<T>>(); 241 242 minimalDfaToNfaStateMap 244 .put(minimalDfa.getStartState(), this.startState); 245 246 for (MinimalDfaState<T> minimalDfaState : minimalDfa.getStates()) { 248 249 if (minimalDfaState == minimalDfa.getDeadEndState() 250 || minimalDfaState == minimalDfa.getStartState()) { 251 continue; 252 } 253 254 minimalDfaToNfaStateMap.put(minimalDfaState, new NfaState<T>(this)); 256 } 257 258 for (Map.Entry <MinimalDfaState<T>, NfaState<T>> stateEntry : minimalDfaToNfaStateMap 260 .entrySet()) { 261 MinimalDfaState<T> startMinimalDfaState = stateEntry.getKey(); 262 NfaState<T> startNfaState = stateEntry.getValue(); 263 264 for (Map.Entry <Symbol<T>, MinimalDfaState<T>> transitionEntry : startMinimalDfaState 265 .getTransitions().entrySet()) { 266 Symbol<T> symbol = transitionEntry.getKey(); 267 MinimalDfaState<T> destinationMinimalDfaState = transitionEntry 268 .getValue(); 269 NfaState<T> destinationNfaState = minimalDfaToNfaStateMap 270 .get(destinationMinimalDfaState); 271 272 startNfaState.addTransition(symbol, destinationNfaState); 273 } 274 } 275 276 for (MinimalDfaState<T> minimalDfaState : minimalDfa.getAcceptStates()) { 278 NfaState<T> nfaState = minimalDfaToNfaStateMap.get(minimalDfaState); 279 280 nfaState.addTransition(null, this.acceptState); 281 } 282 283 stabilize(); 284 } 285 286 295 private Nfa( 296 Alphabet<T> alphabet) { 297 298 init(); 299 300 this.alphabet = alphabet; 301 } 302 303 307 private void init() { 308 309 this.states = new TreeSet <NfaState<T>>(); 310 311 this.startState = new NfaState<T>(this); 312 this.acceptState = new NfaState<T>(this); 313 314 this.isStable = false; 315 } 316 317 322 public Alphabet<T> getAlphabet() { 323 324 return this.alphabet; 325 } 326 327 334 public SortedSet <NfaState<T>> getStates() { 335 336 if (!this.isStable) { 337 throw new InternalException("this Nfa is not stable yet"); 338 } 339 340 return this.states; 341 } 342 343 350 public NfaState<T> getStartState() { 351 352 if (!this.isStable) { 353 throw new InternalException("this Nfa is not stable yet"); 354 } 355 356 return this.startState; 357 } 358 359 364 NfaState<T> getUnstableStartState() { 365 366 return this.startState; 367 } 368 369 376 public NfaState<T> getAcceptState() { 377 378 if (!this.isStable) { 379 throw new InternalException("this Nfa is not stable yet"); 380 } 381 382 return this.acceptState; 383 } 384 385 390 Comparator <Symbol<T>> getSymbolComparator() { 391 392 return this.symbolComparator; 393 } 394 395 402 @Override 403 public String toString() { 404 405 if (this.toString == null) { 406 407 if (!this.isStable) { 408 throw new InternalException("this Nfa is not stable yet"); 409 } 410 411 StringBuilder sb = new StringBuilder (); 412 413 sb.append("Nfa:{"); 414 415 for (NfaState<T> state : this.states) { 416 sb.append(lineSeparator); 417 sb.append(" "); 418 sb.append(state); 419 420 if (state == this.startState) { 421 sb.append("(start)"); 422 } 423 424 if (state == this.acceptState) { 425 sb.append("(accept)"); 426 } 427 428 sb.append(":"); 429 for (Map.Entry <Symbol<T>, SortedSet <NfaState<T>>> entry : state 430 .getTransitions().entrySet()) { 431 Symbol<T> symbol = entry.getKey(); 432 SortedSet <NfaState<T>> targets = entry.getValue(); 433 434 for (NfaState<T> target : targets) { 435 sb.append(lineSeparator); 436 sb.append(" "); 437 sb.append(symbol); 438 sb.append(" -> "); 439 sb.append(target); 440 } 441 } 442 } 443 444 sb.append(lineSeparator); 445 sb.append("}"); 446 447 this.toString = sb.toString(); 448 } 449 450 return this.toString; 451 } 452 453 456 void stabilize() { 457 458 if (this.isStable) { 459 throw new InternalException("this Nfa is already stable"); 460 } 461 462 for (NfaState<T> state : this.states) { 463 state.stabilize(); 464 } 465 466 this.states = Collections.unmodifiableSortedSet(this.states); 467 468 this.isStable = true; 469 } 470 471 483 public Nfa<T> unionWith( 484 Nfa<T> nfa) { 485 486 if (nfa == null) { 487 throw new InternalException("nfa may not be null"); 488 } 489 490 if (!this.isStable) { 491 throw new InternalException("this Nfa is not stable yet"); 492 } 493 494 if (!nfa.isStable) { 495 throw new InternalException("nfa is not stable yet"); 496 } 497 498 NfaCombineResult<T> nfaCombineResult = this.combineWith(nfa); 499 Nfa<T> newNfa = nfaCombineResult.getNewNfa(); 500 501 newNfa.startState.addTransition(null, nfaCombineResult 503 .getNewNfa1StartState()); 504 newNfa.startState.addTransition(null, nfaCombineResult 505 .getNewNfa2StartState()); 506 507 nfaCombineResult.getNewNfa1AcceptState().addTransition(null, 509 newNfa.acceptState); 510 nfaCombineResult.getNewNfa2AcceptState().addTransition(null, 511 newNfa.acceptState); 512 513 newNfa.stabilize(); 514 return newNfa; 515 } 516 517 529 public Nfa<T> concatenateWith( 530 Nfa<T> nfa) { 531 532 if (nfa == null) { 533 throw new InternalException("nfa may not be null"); 534 } 535 536 if (!this.isStable) { 537 throw new InternalException("this Nfa is not stable yet"); 538 } 539 540 if (!nfa.isStable) { 541 throw new InternalException("nfa is not stable yet"); 542 } 543 544 NfaCombineResult<T> nfaCombineResult = this.combineWith(nfa); 545 Nfa<T> newNfa = nfaCombineResult.getNewNfa(); 546 547 newNfa.startState.addTransition(null, nfaCombineResult 549 .getNewNfa1StartState()); 550 551 nfaCombineResult.getNewNfa1AcceptState().addTransition(null, 553 nfaCombineResult.getNewNfa2StartState()); 554 555 nfaCombineResult.getNewNfa2AcceptState().addTransition(null, 557 newNfa.acceptState); 558 559 newNfa.stabilize(); 560 return newNfa; 561 } 562 563 571 public Nfa<T> zeroOrMore() { 572 573 if (!this.isStable) { 574 throw new InternalException("this Nfa is not stable yet"); 575 } 576 577 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 578 579 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 581 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 582 583 NfaState<T> startThis = oldNfaStateMap.get(this.startState); 584 NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState); 585 586 newNfa.startState.addTransition(null, newNfa.acceptState); 588 589 newNfa.startState.addTransition(null, startThis); 591 592 acceptThis.addTransition(null, newNfa.acceptState); 594 595 acceptThis.addTransition(null, startThis); 597 598 newNfa.stabilize(); 599 return newNfa; 600 } 601 602 610 public Nfa<T> zeroOrOne() { 611 612 if (!this.isStable) { 613 throw new InternalException("this Nfa is not stable yet"); 614 } 615 616 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 617 618 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 620 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 621 622 NfaState<T> startThis = oldNfaStateMap.get(this.startState); 623 NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState); 624 625 newNfa.startState.addTransition(null, newNfa.acceptState); 627 628 newNfa.startState.addTransition(null, startThis); 630 631 acceptThis.addTransition(null, newNfa.acceptState); 633 634 newNfa.stabilize(); 635 return newNfa; 636 } 637 638 646 public Nfa<T> oneOrMore() { 647 648 if (!this.isStable) { 649 throw new InternalException("this Nfa is not stable yet"); 650 } 651 652 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 653 654 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 656 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 657 658 NfaState<T> startThis = oldNfaStateMap.get(this.startState); 659 NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState); 660 661 newNfa.startState.addTransition(null, startThis); 663 664 acceptThis.addTransition(null, newNfa.acceptState); 666 667 acceptThis.addTransition(null, startThis); 669 670 newNfa.stabilize(); 671 return newNfa; 672 } 673 674 685 public Nfa<T> simpleExponent( 686 int n) { 687 688 if (!this.isStable) { 689 throw new InternalException("this Nfa is not stable yet"); 690 } 691 692 if (n < 0) { 693 throw new InternalException("n must be greater or equal to zero"); 694 } 695 696 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 697 698 NfaState<T> lastState = newNfa.startState; 700 701 for (int i = 0; i < n; i++) { 702 703 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 705 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 706 707 lastState.addTransition(null, oldNfaStateMap.get(this.startState)); 709 710 lastState = oldNfaStateMap.get(this.acceptState); 712 } 713 714 lastState.addTransition(null, newNfa.acceptState); 716 717 newNfa.stabilize(); 718 return newNfa; 719 } 720 721 736 public Nfa<T> rangeExponent( 737 int lowerBound, 738 int upperBound) { 739 740 if (!this.isStable) { 741 throw new InternalException("this Nfa is not stable yet"); 742 } 743 744 if (lowerBound < 0) { 745 throw new InternalException( 746 "lowerBound must be greater or equal to zero"); 747 } 748 749 if (upperBound < 0) { 750 throw new InternalException( 751 "upperBound must be greater or equal to zero"); 752 } 753 754 if (upperBound < lowerBound) { 755 throw new InternalException( 756 "upperBound must be greater or equal to lowerBound"); 757 } 758 759 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 760 761 NfaState<T> lastState = newNfa.startState; 763 764 for (int i = 0; i < lowerBound; i++) { 765 766 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 768 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 769 770 lastState.addTransition(null, oldNfaStateMap.get(this.startState)); 772 773 lastState = oldNfaStateMap.get(this.acceptState); 775 } 776 777 for (int i = lowerBound; i < upperBound; i++) { 778 779 lastState.addTransition(null, newNfa.acceptState); 781 782 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 784 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 785 786 lastState.addTransition(null, oldNfaStateMap.get(this.startState)); 788 789 lastState = oldNfaStateMap.get(this.acceptState); 791 } 792 793 lastState.addTransition(null, newNfa.acceptState); 795 796 newNfa.stabilize(); 797 return newNfa; 798 } 799 800 812 public Nfa<T> atLeastExponent( 813 int n) { 814 815 if (!this.isStable) { 816 throw new InternalException("this Nfa is not stable yet"); 817 } 818 819 if (n < 0) { 820 throw new InternalException( 821 "lowerBound must be greater or equal to zero"); 822 } 823 824 Nfa<T> newNfa = new Nfa<T>(this.alphabet); 825 826 NfaState<T> lastState = newNfa.startState; 828 829 for (int i = 0; i < n; i++) { 830 831 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 833 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 834 835 lastState.addTransition(null, oldNfaStateMap.get(this.startState)); 837 838 lastState = oldNfaStateMap.get(this.acceptState); 840 } 841 842 { 843 lastState.addTransition(null, newNfa.acceptState); 845 846 SortedMap <NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 848 this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap); 849 850 lastState.addTransition(null, oldNfaStateMap.get(this.startState)); 852 853 oldNfaStateMap.get(this.acceptState).addTransition(null, 855 oldNfaStateMap.get(this.startState)); 856 857 lastState = oldNfaStateMap.get(this.acceptState); 859 } 860 861 lastState.addTransition(null, newNfa.acceptState); 863 864 newNfa.stabilize(); 865 return newNfa; 866 } 867 868 874 public Dfa<T> shortest() { 875 876 return Dfa.shortest(this); 877 } 878 879 889 public Dfa<T> subtract( 890 Nfa<T> nfa) { 891 892 if (nfa == null) { 893 throw new InternalException("nfa may not be null"); 894 } 895 896 return Dfa.difference(this, nfa); 897 } 898 899 909 public Dfa<T> intersect( 910 Nfa<T> nfa) { 911 912 if (nfa == null) { 913 throw new InternalException("nfa may not be null"); 914 } 915 916 return Dfa.intersection(this, nfa); 917 } 918 919 930 NfaCombineResult<T> combineWith( 931 Nfa<T> nfa) { 932 933 if (nfa == null) { 934 throw new InternalException("nfa may not be null"); 935 } 936 937 if (!this.isStable) { 938 throw new InternalException("this Nfa is not stable yet"); 939 } 940 941 if (!nfa.isStable) { 942 throw new InternalException("nfa is not stable yet"); 943 } 944 945 AlphabetMergeResult<T> alphabetMergeResult = this.alphabet 947 .mergeWith(nfa.getAlphabet()); 948 Nfa<T> newNfa = new Nfa<T>(alphabetMergeResult.getNewAlphabet()); 949 950 SortedMap <NfaState<T>, NfaState<T>> oldNfa1StateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 952 this.addStatesAndTransitionsTo(newNfa, oldNfa1StateMap, 953 alphabetMergeResult); 954 955 SortedMap <NfaState<T>, NfaState<T>> oldNfa2StateMap = new TreeMap <NfaState<T>, NfaState<T>>(); 956 nfa.addStatesAndTransitionsTo(newNfa, oldNfa2StateMap, 957 alphabetMergeResult); 958 959 return new NfaCombineResult<T>(newNfa, this, oldNfa1StateMap, nfa, 960 oldNfa2StateMap); 961 } 962 963 975 private void addStatesAndTransitionsTo( 976 Nfa<T> newNfa, 977 SortedMap <NfaState<T>, NfaState<T>> nfaStateMap) { 978 979 if (newNfa.alphabet != this.alphabet) { 980 throw new InternalException( 981 "this Nfa and newNfa must share the same alphabet"); 982 } 983 984 for (NfaState<T> oldState : this.states) { 985 986 NfaState<T> newState = new NfaState<T>(newNfa); 987 nfaStateMap.put(oldState, newState); 988 } 989 990 for (NfaState<T> oldState : this.states) { 991 for (Map.Entry <Symbol<T>, SortedSet <NfaState<T>>> entry : oldState 992 .getTransitions().entrySet()) { 993 994 Symbol<T> symbol = entry.getKey(); 995 SortedSet <NfaState<T>> oldTargets = entry.getValue(); 996 997 for (NfaState<T> oldTarget : oldTargets) { 998 999 nfaStateMap.get(oldState).addTransition(symbol, 1000 nfaStateMap.get(oldTarget)); 1001 } 1002 } 1003 } 1004 } 1005 1006 1018 private void addStatesAndTransitionsTo( 1019 Nfa<T> newNfa, 1020 SortedMap <NfaState<T>, NfaState<T>> nfaStateMap, 1021 AlphabetMergeResult<T> alphabetMergeResult) { 1022 1023 for (NfaState<T> oldState : this.states) { 1024 1025 NfaState<T> newState = new NfaState<T>(newNfa); 1026 nfaStateMap.put(oldState, newState); 1027 } 1028 1029 for (NfaState<T> oldState : this.states) { 1030 for (Map.Entry <Symbol<T>, SortedSet <NfaState<T>>> entry : oldState 1031 .getTransitions().entrySet()) { 1032 1033 Symbol<T> oldSymbol = entry.getKey(); 1034 SortedSet <NfaState<T>> oldTargets = entry.getValue(); 1035 1036 for (NfaState<T> oldTarget : oldTargets) { 1037 1038 if (oldSymbol != null) { 1039 for (Symbol<T> newSymbol : alphabetMergeResult 1040 .getNewSymbols(oldSymbol, this.alphabet)) { 1041 1042 nfaStateMap.get(oldState).addTransition(newSymbol, 1043 nfaStateMap.get(oldTarget)); 1044 } 1045 } 1046 else { 1047 nfaStateMap.get(oldState).addTransition(null, 1048 nfaStateMap.get(oldTarget)); 1049 } 1050 } 1051 } 1052 } 1053 } 1054 1055 1062 int getNextStateId() { 1063 1064 if (this.isStable) { 1065 throw new InternalException("a stable Nfa may not be modified"); 1066 } 1067 1068 return this.states.size(); 1069 } 1070 1071 1080 void addState( 1081 NfaState<T> state) { 1082 1083 if (this.isStable) { 1084 throw new InternalException("a stable Nfa may not be modified"); 1085 } 1086 1087 if (!this.states.add(state)) { 1088 throw new InternalException("state is already in state set"); 1089 } 1090 } 1091 1092} 1093 | Popular Tags |