hoodwink.d enhanced


When Rageling, Bring a Bird Beak #

by why in inspect

While bunking inside Ragel, I’m starting to see the handiness of its lookahead operator. The bird beak :>, which gives a high priority to the next token in the machine.

In SuperRedCloth, this rule here was a flimsy way of matching a bit of text in parens:

 title = ( '(' [^)]+ ')' );

It turns out I was able to cut down the generated grammer by something like fifty K by using this instead:

 title = ( '(' chars+ :> ')' ) ;

The beak is great for any rule that’s getting too greedy and concludes with an exact character. Be warned, it may increase the complexity of the machine depending on how ambiguous your other rules are.

If I could offer one other bit of advice: stay away from the question mark, if you can. It seems like anything which uses the empty token can be expensive.

said on 01 Feb 2007 at 17:54

Let’s also not forget the evil twin brother of our be-beaked friend, that sinister beaky bird, greedy as can be:


said on 01 Feb 2007 at 18:20

Adrian set me straight on one thing with optionality and priorities, by the way. For most things, expr1 :> expr2 expr3 works fine, but not if expr2 can be empty somehow.

Thing is, >: and friends can peel off an optional machine like teflon. You’ve really got to do expr1 :> (expr2? expr3) instead of expr1 :> expr2? expr3.

Once you add that question mark, you’ve got some transitions jumping straight from expr1 to expr3 and you need to make sure they get prioritized too.

I don’t know if that was related to the problems you were having, but it was the cause of my own state inflation issues with question.

said on 01 Feb 2007 at 22:20

I feel so… inadequate. I need to go learn ragel and state machines, be back in a few months.

said on 06 Feb 2007 at 00:28

I have no experience with lexical parsers/analysers, state machines or the like. I’m just a humble (intermediate) Rubyist. But, I would like to learn more about them (i.e. become able to wrap my head around parse.y). Can you recommend a good book to get me started on the right path?

said on 08 Feb 2007 at 12:12

Two books which helped me were the infamous Dragon Book and the O’Reilly Lex & Yacc book. Studies in Theory of Computation would also prove useful.

11 Jul 2010 at 20:41

* do fancy stuff in your comment.