REVIEW FOR FINAL:

Topics from text we covered this semester and may be covered on final exam (You are also responsible for topics covered by class slides and other material covered in lecture and recitations.)

* -- Topics with an asterisk have an extremely high probability of appearing on the final. Other items may also be on final.

Chapter 1 -- Introduction

• 1.2 History of Programming Languages

Chapter 2 -- Language design issues

• 2.1 Simple machine hardware design
• 2.2 Virtual computers
• 2.3 *Language paradigms

Chapter 3 -- Language translation issues

• 3.1 *Syntax
• 3.3 *Formal grammars, *FSA
• (Ignore 3.3.4 on parsing algorithms)
• (Ignore 3.3.5 on semantic modeling)

Chapter 4 -- Data types

• All except 4.3.12 (files)
• *Array referencing, *Record storage, *Struct and *union types

Chapter 5 -- Encapsulation and memory management

• All
• *Garbage collection

Chapter 6 -- Sequence control

• All
• *Postfix, *Pattern matching, *unification, Statement flow control

Chapter 7 -- Subprograms

• All
• *Scope, *Parameter passing, *static and dynamic links and displays

Chapter 8 – Inheritance

• All
• Inheritance and derived classes, Methods and messages, Polymorphism

Chapter 9 -- Other topics

• 9.3.1 *Chomsky hierarchy of grammars

Languages:

• 12.1.7 Ada
• 12.2 C++
• 12.3 Smalltalk
• 13.1 LISP
• 13.2 ML
• 14.1 Prolog

Test questions will be similar to questions in: (1) your previous exams, (2) your homeworks, and (3) the sample questions below. The questions on the final may not be identical to any previously given questions but they will be similar in content.

SAMPLE QUESTIONS:

1. C supports only one parameter passing mechanism, what is it?
2. How is pass-by-reference simulated in C?
3. When do pass-by-name and pass-by-reference differ? There will be a section of code in which you will need to determine the difference.
4. When do pass-by-reference and pass-by-value-result differ? There will be a section of code in which you will need to determine the difference.
5. Which of the following languages support pass-by-reference? Which support pass-by-name?
   • C
   • C++
   • Pascal
   • ALGOL
6. What is a Display vector, and what is the max number of memory accesses needed to retrieve and non-local variable when a Display vector is used?
7. What information is stored in a display vector?
8. What information is stored in an activation record, list specific items.
9. True or False, when static scoping is used, activation records must contain an environment table listing the names and values of all local variables.
10. What is the "lifetime" of a variable. What is the "scope" of a variable. Give examples of when they are different?
11. In general, statically declared variables are stored in the _________, and dynamically declared variables are stored in the __________.
12. In C++, a call to "new()" is made for what purpose?
13. Is "fragmentation" a problem when variables are stored on the run-time stack?
14. How are "reference counts" used in memory management?
15. In the two-stage garbage collection algorithm referred to as "mark and sweep", explain what happens in both the mark stage and the sweep stage.
16. Name 2 languages that allow some form of "unification"?
17. What are the problems associated with recovery of variable-sized memory blocks in garbage collection.
18. True or False, in developing the first programming languages, the main concern was efficient utilization of machine resources and not ease of use by the programmer.
19. True or False, the earliest programming languages (before Fortran and Cobol) were compiled not interpreted.
20. True or False, the first programming language to use the concept of "block structure" was Fortran.
21. True or False, in block structured languages, parameter transmission is typically implemented using the run-time stack.
22. True or False, the ordering of symbols within a program is described by context-free grammars.
23. True or False, the tokens of a programming language are such things as keywords and identifiers. When parsing a program, the ordering of the symbols within a token are described by context-free grammars.
24. True or False, context-free grammars are sufficient to describe all programming language constructs.
25. True or False, Prolog is a functional programming language.
26. The theoretical computational power of C++, prolog, lisp, and Ada are all equivalent.
27. In C++ all objects are stored on the heap.
28. Define reference parameter.
29. Define syntax and semantics.
30. Define binding and binding time.
31. Define lifetime and scope.
32. Define static scope and dynamic scope.
33. Define dynamic type binding and static type binding.
34. Define weakest pre-condition.
35. The following are Smalltalk messages. In each case, identify the object receiving the message.
• ‘Hello World’ printNl
• 2+3
• [sum _ sum + index] value
36. What is the purpose of the keyword virtual in C++?
37. What is the minimum machine capable of recognizing a regular language?
38. What is the minimum machine capable of recognizing a context-free language?
39. Below is a set of grammar rules. With respect to the Chomsky hierarchy, what kind of grammar is this
• R = { S -> AB, S -> A, A -> a, B -> b}
40. Describe the difference between a Finite State Automata and a Pushdown Automata.
41. How does C++ support encapsulation?
42. How does Ada support encapsulation?
43. Identify the programming language used in each of the statements below (each statement may be written in a different programming language):
• function Sub1(X: real; Y:integer): real;
• void Sub2(float X, int Y, float *Z, int *W);
• procedure Sub3(X: in real; Y: in integer; Z: in out real; W: out boolean)
• (Sub3 X Y)
44. Draw the structure for the following Lisp expression:
• (a (b c) d (e))
45. Specify an automata to recognize {ab*a}.
46. Write a egrep regular expression to find all lines containing the expression Fred or Frederic G. Majors.
47. Show the parse tree for a top-down parse of the following sentence using the grammar specified below: The boy bounced the ball.

    S -> NP VP,

    NP -> N

    NP -> D N

    VP -> V

    VP -> V NP

    V -> ran | bounce | caught

    N -> cat | mouse | boy | girl | ball

    D -> the | a  

