exam3

CS 288 Exam #3: Programming Languages

1. Consider the following grammar for Java import statement lists:

istatlist -> istatlist istat | istat
istat -> "import" name ";" | "import" name "." "*" ";" 
name -> name . <id> | <id>

Show how a bottom-up parser would parse the input

import Employee;
import java.util.*;

Show a sequence of "shift" and "reduce" steps

2. a. Compute the PREDICT sets of all productions of the grammar

istatlist -> istat | istatlist istat
istat -> "import" name tail ";"
tail -> "" | "." "*" 
name -> <id> | name . <id>

Recall these definitions:

FIRST(a) = { x: a =>* x b, x ∈T } ∪ (if a =>* ε then { ε } else {})
FOLLOW(A) = { x:S =>* u A x v, x ∈T } ∪ (if S =>* a A then { ε } else {})
PREDICT(A -> a) = FIRST(a) - {ε} ∪ (if a =>* ε then FOLLOW(A) else {})

b. Why is this grammar not LL(1)?

c. Modify this grammar so that you obtain an equivalent LL(1) grammar.

3. Using a grammar of your choice that describes Java import lists, produce an attribute grammar that accumulates two lists of strings singleclass and ondemand, collecting the class names of single imported classes (such as Employee in the example above) and of packages (such as java.util in the example above).

Assume that <id> has synthesized attribute val. Provide attributes singleclass and ondemand for the istatlist start symbol. Provide any other attributes of your choice. Denote string concatenation with +. To append a string s to a list l, write l.add(s).

4. The bash command shell has a rudimentary programming language. Here are some of its features.

You declare global variables with the syntax
```
varname=initialValue
```
You declare functions with the syntax
```
function funname
{
   . . .
}
```
Function parameters are not named. Instead, you refer to them as $1, $2, $3...
You call functions with the syntax
```
funname arg1 arg2 arg3 . . .
```
You declare local variables (inside functions) with the syntax
```
local varname=initialValue
```
You get the value of a variable with the syntax
```
$varname
```
For example, the command
```
echo $a
```
prints the value of a.

a) Write a short program that tests whether bash shell variables are statically or dynamically scoped. Specify the output you expect under static and dynamic scoping.

b) What is the advantage of static scoping over dynamic scoping? (Be brief.)

c) The bash programming language nevertheless uses dynamic scoping. Give a brief reason why that rule is being used.

5. Consider the following code in a C++-like language that supports nested procedures in the style of Pascal/Modula 2:

void work()
{
   int a = 3;
   int b = 4;
   int fib(int n)
   {
      if (n <= 0) return a;
      int x = a; 
      int y = b;
      for (int i = 2; i <= n; i++)
      {
         int z = x + y;
         x = y;
         y = z;
      }
      return y;
   }
   void print()
   {
      for (int i = 0; i <= 10; i++)
      {
         int n = fib(i); // 2
         cout << n << endl;
      }
   }
   print(); // 1
}

void main()
{
   work();
}

a) Write assembly instructions (in x86 assembler or pseudo-assembler) for the function calls to print and fib (labeled 1 and 2). Show how the parameters and the static link are pushed on the stack. Assume that the static link is pushed onto the stack immediately before a nested function is called. Assume that the dynamic link (frame pointer) is stored in the ebp register.

b) Draw a call stack that shows the local and parameter variables as well as the dynamic and static links when the first call to fib is executed.

c) Can work be modified to return a pointer to fib, so that the program has the following structure:

typedef int (*Fun)(int);
Fun work() { . . .  return fib; }
void print(Fun f, int from, int to)
{
   for (int i = from; i <= to; i++) 
      cout << (*f)(i) << endl;
}
void main()
{
   Fun f = work();
   print(f, 0, 10);
}

d) Write equivalent code in a language with closures (such as Scheme or JavaScript) to demonstrate that it is possible for work to return a closure with the action of fib that can be passed to print. Draw a diagram of the closure.

Many compilers for the x86 processor use the following function prologs and epilogs:

pushl %ebp         ; save old frame pointer
movl  %esp, %ebp   ; set frame pointer for this function
. . .
popl  %ebp         ; restore old frame pointer
ret

Afterwards, ebp points to the saved frame pointer. That is, the first local variable is accessed as -4(%ebp).