CISC 670 Programming Languages (Fall 2002)

Midterm Sample Solutions

1.

1a.  False.  Formal languages (also called meta languages) determine 
only the syntax structure of programming languages. By adding semantics, 
programming languages with fairly simple syntax (specified by using CFGs) 
can be Turing complete, as evidenced by many existing Turing complete 
programming languages (e.g., the C language).

1b. True. In pure functional programming languages there are 
no assignments (in order to enforce referential transparency),
which makes a loop construct useless (for there is no way to
pass any side-effect to the outside of the loop).

1c. Not LL(1). Because of the common prefix between
<expr> ::= id = <expr> and
<expr> *=> id <term_tail>

Note: The notation *=> means zero or multiple derivations.
In this case, <expr> *=> id <term_tail> is arrived by combining
the following four productions.

<expr> ::= <term><term_tail>
<term> ::= <factor><factor_tail>
<factor_tail> ::= epsilon
<factor> ::= id


The original grammar reads

<expr> ::= id = <expr>
<expr> ::= <term><term_tail>
<term_tail> ::= <term><term_tail>|epsilon
<term> ::= <factor><factor_tail>
<factor_tail> ::= <factor><factor_tail>|epsilon
<factor> ::= (<expr>) | id


1d. False. Because global variables can have dynamic data as well. 
 


2a.

Note: This problem should have been fairly easy, but turns out 
      to be quite hard, mostly due to a confusion with homework 1.

The problem was to ask you translate the following regular expression
into a context-free grammar. 

xy*x|yx*y

The word "translate" here means that you rewrite
the grammar using context-free format such that the grammar still
accept the same language.

The original grammar (written in regular expression) accepts
sentences like

xx
xyx
xyyx
xyyyx
...

yy
yxy
yxxy
yxxxy
...


With the observation, obviously, the following context-free grammar 
will accept the same language.

<S> ::= x <Y> x | y <X> y
<Y> ::= epsilon | y <Y>
<X> ::= epsilon | x <X>

2b.
Note: This problem is mederately difficult. 

Saying a grammar is ambiguous means that there exists
expressions which you can get two different parse trees or more.

Therefore, the grammar

   <E> ::= <T> | <T> + <E>
   <T> ::= int | int * <E>

is ambiguous.

For example, the following are two parse trees for 1*2+3 

tree 1 ( parses the expression as 1*(2+3) )

                   <E>
                    |
                int * <E>
                /      \
               1    <T> + <E>
                    /      |
                   2      int
                           |
                           3

tree 2 (parses the expression as (1*2)+3 )

                  <E>
                   |
              <T>  +  <E>
               |        \
           int * <E>    <T>
           /      |       \
          1      <T>      int
                  |        |
                 int       3
                  |
                  2

As you can see, the ambiguity causes problem with precedence
order for operators + and *. The above grammar made attempts
to address the issue by distinguishing <E> from terms <T>
(<E> is composed of a term or summation of terms) 
and terms from factors (a term <T> can be a factor int or 
multiplication of factors).
However, the attempt failed at the last step by allowing
a factor to be <E> again. Probably, it meant to allow
a compound factor (that should be introduced by surrounding
<E> with a pair of parentheses). With such analysis, a quick
fix is to restrict factors as either int or <T>. This will
give the following grammar,

   <E> ::= <T> | <T> + <E>
   <T> ::= int | int * <T>
which accepts the same language but has no ambiguity.

Note: The fact that a grammar is not ambiguous does not mean
it can be parsed in certain ways. For example, the modified
grammar is not LL(1) because ofthe common prefix problem.

 

3.   

The problem was to draw the stack of activation records 
just before you hit the print statement in the following program: 

  void main () {
     int a;

     void F (int b) {
        /**** draw stack when code reaches here ****/
        print(a+b);
     }

     void G (int c) {
        void H (int d) {
          F (a+c+d);
        }

        H (a+c);
     }

     a = 1;
     G (a);
  }

For each activation record, you were supposed to show 
the name of the function, the control link, the access link, 
and the names and contents of local variables. 

The stack grows downward. 

   ^  -----------------  ^
   |  |     main      |  |
   |--|access  control|--|
 .>   |      a=1      |
 | .> ----------------- <.
 | |                     |
 | |  -----------------  |
 | |  |       G       |  |
 | |--|access  control|--|
 |    |      c=1      |
 | .> ----------------- <.
 | |                     |
 | |  -----------------  |
 | |  |       H       |  |
 | |--|access  control|--|
 |    |      d=2      |
 |    ----------------- <.
 |                       |
 |    -----------------  |
 |    |       F       |  |
 |----|access  control|--|
      |      b=4      |
      -----------------

The only part that should have been even vaguely tricky 
is the access link of F. We don't know exactly where 
the control/access links of main are pointing 
(in fact, they're probably null).


4. 

Note: This problem should have been fairly easy.

The problem was to write tail recursion for a function that
computes the sum of elements of a list of integers.

  fun rsum [] = 0
    | rsum (x::xs) = x + rsum xs;

In ML, a tail recursion can be written as

  fun rsum [] = 0
    | rsum [x] = x
    | rsum (x1 :: x2 :: xs) = rsum ( (x1 + x2) :: xs);

or

  fun rsum xs = let 
                     fun helper total_tmp [] = total_tmp
                       | helper total_tmp (x::xs') = helper (total_tmp + x) xs'
                in
                     helper 0 xs
                 end


5. 

Note: This problem should have been fairly easy.
 
The sample program was 

    int x = 0;
    int y = 20;

    void foo(int z) {
       x = x + 2;
       y = x + z;
       z = z + 7;
    }

    void main() {
       int x = 10;
       foo(y);
       print(x+y);
    }

General notations: 
x' - the local x defined in main (x'=10) 
x will be the x variable in function foo 
Call-By-Value, Lexical
                x       y       z       x'
foo(y)          0       20      20      10
x=x+2           2
y=x+z                   22
z=z+7                           27
print(x+y)              22              10

=> Result of Call-By-Value is 32

Note1: because of lexical scoping the value of x in print(x+y) 
       is the value of x'. 

Call-By-Reference, Lexical
                x       z/y     x'
foo(y)          0       20      10
x=x+2           2
y=x+z                   22
z=z+7                   29
print(x+y)              29      10

=> Result of Call-By-Reference is 39

Note1: same as in call-by-value.
Note2: in call by reference, variables y and z have the same location.

 
Call-By-Value-Result, Lexical
                x       y       z       x'
foo(y)          0       20      20      10
x=x+2           2
y=x+z                   22
z=z+7                           27
(copy out)              27
print(x+y)              27              10

=> Result of Call-By-Value-Result is 37

Note1 : same as for call by value.
Note2 : in call-by-value-result, initially z gets y's value 
        and then its value will be copied back in y. 

Call-By-Value, Dynamic
                x       y       z       x'
foo(y)          0       20      20      10
x=x+2                                   12
y=x+z                   32
z=z+7                           27
print(x+y)              32              12

=> Result of Call-By-Value, Dynamic is 44

Note1 : same as for call by value (lexical).
Note2 : Since we have dynamic scoping the variable x in foo 
        will actually be variable x' (which is the variable x 
         in function main).