Discussion of LR(1) items: meaning?
-
26-04-2021 - |
سؤال
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..
المحلول
[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 asB->gamma C
, then you can "shift" and go to a state containing[B -> gamma . C, beta]
. As you can see, the.
has moved passedgamma
(becausegamma
is matched and the follow ofB
isbeta
because that's what came afterB
in the ruleA -> alpha B beta
. - If the look-ahead is
a
and assumingB beta
could generatelambda
(empty string) (here, assume beta is a nonterminal that can generatelambda
). Then, you can "reduce" and go to a state that contains rules such asC -> something A . a something_else, follow]
. In this case, you have decided that thealpha
,B
andbeta
on the stack can be grouped into oneA
.
That was the simplest way I could explain this.
نصائح أخرى
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).