GLR parsing algorithm resources [closed]
We don’t allow questions seeking recommendati开发者_如何学JAVAons for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.
Closed last year.
Improve this questionI 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.
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.
Adrian Johnstone publishes a lot of work on advanced versions of GLR algorithms. His publications website will likely be an interesting resource.
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).
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.
精彩评论