fsm

Overview ¶

fsm provides a finite state machine parser for parsing e.g. rulers

This state machine can

• correctly parse matching nested structures

• allows for tabular definitions of a language to be parsed

see also: codeberg.org/japh/go-fsmparser

Overview:

var stateMachine = fsm.LoadStateMachine(...)

func (exp *Expression)Parse( input string ) {
    lexer  := fsm.StringLexer( input )
    parser := fsm.Parser(
                        fsm.WithStateMachine( stateMachine ),
                        fsm.WithLexer( lexer ),
                        )
    for parser.Scan() {
        token := parser.Next()
        switch token.Name {
            ...
        }
    }
}

State Transition Tables:

State transitions are defined as tupels of information for each possible transition. Each transition describes an edge in a graph, in which each state is represented by a graph node and each transition is an edge between two nodes.

At the very minimum, each state transition must provide:

• an source state
• a symbol to match in the input stream (may be the empty string)
• the name of a token to emit when the symbol is found
• a target state

Which might look something like this:

| state           | input    | token      | next          | notes                                                                     |
| --------------- | -------- | ---------- | ------------- | ------------------------------------------------------------------------- |
| want_expression |          | start_exp  | want_term     | initial state                                                             |
| want_term       | {number} | term       | want_operator | {number} will be matched via a custom matcher                             |
| want_term       |          | finish_exp | done          | an empty symbol always matches - must be the last transition from a state |
| want_operator   | +        | add        | want_term     | `+` will be matched verbatim                                              |
| want_operator   | -        | subtract   | want_term     |                                                                           |
| done            |          |            |               | final state                                                               |

The first row of the table must be a header consisting of column names, but the actual names you use can be configured to your liking.

The full set of transition fields are:

• the source state
• a 'slurp' symbol to be consumed before searching for this state's next symbol
• a symbol to match against the input
• a token to emit when the symbol is found and the trasition is followed
• an error token to emit when this transition is triggered
• a target state
• a state to push on the stack when this transition was triggered
• a symbol to pop from the stack, i.e. the transtion for ')' expects the popped symbol to be '('

e.g.:

loader, err := fsm.NewTableLoader(
    //              column id     column name
    fsm.WithColumn( fsm.StateCol, "state"      ),
    fsm.WithColumn( fsm.SlurpCol, "slurp"      ),
    fsm.WithColumn( fsm.MatchCol, "input"      ),
    fsm.WithColumn( fsm.TokenCol, "token"      ),
    fsm.WithColumn( fsm.ErrorCol, "error"      ),
    fsm.WithColumn( fsm.NextCol,  "next state" ),
    fsm.WithColumn( fsm.PopCol,   "pop"        ),
    fsm.WithColumn( fsm.PushCol,  "push"       ),
    ...
)