ParsingAutomaton_MergeStates.cpp

/*********************************************************************** Author: Zihan Chen (vczh) Licensed under https://github.com/vczh-libraries/License ***********************************************************************/

#include "ParsingAutomaton.h"

namespace

{

namespace

parsing

{

using

namespace

collections

;

using

namespace

definitions

;

namespace

analyzing

{

/*********************************************************************** DeleteUnnecessaryStates ***********************************************************************/

void

DeleteUnnecessaryStates

(

Ptr

Automaton

automaton

Ptr

RuleInfo

ruleInfo

List

State

*>&

newStates

) {

// delete all states that are not reachable to the end state

while

(

true

) {

// find a non-end state without out transitions

vint

deleteCount

;

for

(

vint

newStates

Count

()-

;

--) {

State

newState

newStates

[

];

(

newState

transitions

Count

()==

) {

(

newState

ruleInfo

rootRuleEndState

&& !

newState

endState

) {

automaton

DeleteState

(

newState

);

newStates

RemoveAt

(

); } } }

(

deleteCount

) {

break

; } } }

/*********************************************************************** IsMergableCandidate ***********************************************************************/

bool

IsMergableCandidate

(

State

state

Ptr

RuleInfo

ruleInfo

) {

(

state

ruleInfo

rootRuleStartState

state

ruleInfo

rootRuleEndState

state

ruleInfo

startState

) {

return

false

; }

return

true

; }

/*********************************************************************** RearrangeState ***********************************************************************/

#define COMPARE_SYMBOL(S1, S2)\

if (S1 && S2)\

if (S1->GetType() < S2->GetType()) return -1;\

if (S1->GetType() > S2->GetType()) return 1;\

if (S1->GetName() < S2->GetName()) return -1;\

if (S1->GetName() > S2->GetName()) return 1;\

else if (S1)\

return 1;\

else if (S2)\

return -1;\

vint

CompareTransitionForRearranging

(

Transition

) {

(

transitionType

)

return

;

(

transitionType

)

return

;

COMPARE_SYMBOL(t1->transitionSymbol, t2->transitionSymbol);

(

transitionSymbol

) {

(

transitionSymbol

GetType

() <

transitionSymbol

GetType

())

return

;

(

transitionSymbol

GetType

() >

transitionSymbol

GetType

())

return

;

(

transitionSymbol

GetName

()

transitionSymbol

GetName

())

return

;

(

transitionSymbol

GetName

()

transitionSymbol

GetName

())

return

; }

else

(

transitionSymbol

) {

return

; }

else

(

transitionSymbol

) {

return

; };

return

; }

vint

CompareActionForRearranging

(

Ptr

Action

Ptr

Action

) {

(

actionType

)

return

;

(

actionType

)

return

;

COMPARE_SYMBOL(a1->actionSource, a2->actionSource);

(

actionSource

) {

(

actionSource

GetType

() <

actionSource

GetType

())

return

;

(

actionSource

GetType

() >

actionSource

GetType

())

return

;

(

actionSource

GetName

()

actionSource

GetName

())

return

;

(

actionSource

GetName

()

actionSource

GetName

())

return

; }

else

(

actionSource

) {

return

; }

else

(

actionSource

) {

return

; };

COMPARE_SYMBOL(a1->actionTarget, a2->actionTarget);

(

actionTarget

) {

(

actionTarget

GetType

() <

actionTarget

GetType

())

return

;

(

actionTarget

GetType

() >

actionTarget

GetType

())

return

;

(

actionTarget

GetName

()

actionTarget

GetName

())

return

;

(

actionTarget

GetName

()

actionTarget

GetName

())

return

; }

else

(

actionTarget

) {

return

; }

else

(

actionTarget

) {

return

; };

return

; }

#undef COMPARE_SYMBOL

void

RearrangeState

(

State

state

SortedList

State

*>&

stateContentSorted

) {

stateContentSorted

Contains

(

state

)) {

FOREACH(Transition*, transition, state->transitions)

(

bool

__scope_variable_flag__

true

)

for

(

const

collections

ForEachIterator

Transition

*>&

__foreach_iterator__

= ::

collections

CreateForEachIterator

(

state

transitions

);

__scope_variable_flag__

;

__scope_variable_flag__

false

)

for

(

Transition

transition

;

__foreach_iterator__

(

transition

);)

{

CopyFrom

(

transition

actions

From

(

transition

actions

).OrderBy(&

CompareActionForRearranging

)); }

CopyFrom

(

state

transitions

From

(

state

transitions

).OrderBy(&

CompareTransitionForRearranging

));

stateContentSorted

Add

(

state

); } }

/*********************************************************************** MoveActionsForMergingState ***********************************************************************/

void

MoveActionsForMergingState

(

Transition

transition

) {

// collect all movable actions

List

Ptr

Action

movableActions

;

for

(

vint

transition

actions

Count

()-

;

--) {

switch

(

transition

actions

[

]

actionType

) {

// Using and Assign actions are not movable

case

Action

Using

case

Action

Assign

break

;

default

movableActions

Add

(

transition

actions

[

]);

transition

actions

RemoveAt

(

); } }

// copy all movable actions

FOREACH(Transition*, t, transition->source->inputs)

(

bool

__scope_variable_flag__

true

)

for

(

const

collections

ForEachIterator

Transition

*>&

__foreach_iterator__

= ::

collections

CreateForEachIterator

(

transition

source

inputs

);

__scope_variable_flag__

;

__scope_variable_flag__

false

)

for

(

Transition

;

__foreach_iterator__

(

);)

{

CopyFrom

(

actions

movableActions

true

); } }

/*********************************************************************** IsMergableBecause(Transitions|Input) ***********************************************************************/

bool

IsMergableBecauseTransitions

(

State

state1

State

state2

) {

(

state1

transitions

Count

()!=

state2

transitions

Count

())

return

false

;

(

state1

transitions

Count

()==

state2

transitions

Count

()==

) {

Transition

state1

transitions

[

];

Transition

state2

transitions

[

];

(

CompareTransitionForRearranging

(

)==

&& !

Transition

IsEquivalent

(

false

) &&

target

) {

MoveActionsForMergingState

(

);

MoveActionsForMergingState

(

); } }

for

(

vint

;

state1

transitions

Count

();

++) {

Transition

state1

transitions

[

];

Transition

state2

transitions

[

];

Transition

IsEquivalent

(

false

) ||

target

) {

return

false

; } }

return

true

; }

bool

IsMergableBecauseInputs

(

State

state1

State

state2

) {

(

state1

inputs

Count

()!=

state2

inputs

Count

())

return

false

;

for

(

vint

;

state1

inputs

Count

();

++) {

Transition

state1

inputs

[

];

Transition

state2

inputs

[

];

Transition

IsEquivalent

(

false

) ||

source

) {

return

false

; } }

return

true

; }

