Lookahead

The basic problem in parsing is choosing which production rule to use at any stage during a derivation. Any approach to parsing which involves backtracking will probably involve creating complex or inefficient algorithms in a conventional programming language. To make implementation easier, we introduce the notion of lookahead.

Lookahead

means attempting to analyse the possible production rules which can be applied, in order to pick the one most likely to derive the current symbol(s) on the input.

Suppose we are in the middle of a derivation, where we have:

• Current Sentential Form = $\alpha X \beta$
• Input string = $\alpha {\bf a} \gamma$

where:

-

$\alpha$ consists entirely of terminals, and corresponds to the piece of the input that has already been matched

-

$X$ is the leftmost non-terminal, $\beta$ is the rest of the sentential form

-

a is the next symbol on the input, $\gamma$ is the rest of the input

Our job then is to figure out which production rule will allow $X \beta$ can derive ${\bf a} \gamma$; thus we examine the r.h.s. of the production rules for $X$ as follows:

1. If the r.h.s. starts with a terminal symbol, then it must be of the form $X\; \rightarrow\; {\bf a} \delta$ for this rule to be of any use

2. If the r.h.s. starts with a non-terminal, ie. it looks like $X\; \rightarrow\; Y \delta$ say, then
   1. we must examine the production rules for $Y$ to see if any of these can derive an a.
   2. If $Y$ can derive $\varepsilon$, then we must see what $\delta$ can derive; ie. apply steps 1 and 2 to the production rules for $\delta$.

3. If we find that $X$ can derive $\varepsilon$, then we must check to see what the symbols following $X$ in the sentential form (ie. the first symbol in $\beta$) can derive.