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

Haemophiliac

Answer 1

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.

Faso