LR(1) - Items, Look Ahead

Question

I am having difficulties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets? Say for an example that I have the following grammar: ``` S -> AB A -> aAb | b B -> d ``` Then the first state will look like this: ``` S -> .AB , {look ahead} A -> .aAb, {look ahead} A -> .b, {look ahead} ``` I know what look aheads are, but I don't know how to compute them. I have googled for answers but couldn't find a webpage which explains this in a simple manner. Thanks in advance

Accepted Answer

I'll write down the first two states for your example:

```
S -> AB
A -> aAb | b
B -> d
```

State 0:

```
(1) S -> .AB, {$}   # Once we have done this rule it's EOF ($) 
(2) A -> .aAb, {d}  # from (1), after A there has to be a B whose first symbol has to be d
(3) A -> .b, {d}    # as above
```

State 1:

```
(4) A -> a.Ab, {d}   # from (2)
(5) A -> .aAb, {b}   # from (4), the symbol after the A has to be b
(6) A -> .b, {b}     # from (4), as above
(7) A -> b., {d}     # from (3)
(8) S -> A.B, {$}    # from (1) and (7)
(9) B -> .B, {$}     # from (8)
```

and so on, keep following the same shift/reduce/closure as you would for an LR(0) parser, but keep track of (lookahead for) the next symbol... (State 2+ are longer, I don't recommend working them out by hand!)

I suggest looking into Udacity's Programming Languages course to learn more about lexing and parsing. There is also an example on wikipedia and a related SO question.

LR(1) - Items, Look Ahead

Solution

Problem