parsingcompiler-constructionlalr

can't understand this LALR(1) parsing algorithm in aho & Ullman book


The algorithm for computing the lookaheads](https://i.sstatic.net/T3Yzb.jpg)](https://i.sstatic.net/T3Yzb.jpg)

The algorithm says to compute $CLOSURE( { [A \rightarrow \alpha . \beta , # ]}) $ the worked out example

In the worked out example above, When they compute closure of ${[ S^\prime \rightarrow .S ,#]} $ how come the item $[ L \rightarrow . * R, =/# ] $ has the dummy symbol $#$ as its lookahead when $ FIRST(=R#) = { = } $ contains only the $=$ terminal symbol?

The closure algorithm provided in the book says the lookaheads of generated item will be FIRST($\alpha) where alpha is the string of grammar symbols following the non terminal from which the item is generated, but in the given example the string contains the terminal $=$ as the first symbol so the lookahead should just be $ = $ but the example shows the lookahead also containing $ # $ in addition to $ = $.


Solution

  • You are correct that S -> . L = R, # contributes only = to the lookahead set for L -> . * R.

    But R -> . L, # also has a dot before the L, so also leads to the L -> . * R item, and it contributes # to that item's lookahead set.