Predictive Parsing
Table of Contents
Like recursive rescent parsing, but parser can “predict” which production to use next, by looking at the next few tokens (which requires restricted grammars) and no backtracking.
Predictive parsers accept \(LL(k)\) grammars, which means “left-to-right”, “left-most derivation” and “\(k\)-tokens to lookahead”. In \(LL(k)\), at each step, only one choice of production.
1. Left-Factoring the Grammars
The goal is to eliminate common prefixes of terminals, by extracting common prefixes to a production. e.g., the following production
\[ E \to T+E\ |\ T \]
is extracted to
\begin{split} E &\to T\, X \\ X &\to +E\, |\, \epsilon \end{split}1.1. Parsing table
The \(LL(1)\) parsing table has rows representing current non-terminal and columns representing next token, and the cell tells which production to use for parsing.
1.2. Stack
We may also need a stack to record frontier of the parse tree, including non-terminals that have yet to be expanded, terminals that have yet to matched against the input. Top of stack always tells the leftmost pending terminal or non-terminal.
And we reject on reaching error state, accept on end of input and empty stack.
Stack stack = [source_code];
TOKEN* next;
while (stack != empty) {
switch (stack) {
// For non-terminal X on top of stack,
// look up production
case <X, rest>:
if T(X, *next) == RHS[0,1,...,n] {
stack.pop(); // pop X
// Add RHS to top of stack, RHS[0] being the new top
stack <- <RHS[0,1,...,n], rest>;
} else throw error();
// For terminal t on top of stack,
// check if t matches the next input token
case <t, rest>:
if t == *next++ {
stack.pop(); // removes t
} else throw error();
}
}