Discussion of LR(1) items: meaning?

Question

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

Answer 1

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

Answer 2

IIRC, this is an "item", that is, the potential state of some sentential form parse.

What this means:

[A - > alpha.Bbeta , a]

is that when attempting to parse a (substring of the target language) which can be considerat as the nonterminal A, is the alpha has been seen, and (".") that Bbeta is expected next, and that if the elements of the nonterminal are seen, it is a valid A if the next token is a.

(I think you transcribed Bbeta wrong, it was probably beta in the book).