CSC 324, Summer 2001

Tutorial notes for week 2


****************************************************************

1. Listed below is a subset of operators in C.  Operators are listed in
   decreasing order of precedence, with all operators at a given level
   having the same precedence.

    Desc                        Operators       Associativity
    ---------------------------------------------------------
    Unary prefix operators      +, -            N/A
    Multiplicative operators    *, /, %         Left
    Additive operators          +, -            Left
    Shift operators             <<, >>          Right
    Conditional (ternary)       ? :             None
    
   Write a CFG in BNF for C expressions using these operators and
   parentheses.  (Assume the non-terminal <simple-expr> is defined and
   handles literals, variables, etc.)

   Answer: 

      <expr>         ::= <cond-expr> 
      <cond-expr>    ::= <shift-expr>
                      |  <shift-expr> ? <shift-expr> : <shift-expr>
      <shift-expr>   ::= <add-expr> | <add-expr> <shift-op> <shift-expr>
      <add-expr>     ::= <mult-expr> | <add-expr> <add-op> <mult-expr>
      <mult-expr>    ::= <unary-expr> | <mult-expr> <mult-op> <unary-expr>
      <unary-expr>   ::= <primary-expr> | <unary-op> <primary-expr>
      <primary-expr> ::= <simple-expr> | ( <expr> )

      <shift-op> ::= << | >>
      <add-op>   ::= + | -
      <mult-op>  ::= * | / | %
      <unary-op> ::= + | -

    Explaination:

-- left/right associativity means left/right recursion of the given
   nonterminal
-- higher precedence means the given nonterminal is lower down in the
   nonterminal recursion
-- all expression grammars have parentheses, to indicate when default
   associativity or precedence is to be overridden in a given
   expression.


2. For each of the following expressions, draw parse trees with respect
   to the grammar you gave in problem (1):

   a) 3 * - 2 * ( 5 + 4 )
   b) 3 *  32 << 16 << 8 * 6
   c) a ? b * 3 >> 2 : c / + 3

   (In your trees, you can go directly from <simple-expr> to variables
    and numbers.)

 Draw the parse tree yourself.


****************************************************************
3) Develop grammars for the following languages.  

a) a^n c b^n   n >= 0

Answer:

<S> ::= a <S> b | epsilon

<S> ::= a <S> b | c

b) a^n b^n c^m d^m   n,m >= 1

Answer:

<S> ::= <A> <C>
<A> ::= a <A> b | a b
<C> ::= c <C> d | c d


c) a^n b^m c^m d^n   n,m >= 0
  
Answer:

<S> ::= a <S> d | <T>
<T> ::= b <T> c | epsilon


****************************************************************
4) Given English descriptions of the languages described by each of
the following grammars.


a) <S> ::= <S> a <S> b <S> | <S> b <S> a <S> | epsilon

   Answer: All strings with an equal number of a's and b's.  

   You'll need to work through an example string to show why this
   works.

b) <S> ::= a <S> a | b <S> b | c <S> c | epsilon

   Answer: All even length strings where the second half of the string
   is the reverse of the first half.

c) A related exercise: Adjust the grammar in (b) to make it generate
   all palindromes (strings that look the same if read backwards).

   The grammar in (b) only generates even length strings, so you have
   to figure out what to do to generate odd length strings.

   Answer:  <S> ::= a <S> a | b <S> b | c <S> c | a | b | c | epsilon


****************************************************************
5) For each of the grammars in (4), discuss whether it is ambiguous or
not, and explain how to justify your answer.

The main point of this problem is that you need to show two parse
trees for one string to show that a grammar is ambiguous.  You will
not be required to prove that a grammar is unambiguous, although you
should be able to make a convincing (brief) argument.

Answer: 4a is ambiguous.  Show two parse trees for the string abab.

Answer: 4b is not ambiguous.  You simply have to argue that there's
only one way to get a pair of a's, b's or c's, and recursion is all
nested.