Parsing - Lookahead

Lookahead

Lookahead establishes the maximum incoming tokens that a parser can use 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 semantic rule. It is possible to rewrite the grammar to incorporate this into the syntax. However, not all such rules can be translated into syntax.

Simple non-lookahead parser actions

1. Reduces 1 to expression E on input 1 based on rule3.
2. Shift + onto stack on input 1 in anticipation of rule1.
3. Reduce stack element 2 to Expression E based on rule3.
4. Reduce stack items E+ and new input E to E based on rule1.
5. Shift * onto stack on input * in anticipation of rule2.
6. Shift 3 onto stack on input 3 in anticipation of rule3.
7. Reduce 3 to Expression E on input 3 based on rule3.
8. 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

1. Shift 1 onto stack on input 1 in anticipation of rule3. It does not reduce immediately.
2. 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.
3. Shift + onto stack on input + in anticipation of rule1.
4. Shift 2 onto stack on input 2 in anticipation of rule3.
5. Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.
6. 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.
7. Shift 3 onto stack on input 3 in anticipation of rule3.
8. Reduce stack item 3 to Expression after seeing end of input based on rule3.
9. Reduce stack items E * E to E based on rule2.
10. 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.