CS 502
				       
		       COMPILING & PROGRAMMING SYSTEMS

				  HOMEWORK 1

Assigned: 02/09/12
Due:      03/01/12

ASSIGNED PROBLEMS:

1) Construct NFAs for the following REs.  Show the sequence of moves made by
   each in processing the string ababbab.

   a) (ab|b)*
   b) (a*b | b)*
   c) ((ε|a|b)ba)*
   d) (ab|ba)*abb(a|b)*

2) Convert each of the NFAs from question 1 into DFAs using the subset
   construction.  Again, show the sequence of moves for each DFA in processing
   the string ababbab.

3) A production of the form A -> A... is said to be left-recursive.
   Similarly, a production of the form B -> ...B is said to be
   right-recursive.  Show that any grammar that contains both left- and
   right-recursive productions with the same left-hand side symbol must be
   ambiguous.

4) Let G be any CFG and assume that L(G) does not contain the empty string.
   Show that G can be transformed into an equivalent CFG that uses no
   epsilon-productions.

5) Which of the following grammars are LL(1)?  Explain why.

   a) S -> A B c
      A -> a
      A -> ε
      B -> b
      B -> ε

   b) S -> A b
      A -> a
      A -> B
      A -> ε
      B -> b
      B -> ε

   c) S -> A B B A
      A -> a
      A -> ε
      B -> b
      B -> ε

   d) S -> a S e
      S -> B
      B -> b B e
      B -> C
      C -> c C e
      C -> d

6) Construct the LL(1) parse table for the following BNF grammar:

   <exp>     ::= - <exp>
   <exp>     ::= ( <exp> )
   <exp>     ::= <var> <exptail>
   <exptail> ::= - <exp>
   <exptail> ::=
   <var>     ::= id <vartail>
   <vartail> ::= ( <exp> )
   <vartail> ::=

7) Build the LR(0) CFSM for the following grammar.  The non-terminals are P,
   B, SL, S, E, and T; the terminals are $, {, }, ;, :=, +, id, (, and ).

	P  -> B $
	B  -> { SL }
	SL -> SL ; S
	SL -> S
	S  -> B
	S  -> id := E
	E  -> E + T
	E  -> T
	T  -> id
	T  -> ( E )

  Indicate the various LR(0) conflicts, if any.

  Build the LR(1) machine for the same grammar, and indicate the LR(1)
  conflicts, if any.

8) Which of the following grammars are LR(1)?  Which are LALR(1)?  Which are
   SLR(1)?  In each case justify your characterization.  The terminals are :=,
   ;, +, id, (, and ).

   a) S -> id := E ;
      E -> E + P
      E -> P
      P -> id
      P -> ( E )
      P -> id := E

   b) S -> id := A ;
      A -> id := A
      A -> E
      E -> E + P
      E -> P
      P -> id
      P -> ( A )

   c) S -> id := A ;
      A -> id := A
      A -> E
      E -> E + P
      E -> P
      E -> P +
      P -> id
      P -> ( A )

   d) S -> id := A ;
      A -> Pre E
      Pre -> Pre id :=
      Pre -> ε
      E -> E + P
      E -> P
      P -> id
      P -> ( A )

   e) S -> id := A ;
      A -> Pre E
      Pre -> id := Pre
      Pre -> ε
      E -> E + P
      E -> P
      P -> id
      P -> ( A )

   f) S -> id := A ;
      A -> id := A
      A -> E
      E -> E + P
      E -> P
      P -> id
      P -> ( A ; A )
      P -> ( V , V )
      P -> { A , A }
      P -> { V ; V }
      V -> id

   g) S -> id := A ;
      A -> id := A
      A -> E
      E -> E + P
      E -> P
      P -> id
      P -> ( id ; id )
      P -> ( A )