/ 
Parse-Marpa-0.001_071
/ Parse::Marpa::BIBLIOGRAPHY

NAME

Parse::Marpa::BIBLIOGRAPHY - A Marpa Bibliography

Aho and Ullman 1972

The Theory of Parsing, Translation and Compiling, Volume I: Parsing by Alfred Aho and Jeffrey Ullman (Prentice-Hall: Englewood Cliffs, New Jersey, 1972). I think this was the standard source for Earley's algorithm for decades. It certainly was my standard source. The account of Earley's algorithm is on pages 320-330.

Aycock and Horspool 2002

Marpa is based on and derived from the parser described in John Aycock and R. Nigel Horspool's "Practical Earley Parsing", The Computer Journal, Vol. 45, No. 6, 2002, pp. 620-630. I take the idea that LR(0) precomputation can be done for Earley's general parsing algorithm, as well as the details of how to do it, from Aycock and Horspool.

The Aycock and Horspool paper is available on the web, unlike "Earley 1970", and summarizes Earley's very nicely. It is not, however, easy reading. I have been following this particular topic on and off for years. Nonetheless I found this paper very heavy going.

Earley 1970

Jay Earley's most accessible paper on his algorithm. is "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.

Ordinarily, I'd not bother picking at nits in a brilliant and historically important article that's over 35 years old. But not a few people cite this article as not just the first word in Earley parsing, but the last. They need to be aware of two issues.

First, the parse engine itself, as described, has a serious bug. There's an easy fix, but one that greatly slows down an algorithm whose main problem, in its original form, was speed. The whole matter is well laid out by Aycock and Horspool in their article.

Second, according to Tomita there is a mistake in the parse tree representation. See the bibliography entry for this article in "Grune and Jacobs 2008". In the printed edition, it's on page 578, and on the web (ftp://ftp.cs.vu.nl/pub/dick/PTAPG_2nd_Edition/CompleteList.pdf), it's on pp. 583-584. My methods for getting the parses out of Earley sets have come from Aho and Ullman, Aycock and Horspool, and my own device, so I am taking Tomita's word on this one.

Grune and Jacobs 1990

Parsing Techniques: A Practical Guide, by Dick Grune Ceriel Jacobs, (Ellis Horwood Limited: Chichester, West Sussex, England, 1990). This book is available on the Web

Grune and Jacobs 2008

Parsing Techniques: A Practical Guide, by Dick Grune Ceriel Jacobs, 2nd Edition. (Springer: New York NY, 2008).

This is "Grune and Jacobs 1990" updated. The bibliography for this book is available in enlarged form on the web: ftp://ftp.cs.vu.nl/pub/dick/PTAPG_2nd_Edition/CompleteList.pdf.

Wikipedia

Wikipedia's article on Backus-Naur form is http://en.wikipedia.org/wiki/Backus-Naur_form. It's a great place to start if you don't know the basics of grammars and parsing.

As Wikipedia points out, BNF might better be called Panini-Backus Form. The grammarian Panini gave a precise description of Sanskirt more than 23 centuries earlier in India using a similar notation.