GLR parsing algorithm resources

Question

Hi, I am writing a GLR parser generator and would like some advice on resources relating to this algorithm both on the internet and of the dead-tree variety (books for those unfamiliar with the geek-speak).

I know Bison can generate GLR parsers, and given it's under the GPL I can examine its code, however it'd be nice to have a full description of the algorithm.

So, does anybody know of any good resources out there which I can make use of? Thanks.

Answer 1

From what I'm aware, it functions the same as an LALR parser - except when it encounters an ambiguity.

When it does, it essentially divides into separate parses corresponding to the possible options at that point, and continues with them in tandem - when a parse fails (due to encountering an illegal element), it is simply dropped, because it must have been a wrong guess at an earlier ambiguity.

At the end, all but one parse should have died - and the surviving one is the "correct" parse of those ambiguous points.

Answer 2

Some good stuff I've come across before online:

• a paper about Elkhound, another open source GLR parser: Scott McPeak, George C. Necula. Elkhound: A Fast, Practical GLR Parser Generator. In Proceedings of Conference on Compiler Constructor (CC04), April 2004.

and for more detail:

• the UCB/CSSD-2-1214 technical report, which is an expanded version of the above paper;
• the paper referenced in the Bison documentation: Elizabeth Scott, Adrian Johnstone and Shamsa Sadaf Hussain. Tomita-Style Generalised LR Parsers. TR-00-12, Royal Holloway, University of London, Department of Computer Science, December 2000.

And I know of a third open source GLR parser: DParser.

Answer 3

The best description I have ever seen, with pictures illustrating each step of the algorithm, is contained in this book:

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

For pseudocode, go to the source: Generalized LR Parsing by Tomita, page 70 or so. Farshi's paper contains a compact description.

http://books.google.ca/books?id=PvZiZiVqwHcC&lpg=PP1&dq=generalized%20lr%20parsing&pg=PA70#v=onepage&q=&f=false

It's one of the techniques I tried for qb.js (qbasic in javascript).