Lookahead
|
|
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. But 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 at an earlier time. 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 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.