CPSC 411 - Lab Notes - 02-10 (Grammars)

We will examine the grammar from the 1999 CPSC510 midterm (Available for download from Dr. Cockett's site.)

The grammar is:

s_expression  -> atomic_symbol
              |  LPAR s_expression end_s_expression RPAR .

end_s_expression -> DOT s_expression
                 |  s_expressions .

s_expressions -> s_expressions DOT s_expression
              |    .

atomic_symbol  -> LETTER atom_part .

atom_part  -> LETTER atom_part
           |  NUMBER atom_part
           | .

Some valid s_expression(s) are:

• a
• (a15.a)
• (a17.a.b.c)

In the lab, we will work through the answers to:

• Which non-terminals are nullable?
• Which non-terminals are endable?
• What are the first sets of each non-terminal?
• What are the follow sets of each non-terminal?

In addition, we will discuss if the grammar is LL(1) and transform the grammar to remove left recursion.

Last modified by Brett Giles
Last modified: Sat Feb 22 15:12:43 MST 2003