Pushdown Automaton

PDA - Wikipedia Page

afsm library provides a feature to push down (and pop up) the entire state machine or a part of it. The machine that can be pushed operates a stack of sub-states instead of a plain sub-state table. Available are only the states at the top of the stack. The machine can be pushed down or popped up as a result of state state transition.

For the purpose of operating a state stack, afsm introduces two pseudo-states:

namespace afsm{ namespace def {

/** Pushes current state of the machine specified down the stack 
 *  and places a new copy on top. Invokes entry action of the
 *  machine with the event that caused the transition.
 *  Inside state machine declaration this type has alias `push`
 */
template <typename T, typename Machine, typename ... Tags>
struct pushdown;
/** Invokes exit action of the machine's current stack top
 *  and pop it. The machine will be in pushdown state that
 *  caused stack pushing.
 *  Inside state machine declaration this type has alias `pop`
 */
template <typename T, typename Machine, typename ... Tags>
struct popup;

} /* namespace def */ } /* namespace afsm */

Example:

struct my_pda_def : ::afsm::def::state_machine<my_pda_def> {
    struct start : state<start> {};
    struct recursive : push<recursive, my_pda_def> {};
    struct end : pop<end, my_pda_def> {};
    using initial_state = start;
    // Skip ...
};

After transiting to the recursive state the state machine's internal states will be pushed down the stack and the state machine will enter it's initial state. When the state machine transits to the end state, current stack top will be popped and destroyed.

An example of fully functional FSM with PDA can be found in json parser FSM test

Limitations of current implementation

• The push and pop states must be inside the state machine they manipulate;
• The state machine being pushed down operates stack of it's internal states, not the data contained in the definition class.