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

1. 

        a. YES. (ab+)*

        b. YES. (a+b)*

        c. NO.  A finite automata cannot remember arbitrary numbers
	(maintain unbounded count).



2.

        number  [0-9]+("."[0-9]*)?

        %%

        \${number}              { printf("%gFr",atof(yytext+1)*7.73);}

        {number}"DM"    { printf("%gFr",atof(yytext)*3.35);  }



3.

        a. FIRST(A) = {e}  *e means epsilon*

                FIRST(B) = {e}  

                FIRST(S) = {a,b}  

        

        b. FOLLOW(S) = {$}

                FOLLOW(A) = {a,b}  

                FOLLOW(B) = {b}

  

        c. YES

           |   a       |   b    | $



         __|___________|________|___

         S | S->AaAb   |  S->Bb |  

         A | A->e      |  A->e  |

         B |           |  B->e  |



4. 

step1: Augment grammar to G3'; *e means epsilon*

                 (R0) S'->S

                 (R1) S->AaAb

                 (R2) S->B

                 (R3) A->e

                 (R4) B->e



step2: Item sets

                I0 : S'->.S

                          S->.AaAb

                          S->.Bb

                          A->.

                          B->.

                I1:  S'->S.

                I2:  S->A.aAb

                I3:  S->B.b



                I4:  S->Aa.Ab

                          A->.

                I5:  S->Bb.

                I6:  S->AaA.b

                I7:  S->AaAb.



step3:tables

                              SLR parsing table

           |   a       |   b    |  $   ||   S   |    A     |    B

         __|___________|________|______||_______|__________|_______ 

         0 |  R3       |  R3,R4 |      ||   1        2          3

         1 |           |        |accept||

         2 |  S4       |        |      ||

         3 |           |  S5    |      ||

         4 |  R3       |  R3    |      ||            6

         5 |           |        |  R2  ||

         6 |           |   S7   |      ||

         7 |           |        |  R1  ||



5.

        a. right associative

        b. left associative

        c. 

                new_operator # high left

                new_operator | medium right

        d.
	   step 1. Introduce 6 new tokens: binop_high_left, 
	           binop_high_right, etc.
		 
	   step 2. Add a grammar rule for the new_operator declaration
	           and add actions to insert the operator into the
		   symbol table, with the corresponding token
		   as an attribute.

		   Also add grammar rules for expressions containing
		   binop_*_* tokens.

	   step 3. From the scanner, whenever a new operator (e.g., #)
	           return its token number from the symbol table.