关于算法:COMS-W4115翻译器的实现原理

COMS W4115 Programming Languages and Translators
Homework Assignment 3
Submit this assignment online via Courseworks as a PDF file. Fill in or annotate this PDF or print it out, write on it, and scan it.
Please keep your answers in the boxes.
Do this assignment alone. You may consult the instructor and the TAs, but not other students.
Name: Uni:

1. (20 pts.) For the following C array on a processor with the usual alignment rules,
   i n t a [2] [3] ;
   (a) Show the order in which its elements are arranged in memory.
   (b) Write an expression for the byte address of ai in terms of a (the address of the start of the array), i , and j .
   (c) Verify parts a) and b) by writing a small C program that tests your hypothesis. Examine the assembly language output with
   the C compiler’s -S flag (e.g., gcc -O -S array.c). Such a program should be simple and contain and access such an array,
   but not be so simple that the compiler optimizes most of it away. On the next page, include in an annotated assembly
   listing that explains how it verifies your hypothesis. Make sure the assembly listing is no more than about 40 lines, either
   by simplifying your program or trimming the output.
   C program:
   1
   Assembly listing:
2. (20 pts.) For a 32-bit little-endian processor with the usual alignment rules, show the memory layout and size in bytes of the
   following three C variables.
   union {
   s t r u c t {
   char a ; / 8 – b i t /
   i n t b ; / 32 – b i t /
   shor t c ; / 16 – b i t /
   } s ;
   s t r u c t {
   i n t d ; / 32 – b i t /
   shor t e ; / 16 – b i t /
   } t ;
   } u1 ;
   Layout:
   Size in bytes:
   s t r u c t {
   char a ;
   i n t b ;
   shor t c ;
   shor t d ;
   } s1 ;
   Layout:
   Size in bytes:
   s t r u c t {
   shor t a ;
   char b ;
   shor t c ;
   char d ;
   shor t e ;
   } s2 ;
   Layout:
   Size in bytes:
3. (20 pts.) Draw the layout of the stack just before bar is called in foo. Indicate storage for function arguments, local variables,
   return addresses, and stored frame pointers. Indicate where the stack and frame pointers point.
   void bar (i n t x , i n t y , i n t z) ;
   void foo (i n t a , i n t b) {
   i n t d , e ;
   bar (2 , 5 , 7) ;
   }
4. (20 pts.) Draw the layouts of s1 and s2 and the virtual tables for the Ellipse and Square classes.
   pub l i c c l a s s Shape {
   double x , y ;
   pub l i c double area () { . . .}
   }
   c l a s s E l l i p s e extends Shape {
   p r i va t e double height , width ;
   pub l i c double area () { . . .}
   }
   c l a s s Square extends Shape {
   p r i va t e double width ;
   pub l i c double area () { . . .}
   }
   pub l i c c l a s s Main {
   pub l i c s t a t i c void main () {
   Shape s1 = new Square (10 , 3 , 1 4) ;
   Shape s2 = new E l l i p s e (3 , 8 , 2 , 6) ;
   System . out . p r i n t l n (s1 . area () ) ;
   }
   }
   Square Virtual Table:
   s1 object:
   Ellipse Virtual Table:
   s2 object:
5. (20 pts.) For the program below written in a C-like language with nested function definitions,
   void main () {
   i n t x = 5 ;
   void bar () {
   x = x + 2 ;
   }
   void foo () {
   i n t x = 8 ;
   bar () ;
   p r i n t f (“%d\n” , x) ;
   }
   foo () ; / Body o f main () /
   }
   What would it print if the language used static scoping?
   What would it print if the language used dynamic scoping?