Follow by Email

Thursday, July 15, 2010

Recursive-ascent parsers

Instead of representing your LR parsing tables as tables and user a driver to trace them over an input stream, you can simply implement each state as a function and use the machine stack as the push-down stack.

It turns out that this way is called "recursive-ascent" parsers. It is faster as the parsing is done without "interpretation" of the parsing table. It might also be clearer for the user that the plain parsing tables as the parsing actions/driving are encoded in the function.

Indeed it is more tedious to write such code from scratch, unlike recursive-descent parsers. That's why it is usually better to use a parser generator for that task.