48. Consider the following program in a language that allows for nested scope:

procedure main 
  integer I; 
  integer A[0:4]; 
  for I=0 to 4 do A[I] = I; 
  I=1; 
  P(I,A[I]); 
  write(I,A[I]); 

  procedure P(integer A; integer B); 
    integer T; 
    A=A+1; 
    T=B+1; 
    I=I+1; 
    B=A+T; 
    write(A,B); 
  end P; 
end main; 
 

1. Assuming Call by Reference:
   1. What is printed for A?
   2. What is printed for B?
   3. What is printed for I?
   4. What is printed for A[I]?
2. Assuming Call by Value­Result:
   1. What is printed for A?
   2. What is printed for B?
   3. What is printed for I?
   4. What is printed for A[I]?
3. Assuming Call by Value:
   1. What is printed for A?
   2. What is printed for B?
   3. What is printed for I?
   4. What is printed for A[I]?
4. Assuming Call by Name:
   1. What is printed for A?
   2. What is printed for B?
   3. What is printed for I?
   4. What is printed for A[I]?
49. For the program above, assume the following addresses:
• Location of the instruction in the operating system which calls the main
• program is 400.
• Location of the call to P in procedure main is 600.
• Data storage for program begins at 900.
• Activation record for main begins at location 1000.
• Storage for array A begins at location 1050.
• Activation record for P begins at 1100.

Fill in the following values:

• Static link in P
• Dynamic link in P
• Virtual origin of A
50. Every activation record in C must contain:
• Static links
• Dynamic links
• Displays
51. Which statements are true?
1. C uses the mark­sweep algorithm to clean up the runtime heap.
2. LISP, ML and Smalltalk all use automatic garbage collection.
3. If C used reference counts, then dangling references would never occur.
4. Tombstones are a method for compacting storage during garbage collection.
52. Which statements are true?
1. C activation records do not need dope vectors
2. Smalltalk implements mixed inheritance
3. Functional programming can be done in C
4. Imperative programs can be written in Prolog
53. Give the Postfix (a) and value (b) for the C­language expression 8 + 4/2 - 5
54. What is printed by the following C program assuming write simply writes out the values:

main()
{
  union{ union {int A; real B} C; int D} E[4]; 
  E[1].C.A = 2; 
  E[1].C.B = 3; 
  E[1].D = 4; 
  write(E[1].C.A , E[1].D );
}

1. E[1].C.A
2. E[1].D

 

55. Consider the C++ program:

 
#include <stream.h> 
class top {
   public: top() {a=1;}; 
   void newfcn() {local();}; 
   protected: int a; 
   virtual void local() {cout<<a<<endl;};
}; 
class bottom: public top {
   public: bottom() {a=2;}; 
   protected: void local() {cout<<a<<endl;};
}; 
main() {
   top x; 
   bottom y; 
   x.newfcn(); 
   y.newfcn();
}

1. What is printed for x.newfcn?
2. What is printed for y.newfcn?
56. In the program above, what happens if virtual were deleted in the above definition?
1. What is printed for x.newfcn?
2. What is printed for y.newfcn?