next up previous
Next: Left and Right recursion Up: CS2121: The Implementation and Previous: Example run of YACC

Subsections

A larger example illustrating the Phases of Compilation

Phases of Compilation - larger example

Example C program 

int i;
int count = 0;
char * fred (char c, int i)
{
  static int mark = 0;
  char * result = (char *) malloc (i + 2);
  count += i;
  {
    int k;
    for (k = 0; k < i; k++)
      result [k] = c;
  }
  result [i++] = 0;
  result [i] = ++mark;
  return result;
}
int main (void)
{
  char * string;
  i = 5;
  string = fred ('a', i);
  printf ("%s, %d, %d\n", string, string [i+1], count);
  string = fred ('b', i);
  printf ("%s, %d, %d\n", string, string [i+1], count);
  return 0;
}

Dictionary

Snap-shots of the dictionary at various points during the semantic analysis of the example program.

We start with just the built-in names, at level 0.

char \fbox{type $\vert$0 $\vert$1 byte}
int \fbox{type $\vert$0 $\vert$4 bytes}

Global declarations are at level 1.

int i;
char \fbox{type $\vert$0 $\vert$1 byte}
int \fbox{type $\vert$0 $\vert$4 bytes}
i \fbox{var $\vert$1 $\vert$1 $\vert$int}

int count = 0;
char \fbox{type $\vert$0 $\vert$1 byte}
int \fbox{type $\vert$0 $\vert$4 bytes}
i \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}

Declarations within functions are (initially) at level 2. The eventual position of fred in the compiled code is currently unknown. The new declaration for i, as a parameter, temporarily overrides the previous declaration (global variable).

char * fred (char c, int i) {
char \fbox{type $\vert$0 $\vert$1 byte}  
int \fbox{type $\vert$0 $\vert$4 bytes}  
i \fbox{param $\vert$2 $\vert$2 $\vert$int} \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}  
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}  
c \fbox{param $\vert$2 $\vert$1 $\vert$char}  

static int mark = 0;
char \fbox{type $\vert$0 $\vert$1 byte}  
int \fbox{type $\vert$0 $\vert$4 bytes}  
i \fbox{param $\vert$2 $\vert$2 $\vert$int} \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}  
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}  
c \fbox{param $\vert$2 $\vert$1 $\vert$char}  
mark \fbox{var $\vert$2 $\vert$1 $\vert$static int $\vert$0}  

char * result = (char *) malloc (i + 2);
char \fbox{type $\vert$0 $\vert$1 byte}  
int \fbox{type $\vert$0 $\vert$4 bytes}  
i \fbox{param $\vert$2 $\vert$2 $\vert$int} \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}  
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}  
c \fbox{param $\vert$2 $\vert$1 $\vert$char}  
mark \fbox{var $\vert$2 $\vert$1 $\vert$static int $\vert$0}  
result \fbox{var $\vert$2 $\vert$2 $\vert$char*}  
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}  

We don't have a declaration for malloc, so we have to try to construct something for it.

count += i;
At this point, for example, when we look up i, we find information describing it as a parameter of fred, rather than a global variable. Also, when we look up count, we discover that it is a variable, so it can be assigned to, and it and i are integers, so we know what sort of addition to perform.

The inner block starts a new level, level 3.
{ int k;
char \fbox{type $\vert$0 $\vert$1 byte}  
int \fbox{type $\vert$0 $\vert$4 bytes}  
i \fbox{param $\vert$2 $\vert$2 $\vert$int} \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}  
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}  
c \fbox{param $\vert$2 $\vert$1 $\vert$char}  
mark \fbox{var $\vert$2 $\vert$1 $\vert$static int $\vert$0}  
result \fbox{var $\vert$2 $\vert$2 $\vert$char*}  
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}  
k \fbox{var $\vert$3 $\vert$1 $\vert$int}  

for (k = 0; k < i; k++) result [k] = c; }
char \fbox{type $\vert$0 $\vert$1 byte}  
int \fbox{type $\vert$0 $\vert$4 bytes}  
i \fbox{param $\vert$2 $\vert$2 $\vert$int} \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}  
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}  
c \fbox{param $\vert$2 $\vert$1 $\vert$char}  
mark \fbox{var $\vert$2 $\vert$1 $\vert$static int $\vert$0}  
result \fbox{var $\vert$2 $\vert$2 $\vert$char*}  
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}  
k    

As we exit level 3, the variable k is no longer visible, so we detach the corresponding property from the name-list. However, we retain the name-list entry for k, as it may occur again lower down.

