#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
% Copyright 2011 Jeffrey Kegler
% This document is not part of the Marpa or Marpa::R2 source.
% Although it may be included with a Marpa distribution that
% is under an open source license, this document is
% not under that open source license.
% Jeffrey Kegler retains full rights.
\end_preamble
\use_default_options false
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\leftmargin 0.75in
\topmargin 0.75in
\rightmargin 0.75in
\bottommargin 0.75in
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author ""
\author ""
\end_header
\begin_body
\begin_layout Title
Notes to Aycock and Horspool 2002
\end_layout
\begin_layout Author
Jeffrey Kegler
\end_layout
\begin_layout Abstract
The 2002 paper by Aycock and Horspool, on a modification to Jay Earley's
parser, has been essential to my work on general BNF parser.
It is a difficult read for several reasons.
First, the paper is dense with important, but difficult, insights.
Second, a reader needs to be familiar with much previous work, including
in the now-neglected field of general BNF parsing.
Finally, there are a number of obscurities and some errors.
This paper is a series of notes and errate intended to address the last
problem.
\end_layout
\begin_layout Section
THIS IS A DRAFT
\end_layout
\begin_layout Standard
This paper is in late stages, but not yet finished.
It will contain many errors of the kind that the last drafts should remove.
\end_layout
\begin_layout Section
Introduction
\end_layout
\begin_layout Standard
The 2002 paper by Aycock and Horspool contains a number of obscurities and
some errors.
This paper is a series of notes and errata intended to address the last
problem.
Notes are not distinguished from errata in what follows.
The difference is a fine one, and it is not clear that it would serve the
reader to know where this author draws the line in this particular cloud.
\end_layout
\begin_layout Standard
The discerning reader will realize that an exercise in nit-picking like
this article is an especially sincere form of praise.
Only if this author truly thought Aycock and Horspool's 2002 paper rewarded
careful and repeated study, would he have collected these notes.
\end_layout
\begin_layout Section
Lemma 5.2 is Incomplete
\end_layout
\begin_layout Standard
The proof of Lemma 5.2 seems incomplete.
In case 4 on page 622, the last sentence begins
\begin_inset Quotes eld
\end_inset
If
\begin_inset Formula $I''$
\end_inset
\begin_inset Formula $\in S_{i}'$
\end_inset
\begin_inset Quotes erd
\end_inset
.
There is no justification given in the proof for the assertion that
\begin_inset Formula $I''$
\end_inset
\begin_inset Formula $\in S_{i}'$
\end_inset
.
A justification is necessary in order for Lemma 5.2 and Theorem 5.1 to go
through.
\end_layout
\begin_layout Standard
Case 4 can be shown, and the proof successfully completed, if all 4 cases
are wrapped in an induction.
This induction could be on completion depth, where the completion depth
of an item is defined as the number of completion steps (
\begin_inset Formula $E_{c}$
\end_inset
or
\begin_inset Formula $E'_{c}$
\end_inset
) within the current Earley set needed to add that item to the Earley set.
For example, a scanned item would have zero completion depth.
\end_layout
\begin_layout Standard
Lemma 5.3, case 4 relies on Lemma 5.2's case 4 for its justification, and
therefore has the same issue.
\end_layout
\begin_layout Section
Parent Pointers in Theorem 6.1
\end_layout
\begin_layout Standard
In the definitions leading up to Theorem 6.1 on page 624,
\begin_inset Formula $l\sqsubset S$
\end_inset
is stated to be equivalent to
\begin_inset Formula $[\, A\,→\,α•β,\: j]\,\in\, S_{i}$
\end_inset
, where
\begin_inset Formula $j$
\end_inset
is never defined.
Similarly,
\begin_inset Formula $L\sqsubset S_{i}$
\end_inset
is stated to be equivalent to
\begin_inset Formula $l\sqsubset S_{i}$
\end_inset
for all
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $l\in L$
\end_inset
.
\end_layout
\begin_layout Standard
LR(0) items never appear alone as member of Earley sets.
They are always in a duple with a parent pointer.
Many of the subsequent statements using the
\begin_inset Formula $l\sqsubset S$
\end_inset
and
\begin_inset Formula $L\sqsubset S_{i}$
\end_inset
notations are only true for the correct choice of parent pointer.
\end_layout
\begin_layout Standard
The problem can be resolved, and all statements involving the square subset
(
\begin_inset Formula $\sqsubset$
\end_inset
) notation become true, if it is revised to include the parent pointer.
This can be done by setting
\begin_inset Formula $l@j\sqsubset S$
\end_inset
to the equivalent of
\begin_inset Formula $[\, A\,→\,α•β,\: j]\,\in\, S_{i}$
\end_inset
, and
\begin_inset Formula $L@j\sqsubset S_{i}$
\end_inset
to be equivalent to
\begin_inset Formula $l@j\sqsubset S_{i}$
\end_inset
for all
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $l\in L$
\end_inset
.
The square subset notation is only used in column one on page 624.
If
\begin_inset Quotes eld
\end_inset
\begin_inset Formula $@j$
\end_inset
\begin_inset Quotes erd
\end_inset
is introduced before the square subset symbol everywhere it occurs, the
expectations for the parent pointer are made clear.
This change in notation leaves Theorem 6.1 true, and its proof correct.
\end_layout
\begin_layout Section
LR(0) State versus LR(0) Item
\end_layout
\begin_layout Standard
On page 624, the notation for LR(0) states and LR(0) items, while not incorrect,
is inconsistent is a way this is very likely to be confusing.
In column one, LR(0) states are always designated with a capital letter
(
\begin_inset Formula $L$
\end_inset
), while LR(0) items are always designated with lowercase letters (
\begin_inset Formula $l$
\end_inset
).
But in the second paragraph of column two on the same page, LR(0) states
are designated with the lowercase letter
\begin_inset Formula $l$
\end_inset
, previously reserved for LR(0) items.
\end_layout
\begin_layout Section
Prediction Items are included in LR(0) States
\end_layout
\begin_layout Standard
\noun on
Note
\noun default
: In the second paragraph of page 624, this sentence occurs:
\begin_inset Quotes eld
\end_inset
All items
\begin_inset Formula $[A→•α]$
\end_inset
must be in
\begin_inset Formula $l$
\end_inset
too
\begin_inset Quotes erd
\end_inset
.
As pointed out above, use of
\begin_inset Formula $L$
\end_inset
for the LR(0) state would be more consistent than the use of
\begin_inset Formula $l$
\end_inset
.
\end_layout
\begin_layout Standard
Also, I found it necessary to remind myself why the assertion is true: By
the definition of LR(0) states, whenever an item
\begin_inset Formula $[B→...•A...,k]$
\end_inset
is in an LR(0) state, all prediction items for
\begin_inset Formula $A$
\end_inset
must also be in that same LR(0) state.
\end_layout
\begin_layout Section
\family typewriter
foreach
\family default
over Worklists
\family typewriter
\end_layout
\begin_layout Standard
\noun on
Note
\noun default
: In the pseudocode on page 625 and on page 627 it's important to realize
that, in the
\family typewriter
foreach
\family default
loops over the contents of Earley sets, the Earley sets should be implemented
as
\begin_inset Quotes eld
\end_inset
worklists
\begin_inset Quotes erd
\end_inset
.
This is stated on page 625, but is easy to miss.
Implementation as worklists means the the loop must be able to add new
items as it proceeds, and that the iteration includes must include those
newly added items.
A naive implementation of a foreach loop would usually not provide worklist
semantics.
\end_layout
\end_body
\end_document