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, 2012 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? Nov 29, 2012 at 20:43
  • Please consider that you've not even constructed the FOLLOW set before replying. Please do.
    – Onno
    Nov 29, 2012 at 21:09
  • 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. Nov 29, 2012 at 21:15
  • 1
    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, 2012 at 21:29

2 Answers 2


A 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. Look at the possible transitions from Follow to the next FIRST and consider that the next token is possibly the eof token because of the nature of LR parsing. (it considers the whole next token and its inner unfoldings. hence bottom-up parsing.)

  • 1
    Thank you. Small clarification for further readers -- FOLLOW set of the lhs non-terminal of production. Nov 30, 2012 at 6:43

Consider the expression

A - B - C

You would have E - B .- in your parse state. At that point, you have to reduce B to a T, then reduce E - T to E, leaving E .- C as the parse state. (Yes, that's sloppy.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.