Search code examples
parsingcontext-free-grammarlr1

Which productions are considered in LR(1) lookahead?

I'm currently looking at two closure calculation examples using the tool at http://jsmachines.sourceforge.net/machines/lr1.html

Example 1

S -> A c
A -> b B
B -> A b

Here, in the initial state ends up with a closure of:

[S -> .A c, $]; [A -> .b B, c]}

Example 2

S -> A B
A -> a
B -> b
B -> ''

The calculated first step closure is:

{[S -> .A B, $]; [A -> .a, b/$]}

In example 1, why is the follow of b from rule 3 not included in the lookahead? In case 2, we follow B to figure out that $ is part of the lookahead so is there some special reason to not consider all rules in case 1?

Solution

  • When doing a closure with ". A α" we use FIRST(α) as the lookahead, and only include the containing (parent) lookahead if ε ∈ FIRST(α). In example 1, ε ∉ FIRST(c), so the lookahead is just c. In example 2, ε ∈ FIRST(B), so we add the containing lookahead ($ in this case) to the lookahead.

    FOLLOW is never relevant.