"{ 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 

! !