3 ms·

Some years ago, I heard of several projects using the ragel state machine compiler for parsing network protocols http://www.colm.net/open-source/ragel/ http://w

by fanf2 3y ago

Some years ago, I heard of several projects using the ragel state machine compiler for parsing network protocols http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/. It sounded great, but I found it was too low-level for me: it seemed that to use it effectively, I would have to attain oneness with the state machine, whereas one of the great advantages of regular expressions is that I don’t have to think (much) about how they are implemented. On the other hand, for a small project I wanted to wire up a C library (adns) to a simple parser, but adns lacks bindings to higher-level languages. So I thought, why not go retro and use the classic Unix swiss army knife, lex [•]. And it was actually a lot nicer than I expected, and the results were great. More recently I used re2c for a C/C++ lexer. Its user interface is fairly similar to lex, but cleaned up for modern tastes – in fact, re2c is easier and more flexible than lex, I think. And like ragel, re2c produces a directly-coded state machine, instead of a table-driven state machine. So the resulting code is (generally speaking) bigger but faster than lex. I think re2c is a great tool, and its developers are helpful and responsive. [•] perl was referred to as a unix swiss army chainsaw, because where lex is regexes + C, perl is regexes + scripting, and perl allows you to go from idea to huge mess much faster

chubot 3y ago
Hm as an re2c user, I always thought that Ragel vs. re2c was a push/pull issue (though re2c flag has a --storable-state flag to generate the push style -- I haven't used it) But now that I look at the example on the front page: http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/ action dgt { printf("DGT: %c\n", fc); } action dec { printf("DEC: .\n"); } number = ( [0-9]+ $dgt ( '.' @dec [0-9]+ $dgt )? I don't like how the dgt and dec actions are "inline" in the regex. This seems to be breaking the key abstraction of regexes, which in my mind is "NON-DETERMINISM for free". The better mechanism is submatch extraction, which re2c supports, and they even wrote a 2017 paper about - https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 , also see https://re2c.org/ https://re2c.org/ (I don't use re2c submatch extraction in https://www.oilshell.org https://www.oilshell.org, but I just used in a brand new program, and it works great. Very easy and natural.) So I think Ragel is doing something Perl-ish and recasting regular languages as imperative. But that can be asymptotically slower and breaks reasoning by sets, forcing you to reason by stepping through code.
- ulrikrasmussen 3y ago
  Check out Kleenex which also allows you to inline actions in the (regular) grammar, but which promises to only execute them when it has resolved all non-determinism for the input seen so far: https://kleenexlang.org/ https://kleenexlang.org/ The compiler translates regular grammars with embedded semantic actions to fast C code. Full disclosure: I am one of the authors.

by fanf2 3y ago

chubot 3y ago

Hm as an re2c user, I always thought that Ragel vs. re2c was a push/pull issue (though re2c flag has a --storable-state flag to generate the push style -- I haven't used it) But now that I look at the example on the front page: http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/ action dgt { printf("DGT: %c\n", fc); } action dec { printf("DEC: .\n"); } number = ( [0-9]+ $dgt ( '.' @dec [0-9]+ $dgt )? I don't like how the dgt and dec actions are "inline" in the regex. This seems to be breaking the key abstraction of regexes, which in my mind is "NON-DETERMINISM for free". The better mechanism is submatch extraction, which re2c supports, and they even wrote a 2017 paper about - https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 , also see https://re2c.org/ https://re2c.org/ (I don't use re2c submatch extraction in https://www.oilshell.org https://www.oilshell.org, but I just used in a brand new program, and it works great. Very easy and natural.) So I think Ragel is doing something Perl-ish and recasting regular languages as imperative. But that can be asymptotically slower and breaks reasoning by sets, forcing you to reason by stepping through code.

ulrikrasmussen 3y ago
Check out Kleenex which also allows you to inline actions in the (regular) grammar, but which promises to only execute them when it has resolved all non-determinism for the input seen so far: https://kleenexlang.org/ https://kleenexlang.org/ The compiler translates regular grammars with embedded semantic actions to fast C code. Full disclosure: I am one of the authors.