CS 214 Project 2: Practicing with BNFs

This week's project is to practice creating BNF definitions and work with derivations.

The are three key ideas to keep in mind:

• If a portion of a language construct is complicated, hide the complexity by creating a nonterminal for it, and then define the nonterminal (later).
• If a language construct is optional, create a nonterminal that has two productions, one of which defines the optional part, and the other of which is an Ø-production.
• If a language construct can be repeated, create a non-terminal that has two productions, one of which is a recursive production providing the repetition, and the other of which is an Ø-production by which the recursion can terminate.

1. Using these ideas, define the constructs below with BNF productions. Underline the terminals in your productions, to distinguish them from the nonterminals. You may assume that the following have already been defined:

      <letter>   ::=   A | B | C | D | E | F | G | H | I | J | K | L 
                       | M | N | O | P | Q | R | S | T | U | V | W 
                       | X | Y | Z | a | b | c | d | e | f | g | h
                       | i | j | k | l | m | n | o | p | q | r | s
                       | t | u | v | w | x | y | z
      <digit>   ::=   0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
      

   1. A Java character literal
      
      
      
      
      
      
      
      
      
      
      
      
   2. A Java character string literal
      
      
      
      
      
      
      
      
      
      
      
      
      
   3. A Java integer literal
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   4. A Java real (floating point) literal
      
      
      
      
      
      
      
      
      
      
   5. A Java identifier:
      
      
      
      
      
      
      
      
      
      
   6. A Java function declaration (prototype):
      
      
      
      
      
      
      
      
      
      
      
   7. A Java if statement (you may assume that the nonterminals <statement> and <expression> are defined elsewhere):
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   8. A Java while statement (you may assume that the nonterminals <statement> and <expression> are defined elsewhere):
      
      
      
      
      
      
      
      
      
      
2. Prove that the following grammar is ambiguous:
   

   <S> ::= <A>
<A> ::= <A> + <A> | <id>
<id> ::= a | b | c

   
   
   
   
   
   
   
   
   
3. Give a left-most derivation for A = A * (B + C) using the following BNF grammar:
   

   <assign> ::= <id> = <expr>
<id> ::= A | B | C
<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <expr> ) | <id>

   
   
   
   
   
   
   
   
   
   

Turn in. Using any text editor or word processor, make an electronic copy of this page and write your name prominently at the top. Then enter your solutions directly on that electronic copy. When you are finished, copy it into your personal folder in /home/cs/214/current/.

Calvin > CS > 214 > Projects > 02