0

Lately I've been working on a project that involves parsing a toy domain-specific-language. While building it out, I realized that an efficient way to handle parsing tokens would be to represent the parser as a state machine. To great success. Representing each possible state of the parser got rid of many problems I was facing. However, I recently ran into a new issue. Modeling the complete state graph is slowly becoming unmanageable. You can see here that even now the state graph is rather small. It got me thinking, how would one manage the state graph for a large enterprise application?

I'm sure there are 3rd party libraries that do this, but if one was to roll a scalable state machine from scratch how would one do that? Any advice / wisdom would be greatly appreciated here!

10
  • 1
    Standard answer: Use a parser generator.
    – whatsisname
    Commented Jun 23, 2016 at 15:54
  • 1
    why is this the standard answer?
    – dopatraman
    Commented Jun 23, 2016 at 16:07
  • 2
    Because those are pieces of software designed to do exactly what you are looking for for exactly your application.
    – whatsisname
    Commented Jun 23, 2016 at 16:12
  • 1
    @dopatraman A reference: dec.bournemouth.ac.uk/staff/kphalp/statecharts.pdf
    – Frank Hileman
    Commented Jun 23, 2016 at 23:41
  • 1
    Please note that impact with compression is huge, so if you write your states by hand and you use them just as you wrote them you will have problem with managing them but also with using them. As an example consider going from LR parser to LALR -- you lose some of the power, but your state machine becomes much smaller.
    – greenoldman
    Commented Jun 25, 2016 at 6:24

1 Answer 1

Reset to default
2

To parse a toy language, use a parser generator such as Antlr. The generated parser will keep track of the states for you.

While there is no need to manage a state graph for your toy language, state machines in general benefit from the idea of composite states and sub states. See Harel statecharts. If the state machine becomes too messy, you probably did not break it up properly.

3
  • I dont think i was clear... i dont care about my own application. how would one manage this problem for a non-compiler related application?
    – dopatraman
    Commented Jun 24, 2016 at 14:48
  • Composite states and sub-states, using Harel state charts. The other thing to note is that if that cannot fix your problem, your state machine needs a fundamental rework. I have seen state machines drop in complexity dramatically simply by having a more experienced engineer review the diagram.
    – Frank Hileman
    Commented Jun 24, 2016 at 16:04
  • @dopatraman: the way you'd manage it for a non compiler application would depend on the application.
    – whatsisname
    Commented Sep 22, 2016 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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