If a standard Earley parser (with proper handling of nullable non-terminals, see Section 4 of "Practical Earley Parsing" by Aycock and Horspool) is modified with LL(1)-style lookahead, does it then parse all LL(1) grammars in linear time?

To be precise with "LL(1)-style lookahead", I reproduce the $\text{Predictor}$ and $\text{Completer}$ steps of the Earley algorithm, with modifications in bold:

$\text{Predictor}$. If $[A \to \ldots\bullet B\dots, j]$ is in $S_i$, add $[B \to \bullet \alpha, i]$ to $S_i$ for all rules $B \to \alpha$ where $x_{i+1} \in \text{FIRST}(\alpha)$ or $\alpha \Rightarrow^* \lambda$.

$\text{Completer}$. If $[A \to \ldots \bullet, j]$ is in $S_i$, add $[B \to \alpha A \bullet \beta, k]$ to $S_i$ for all items $[B\to \alpha \bullet A \beta, k]$ in $S_j$ where $x_{i+1} \in \text{FIRST}(\beta)$ or $\beta \Rightarrow^* \lambda$.

This is also assuming (for the purposes of this lookahead) that the input is augmented with an EOF symbol $\$$. Note that all $\text{FIRST}$ invocations occur on suffixes of productions, and can be precomputed and stored in a table indexed by production number and dot location.

I am aware of the work by Joop Leo that augments an Earley parser to parse all LR(k) grammars in linear time, but I am curious if just the above is enough for LL(1).

As an example grammar where the above reduces complexity, the grammar $S\to a S \mid \lambda$ normally has an quadratic number of Earley items which goes to linear with the above optimization.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.