result [i++] = 0; result [i] = ++mark; return result; }
char \fbox{type $\vert$0 $\vert$1 byte}
int \fbox{type $\vert$0 $\vert$4 bytes}
i \fbox{var $\vert$1 $\vert$1 $\vert$int}
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*}
  \fbox{param $\vert$2 $\vert$1 $\vert$char}
  \fbox{param $\vert$2 $\vert$2 $\vert$int}
c  
mark  
result  
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}
k  

As we exit level 2, we discard the declarations made inside it (c, i, mark, result). In particular, we have to reconnect i to its original declaration as a global variable. We don't completely discard the entries for the parameters, as we need them to check calls to fred lower down.

int main (void) {
char \fbox{type $\vert$0 $\vert$1 byte}    
int \fbox{type $\vert$0 $\vert$4 bytes}    
i \fbox{var $\vert$1 $\vert$1 $\vert$int}    
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}    
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*} \fbox{param $\vert$2 $\vert$1 $\vert$char} \fbox{param $\vert$2 $\vert$2 $\vert$int}
c      
mark      
result      
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}    
k      
main \fbox{fun $\vert$1 $\vert$? $\vert$int}    

char * string;
char \fbox{type $\vert$0 $\vert$1 byte}    
int \fbox{type $\vert$0 $\vert$4 bytes}    
i \fbox{var $\vert$1 $\vert$1 $\vert$int}    
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}    
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*} \fbox{param $\vert$2 $\vert$1 $\vert$char} \fbox{param $\vert$2 $\vert$2 $\vert$int}
c      
mark      
result      
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}    
k      
main \fbox{fun $\vert$1 $\vert$? $\vert$int}    
string \fbox{var $\vert$2 $\vert$1 $\vert$char*}    

i = 5;
At this point, for example, when we look up i, we find information describing it as a global variable, rather than a parameter of fred. string = fred ('a', i); printf ("%s, %d, %d\n", string, string [i+1], count);
char \fbox{type $\vert$0 $\vert$1 byte}    
int \fbox{type $\vert$0 $\vert$4 bytes}    
i \fbox{var $\vert$1 $\vert$1 $\vert$int}    
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}    
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*} \fbox{param $\vert$2 $\vert$1 $\vert$char} \fbox{param $\vert$2 $\vert$2 $\vert$int}
c      
mark      
result      
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}    
k      
main \fbox{fun $\vert$1 $\vert$? $\vert$int}    
string \fbox{var $\vert$2 $\vert$1 $\vert$char*}    
printf \fbox{fun? $\vert$1? $\vert$? $\vert$?}    

string = fred ('b', i); printf ("%s, %d, %d\n", string, string [i+1], count); return 0; }
char \fbox{type $\vert$0 $\vert$1 byte}    
int \fbox{type $\vert$0 $\vert$4 bytes}    
i \fbox{var $\vert$1 $\vert$1 $\vert$int}    
count \fbox{var $\vert$1 $\vert$2 $\vert$int $\vert$0}    
fred \fbox{fun $\vert$1 $\vert$? $\vert$char*} \fbox{param $\vert$2 $\vert$1 $\vert$char} \fbox{param $\vert$2 $\vert$2 $\vert$int}
c      
mark      
result      
malloc \fbox{fun? $\vert$1? $\vert$? $\vert$?}    
k      
main \fbox{fun $\vert$1 $\vert$? $\vert$int}    
string      
printf \fbox{fun? $\vert$1? $\vert$? $\vert$?}    

Parse Tree 

int     i

int     count   0

char*() fred
        ()      char    c
                int     i
        {}      st.int  mark    0
                char*   result  (char*) malloc  +       i
                                                        2
                +=      count
                        i
                {}      int     k
                        for     =       k
                                        0
                                <       k
                                        i
                                post++  k
                                =       []      result
                                                k
                                        c
                =       []      result
                                post++  i
                        0
                =       []      result
                                i
                        pre++   mark
                return  result

int()   main
        ()      void
        {}      char*   string
                =       i
                        5
                =       string
                        fred    'a'
                                i
                printf  "%s, %d, %d\en"
                        string
                        []      string
                                +       i
                                        1
                        count
                =       string
                        fred    'b'
                                i
                printf  "%s, %d, %d\en"
                        string
                        []      string
                                +       i
                                        1
                        count
                return  0

next up previous
Next: Left and Right recursion Up: CS2121: The Implementation and Previous: Example run of YACC
Pete Jinks
2004-10-26