I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them?
Any help is appreciated.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No, you still consume one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol.
Here's a simple example: the grammar of context-free grammars. Informally, a CFG is a sequence of productions, where each production consists of a non-terminal, the derives symbol ($\to$) and a replacement list, which is a possibly-empty sequence of non-terminal and terminal. Formally, we have
$$\begin{align} Grammar &\to \lambda \\ Grammar &\to Nonterminal \ Arrow \ Derivation \ Grammar \\ Derivation &\to \lambda \\ Derivation &\to Nonterminal \ Derivation \\ Derivation &\to Terminal \ Derivation \\ \end{align}$$
That's not an LL(1) grammar, because when $Derivation$ is on top of the stack and the next input symbol is $Nonterminal$, then there are two possible actions:
Predict $Derivation \to \lambda$, which means popping the $Derivation$ off the stack without consuming the input token.
Predict $Derivation \to Nonterminal Derivation$, which means popping the $Derivation$ off the stack and replacing it with $Derivation \ Nonterminal$; then matching the $Nonterminal$ from the input and the $Nonterminal$ on top of the stack, discarding both.
How can the parser decide which action to take? If it can only see one input symbol, then it has no way to decide. But if it can see 2 input symbols, then it can choose action 1 if the second next input symbol is $Arrow$ and action 2 in any other case.
So we can conclude that our grammar for grammars is LL(2).
