Re: Closure and Goto

> thomas.strinnhed@swipnet.se


>Theese functions are Closure and Goto for determining
>sets-of-items
>I've got some difficulties understanding them, and would much
>appreciate some explanation along with some examples




Closure of a set of items I in a grammar G is constructed by the
following two rules:


1. Every item in I is added to closure(I)


2. If there's an item
          A -> a.Bb in closure(I) and
          B -> g is a production in the grammar
              (where a, b, and g are strings of grammar symbols)
      then
            the item B -> .g is added to closure(I)


      If A -> a.Bb is in closure(I), it indicates that we've seen "a"
      and we expect to see some substring derivable by "Bb"


      Since B is a non-terminal, it also means we expect to see some
      substring derivable by "gb"
      That's why we add B -> .g to closure(I)




For example,


Consider the following augmented grammar:
(same as in the Dragon Book)


1. E' -> E
2. E -> E+T | T
3. T -> T*F | F
4. F -> (E) | id


[The augmented grammar is because the input is acceptable only
when the parser is about to reduce by E' -> E.]


If I is a set of one item containing { [E' -> .E] } then
closure(I) contains:


      {
          [E' -> .E], // by rule 1


          [E -> .E+T], // by rule 2 on the previous item (use production 2 of the grammar)
          [E -> .T],


          [T -> .T*F], // by rule 2 on the previous item (use production 3)
          [T -> .F],


          [F -> .(E)], // by rule 2 on the previous item (use production 4)
          [F -> .id]
      }






Goto(I, X)
where I is a set of items and X is a grammar symbol is:
the closure of all items
[A -> aX.b] such that
[A -> a.Xb] is in I


(where "a" & "b" are strings of grammar symbols)




For example,
if I is the set of two items
          {
              [E' -> E.],
              [E -> E .+ T]
          }
then goto(I, +) is, by definition ,


    closure of { [E -> E + .T] }


that is we examine all items in I which have a "+" immediately to
the right of a "." (in our example, the second item),
move the dot over the "+" to get E -> E + .T
and find its closure


closure of { [E -> E + .T] } is
        {
            [E -> E + .T], // by rule 1 to find closure


            [T -> .T*F], // by rule 2 on the previous item (production 3)
            [T -> .F],


            [F -> .(E)], // by rule 2 on the previous item (production 4)
            [F -> .id]
        }








The complete set of LR(0) items for the grammar is given below:
(reproduced from the Dragon book & paraphrased)


I0 = closure({ [E' -> .E] }) // since E' is the start symbol of
                                                          // the augmented grammar
      = {
              E' -> .E
              E -> .E + T
              E -> .T
              T -> .T * F
              T -> .F
              F -> .(E)
              F -> .id
            }


I1 = goto(I0, E)
      = {
              E' -> E. // from I0; note, however, that closure of these
              E -> E. + T // two items don't yield anything
          }


I2 = goto(I0, T)
      = {
              E -> T. // from I0; their closure yields nothing
              T -> T. * F
          }




I3 = goto(I0, F)
      = {
              T -> F. // closure yields nothing
          }


I4 = goto(I0, ')')
      = {
              F -> (.E) // from I0


              E -> .E + T // closure of the previous item
              E -> .T
              T -> .T * F
              T -> .F
              F -> .(E)
              F -> .id
          }


I5 = goto(I0, id)
      = {
              F -> id.
          }


// we ran out of grammar symbols in I0
// note that we cannot have goto(I0, *) because there's no item
// in I0 which has "*" immediately to the right of a "."




I6 = goto(I1, +)
      = {
              E -> E +. T // from I1


              T -> .T * F // closure of the previous item
              T -> .F
              F -> .(E)
              F -> .id
          }


// we cannot have goto(I1, E) and goto(I1, T)


I7 = goto(I2, *)
      = {
              T -> T *. F // from I2


              F -> .(E) // closure of the previous item
              F -> .id
          }


// we cannot have goto(I2, T) and goto(I2, F)
// neither can we have goto(I3, F)




I8 = goto(I4, E)
      = {
              F -> (E.)
              E -> E. + T // their closure yields nothing
          }


// note that goto(I4, T) = I2 and goto(I4, F) = I3
// we cannot have any more gotos in I4 and I5


I9 = goto(I6, T)
      = {
              E -> E + T.
              T -> T. * F // their closure yields nothing
          }


// no more gotos in I6


I10 = goto(I7, F)
        = {
                T -> T * F.
            }


// no more gotos in I7


I11 = goto(I8, ')')
        = {
                F -> (E).
            }


// no more gotos in I9, I10 and I11

Return to the comp.compilers page.
Search the comp.compilers archives again.