Lookahead

Lookahead is a tool in algorithms for looking ahead a few more input items before making a cost effective decision at one stage of the algorithm.

Lookahead vs. Lazy evaluation

This is in contrast to another technique called lazy evaluation that delays the computation until it is really needed. Both techniques are used for economical usage of space or time. Lookahead makes the right decision and so avoids backtracking from undesirable stages at later stages of algorithm and so saves space, at the cost of a slight increase of time due to the overhead of extra lookups. Lazy evaluation normally skips the unexplored algorithmic paths and thus saves both the time and space in general. Some applications of lazy evaluations are demand paging in operating systems and lazy parse tables in compilers.

In search space exploration, both the techniques are used. When there are already promising paths in the algorithm to evaluate, lazy evaluation is used and to be explored paths will be saved in the queue or stack. When there are no promising paths to evaluate and to check whether the new path can be a more promising path in leading to solution, lookahead is used.

Compilers also use both the techniques. They will be lazy in generating parse tables from given rules, but they lookahead in parsing given input.

Applications

Lookahead in search problems

In artificial intelligence, lookahead is an important component of combinatorial search which specifies, roughly, how deeply the graph representing the problem is explored. The need for a specific limit on lookahead comes from the large problem graphs in many applications, such as computer chess and computer Go. A naive breadth-first search of these graphs would quickly consume all the memory of any modern computer. By setting a specific lookahead limit, the algorithm's time can be carefully controlled; its time increases exponentially as the lookahead limit increases.

More sophisticated search techniques such as alpha-beta pruning are able to eliminate entire subtrees of the search tree from consideration. When these techniques are used, lookahead is not a precisely defined quantity, but instead either the maximum depth searched or some type of average.

Lookahead in parsing

Lookahead is also an important concept in parsers in compilers which establishes the maximum number of incoming input tokens the parser can look at to decide which rule it should use.

Lookahead is especially relevant to LL, LR, and LALR parsers, where it is often explicitly indicated by affixing the lookahead to the algorithm name in parentheses, such as LALR(1).

Most programming languages, the primary target of parsers, are carefully defined in such a way that a parser with limited lookahead, typically one, can parse them, because parsers with limited lookahead are often more efficient. One important change to this trend came in 1990 when Terence Parr created ANTLR for his Ph.D. thesis, a parser generator for efficient LL("k") parsers, where "k" is any fixed value.

Parsers typically have only a few actions after seeing each token. They are shift (add this token to the stack for later reduction), reduce (pop tokens from the stack and form a syntactic construct), end, error (no known rule applies) or conflict (does not know whether to shift or reduce).

Lookahead has two advantages.
* It helps the parser take the correct action in case of conflicts. For example, parsing the if statement in the case of an else clause.
* It eliminates many duplicate states and eases the burden of an extra stack. A C language non-lookahead parser will have around 10,000 states. A lookahead parser will have around 300 states.

Example: Parsing the Expression 1 + 2 * 3

Set of expression parsing rules (called grammar) is as follows,
Rule1: E → E + E Expression is the sum of two expressions. Rule2: E → E * E Expression is the product of two expressions. Rule3: E → number Expression is a simple number Rule4: + has less precedence than *

Most programming languages (except for a few such as APL and Smalltalk) and algebraic formulas give higher precedence to multiplication than addition, in which case the correct interpretation of the example above is (1 + (2*3)).Note that Rule4 above is a semantical rule. It is possible to rewrite the grammar to incorporate this into the syntax. However, not all semantic rules can be translated into syntax.

Simple non-lookahead parser actions
# Reduces 1 to expression E on input 1 based on rule3.
# Shift + onto stack on input 1 in anticipation of rule1.
# Reduce stack element 2 to Expression E based on rule3.
# Reduce stack items E+ and new input E to E based on rule1.
# Shift * onto stack on input * in anticipation of rule2.
# Shift 3 onto stack on input 3 in anticipation of rule3.
# Reduce 3 to Expression E on input 3 based on rule3.
# Reduce stack items E* and new input E to E based on rule2.

The parse tree and resulting code from it is not correct according to language semantics.

To correctly parse without lookahead, there are three solutions.
* The user has to enclose expressions within parentheses. This often is not a viable solution.
* The parser needs to have more logic to backtrack and retry whenever a rule is violated or not complete. The similar method is followed in LL parsers.
* Alternatively, the parser or grammar needs to have extra logic to delay reduction and reduce only when it is absolutely sure which rule to reduce first. This method is used in LR parsers. This correctly parses the expression but with many more states and increased stack depth.

Lookahead parser actions
# Shift 1 onto stack on input 1 in anticipation of rule3. It does not reduce immediately.
# Reduce stack item 1 to simple Expression on input + based on rule3. The lookahead is +, so we are on path to E +, so we can reduce the stack to E.
# Shift + onto stack on input + in anticipation of rule1.
# Shift 2 onto stack on input 2 in anticipation of rule3.
# Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.
# Now stack has E + E and still the input is *. It has two choices now, either to shift based on rule2 or reduction based on rule1. Since * has more precedence than + based on rule4, so shift * onto stack in anticipation of rule2.
# Shift 3 onto stack on input 3 in anticipation of rule3.
# Reduce stack item 3 to Expression after seeing end of input based on rule3.
# Reduce stack items E * E to E based on rule2.
# Reduce stack items E + E to E based on rule1.The parse tree generated is correct and simply more efficient than non-lookahead parsers. This is the strategy followed in LALR parsers.

See also

* Regular Expression