1Marpa::XS::Advanced::BiUbsleirogCroanpthryi(b3u)ted PerlMaDropcau:m:eXnSt:a:tAidovnanced::Bibliography(3)
2
3
4

NAME

6       Marpa::XS::Advanced::Bibliography - A Marpa Bibliography
7

HISTORY OF THE MARPA ALGORITHM

9       1970
10           Jay Earley invents the algorithm that now bears his name.
11
12       1991
13           Joop Leo describes a way to modify Earley's algorithm so that it
14           runs in O(n) time for all LR-regular grammars.  LR-regular is a
15           vast class of grammars, including all the LR(k) grammars, all
16           grammars parseable with recursive descent, and regular expressions.
17           LR-regular can safely be thought of as including all grammars in
18           practical use today, and then some.
19
20       2002
21           Aycock and Horspool describe a way to do LR(0) precomputation for
22           Earley's algorithm.  Their method makes Earley's faster in most
23           practical situations, but not all.  In particular, right-recursion
24           remains quadratic in the Aycock and Horspool algorithm.  Worst case
25           is no better than Earley's.  Leo is unaware of Aycock and
26           Horspool's work and Aycock and Horspool seem unaware of Leo.
27
28       2010
29           Marpa combines the Leo and Aycock-Horspool algorithms, in the
30           process making significant changes to both of them.  The result
31           preserves the best features of both.  Marpa also tackles the many
32           remaining implementation issues.
33

BIBLIOGRAPHY