/*********************************************************************** MergeState2ToState1Because(Transitions|Input) ***********************************************************************/

void

MergeState2ToState1BecauseTransitions

(

Ptr

Automaton

automaton

State

state1

State

state2

) {

// modify state1's expression

state1

stateExpression

L"\r\n"

state2

stateExpression

;

// retarget state2's input to state1

for

(

vint

state2

inputs

Count

()-

;

--) {

Transition

state2

inputs

[

];

bool

add

true

;

FOREACH(Transition*, t1, state1->inputs)

(

bool

__scope_variable_flag__

true

)

for

(

const

collections

ForEachIterator

Transition

*>&

__foreach_iterator__

= ::

collections

CreateForEachIterator

(

state1

inputs

);

__scope_variable_flag__

;

__scope_variable_flag__

false

)

for

(

Transition

;

__foreach_iterator__

(

);)

{

(

Transition

IsEquivalent

(

false

) &&

source

) {

add

false

;

break

; } }

(

add

) {

state1

inputs

Add

(

);

target

state1

;

state2

inputs

RemoveAt

(

); } }

automaton

DeleteState

(

state2

); }

void

MergeState2ToState1BecauseInputs

(

Ptr

Automaton

automaton

State

state1

State

state2

) {

// modify state1's expression

state1

stateExpression

L"\r\n"

state2

stateExpression

;

// retarget state2's input to state1

for

(

vint

state2

transitions

Count

()-

;

--) {

Transition

state2

transitions

[

];

bool

add

true

;

FOREACH(Transition*, t1, state1->transitions)

(

bool

__scope_variable_flag__

true

)

for

(

const

collections

ForEachIterator

Transition

*>&

__foreach_iterator__

= ::

collections

CreateForEachIterator

(

state1

transitions

);

__scope_variable_flag__

;

__scope_variable_flag__

false

)

for

(

Transition

;

__foreach_iterator__

(

);)

{

(

Transition

IsEquivalent

(

false

) &&

target

) {

add

false

;

break

; } }

(

add

) {

state1

transitions

Add

(

);

source

state1

;

state2

transitions

RemoveAt

(

); } }

automaton

DeleteState

(

state2

); }

/*********************************************************************** MergeStates ***********************************************************************/

void

MergeStates

(

Ptr

Automaton

automaton

Ptr

RuleInfo

ruleInfo

List

State

*>&

newStates

) {

SortedList

State

stateContentSorted

;

while

(

true

) {

for

(

vint

;

newStates

Count

();

++) {

State

state1

newStates

[

];

(

IsMergableCandidate

(

state1

ruleInfo

)) {

for

(

vint

;

newStates

Count

();

++) {

State

state2

newStates

[

];

(

state1

state2

IsMergableCandidate

(

state2

ruleInfo

)) {

RearrangeState

(

state1

stateContentSorted

);

RearrangeState

(

state2

stateContentSorted

);

(

IsMergableBecauseTransitions

(

state1

state2

)) {

MergeState2ToState1BecauseTransitions

(

automaton

state1

state2

);

newStates

RemoveAt

(

);

goto

MERGED_STATES_PAIR; }

else

(

IsMergableBecauseInputs

(

state1

state2

)) {

MergeState2ToState1BecauseInputs

(

automaton

state1

state2

);

newStates

RemoveAt

(

);

goto

MERGED_STATES_PAIR; } } } } }

break

; MERGED_STATES_PAIR:

continue

; } } } } }