Thanks for the doc fixes, which are now fixed in the working version.
Your comment on Earley's may clear up what has been kind of a mystery to
me. Much of Marpa is taken from others, but one new feature of the parse
engine is definitely mine -- Marpa''s Earley items are created exactly in
sync ("on the fly", as you put it) with their occurrence in the parse.
(Previous Earley's implementations has muddled this a bit by working on
two Earley sets at once.) As you can see, it's clearly a useful feature,
and there's no efficiency hit.
The mystery for me had been why had nobody else done this before? Many
theoretical descriptions of Earley's are agnostic about the exact order of
operations, so they don't exclude this way of doing things, but clearly
nobody before me had seen it as an important property of the parse engine.
And the answer may have been that the mindset among parsing theorists that
"eager" or "on the fly" or "in sync" recording of what's going on is a
disadvantage. To my mind it was the difference between being accurate or
not. In this connection, it is worth noting that Joop Leo's modification
(that one that makes Earley fast for all deterministic grammars) in Joop's
1991 paper has a "lazy" implementation, one that I changed to an "eager"
one.
On Thu, Nov 20, 2014 at 4:05 PM, <[email protected]> wrote:
> Sorry for a late reply. I had to read your article (the POD for the
> progress reports <http://search.cpan.org/dist/Marpa-R2/pod/Progress.pod>,
> a very concise example) and revisit Earley algorithm. It seems that Earley
> parsers benefit from what at first sight seems a disadvantage (compared to
> deterministic context-free parsers): they have to construct Earley items on
> the fly, so they know exact positions in input string.
>
> I noticed some minor typos in your article:
>
> 1. in section "Progress report lines": text '*Here the "R12:2" indicates'*
> should be '*Here the "R11:2" indicates'* (and later on)
> 2. in section "Ok! Now to find the bug": rule 19 in example should
> actually be rule 18
> 3. in section "Multiple instances of dotted rules": x13 should be x12
> 4. in section "progress()": N+X+1 should be N-X+1
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "marpa parser" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"marpa parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
