10 ms·

Ragel State Machine Compiler

49 points by Arubis 11y ago

kbob 11y ago
How is this different from Lex, written in 1975? Even the syntax looks fairly similar. https://en.wikipedia.org/wiki/Lex_(software) https://en.wikipedia.org/wiki/Lex_(software)
- thurston 11y ago
  Ragel allows embedding actions into the subexpressions of a regular expression. This allows one to compose a parser using a single regular expression.
  - hedgehog 11y ago
    To add some color: Without much difficulty I was able to build a small POP3 server by describing the protocol as a Ragel grammar with the verbs implemented as semantic actions (a small amount of Go). It reads very nicely compared to a hand-built version of the same thing. The only real downside I found was that it was hard to tell what's wrong when your grammar isn't behaving as expected but no worse than other parser generators I've used.
  - ticviking 11y ago
    Why would you want to do that?
    - jasonwatkinspdx 11y ago
      There are a lot of advantages to a declarative approach, and a lot of risks and problems with hand written parsers and state machines. A good example is the http code Zed wrote with ragel. From what I remember it was contracted by verisign because they wanted an implementation that actually followed the spec in detail, unlike all other code available at the time. That ragel code has been reused by a lot of embedded http servers in many languages now.
      - iofj 11y ago
        The thing I keep finding problematic about declarative approaches is that nobody knows them. That means if you're not a lone wolf on a project, the people editing your declarative state machine are going to be unfamiliar with it. Aside from the complaints that gives (and the "look I rewrote it" issues), that means they make mistakes and don't understand what happens. So they don't last. They're not all that maintainable in real teams. My experiences are mostly with ANTLR code (which has a debugger and lots of tooling and isn't that hard at all). I'm at a loss for how to overcome this.
        thurston 11y ago
        Keep using them is how you overcome this ;)
    - thurston 11y ago
      Same reason you would want to use yacc to write a parser. A grammar annotated with code is a nice way to express a parser. If the language happens to be regular, you can use ragel to generate a directly executable deterministic state machine. The code is simple and fast.
- sanderjd 11y ago
  I tried to find a good quote to summarize, but really, it's probably just worth reading the "Motivation" section of the guide[0], if your question is asked in good faith. Note also that Ragel isn't some new-fangled thing. It was first released in January of 2002, and is very mature. [0]: http://www.colm.net/files/ragel/ragel-guide-6.9.pdf http://www.colm.net/files/ragel/ragel-guide-6.9.pdf
