Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The method is described in Dragon Book, however I read about it in ""Parsing Techniques" by D.Grune and C.J.H.Jacobs".

I start from my understanding of building channels for NFA:

  1. channels are built once, they are like water channels with current
  2. you "drop" lookahead symbols in right places (sources) of the channel, and they propagate with "current"
  3. when symbol propagates, there are no barriers (the only sufficient things for propagation are presence of channel and direction/current); i.e. lookahead cannot just die out of the blue

Is that right?

If I am correct, then eof lookahead should be present in all states, because the source of it is the start production, and all other production states are reachable from start state.

How the DFA is made out of this NFA is not perfectly clear for me -- the authors of the mentioned book write about preserving channels, but I see no purpose, if you propagated lookaheads. If the channels have to be preserved, are they cut off from the source if the DFA state does not include source NFA state? I assume no -- the channels still runs between DFA states, not only within given DFA state.

In the effect eof should still be present in all items in all states. But when you take a look at DFA presented in book (pdf is from errata):

DFA for LALR (fig. 9.34 in the book, p.301)

you will see there are items without eof in lookahead.

The grammar for this DFA is:

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

So how it was computed, when eof was dropped, and on what condition?


It is textual pdf, so two interesting states (in DFA; # is eof):

State 1:

S--- >•E[#]
E--- >•E-T[#-]
E--- >•T[#-]
T--- >•n[#-]
T--- >•(E)[#-]

State 6:

T--- >(•E)[#-)]
E--- >•E-T[-)]
E--- >•T[-)]
T--- >•n[-)]
T--- >•(E)[-)]

Arc from 1 to 6 is labeled (.

share|improve this question
Wrong SE site. Theoretical CS? – Ramon Snir Nov 30 '12 at 18:44
@RamonSnir, I don't know, there are too many SE sites with very similar target. Anyway, for TCS -- LALR parser is a subject for teaching students, so it is not that advanced for TCS (see FAQ). – greenoldman Nov 30 '12 at 21:32
I think is probably the site where you're most likely to get a good answer for these kinds of questions. – Alex ten Brink Dec 1 '12 at 10:36
up vote 0 down vote accepted

I think I got it.

There are barriers. When you think about NFA (and DFA, but then think about items, not states), there closure transitions and shift transitions, right?

For example -- when you have T -> . ( E ) (state 1, last item in the pdf file) to T -> ( . E ) (state 6, first item) this is shift transition, and all lookahead symbols (# and -) are flowing happily.

However, initial closure transition kills all lookaheads (x) -- you have to compute them from scratch. Continuing closure transition does not kill lookaheads.

Take a look at state 6 -- all except the first item, are effects of closure transitions. The second gets ) from the top one, and - from itself. The third no matter which transition you consider gets ) and -. And for the last 2 ones, continuing closure transition gives also ) and -.

(x) There is an exception -- if the pointer sits next to last symbol in production, you copy the lookaheads. Example A -> B . C, when you create closure for C you copy the lookaheads from A, because C in such case has to end with the same stuff as A.

To sum up -- you have shift transition, copy all lookaheads.

You have closure:

  • as from X -> A B C D . E, in such case copy lookaheads as for shift transition

  • as from X -> A . B C D E, compute FIRST for C D E (mind you, not just C) and use it (copy) as lookaheads for B closure, if entire chain can be empty (C D E) copy lookaheads as for shift too

share|improve this answer

Your Answer


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.