--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compiler/PEGFsaMinimizator.st	Mon Aug 17 12:13:16 2015 +0100
@@ -0,0 +1,105 @@
+"{ Package: 'stx:goodies/petitparser/compiler' }"
+
+"{ NameSpace: Smalltalk }"
+
+Object subclass:#PEGFsaMinimizator
+	instanceVariableNames:'fsa joinDictionary'
+	classVariableNames:''
+	poolDictionaries:''
+	category:'PetitCompiler-FSA'
+!
+
+!PEGFsaMinimizator methodsFor:'comparison'!
+
+info: info equals: anotherInfo
+    (info == anotherInfo) ifTrue: [ ^ true ].
+    (info class == anotherInfo class) ifFalse: [ ^ false ].
+
+    "	
+        I suppose I don't if someone does not have the priority set.
+        Please note that equals is used for minimization, so I try to
+        be as liberal as possible to get as small automaton as possible.
+    "
+    (info hasPriority and: [anotherInfo hasPriority]) ifTrue: [ 	
+        (info priority == anotherInfo priority) ifFalse: [ ^ false ].
+    ].
+
+    (info isFinal == anotherInfo isFinal) ifFalse: [ ^ false ].
+    (info isFsaFailure == anotherInfo isFsaFailure) ifFalse: [ ^ false ].
+
+    ^ true
+!
+
+state: state equals: anotherState
+    (state == anotherState) ifTrue: [ ^ true ].
+    (state class == anotherState class) ifFalse: [ ^ false ].
+    
+    (state isFinal = anotherState isFinal) ifFalse: [ ^ false ].
+
+    (state stateInfos size == anotherState stateInfos size) ifFalse: [ ^ false ].
+    state retvals do: [:retval |
+        (self info: (state infoFor: retval) equals: (anotherState infoFor: retval ifAbsent: [ ^ false ])) ifFalse: [ ^ false ]
+    ].
+
+
+    (state transitions size == anotherState transitions size) ifFalse: [ ^ false ].
+    anotherState transitions do: [ :anotherStateT | 
+        (state transitions contains: [ :stateT | 
+            (anotherStateT equals: stateT) or: [
+                "this is condition for self reference" 
+                (anotherStateT destination == anotherState) and: [ stateT destination == state ]	
+            ] ] ) ifFalse: [ ^ false ]
+    ].
+    
+    ^ true
+! !
+
+!PEGFsaMinimizator methodsFor:'joining'!
+
+joinInfo: state with: anotherState
+    self assert: state stateInfos size == anotherState stateInfos size.
+
+    state stateInfos do: [ :si1 | 
+        self assert: (anotherState stateInfos contains: [ :si2 | 
+            si1 isFinal == si2 isFinal and: [ si1 isFsaFailure == si2 isFsaFailure  ]
+        ])
+    ]
+!
+
+joinName: state with: anotherState
+    state name: state name asString, '+', anotherState name asString.
+!
+
+joinState: state with: anotherState
+    self assert: state hasZeroPriorityOnly.
+    self assert: anotherState hasZeroPriorityOnly.
+
+    self joinName: state with: anotherState.
+    self joinInfo: state with: anotherState.
+    
+! !
+
+!PEGFsaMinimizator methodsFor:'minimization'!
+
+minimize
+    | pair |
+    pair := fsa statePairs detect:  [ :p | self state: p first equals: p second ] ifNone: [ nil ].
+
+    [ pair isNil not ] whileTrue: [ 
+        "Join priorities, because equivalency of priorities does not follow from the `equals:` of states"
+        self joinState: pair first with: pair second.
+        fsa replace: pair second with: pair first.
+        fsa mergeTransitions.
+
+        pair := fsa statePairs detect: [ :p | self state: p first equals: p second ] ifNone: [ nil ].
+ 	].
+!
+
+minimize: anFsa
+    fsa := anFsa.
+
+    self minimize.
+    fsa checkSanity.
+    ^ fsa
+! !
+