Lambda the Ultimate

Owl is a parser generator which targets the class of visibly pushdown languages. It is:

• Efficient - Owl can parse any syntactically valid grammar in linear time.
• Understandable - like regular expressions, its parsing model (and error messages) can be understood without talking about parser states, backtracking, lookahead, or any other implementation details.
• Easy to use - using Owl's interpreter mode, you can design, test, and debug your grammar without writing any code. An Owl grammar compiles to a single C header file which provides a straightforward parse tree API.

The restriction to visibly pushdown languages imposes restrictions on recursion. Rules can only refer to later rules, not earlier ones, and all recursion must be guarded inside guard brackets.

[ begin ... end ]

The symbols just inside the brackets are the begin and end tokens of the guard bracket. Begin and end tokens can't appear anywhere else in the grammar except as other begin and end tokens. This is what guarantees the language is visibly pushdown: all recursion is explicitly delineated by special symbols.

https://github.com/ianh/owl

Note: I am not the Owl author, but I found it to be a useful tool for my own projects. I play around with toy programming languages as a hobby and I am not well-versed on automata theory.

I am posting here because I would be interested to know what your thoughts are about the class of visibly pushdown languages, specifically the constraints it imposes on recursion, how that compares to recursive descent, and any pointers to variations or similar approaches that you know of.