CODEWITHSUNDEEP
pythonparsingcompiler-constructionparser-generator
sap
sap

Reputation: 87

Creation Of Simple LR Parser Closure items

Suppose The G (augmented Grammar):

E' - > E
E  - > E+T|T
T  - > T*F|F
F -  > (E)|id

So in one of the levels of creation of the dfa , I had reached to this :(I6 in dragon book)

    I6                   I9
 ---------            ---------
|E -> E+.T|          | E->E+T. |   
|T -> .T*F|     T    | T->T.*F |
|T -> .F  |  ----->   ---------
|F -> .(E)|       
|F -> .id |
 ---------

I am wondering , why we don't add the T->.F and F->.(E) and F->.id to I9 ?

When We Reach T in input string , we should Add T->.F and Now we have reached to F and we should Add F->.(E) and F->.id.

Why I9 won't contains those ?

Upvotes: 1

Views: 592

Answers (1)

Dervall
Dervall

Reputation: 5744

It's because of the how the closure and goto algorithms works. Since when you create I9 by using GOTO(T) on I6 the dot moves one step to the right over any T and add those to a new set. This set is then the I9 GOTO set. Those that do not have a T to the right of the dot in I6 will not get added to the I9 GOTO set. After doing the GOTO you get set I9

E->E+T.
T->T.*F

When you apply closure on set I9 you expand every nonterminal on the right of the dot. On I9 you have no non-terminals to the right of the dot so there is nothing to expand.

I recently made a post about a very similar albeit a bit more complex problem that might be of help if you need additional clarification, Computing LR1 closure

Upvotes: 2

Related Questions