# How to get lookahead symbol when constructing LR(1) NFA for parser?

I am reading an explanation (awesome "Parsing Techniques" by D.Grune and C.J.H.Jacobs; p.292 in the 2nd edition) about how to construct an LR(1) parser, and I am at the stage of building the initial NFA. What I don't understand is how to get/compute a lookahead symbol.

Here is the example from the book, the grammar:

``````S -> E
E -> E - T
E -> T
T -> ( E )
T -> n
``````

`n` is terminal. The "weird" transitions for me are is the sequence:

``````1)   S -> . E        eof
2)   E -> . E - T    eof
3)   E -> . E - T    -
4)   E -> E . - T    -
5)   E -> E - . T    -
``````

(Note: In the above table, the state numbers are in front and the lookahead symbol is at the end.)

What puzzles me is that transition from (4) to (5) means reading `-` token, right? So how is it that `-` is still a lookahead symbol and even more important why is it that `eof` is no longer a lookahead symbol? After all in an input such as `n - n eof` there is only one `-` symbol.

My naive thinking tells me (5) should be written as:

``````5)   E -> E - . T    - eof
``````

And another thing -- `n` is terminal. Why it is not used at all as a lookahead symbol? I mean -- we expect to see `-` or `(`, it is ok, but lack of `n` means we are sure it won't appear in input?

Update: after more reading I am only more confused ;-) I.e. what is really a lookahead? Because I see such state as (p.292, 2nd column, 2nd row):

``````E -> E . - T      eof
``````

Lookahead says `eof` but the incoming input says `-`. Isn't it a contradiction? And it is not only in this book.

-
I'm not going to give you the answer outright, this is clearly a homework question which needs to be understood by you using your own logic in order to be able to really understand the topic in-depth. Construct the FIRST and FOLLOW sets and you'll know why the - sign is in the look-ahead. You should be able to find the answer you're looking for after you've done this. Otherwise, more reading is in order. – Onno Nov 29 '12 at 20:35
`-` is not in the FIRST of `T`. In state (5) the only valid tokens are `(` and `n`. Since you "clearly know" this is a homework, by pure curiosity -- what was the question? – greenoldman Nov 29 '12 at 20:43
Fortune teller in action again, and wrong again. Please stop that, it is actually rude. Now, on topic -- thank you for that hint (the one you deleted). I think you are wrong with FIRST, but now when I look at the examples it would make sense to think of lookahead as symbol from FOLLOW set of lhs of production. This is why `n` is omitted (for example). I have to digest it more deeply. – greenoldman Nov 29 '12 at 21:15
I retraced the statement because I thought it might have been worded a bit offensively, and my first version contained an error as well. For clarity for other readers: the lookahead token is a character (or sequence of characters, it's a token after all) defined as either one of the terminals or those tokens which are in the FOLLOW set. – Onno Nov 29 '12 at 21:29