Practice Midterm 1 - Scanning, Parsing, Symbol Tables, Semantic Actions 
CS 524 Spring 2008 
Closed book exam: Wednesday 12 March 2008

1)  Consider the Pascal-like fixed-decimal literal with no
superfluous leading or trailing zeros.  That is, 0.0, 123.01 
and 123005.0 are legal, but 00.0, 001.000 and 0023.100 are illegal.

a) construct the determinstic machine that can recognize valid
Pascal-like fixed decimal literals.






b) number the state of your machine and list of the state, in order,
that are passed through in recognizing 3501.3601


2)  Given the following grammar

    S -> S A S C | lambda  
    A -> A a | b
    C -> D c D
    D -> d

a) construct the derivation tree (parse tree) for the following
   input string:

    baadcd


b) give the right-most derivation, starting from the start symbol, of 
this phrase




3)  given the following grammar

e ::= e + f 
e ::= f 
f ::= ( e ) 
f ::= a [ e ] 
f ::= a 

a) what language construct does this describe?

b) construct the CFSM(0) for this grammar

c) is this grammar LR(0)?  Why or why not?  Be specific.

d) Is this grammar SLR(1)?  Why or Why not?  be specific

e) Construct the Action and Goto tables from the CFSM(0)






4)  Given the folllowing grammar:

1 assign -> mem := E         {assign();}   
2 mem    -> ident            {idtoaddr();}
3 ident  -> Id               {pushid(yytext);}
4 E      -> E + T            {performop(addop);}
5 E      -> T
6 T      -> T * P            {performop(multop);}
7 T      -> P
8 P      -> ( E )
9 P      -> mem              {addrtoprimary();}

With its corresponding Action and GoTo Tables:

Action
                      Lookahead
---------------------------------------------------------
State|  Id      +       *       (       )       :=      eof
---------------------------------------------------------
  1     S
  2                                             S
  3             R2      R2              R2      R2      R2
  4             R3      R3              R3      R3      R3
  5     S                       S
  6             R9      R9              R9              R9
  7             S                                       A
  8             R5      S               R5              R5
  9             R7      R7              R7              R7
 10     S                       S
 11     S                       S
 12     S                       S
 13             S                       S
 14             R4      S               R4              R4
 15             R6      R6              R6              R6
 16             R8      R8              R8              R8


GoTo:
                      Symbol
State| assign  mem  ident  E  T  P  Id  +  *  (  )  :=  eof
----------------------------------------------------------
  1  |       |  2  |  3  |   |  |  | 4 |  |  |  |  |   |
  2  |       |     |     |   |  |  |   |  |  |  |  | 5 |
  3  |       |     |     |   |  |  |   |  |  |  |  |   |
  4  |       |     |     |   |  |  |   |  |  |  |  |   |
  5  |       |  6  |  3  | 7 |8 |9 | 4 |  |  |10|  |   |
  6  |       |     |     |   |  |  |   |  |  |  |  |   |
  7  |       |     |     |   |  |  |   |11|  |  |  |   |
  8  |       |     |     |   |  |  |   |  |12|  |  |   |
  9  |       |     |     |   |  |  |   |  |  |  |  |   |
 10  |       |  6  |  3  | 13|8 | 9| 4 |  |  |10|  |   |
 11  |       |  6  |  3  |   |14| 9| 4 |  |  |10|  |   |  
 12  |       |  6  |  3  |   |  |15| 4 |  |  |10|  |   | 
 13  |       |     |     |   |  |  |   |11|  |  |16|   |
 14  |       |     |     |   |  |  |   |  |12|  |  |   |     
 15  |       |     |     |   |  |  |   |  |  |  |  |   |
 16  |       |     |     |   |  |  |   |  |  |  |  |   |



4a) Using as many steps as are necessary, construct the parse by
filling in the following table. (use as many lines as are appropriate)

-----------------------------------------------------------------------
Step| Parse Stack              | Remaining Input |  Parser Action
-----------------------------------------------------------------------
(1) | 1                        | a := b * c      |
-----------------------------------------------------------------------
    |                          |                 |
-----------------------------------------------------------------------
    |                          |                 |
-----------------------------------------------------------------------











4b) For each reduction which has a semantic action corresponding
to it, i.e. those with {something();} after the grammar rule, show
the current semantics stack.  Number the semantic reduction steps in
the parse above, then use the same number to label a drawing of the
semantic stack.

   You should use your knowledge of our project and the fact that
this is a simplified subset of the grammar.  NOTE, the routine
performop has an argument, which is used instead of pushing the
actual operator onto the semantic stack.


5) Consider the following code fragment

          package main is body                -- open level 0
               x,y: integer;

               procedure a is           
                    x,y: boolean;           -- open level 1

                    procedure b is       
                         x: character;         -- open level 2

                         procedure c is 
                              x,y: foogle; -- open level 3
                         begin -- c
                              ...

                         end;  -- c           -- close level 3

                    begin -- b
                        ...
                    end;  -- b                -- close level 2

               begin -- a
                   ...
               end;  -- a                     -- close level 1

          begin -- main;
              ...
          end;  -- main;                      -- closel level 0

a) Draw a diagram to represent a Scope Stack of Symbol Tables for 
the code fragment above.



b) In the body of procedure c, what is the data type of the variable y?



c) In the body of the main procedure, what is the data type of the 
variable y?