CS 3721 Programming Languages   Spring 2014
Recitation 1.  Grammars
Week 1: Jan 14-16

Submit following directions at: submissions and rules at: rules. Deadlines are: 2014-01-21  23:59:59 (that's Tue, 21 Jan 2014, 11:59:59 pm) for full credit. 2014-01-24  23:59:59 (that's Fri, 24 Jan 2014, 11:59:59 pm) for 75% credit.

Syntax Diagrams:

Note: In work you submit for this course, I insist that you use −−> for grammar rules, and ==> for derivations. Don't mix up the notations.

---

1. In each case below give three distinct derivations leading to a sequence of terminals (a sentence in the language generated by the grammar). From this initial work come up with an informal description of the language defined by the given grammar. "Informal" means short and simple, perhaps using an English language description or set-theory notation. Note that there are no blank symbols used, since I'll usually stay away from blanks (which are handled by the scanner anyway).
   [For example, in 1.a. below, one such derivation is:
   A ==> a A c ==> a a A c c ==> a a b c c .
   You need two more derivations and then need to guess the language. Notice that we didn't need to specify the start symbol, since it follows our convention of being the first non-terminal encountered.]

   1.      A −−> a A c                 (A is start symbol)
           A −−> b
         

   2.      O −−> a  |  a E             (O is start symbol)
           E −−> a O                     (Hint: Why use symbols E and O?)
         

   3.      L −−> L A | A               (L is start symbol)
           A −−> a
         

   4.      N −−> ( C )                 (N is start symbol)
           C −−> C , A | A             (Anything not a non-terminal and not
           A −−> a | b | c | d          a meta-symbol must be a terminal.)
         

   5.      S −−> A B                   (S is start symbol)
           A −−> a A  |  a
           B −−> b B c  |  b c
         

   ---

2. Here is a very simple example grammar:

   
   E  −−> E + E
   E  −−> E * E 
   E  −−> ( E ) | a | b | c | d 
   

   1. Give the unique leftmost derivation and the unique parse tree for:

      a * ( b + c )

   2. Give the two distinct leftmost derivations and the two distinct parse trees for:

      a * b + c 

   ---

3. Here is a "standard" simple example grammar that I will often use:

   
   E  −−> E + T |  T
   T  −−> T * F |  F
   F  −−> ( E ) | a | b | c | d 
   

   In each case below, given the sentence, construct the leftmost derivation sequence ( = replacement sequence = derivation) and the parse tree. (These are both unique.)

   1.   a + b + c

   2.   a * b + c * d

   ---

4. Consider the following grammar for an assignment statement (A), with an operator ^ representing exponentiation. (This is a "beefed-up" version of the standard grammar.)

   
   A  −−> L = E
   E  −−> E + T | E - T | T
   T  −−> T * S | T / S | S
   S  −−> F ^ S | F
   F  −−> ( E ) | L
   L  −−> a | b | c | d 
   

   1. What are the terminal symbols? The non-terminal symbols? The metasymbols?

   2. Construct leftmost derivations and parse trees for each of the following sentences:

      1.    d = a ^ b ^ c

      2.    d = a + b * c ^ d

   3. What do the derivations and trees in i. and ii. above say about the precedence and associativity of the new operator ^?

   ---

5. Refer to the first link at the top of this page. Using the grammar for a double at the end of that page, give the parse tree for the following double. (You should ignore blanks in the grammar rules. Blanks are not usually handled by the grammar, but instead by the lexical level, which we will do later in the course.)
   1.  2.45E−3

   ---

6. Refer to the third link at the top of this page. Using either one of the first two grammars on the page, give the parse tree for each of the following sentences. (Assume that "id" and"const" are terminals, since they would be normally be handled by the scanner. In the real source, each of these would be an actual identifier or constant, not all the same. Again ignore blanks.)
   1. if ( id ) { while ( id ) id = id + const ; }

   2. The original version of this statement is wrong and cannot be derived from the given grammar. The original version was:

      while ( const - id ) if (id) id = id * const ; { id = const ; id = id ; }

      Instead you should use either:

      { while ( const - id ) if (id) id = id * const ; { id = const ; id = id ; } }

      or

      while ( const - id ) { if (id) id = id * const ; { id = const ; id = id ; } }

   ---

7. Using the same grammar as in the previous problem, say whether the following is legal.
   1. while ( id ) while ( id ) id = id + id;

   2. Is there any ambiguity problem with a complex while like the above example, or with one involving even more whiles (but no ifs)?

   ---

8. Refer to the fourth link at the top of this page. Refer to the complex if-else statement at the end of this page. The syntax of C would allow three additional and non-trivial pairs of {} bracket to appear.
   1. Write out the code with these additional brackets properly inserted, and format the result in a reasonable way. (In this situation Java permits exactly the same thing.)

   2. Give a simple rule for writing complex if statements that would allow you to eliminate the three extra brackets inserted above, while keeping the fourth one as it is?