1 "{ Package: 'stx:goodies/petitparser/compiler' }"

     2 

     3 "{ NameSpace: Smalltalk }"

     4 

     5 Object subclass:#PEGFsaMinimizator

     6 	instanceVariableNames:'fsa joinDictionary'

     7 	classVariableNames:''

     8 	poolDictionaries:''

     9 	category:'PetitCompiler-FSA'

    10 !

    11 

    12 !PEGFsaMinimizator methodsFor:'comparison'!

    13 

    14 info: info equals: anotherInfo

    15     (info == anotherInfo) ifTrue: [ ^ true ].

    16     (info class == anotherInfo class) ifFalse: [ ^ false ].

    17 

    18     "	

    19         I suppose I don't if someone does not have the priority set.

    20         Please note that equals is used for minimization, so I try to

    21         be as liberal as possible to get as small automaton as possible.

    22     "

    23     (info hasPriority and: [anotherInfo hasPriority]) ifTrue: [ 	

    24         (info priority == anotherInfo priority) ifFalse: [ ^ false ].

    25     ].

    26 

    27     (info isFinal == anotherInfo isFinal) ifFalse: [ ^ false ].

    28     (info isFsaFailure == anotherInfo isFsaFailure) ifFalse: [ ^ false ].

    29 

    30     ^ true

    31 !

    32 

    33 state: state equals: anotherState

    34     (state == anotherState) ifTrue: [ ^ true ].

    35     (state class == anotherState class) ifFalse: [ ^ false ].

    36     

    37     (state isFinal = anotherState isFinal) ifFalse: [ ^ false ].

    38 

    39     (state stateInfos size == anotherState stateInfos size) ifFalse: [ ^ false ].

    40     state retvals do: [:retval |

    41         (self info: (state infoFor: retval) equals: (anotherState infoFor: retval ifAbsent: [ ^ false ])) ifFalse: [ ^ false ]

    42     ].

    43 

    44 

    45     (state transitions size == anotherState transitions size) ifFalse: [ ^ false ].

    46     anotherState transitions do: [ :anotherStateT | 

    47         (state transitions contains: [ :stateT | 

    48             (anotherStateT equals: stateT) or: [

    49                 "this is condition for self reference" 

    50                 (anotherStateT destination == anotherState) and: [ stateT destination == state ]	

    51             ] ] ) ifFalse: [ ^ false ]

    52     ].

    53     

    54     ^ true

    55 ! !

    56 

    57 !PEGFsaMinimizator methodsFor:'joining'!

    58 

    59 joinInfo: state with: anotherState

    60     self assert: state stateInfos size == anotherState stateInfos size.

    61 

    62     state stateInfos do: [ :si1 | 

    63         self assert: (anotherState stateInfos contains: [ :si2 | 

    64             si1 isFinal == si2 isFinal and: [ si1 isFsaFailure == si2 isFsaFailure  ]

    65         ])

    66     ]

    67 !

    68 

    69 joinName: state with: anotherState

    70     state name: state name asString, '+', anotherState name asString.

    71 !

    72 

    73 joinState: state with: anotherState

    74     self assert: state hasZeroPriorityOnly.

    75     self assert: anotherState hasZeroPriorityOnly.

    76 

    77     self joinName: state with: anotherState.

    78     self joinInfo: state with: anotherState.

    79     

    80 ! !

    81 

    82 !PEGFsaMinimizator methodsFor:'minimization'!

    83 

    84 minimize

    85     | pair |

    86     pair := fsa statePairs detect:  [ :p | self state: p first equals: p second ] ifNone: [ nil ].

    87 

    88     [ pair isNil not ] whileTrue: [ 

    89         "Join priorities, because equivalency of priorities does not follow from the `equals:` of states"

    90         self joinState: pair first with: pair second.

    91         fsa replace: pair second with: pair first.

    92         fsa mergeTransitions.

    93 

    94         pair := fsa statePairs detect: [ :p | self state: p first equals: p second ] ifNone: [ nil ].

    95  	].

    96 !

    97 

    98 minimize: anFsa

    99     fsa := anFsa.

   100 

   101     self minimize.

   102     fsa checkSanity.

   103     ^ fsa

   104 ! !

   105