CS 3721 Programming Languages   Spring 2013
Recitation 3.   Grammars
Week 3: Jan 28-Feb 1

Submit following directions at: submissions and rules at: rules. Deadlines are: 2013-02-04  23:59:59 (that's Mon, 04 Feb 2013, 11:59:59 pm) for full credit. 2013-02-08  23:59:59 (that's Fri, 08 Feb 2013, 11:59:59 pm) for 75% credit.

In ordinary programming it is usually a good idea to use library functions rather than rewrite them from scratch. In this recitation, however, we are studying some of the low-level language mechanisms, and for this assignment you are not to use a library function. Instead, you should realize that given the code:

char ch = '4';
int i = ch -'0';

You should not use the pow function in C or the static Math.pow() function in Java in order to handle the exponent, but you should handle this "from scratch" also. (You don't need the full power of pow, but just some multiplies or divides by 10.

You can test your program with the same list of numbers used in the previous recitation:

11     11.     62.47     .14     11.75e2     .75e2     11.e2     11e2     11.5e-2
11.5e+2     11.75E2     11.75     .75     .23     .84e-2     666     345.578e5     1234.5678

.75e2
Raw number: 75.000000, combined Exponent: 0, value:"75.000000"
11.5e-2
Raw number: 115.000000, combined Exponent: -3, value:"0.115000"
11.5e+2
Raw number: 115.000000, combined Exponent: 1, value:"1150.000000"
11.75E2
Raw number: 1175.000000, combined Exponent: 0, value:"1175.000000"
345.578e5
Raw number: 345578.000000, combined Exponent: 2, value:"34557800.000000"

1. In each case below give an informal description of the language defined by the given grammar. "Informal" means short and simple. One way to get started is to try various derivation sequences and get intuition about what sentences can be generated. For example, in 1.a. below, one can write A ==> a A c ==> a b c, or A ==> a A c ==> a a A c c ==> a a b c c, and so forth.

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

   2.      O ---> a  |  a E             (O is start symbol)
           E ---> a O
         

   3.      S ---> A B                   (S is start symbol)
           A ---> a A  |  a
           B ---> b B c  |  b c
         

   4.      S ---> ( S ) S  |  e         (S is start symbol. This one is hard.)
                                          (e is the empty symbol)
         

   5.      S ---> a B  |  b A           (S is start symbol. This one is really hard.)
           A ---> a S  |  b A A  |  a     (Just for "fun" or extra credit.)
           B ---> b S  |  a B B  |  b     (Work on this last.)
         

2. Consider the following grammar for an assignment statement (A), with an operator ^ representing exponentiation:

   
   A    ---> <id> = E
   E    ---> E + T | E - T | T
   T    ---> T * S | T / S | S
   S    ---> F ^ S | F
   F    ---> ( E ) | <id>
   <id> ---> 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: (But only submit the derivations and not the parse trees, since they are too irritating to do in a text file.)
      1. d = a + b + c
      2. d = a ^ b ^ c
      3. d = a + b * c ^ d

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

Contents of submission for Recitation 3: Last Name, First Name; Course Number; Recitation Number (3) Last Name, First Name (of second person, if two are working together). First part: adding code to your recognizer for doubles so that they convert the string representing a double into an internal double. Run your program with the examples given above. You should have some extra debug output, perhaps similar to what is above. Answers to questions 1 and 2 above. Problem 1(e) is just to torment you. (In the past some students have spent endless hours on this.)