State machine classes to describe an allowed sequences of tokens.

A state machine is a DFA (deterministic finite automaton, always at most one edge that matches). An edge is associated with a matched token, locations are decision points between tokens.

An edge may tag occurrences of tokens to simplify extraction of relevant information for future compiler phases. A location may record matching of a valid sequence of tokens by accepting.

Module Contents#



Location in a state machine.


Edge to a next location.


State machine containing locations and edges.


Result data of a matching process in StateMachine.match().

class raesl.compile.state_machine.Location(name: str, accept: str | None = None)#

Location in a state machine.

  • accept – Name of the rule that could be accepted at this location. If None, no such rule exists.

  • name – Name of the location, mostly for identifying purposes.


Outgoing edges, initially empty.

class raesl.compile.state_machine.Edge(dest: Location, tok_type: str, tag_name: str | None = None)#

Edge to a next location.

  • dest – Destination of the edge.

  • tok_type – The value of the ‘tok_type’ attribute of a token that can trigger this transition.

  • tag_name – If not None, the name to use for recording the transition in the state machine.

class raesl.compile.state_machine.StateMachine(name: str)#

State machine containing locations and edges.

Note that it only stores the initial location, all other locations and edges are reachable from it.


name – Name of the state machine, also the name of the matched sequence.


Initial location of the state machine. Set after construction.


Sort edges of the state machine to get specific tokens checked first.

dump(fname: str | None = None)#

Dump the state machine to a file in Graphviz format.


fname – If not None, name of the file to write, else a filename is constructed from the name of the state machine.

match(lexer: raesl.compile.scanner.Lexer) MatchResult | None#

Try to match the machine against tokens from the scanner.


lexer – Token stream to match. Instance is useless afterwards, make a copy beforehand if you need it again.


Result of the matching process.


This routine is currently only used for testing.

single_step(lexer: raesl.compile.scanner.Lexer, current_loc: Location, tags: Dict[str, List[raesl.compile.scanner.Token]]) Tuple[Location, raesl.compile.scanner.Token] | None#

Try to perform a single step in the state machine.

  • lexer – Token stream to match. Instance is modified in-place if a transition is taken.

  • current_loc – Location to use for finding edges to try.

  • tags – Collected tags so far, may be updated in-place if transition was performed.


New location and the matching token if a transition could be performed, else None.

class raesl.compile.state_machine.MatchResult(accepted_name: str | None, accepted_tags: Dict[str, List[raesl.compile.scanner.Token]], lexer: raesl.compile.scanner.Lexer)#

Result data of a matching process in StateMachine.match().

  • accepted_name – Acceptance name from the last visited accepting location.

  • accepted_tags – Collected tag data at the point of accepting.

  • lexer – Lexer at the time of the last fail or at the time of the last accept