Finite state machines

An LR(1) parser generator is a very sophisticated tool that produces an extremely flexible input event pattern recogniser. It does however produce a complex state machine that requires a push-down automaton to drive it. For simple state machines this is complete overkill.

Many workflow engines or state machine based controllers just need to have a set of states that they can be in at different times, and a set of rules that define that when in a particular state, if an event of a specified type occurs and an optional guard condition is true, we are going to execute some action in response to the event and then jump to a new state. The ParseLR toolkit is capable of describing these simple finite state machines (FSMs) with a grammar input description, and then of translating the input description into source code that will execute that state machine. Alternatively it can take the input grammar description at run time, and create an executable state machine within the currently running program and begin executing it.

When using ParseLR to create source code for a state machine, the output source code is in C#. When using the ParseLR runtime libraries to create an in-process state machine at runtime, the inline code embedded in the grammar is in C#, but the target language used for other parts of the application can be in any .NET language.

This page and the links from it provide documentation for the ParseLR library and toolkit when they are being used to create simple finite state machines as described above. Alternatively, for details on how to use the toolkit to develop LR(1) canonical parsers, go to these pages.

Documentation

The description of how to write a finite state machine specification for consumption by the parser generator spans a number of pages. These are best viewed in order as follows:

• An overview of the syntax and structure of the FSM description;
• Details of the options that can be given at the top of the FSM description;
• The listing of input event types in the FSM description;
• The listing of guard functions in the FSM description;
• The structure of the grammar rules section of the state machine;
• The detail on how to write individual rules;
• Adding guards to events in state machine transitions;
• How errors are handled in state machines;
• Including action source code into rules for state machines;
• How to write the FSM class for an in-line state machine;
• How to instantiate in-line state machines;
• Writing an input event source (tokeniser);
• How to write the FSM class for an offline state machine;
• How to instantiate and use an offline state machine;
• The ParseLR command-line tool used to create source code for offline state machines.
• You may download the toolkit, this documentation, and the source code for the examples.