Answer Key for CSE-304 Mid-term Exam of Fall '97

1. Lexical Analysis phase
   Syntax Analysis Phase, 
   Semantic Analysis Phase,

2. a. (0|1)*00
   b. Initial state: S0
   Transitions:
    From            To               Symbol
     S0             S0                 0
     S0             S0                 1
     S0             S1                 0
     S1             S2                 0
    Final state: S2
 
Or (refer to textbook):
    Initial State: S0
    From           	To           Symbol
     S0            	S1              e(Epsilon)
     S1            	S2 		e 
     S2 		S3 		0
     S3 		S6 		e
     S1 		S4 		e
     S4 		S5 		1
     S5 		S6 		e
     S6 		S1 		e
     S6 		S7 		e
     S0 		S7 		e
     S7 		S8 		0
     S8 		S9 		0
Final State: S9

3. Solution 1 (does not take care of the first sentence):

  %{
     char ucase(char);
  %}

  ws               [ \t\n]*
  lc_letter           [a-z]

  %%
  "."{ws}{lc_letter}   {yytext[yyleng-1] = ucase(yytext[yyleng-1]);
			printf("%s", yytext);}

  .|\n		 { printf(%s, yytext);}
  %%
  ------------

  Solution 2 (complete solution):

  %{
     char ucase(char);
  %}

  %%
  [^ \t\n]([^.]*)"."   { printf("%c", ucase(yytext[0]));
			 printf("%s", yytext+1);}

  .|\n		 	{ printf(%s, yytext);}
  %%

4.  a. First(S) = {a, e}
    b. Follow(S) = {a, $}
    c. It violates both two rules:
       i)First (aaSab) /\ First (abSaa) = {a} <> {} 
       ii)Follow (S) /\ First (abSaa)  = {a}  <> {}
          Follow (S) /\ First (aaSab)  = {a}  <> {} 

5. a. No. Consider an abstraction grammar, where i stands for if expr then,
      e stands for else, and a stands for "all other productions". We write
      augment grammar as following:

	S' -> S
	S -> iSeS | iS |a

	LR(0) set of item as following:
	    I0: S' -> S		I3: S -> a.
		S -> .iSeS
		S -> .iS	I4: S -> iS.eS
		S -> .a	            S -> iS.

	    I1: S' -> S		I5: S -> iSe.S
	    I2: S -> i.SeS 	    S -> .iSeS
		S -> i.S	    S -> .iS
		S -> .iSes          S -> .a
		S -> .iS
		S -> .a		I6: S -> iSeS.

      There is a shift/reduce conflict in I4. There, S -> iS.eS calls for a
      shift of e and, since Follow(S) = {e,$}, item S -> iS. Calls for
      reduction by S -> iS on input e.

  b.  Yes. If one rule doesn't match, the recursive descent parser will
      try anotherrule.

6. a. LR(0) set of items is as following:
    I0: E' ->.E
	E -> .E + E
  	E -> .E * E
	E -> .id
    I1: goto(I0, E)
	E' -> E.
	E -> E. + E
 	E -> E. * E
    I2: goto(I0, id)
	E -> id.
    I3: goto (I1, +)
	E -> E +. E
	E -> .E + E
  	E -> .E * E
	E -> .id
    I4: goto(I1, *)
	E -> E *. E
	E -> .E + E
  	E -> .E * E
	E -> .id
    I5: goto(I3, E)
	E -> E + E.
	E -> E.+ E
	E -> E. * E
    I6: goto(I4, E)
  	E -> E * E.
	E -> E.+ E
	E -> E. * E

b. SLR(1) action table is as following:
	
	id	+	*	$
0	s2                     			
1		s3	s4	acc
2		r3	r3	r3
3	s2			
4	s2			
5		s3	s4	r1
		r1	r1
6		s3	s4	r2
		r2	r2

c. E -> id + E 
   E -> id * E 
   E -> id