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 - VALID
   2. a cat dog loves the cat  - INVALID
   3. the loves the dog a cat - INVALID

    

2. (6) Give the parse tree of:
   1. a dog climbs a tree
   2. the dog loves the dog cat

a dog climbs a tree                     <S>                   /   |    \           <NP> <V> <NP>            /          |         \   <A><N>  climbs  <A><N>      |     |                 |      |     a   dog                a    tree

the dog loves the dog cat                     <S>                  /    |     \           <NP> <V> <NP>             /         |         \   <A> <N>   loves  <A><N>      |      |                  |     |    the  dog               the  dog   cat                                             Fails




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

      <exp>   = <exp>*<exp>             = <exp>*<exp>+<exp>             = a * b + c

      <exp>                   /   |   \             <exp>*<exp>                |         /  |   \                a  <exp> + <exp>                         |           |                         b           c

       

   2. a * ( b + c)

      <exp>   = <exp>*<exp>
                  = <exp>*(<exp>)
                  = <exp>*(<exp>+<exp>)
                  = a * (b + c)

   <exp>   = <exp>*<exp>             = <exp>*(<exp>)             = <exp>*(<exp>+<exp>)             = a * (b + c)

   <exp>                   /   |   \             <exp>*<exp>                |           |                  a     ( <exp> )                         /     |    \                     <exp> + <exp>                         |           |                         b           c

4. (6) Given the following grammar:

   <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>.

      <number> ::= <integer> | <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>.

      <scientific> ::= <number>E<integer>

       

   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.

      <small number> ::= <digit> | <digit> <digit> | <digit> <digit> <digit>

       

   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.

<identifier> ::= <alpha> | <identifier> <alpha> | <identifier> <digit>