The pseudo-code on the Wikipedia page <http://en.wikipedia.org/wiki/Earley_parser#Pseudocode> is a good example. Note that SCANNER is adding Earley items to one set, while PREDICTOR and COMPLETER are still working on the other. Every pre-Marpa description I know of is either like this, or agnostic about the order. It makes a difference. In the traditional order, you usually start each Earley set before the previous one is complete, which would make things like the Ruby Slippers impossible.
Marpa does *not* as a rule use lookahead, although recent hacks would allow applications to add it. I follow some suggestions in the literature that lookahead is really about getting around the limitations of deterministic parsing, and not in general helpful for Earley parsing. -- jeffrey On Fri, Nov 21, 2014 at 2:10 PM, <[email protected]> wrote: > Hmm, when I said "on the fly" I meant "when consuming next input > character". And (to the extent of my knowledge) this is exactly how Earley > algorithm works: consume next input character, compute Earley item sets > (active, predicted, completed), repeat. There're many variations > (prediction/reduction lookahead, Aycock & Horspool trick for empty rules, > Leo's memoization, LR(0) items), but they don't break general order of > things. > > In Earley's algorithm most of the work must be done at runtime, as opposed > to e.g. LR-family where most of the work can be done ahead of time, and > thus no information about input string is encoded in the parser. > > What are the other implementations you mentioned? > > By the way, do you use lookahead in Marpa? > > -- > 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.
