Search code examples
parsingcompiler-constructionlr-grammar

Look ahead in LR(1) parsing

I have some problem to understand how to make look ahead in LR(1). I've already found this question about the same problem LR(1) - Items, Look Ahead but this don't help me.

S'->.S,$
S->.L=R,$
S->.R,$
L->.*R,=/$
L->.id,=/$
R->.L,$

I understand the lookahead of S' and S production, but not the L and R one... can you help me please? thank you in advance.

Solution

  • For a really nice treatment of LR/SLR/LALR parsing, I'd recommend The Dragon Book.

    Constructing the LR(1) sets of items is in Section 4.7.2, the procedure CLOSURE.

    For your example, consider performing "expanding" (during CLOSURE) the LR(1) item S->.L=R,$: the result are the LR(1) items

    L->.*R,=
L->.id,=

    The lookaheads are each terminal symbol in FIRST("=R$"), i.e. everything that follows the non-terminal in front of the dot, plus the lookahead, The new items' lookaheads are just = at this point.

    Next, consider "expansion" of S->.R,$. Again, the lookaheads in the new items are all the terminal symbols in FIRST("$"): nothing follows the R, hence only the lookahead. This produces the item

    R ->.L,$

    Further expanding this item, using as lookaheads all the non-terminals in FIRST("$") gives us

    L->.*R,$
L->.id,$

    So, you can see that L->.*R,=/$ in you original example is just a shorthand notation for the two individual items, L->.*R,= and L->.*R,$, each of them obtained along separate "expansion" chains.