Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
Please consider that you've not even constructed the FOLLOW set before replying. Please do. –  Onno Nov 29 '12 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. –  greenoldman Nov 29 '12 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 '12 at 21:29

2 Answers 2

up vote 2 down vote accepted

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.)

share|improve this answer
1  
Thank you. Small clarification for further readers -- FOLLOW set of the lhs non-terminal of production. –  greenoldman Nov 30 '12 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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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