Lab 5 - Finishing the LL(1) Table and the Parser

Objectives

The objectives of this laboratory exercise are

• To provide you opportunity to demonstrate your parser as it stands (if you can parse some programs)
• To have you finish constructing the LL(1) tables for mPascal
• To give you experience with the individual algorithms underlying LL(1) table construction if you haven't already tried them
• To have you begin the completion of your parser based on the LL(1) table

Preparing for Lab

No special preparations needed.

To Do

This day is primarily a catch up day.

• If you can parse some programs, be prepared to demo.  We will come around and check your parser to see what it is able to parse at this point.  Before we come to your station, do your demos for other teams sitting nearby.
• Be sure your LL(1) table is complete.  This table is to be completed according to the grammar you have worked with so far. Thus, what you have should reflect any of the conflicts resulting from this grammar.
• Discuss among your group how to resolve any conflicts in the table.  Make a NEW TABLE (do not modify the original table, rather use a copy of that table) that reflects any changes you make to resolve conflicts.  In cases where there is no resolution, discuss and write down how you will handle the conflicts.
• Discuss among yourselves how to include parsing error messages to include information about what token was found that caused the error and what tokens were expected in that location. Begin to include these error messages (in the default clause of your switch statements in the nonterminal methods).
• Finish working on your parser.  Be sure that each member finishes some of the parser stubs with proper lookaheads.  Make sure this is done in a "stepwise" fashion so that you can continue to test new features of the grammar as you parse them.

The Algorithms

If you need them, here they are. Remember that algorithms are for computers. When you understand how the First and Follow algorithms work, you can generally "eyeball" your grammar and figure most of it out.

First

let ε stand for the empty string
loop for each nonterminal A
   set First(A) = {} -- set First(A) to the empty set.
                     -- note that the empty set does not contain anything, 
                     -- not even ε
end loop

loop for each terminal a
   set First(a) = {a}
end loop

loop for each rule in the grammar
   if the rule is A ⟶ ε then
      set First(A) = {ε}
   end if
end loop

loop while this is the first time through the loop, or any additions have
           been made to any set First(A) for all A during the previous pass
           through the loop
   loop through each non-ε 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) ∪ (First(Xk) - {ε})
         if ε is  ∉  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 ε, then that means that A can derive ε as well, so we
      -- must add ε to First(A).  If not every symbol on the right hand side of
      -- this rule can derive ε, then neither can A through application of this
      -- rule, so we should not include ε in First(A) (although it might already
      -- be there for some other reason, and will not be removed
      if k > n and ε ∈ First(Xn) then
         set First(A) := First(A) ∪ {ε}
      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.

Follow

    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 during the previous pass through the loop 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) ∪ First(Xi+1 Xi+2 ... Xn) - {ε}
               -- if i = n, First(Xi+1 Xi+2 ... Xn) = {ε}(the set containing the empty string)
               if ε is in First(Xi+1 Xi+2 ... Xn) then
                  Follow(Xi) := Follow(Xi) ∪ Follow(A)
               end if      
           end for
       end for
    end while 

Predict

• Move through the rules in the grammar.
• Look at each symbol on the right hand side of the rule, from left to right.
• Union First of each symbol on the right in the lookahead token set for this rule, as long as First of these symbols also contain the empty string.
• If the right hand side is empty, or the entire right had side can derive the empty string, union the lookahead symbols found so far with Follow of the nonterminal on the left hand side of the rule.

To Turn In

Put your current LL(1) table in the Lab 5 dropbox. .