--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compiler/PEGFsaAbstractDeterminizator.st	Mon Aug 17 12:13:16 2015 +0100
@@ -0,0 +1,163 @@
+"{ Package: 'stx:goodies/petitparser/compiler' }"
+
+"{ NameSpace: Smalltalk }"
+
+Object subclass:#PEGFsaAbstractDeterminizator
+	instanceVariableNames:'fsa joinDictionary'
+	classVariableNames:''
+	poolDictionaries:''
+	category:'PetitCompiler-FSA'
+!
+
+!PEGFsaAbstractDeterminizator class methodsFor:'as yet unclassified'!
+
+new
+    ^ self basicNew initialize
+! !
+
+!PEGFsaAbstractDeterminizator methodsFor:'accessing - keys'!
+
+joinKey: key with: anotherKey
+    ^ Set new
+        addAll: key;
+        addAll: anotherKey;
+        yourself.
+!
+
+keyFor: state
+    ^ joinDictionary keyAtIdentityValue: state ifAbsent: [ Set with: state ]
+!
+
+keyFor: state and: anotherState
+    | key anotherKey |
+    key := self keyFor: state.
+    anotherKey := self keyFor: anotherState.
+    
+    ^ self joinKey: key with: anotherKey
+! !
+
+!PEGFsaAbstractDeterminizator methodsFor:'determinization'!
+
+determinize
+    | states |
+"	fsa checkSanity."
+    fsa removeEpsilons.
+    fsa removeUnreachableStates.
+    fsa mergeTransitions.
+    
+    states := fsa topologicalOrder asOrderedCollection.
+    states do: [ :state |
+        self determinizeState: state
+    ].
+
+    fsa states:	fsa startState reachableStates.
+    
+    fsa removeUnreachableStates.
+    fsa mergeTransitions.
+!
+
+determinize: anFsa
+    fsa := anFsa.
+    joinDictionary := Dictionary new.
+    
+    self determinize.
+    ^ fsa
+!
+
+determinizeOverlap: t1 second: t2 state: state
+    |  t1Prime t2Prime tIntersection |
+    self assert: (state transitions includes: t1).
+    self assert: (state transitions includes: t2).
+    
+    tIntersection := self joinTransition: t1 with: t2.
+
+    t1Prime := PEGFsaCharacterTransition new
+                    destination: t1 destination;
+                    characterSet: (t1 complement: t2);
+                    yourself.
+    t2Prime := PEGFsaCharacterTransition new
+                    destination: t2 destination;
+                    characterSet: (t2 complement: t1);
+                    yourself.					
+                                    
+                                
+    state removeTransition: t1.
+    state removeTransition: t2.
+    
+    tIntersection isEmpty ifFalse: [ state addTransition: tIntersection  ].
+    t1Prime isEmpty ifFalse: [ state addTransition: t1Prime ].
+    t2Prime isEmpty ifFalse: [ state addTransition: t2Prime ].
+!
+
+determinizeState: state
+    | pairs |
+
+    pairs := state transitionPairs asOrderedCollection.
+
+    [pairs isEmpty] whileFalse: [ 
+        | pair |
+        
+        (joinDictionary size > 100) ifTrue: [ self error: 'Oh man, this is really big FSA. Are you sure you want to continue?' ].
+        
+        pair := pairs removeFirst.
+        self assert:((pair first destination = pair second destination) not 
+                    or: [pair first isPredicateTransition not 
+                    or: [pair second isPredicateTransition not ] ]).
+                
+        self assert: (pair contains: #isEpsilon) not.		
+                
+        (pair first overlapsWith: pair second) ifTrue: [ 
+            self determinizeOverlap: pair first second: pair second state: state.
+            "recompute pairs after the determinization"
+            pairs := state transitionPairs asOrderedCollection.
+        ]
+    ].
+! !
+
+!PEGFsaAbstractDeterminizator methodsFor:'initialization'!
+
+initialize
+    super initialize.
+    joinDictionary := Dictionary new
+! !
+
+!PEGFsaAbstractDeterminizator methodsFor:'joining'!
+
+joinName: state with: anotherState into: newState
+    newState name: state name asString, '_', anotherState name asString.
+!
+
+joinState: state with: anotherState
+    | key newState |
+    key := self keyFor: state and: anotherState.
+    (joinDictionary includesKey: key) ifTrue: [ ^ joinDictionary at: key ].
+    
+    newState := PEGFsaState new.
+    joinDictionary at: key put: newState.
+
+    self joinRetval: state with: anotherState into: newState.
+    self joinInfo: state with: anotherState into: newState.
+    self joinName: state with: anotherState into: newState.
+    self joinTransitions: state with: anotherState into: newState.	
+
+    self determinizeState: newState.
+    
+    self assert: ((joinDictionary at: key) == newState).
+    ^ newState
+!
+
+joinTransition: t1 with: t2
+    | newDestination newTransition |
+    self assert: t1 isCharacterTransition.
+    self assert: t2 isCharacterTransition.
+    
+    newDestination := self joinState: t1 destination with: t2 destination.
+    
+    newTransition := PEGFsaCharacterTransition new.
+    newTransition destination: newDestination.
+    newTransition characterSet: (t1 intersection: t2).
+    newTransition priority: (t1 priority max: t2 priority).
+    
+    ^ newTransition 
+! !
+