HMWK1

Due: 20 Feb 2018, by end of class

1) Given the grammar:

S -> I = E
I -> a | b | c
E -> I + E
  |  I * E
  |  ( E )
  | I

Draw a parse tree and leftmost derivatiion for the following sentences:

a) A = A * (B + (C * A))
b) B = C * (A * C + B)
c) A = A * (B + (C))

2) Demonstrate that the following grammar is ambigious:

S -> X 
X -> X |  X & X | I
I -> a | b | c

3) Determine which of the sentences (a-e) are in this grammar:

S -> aScB | A | b
A -> cA | c
B -> d | A

a) abcd
b) abc 
c) acccbcc
d) acd
e) accc

4) Convert the following EBNF rules to the basic BNF notation:

S -> A{Ac}
A -> d[b]A