COSC 170 - ASSIGNMENT #1
                 Due date: Wednesday, Jan. 23, 2019


Problems 1 and 2 refer to the list of five grammars below.

1. For each grammar, give 4 different strings which  are  in  the
language   defined   by  the  grammar.  Note that in each case, S
is the only non-terminal symbol, so all  other   symbols  (except
the  arrows, vertical bars and <epsilon>'s) are terminal symbols.

2. For each grammar decide if it is ambiguous.  If so,   give  an
example   of  a  string  with  two  parse trees.  If not, explain
briefly why you won't ever have two parse  trees   for  the  same
string.

a) S -> 1 0 S
      | 1

b) S -> S , S
      | x
      | y

c) S -> S S +
      | S S -
      | x

d) S -> S ( S ) S
      | <epsilon>

e) S -> x
      | S + S
      | S S
      | - S


3.  Construct  a  syntax-directed  definition (i.e. grammar with
associated semantic attribute) that translates
arithmetic  expressions  from infix notation into prefix notation
in which an operator appears before its operands: e.g.,   -  x  y
is the prefix notation for  x - y .

  Give annotated parse trees for  4 + 2 - 3  and  1 - 6 * 8  .