GLR parsing algorithm resources

Question

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.

Very cool project (Terse, not the parser generator), I’ll follow its progress with interest. — Konrad Rudolph, Mar 09 '10 at 13:49
Unfortunately I've been distracted by many things, so the project has stalled but... more work will commence on it soon promise!! — ljs, Nov 04 '10 at 17:54

score 17 · Accepted Answer · answered Jan 26 '10 at 00:43

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.

score 6 · Answer 2 · edited Sep 11 '14 at 15:15

6

Adrian Johnstone publishes a lot of work on advanced versions of GLR algorithms. His publications website will likely be an interesting resource.

edited Sep 11 '14 at 15:15

Kenneth Cochran

11,954
3
52
117

answered Nov 04 '10 at 14:30

Ira Baxter

93,541
22
172
341

Steve Hanov · Answer 3 · 2010-03-09T13:50:00.980

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).

score 2 · Answer 4 · answered Jan 25 '10 at 00:30

2

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.

answered Jan 25 '10 at 00:30

Anon.

58,739
8
81
86

Is it really as simple as that? Or are there specific alternative GLR algorithms out there? – ljs Jan 25 '10 at 00:32
1

That's basically it from my reading of the Bison manual (http://www.gnu.org/software/bison/manual/bison.html#GLR-Parsers) - it's actually pretty clear on how GLR parsers work. – Anon. Jan 25 '10 at 00:35
1

You might find it a bit more complicated than this. – Ira Baxter Jan 27 '10 at 05:29
1

yeah, having read one of the papers @Matthew Slattery recommended, I do think the algorithm is rather more involved than that :) – ljs Jan 27 '10 at 09:13

GLR parsing algorithm resources

4 Answers4