Exercise 8      Name       ____________________   Points __/21

Document last modified: 
 

<S> ::= <NP> <V> <NP>
<NP> ::= <A> <N>
<V> ::= loves | hates | climbs
<A> ::= a | the
<N> ::= dog | cat | tree

1. (3) Which of the following are valid <S>?

    

   1. a dog climbs a tree
   2. a cat dog loves the cat
   3. the loves the dog a cat

    

2. (6) Give the parse trees of:

    

   1. a dog climbs a tree
   2. the loves the dog cat

    

3. (6) Parse and give the parse tree for each of the following using:
   
       <exp> ::= <exp> + <exp> | <exp> * <exp> | ( <exp> ) | a | b | c

    

   1. a * b + c
   2. a * ( b + c)

    

4. (6) Given the following definitions:

   <alpha> ::= a | b | ... | z | A | ... | Z
   <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   <unsigned> ::= <digit> | <unsigned> <digit>
   <signed> ::= +<unsigned> | -<unsigned>
   <integer> ::= <unsigned> | <signed>
   <decimal> ::= <integer> . | <integer> . <unsigned>

   Define in BNF:

    

   1. <number> as the set of all strings of <integer> or <decimal>.
   2. <scientific> that defines numbers represented in scientific notation; for example: -1.3E+4, -8E-5, 8E5,  +3.14E+0, 7.878E-12 are valid <scientific>, 3E4.5 is not valid <scientific>.
   3. <small number> as the set of all strings of one, two or three <digit>. For example: 1, 23, 456 are all <small number> but 1234, -12, +3 are not.
   4. <identifier> as the set of all strings that begin with an <alpha> followed by any number of <alpha> or <digit>. For example: a, A, AB, A1, A2z are <identifier> but 1a, 123 are not.