3

I'm doing a lot of code analysis using lexer and finite state machine. For time being I'm using table to describe FSM:

| token | current state | target state |
+-------+---------------+--------------+
| .     | start         | dot          |
| trace | dot           | method       |
| (     | method        | detected     |

Using this table and implicit start state FSM is created:

enter image description here

Lexer is used to generate a stream of tokens and token used as trigger for state transition. In case transition from current state is impossible - FSM is set to start state.

Using table to describe FSM is alright for fairly small number of states, but it gets complicated fairly quickly. Google search suggested very few interesting results:

So the question is there standard or de facto language to describe finite state machines?

  • 3
    using state-transition tables is the regular way of doing it. However, if I remember correctly, then Type-3-Grammatics are recognized by finite state machines, so I think you could use those as description language (en.wikipedia.org/wiki/Regular_grammar) – Lovis Aug 26 '16 at 10:17
  • Why don't you use a parser generator? – whatsisname Aug 26 '16 at 16:33
  • Thats a good question, I'll look into parser generator as well. – aisbaa Aug 30 '16 at 8:57
  • So you are building this FSM in order to parse code and analyze it, correct? So you are building the in memory representation of the FSM, right? If I've got that right, are you handling the parsing the table? – JimmyJames Aug 30 '16 at 16:18
  • 1
    One of the simplest languages which can encode the information set of a state-transition table, along with parseable predicates for labelled (or not) transitions, is probably those good old S-expressions: en.wikipedia.org/wiki/S-expression – YSharp Aug 31 '16 at 5:41
3

Since finite state machines are a basically subset of (labelled) directed graphs, what about something like DOT. It was just the first thing that popped up on a Google "directed graph language". I've never used it.

  • DOT and graphviz is for making diagrams, it's not useful for code analysis. – whatsisname Aug 26 '16 at 16:38
  • 1
    @whatsisname My understanding is that the question is about how to describe the finite state machine. DOT does that. Are you saying that the DOT representation can only be used to for making diagrams? If so, that seems to be obviously not true. – JimmyJames Aug 26 '16 at 16:46
  • I interpreted his question as he needs to do some analysis on code, but not necessarily report his findings to someone else. Graphviz might be useful for reporting the findings, but not the actual analysis. We often use "describe" as a synonym for "characterize" in this context. – whatsisname Aug 26 '16 at 19:15
  • Additionally, if he is going to use DOT for whatever he's doing, now he has two problems. – whatsisname Aug 26 '16 at 19:15
  • @whatsisname If you look at around the middle of the page from my link, there are 10 different tools listed that can supposedly use this format. All I see in the question is a request for a different way to format the FMS as text. The question is unclear so maybe you are right and it's not helpful. I'd need clarification on the question to be sure. – JimmyJames Aug 29 '16 at 13:26
2

Most of what has been standardised goes beyond simple finite state machines.

If you like XML, there's State Chart XML and UML's XMI for UML state charts, both of which are a superset of finite state machine.

There's also Matlab's stateflow, but I'm not sure if there's a text based language behind them or a proprietary format.

Trawling my links from a few years back, Microsoft's Abstract state machine language has an implementation XASM ( I've not used it ) and a paper 'SML-a high level language for the design and verification of finite state machines'. If you want something more of domain language within a programming languages, there's this question Is there a programming language with built-in state machine construct?

protected by gnat Mar 6 '18 at 15:02

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.