Note:  You might want to listen to Justin Hart's talk on DirectX in EPS 103 at 5:00 today (Thursday, February 26).  Justin is one of our students and has constructed a new visual virtual machine for our compiler class, among other things.

Objectives

• To have you begin constructing the LL(1) tables for mPascal.
• To give you experience with the individual algorithms underlying LL(1) table construction.

Preparing for Lab

To Do

• Bring the mPascal context free grammar on the resources page up in your browser.
• Print the grammar.
• On the printout, number all of the rules in the grammr.
• Look at the section of the definition that defines the different kinds of statements.
• Locate the definition of AssignmentStatement

• Put your team names and group number at the top left of the page.
• Identify all of the nonterminals in all of the rules you will need to use starting with the rules for AssignmentStatement in order to do this part of the LL(1) table
• Similarly, identify all of the tokens for this part of the table.
• Build an empty LL(1) table based on your results.  This should be done as usual, with the nonterminals labeling the rows and the token labeling the columns.

 
                                           Pass 1        Pass 2              . . .                Pass M
First(NonTerminal 1)
First(NonTerminal 2)
    . . .
First(NonTerminal N)

• Fill in this table by showing which lookahead symbols get added to First(NonTerminal I) on each pass through the algorithm from the book until the algorithm terminates.
 
 

let e stand for the empty string

loop for each nonterminal A
  set First(A) = {} -- set First(A) to the empty set.
end loop            -- note that the empty set does not contain anything, 
                    -- not even e
loop for each terminal a
  set First(a) = {a}
end loop

loop for each rule in the grammar
  if the rule is A --> e then
    set First(A) = {e}
  end if
end loop

loop while this is the first time through the loop, or any additions have 
           been made to set First(A) for any A during the previous pass 
           through the loop

  loop through each non-e rule in the grammar
    -- the current rule being processed has the general form A --> X1 X2...Xn
    -- where A is the nonterminal on the left, and each Xi represents a single 
    -- symbol on the right, either a terminal or nonterminal.  

    k := 1
    loop while k <= n
      First(A) = First(A) union (First(Xk) - {e})
      if e is not in First(Xk) then
        exit this loop
      end if
      k := k + 1
    end loop

     -- at this point we have finished examining the right hand side of the
    -- current rule.  If we have discovered that every symbol on the right hand
    -- side can derive e, then that means that A can derive e as well, so we
    -- must add e to First(A).  If not every symbol on the right hand side of
    -- this rule can derive e, then neither can A through application of this
    -- rule, so we should not include e in First(A) (although it might already
    -- be there for some other reason, and will not be removed)
    if k > n and e is in First(Xn) then
      set First(A) := First(A) union {e}
    end if

  end loop through

end loop while

-- at this point, first(A) has been computed for every nonterminal A, and
-- First(a) has been set to {a} for each terminal a.

Prepare a third sheet exactly as above, except that the row headings should be Follow(NonTerminal) instead of First(Nonterminal).  If there is room on your First Set sheet, you may use it.

• Build an empty table as for doing the First sets above, but name the rows Follow(Nonterminal 1) and so forth.
• Fill in the table by the algorithm below.

for each nonterminal A in grammar G 
   Follow(A) := {}
end for loop

Follow(S) := {eof}, where S is the start symbol of G

while there are changes to any Follow set loop
   for each rule A --> X1 X2 ... Xn in grammar G loop
     for each Xi in the current rule that is a nonterminal loop
        Follow(Xi) := Follow(Xi) union First(Xi+1 Xi+2 ... Xn) - {e}
        -- if i = n, First(Xi+1 Xi+2 ... Xn) = {e} (the set containing the empty string)
        if e is in First(Xi+1 Xi+2 ... Xn) then
           Follow(Xi) := Follow(Xi) union Follow(A)
        end if
     end for
   end for
end while

 

You now have all of the information you need to fill in the LL(1) table.

• For each nonterminal A in the empty LL(1) table you constructed at the start
• For each rule number i, A --> a, in mPascal (with that nonterminal A on the left)
• Determine First(a) of that rule by looking at your First sets above.
• Put rule number i in the column a for each token a in First(a) in the LL(1) table in row A.
• If l is in the First(a), look at Follow(A) as constructed earlier.  For each token a in follow A, also put i in row A and column a.

To Turn In

1. First Sets Table
2. Follow Sets Table
3. LL(1) Table