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!

  • 1
    Standard answer: Use a parser generator. – whatsisname Jun 23 '16 at 15:54
  • 1
    why is this the standard answer? – dopatraman Jun 23 '16 at 16:07
  • 2
    Because those are pieces of software designed to do exactly what you are looking for for exactly your application. – whatsisname Jun 23 '16 at 16:12
  • 1
    @dopatraman A reference: dec.bournemouth.ac.uk/staff/kphalp/statecharts.pdf – Frank Hileman Jun 23 '16 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 Jun 25 '16 at 6:24
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.

  • 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 Jun 24 '16 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 Jun 24 '16 at 16:04
  • @dopatraman: the way you'd manage it for a non compiler application would depend on the application. – whatsisname Sep 22 '16 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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