Exercise Set 1

1. Using grammar

           <E> ::= <E> + <T>
               |   <T>
   
           <T> ::= <T> * <F>
               |   <F>
   
           <F> ::= num
               |   ( <E> )
     

   give parse trees for each of the following strings, where num is a token whose lexemes are decimal numerals.

   1. 2+3
   2. 2*3+5
   3. (2+3)*5

2. Show that the following grammar is ambiguous by deriving two different parse trees for the same sequence of tokens starting from <S>.

        <S> ::= <S> a <S>
            |   a
     

3. Show a grammar for Pascal identifiers, which consist of a sequence of letters and digits, beginning with a letter. Presume that <letter> and <digit> are available, where <letter> generates any single letter and <digit> generates any single digit. Call your syntactic classification <identifier>. (Note: identifiers are normally handled at the lexical level. This excercise is asking how an identifier would be described if it were handled at the syntactic level.)

4. The binary operators of Pascal are as follows.
   1. <  <=  =  <>  >=  >  in
   2. +  -  or
   3. *  /  div  mod  and

   Operators that are listed together have the same precedence, and the lines are in order of increasing precedence. All operators associate to the left. For example, a/b/c is understood to mean (a/b)/c, not a/(b/c).

   1. Write a BNF grammar for Pascal expressions. In addition to the above operators, allow parentheses. Use tokens RELOP, ADDOP and MULOP, each of which can have several lexemes. A RELOP is a relational operator, an ADDOP is an addition/subtraction operator and a MULOP is a multiplication/division operator. As basic expressions, use only VAR, which is a token that stands for a variable.

      Make your grammar unambiguous, so that it enforces the correct precedence and associativity rules.

   2. Show a parse tree for expression (VAR = VAR or VAR > VAR). Be careful to follow the rules! You might be surprised by what you get.