- ksherlock 11y ago
  lex is more opinionated (in today's parlance). Ragel is easier to embed in your own code.
- mtdewcmu 11y ago
  Lex solves a restricted subset of state machine code generation problems; Ragel aims to solve all state machine code generation problems generally. You can do anything you can do in Lex in Ragel. The reverse is not true. Lex is simpler, but less powerful than Ragel. It's sort of like awk versus Perl. I'd rather use Lex where Lex is good enough.
jdnier 11y ago
Are you aware of anyone working to add Python as a target language? Will Ragel 7's intermediate codegen language make that easier?
- thurston 11y ago
  Not at this time. But yes Ragel 7 will make it much easier. The first round of new languages I added helped me polish the technique. Once 7 is out and vetted it will make sense to add more.
lsllc 11y ago
I've used Ragel extensively with both C and Go; I can't recommend it more highly enough! Thanks Adrian for your efforts.
- thurston 11y ago
  My pleasure, thank you for the note!
clumsysmurf 11y ago
I've been using Ragel on Android since Froyo (Java target); amazing software!
- thurston 11y ago
  Thanks!
fasteo 11y ago
Seems like Lua would be a perfect target for Ragel. Do you know if anyone is working in this direction ? How does it compare with LPeg[1] ? This is what I currently use for all my parsing needs. [1] http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/
- leafo 11y ago
  Ragel doesn't support recursion (last I checked), so it's not suitable for many parsing jobs. I considered it for MoonScript's parser at one point but it didn't seem like it could do it. I've been experimenting with this project as a replacement for LPEG for the MoonScript parser: http://piumarta.com/software/peg/ http://piumarta.com/software/peg/ I've made an LPEG style syntax that compiles to the peg syntax for that tool, which is then compiled to c and linked into a Lua module, you can see how the parser is written here: https://github.com/leafo/moonparse/blob/master/parse.peg.moon#L115 https://github.com/leafo/moonparse/blob/master/parse.peg.moo...
- thurston 11y ago
  At their core they target different language classes. Ragel deals with regular, whereas LPeg deals with context-free grammars.
- thurston 11y ago
  WRT Lua, not at this time, but it is one I would like to support. Won't be too much work to add it.

49 points by Arubis 11y ago

kbob 11y ago

How is this different from Lex, written in 1975? Even the syntax looks fairly similar. https://en.wikipedia.org/wiki/Lex_(software) https://en.wikipedia.org/wiki/Lex_(software)

thurston 11y ago
Ragel allows embedding actions into the subexpressions of a regular expression. This allows one to compose a parser using a single regular expression.
- hedgehog 11y ago
  To add some color: Without much difficulty I was able to build a small POP3 server by describing the protocol as a Ragel grammar with the verbs implemented as semantic actions (a small amount of Go). It reads very nicely compared to a hand-built version of the same thing. The only real downside I found was that it was hard to tell what's wrong when your grammar isn't behaving as expected but no worse than other parser generators I've used.
- ticviking 11y ago
  Why would you want to do that?
  - jasonwatkinspdx 11y ago
    There are a lot of advantages to a declarative approach, and a lot of risks and problems with hand written parsers and state machines. A good example is the http code Zed wrote with ragel. From what I remember it was contracted by verisign because they wanted an implementation that actually followed the spec in detail, unlike all other code available at the time. That ragel code has been reused by a lot of embedded http servers in many languages now.
    - iofj 11y ago
      The thing I keep finding problematic about declarative approaches is that nobody knows them. That means if you're not a lone wolf on a project, the people editing your declarative state machine are going to be unfamiliar with it. Aside from the complaints that gives (and the "look I rewrote it" issues), that means they make mistakes and don't understand what happens. So they don't last. They're not all that maintainable in real teams. My experiences are mostly with ANTLR code (which has a debugger and lots of tooling and isn't that hard at all). I'm at a loss for how to overcome this.
      - thurston 11y ago
        Keep using them is how you overcome this ;)
  - thurston 11y ago
    Same reason you would want to use yacc to write a parser. A grammar annotated with code is a nice way to express a parser. If the language happens to be regular, you can use ragel to generate a directly executable deterministic state machine. The code is simple and fast.
sanderjd 11y ago
I tried to find a good quote to summarize, but really, it's probably just worth reading the "Motivation" section of the guide[0], if your question is asked in good faith. Note also that Ragel isn't some new-fangled thing. It was first released in January of 2002, and is very mature. [0]: http://www.colm.net/files/ragel/ragel-guide-6.9.pdf http://www.colm.net/files/ragel/ragel-guide-6.9.pdf
ksherlock 11y ago
lex is more opinionated (in today's parlance). Ragel is easier to embed in your own code.
mtdewcmu 11y ago
Lex solves a restricted subset of state machine code generation problems; Ragel aims to solve all state machine code generation problems generally. You can do anything you can do in Lex in Ragel. The reverse is not true. Lex is simpler, but less powerful than Ragel. It's sort of like awk versus Perl. I'd rather use Lex where Lex is good enough.

jdnier 11y ago

Are you aware of anyone working to add Python as a target language? Will Ragel 7's intermediate codegen language make that easier?

thurston 11y ago
Not at this time. But yes Ragel 7 will make it much easier. The first round of new languages I added helped me polish the technique. Once 7 is out and vetted it will make sense to add more.

lsllc 11y ago

I've used Ragel extensively with both C and Go; I can't recommend it more highly enough! Thanks Adrian for your efforts.

thurston 11y ago
My pleasure, thank you for the note!

clumsysmurf 11y ago

I've been using Ragel on Android since Froyo (Java target); amazing software!

thurston 11y ago
Thanks!

fasteo 11y ago

Seems like Lua would be a perfect target for Ragel. Do you know if anyone is working in this direction ? How does it compare with LPeg[1] ? This is what I currently use for all my parsing needs. [1] http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/

leafo 11y ago
Ragel doesn't support recursion (last I checked), so it's not suitable for many parsing jobs. I considered it for MoonScript's parser at one point but it didn't seem like it could do it. I've been experimenting with this project as a replacement for LPEG for the MoonScript parser: http://piumarta.com/software/peg/ http://piumarta.com/software/peg/ I've made an LPEG style syntax that compiles to the peg syntax for that tool, which is then compiled to c and linked into a Lua module, you can see how the parser is written here: https://github.com/leafo/moonparse/blob/master/parse.peg.moon#L115 https://github.com/leafo/moonparse/blob/master/parse.peg.moo...
thurston 11y ago
At their core they target different language classes. Ragel deals with regular, whereas LPeg deals with context-free grammars.
thurston 11y ago
WRT Lua, not at this time, but it is one I would like to support. Won't be too much work to add it.