Updated splicemaps.
"{ 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
! !