35   Aho and Ullman 1972
36       The Theory of Parsing, Translation and Compiling, Volume I: Parsing by
37       Alfred Aho and Jeffrey Ullman (Prentice-Hall: Englewood Cliffs, New
38       Jersey, 1972).  I think this was the standard source for Earley's
39       algorithm for decades.  It certainly was my standard source.  The
40       account of Earley's algorithm is on pages 320-330.
41
42   Aycock and Horspool 2002
43       Marpa is based on ideas from John Aycock and R.  Nigel Horspool's
44       "Practical Earley Parsing", The Computer Journal, Vol. 45, No. 6, 2002,
45       pp. 620-630.  The idea of doing LR(0) precomputation for Earley's
46       general parsing algorithm, and Marpa's approach to handling nullable
47       symbols and rules, both came from this article.
48
49       The Aycock and Horspool paper summarizes Earley's very nicely and is
50       available on the web:
51       <http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf>.
52       Unlike "Earley 1970", Aycock and Horspool 2002 is not easy reading.  I
53       have been following this particular topic on and off for years and
54       nonetheless found this paper very heavy going.
55
56   Dominus 2005
57       Although my approach to parsing is not influenced by Mark Jason
58       Dominus's Higher Order Perl, Mark's treatment of parsing is an
59       excellent introduction to parsing, especially in a Perl context.  His
60       focus on just about every other technique except general BNF parsing is
61       pretty much standard, and will help a beginner understand how
62       unconventional Marpa's approach is.
63
64       Mark's book opened my eyes to many new ideas.  Both Mark's Perl and his
65       English are examples of good writing, and the book is dense with
66       insights.  Mark's discussion on memoization in Chapter 3 is the best
67       I've seen.  I wish I'd bought his book earlier in my coding.
68
69       Mark's book is available on-line.  You can download chapter-by-chapter
70       or the whole thing at once, and you can take your pick of his original
71       sources or PDF, at <http://hop.perl.plover.com/book/>.  A PDF of the
72       parsing chapter is at
73       <http://hop.perl.plover.com/book/pdf/08Parsing.pdf>.
74
75   Earley 1970
76       Of Jay Earley's papers on his general parsing algorithm, the most
77       readily available is "An efficient context-free parsing algorithm",
78       Communications of the Association for Computing Machinery, 13:2:94-102,
79       1970.
80
81       Ordinarily, I'd not bother pointing out 35-year old nits in a brilliant
82       and historically important article.  But more than a few people treat
83       this article as not just the first word in Earley parsing, but the last
84       as well.  Many implementations of Earley's algorithm come, directly and
85       unaltered, from his paper.  These implementers and their users need to
86       be aware of two issues.
87
88       First, the recognition engine itself, as described, has a serious bug.
89       There's an easy fix, but one that greatly slows down an algorithm whose
90       main problem, in its original form, was speed.  This issue is well laid
91       out by Aycock and Horspool in their article.
92
93       Second, according to Tomita there is a mistake in the parse tree
94       representation.  See page 153 of "Grune and Jacobs 1990", page 210 of
95       "Grune and Jacobs 2008", and the bibliography entry for Earley 1970 in
96       "Grune and Jacobs 2008".  In the printed edition of the 2008
97       bibliography, the entry is on page 578, and on the web
98       (<ftp://ftp.cs.vu.nl/pub/dick/PTAPG_2nd_Edition/CompleteList.pdf>),
99       it's on pp. 583-584.  My methods for producing parse results from
100       Earley sets do not come from Earley 1970, so I am taking Tomita's word
101       on this one.
102
103   Grune and Jacobs 1990
104       Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel Jacobs,
105       (Ellis Horwood Limited: Chichester, West Sussex, England, 1990).  This
106       book is available on the Web: <http://www.cs.vu.nl/~dick/PTAPG.html>
107
108   Grune and Jacobs 2008
109       Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel Jacobs,
110       2nd Edition.  (Springer: New York NY, 2008).  This is the most
111       authoritative and comprehensive introduction to parsing I know of.  In
112       theory it requires no mathematics, only a programming background, but
113       even so it is moderately difficult reading.
114
115       This is "Grune and Jacobs 1990" updated.  The bibliography for this
116       book is available in enlarged form on the web:
117       <ftp://ftp.cs.vu.nl/pub/dick/PTAPG_2nd_Edition/CompleteList.pdf>.
118
119   Leo 1991
120       Marpa's handling of right-recursion uses the ideas in Joop M.I.M. Leo's
121       "A General Context-Free Parsing Algorithm Running in Linear Time on
122       Every LR(k) Grammar Without Using Lookahead", Theoretical Computer
123       Science, Vol. 82, No. 1, 1991, pp 165-176.  This is a difficult paper.
124       Unfortunately, there is no copy of it on-line.
125
126   Wikipedia
127       Wikipedia's article on Backus-Naur form is
128       <http://en.wikipedia.org/wiki/Backus-Naur_form>.  It's a great place to
129       start if you don't know the basics of grammars and parsing.  As
130       Wikipedia points out, BNF might better be called Panini-Backus Form.
131       The grammarian Panini gave a precise description of Sanskirt more than
132       23 centuries earlier in India using a similar notation.
133
135         Copyright 2012 Jeffrey Kegler
136         This file is part of Marpa::XS.  Marpa::XS is free software: you can
137         redistribute it and/or modify it under the terms of the GNU Lesser
138         General Public License as published by the Free Software Foundation,
139         either version 3 of the License, or (at your option) any later version.
140
141         Marpa::XS is distributed in the hope that it will be useful,
142         but WITHOUT ANY WARRANTY; without even the implied warranty of
143         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
144         Lesser General Public License for more details.
145
146         You should have received a copy of the GNU Lesser
147         General Public License along with Marpa::XS.  If not, see
148         http://www.gnu.org/licenses/.
149

POD ERRORS

151       Hey! The above document had some coding errors, which are explained
152       below:
153
154       Around line 29:
155           Expected text after =item, not a number
156
157       Around line 40:
158           Expected text after =item, not a number
159
160       Around line 53:
161           Expected text after =item, not a number
162
163
164
165perl v5.32.0                      2020-07-2M8arpa::XS::Advanced::Bibliography(3)
Impressum