Search code examples
parsingcompiler-constructionlr-grammar

Discussion of LR(1) items: meaning?


What is the canonical LR(1) items ! I have read the Dragon Book, It confuses Me , (delta,gamma,toh,...)

Can Someone help me with this issue ?

What is this meaning in English? [A - > alpha.Bbeta , a]

Thanks a lot..


Solution

  • [A -> alpha . B beta , a] basically means "assuming rule A was being expanded, so far we have seen alpha. We then expect to see B beta. We also know that after A, we are going to see an a"

    So, in CLR(1), you have states consisting of some of these items. You then have many options:

    • If the look-ahead (gamma) is a member of first(B), and assuming you have a rule such as B->gamma C, then you can "shift" and go to a state containing [B -> gamma . C, beta]. As you can see, the . has moved passed gamma (because gamma is matched and the follow of B is beta because that's what came after B in the rule A -> alpha B beta.
    • If the look-ahead is a and assuming B beta could generate lambda (empty string) (here, assume beta is a nonterminal that can generate lambda). Then, you can "reduce" and go to a state that contains rules such as C -> something A . a something_else, follow]. In this case, you have decided that the alpha, B and beta on the stack can be grouped into one A.

    That was the simplest way I could explain this.