1
$\begingroup$

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.

$\endgroup$

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.