Re:Earley Parsing Explained
by kazinator on Tuesday September 15, 2015 @08:36PM
(#10224002)
I'm looking at this, and the Earley items with the "fat dot" look a heck of a lot like LR(0) kernel items in LALR(1) parser generation.
Then it hits me: it looks like Earley parsing is to LALR(1) (vaguely ) like NFA simulation is to DFA table.
If we look at it at a very high level: Earley is making these items dynamically while scanning the input, and grouping them into sets representing states. Whereas a LALR parser generator will generate the items and group them into subsets statically, while processing the grammar, generating a push-down table driven by lookahead which is then applied to the input.
Analogously, NFA computes sets of states dynamically according to the input, by performing closures on the NFA graph, whereas DFA does it statically in the absence of input.
Then it hits me: it looks like Earley parsing is to LALR(1) (vaguely ) like NFA simulation is to DFA table.
If we look at it at a very high level: Earley is making these items dynamically while scanning the input, and grouping them into sets representing states. Whereas a LALR parser generator will generate the items and group them into subsets statically, while processing the grammar, generating a push-down table driven by lookahead which is then applied to the input.
Analogously, NFA computes sets of states dynamically according to the input, by performing closures on the NFA graph, whereas DFA does it statically in the absence of input.