CIS 425 Midterm Solution

Grammars

Here is a fragment of the grammar for a C-like language. The terminals of the grammar are LPAREN (a left parenthesis), RPAREN (a right parenthesis), and IDENTIFIER (a sequence of letters):
exp ::= cast |  call |  LPAREN exp RPAREN | IDENTIFIER

cast ::= LPAREN type RPAREN exp

call ::= function LPAREN argument RPAREN

function ::= exp

argument ::= exp

type ::= IDENTIFIER

Prove the syntactic ambiguity of the this grammar by finding a string that has more than one parse tree. Draw the parse trees.

Solution

A possible string is (x)(y) . It can be parsed as:


ML Datatypes

You are given a simple datatype of geometric shapes:
datatype shape = 
    Rect 
  | Square 
  | Circle 
  | Intersect of (shape * shape)
A shape is either a rectangle, a square, a circle, or created by intersecting two other shapes. For example, one can declare the following four shapes:
val s1 = Rect
val s2 = Circle
val s3 = Intersect(s1,s2)
val s4 = Intersect(s2,s3)
Write an ML function countC that counts the number of circles used in creating a shape:
- countC(s1);
val it = 0 : int
- countC(s2);
val it = 1 : int
- countC(s3);
val it = 1 : int
- countC(s4);
val it = 2 : int

Solution

fun countC Rect = 0
  | countC Square = 0
  | countC Circle = 1
  | countC (Intersect(s1,s2)) = countC(s1) + countC(s2)


Invariants

The C library assert.h can be used to check invariants at run-time. Here is an example program:
#include "assert.h"

main () {
  int x = 3;
  int y = 5;
  assert (x > 0 && y < 10);
  x = x+y;
  assert (x < 0);
}
When compiled and executed, this program prints:
Assertion failed: x < 0, file testassert.c, line 8
Abort
which indicates that the first assertion succeeded and that the second assertion failed.

A programmer developing a new fast multiplication algorithm carefully intrumented the code with assertions that would guarantee the correctness of the code:

int fastmul (int a0, int b0) {
  int result = 0;
  int a = a0;
  int b = b0;
  assert(result == a0*b0 - a*b);
  while (a >= 1) {
    assert(result == a0*b0 - a*b);
    if (a % 2 == 0) {
      result = 2 * result;
      a = a / 2;
    }
    else {
      result = result + b;
      a = a - 1;
    }
  }
  assert(result == a0*b0 - a*b && a == 0);
  return result;
}
Answer the following questions.


Types

In Homework IV, we wrote a type checker for a little language of expressions. For this problem, we will consider the problem of typechecking an even smaller language of expressions. Here is the code for the definitions and typechecker:
datatype BOp = PLUS | DIV | EQ

datatype Expression =
    Number of int
  | True | False
  | Binary of Expression * BOp * Expression

datatype ExpType = Integer | Boolean

exception TypeError

fun typecheck (Number(i)) = Integer
  | typecheck (True) = Boolean
  | typecheck (False) = Boolean
  | typecheck (Binary(e1,bop,e2)) = 
    let val t1 = typecheck(e1)
        val t2 = typecheck(e2)
    in case (t1,bop,t2) of 
        (Integer,PLUS,Integer) => Integer
      | (Integer,DIV,Integer) => Integer
      | (_,EQ,_) => if t1=t2 then Boolean else raise TypeError
      | _ => raise TypeError
    end
Answer the following questions:


Scope and Parameter-Passing

Consider the following C program:
#include 

#define count(N) { int i; for(i=1; i<=N; i++) { printf("%d\n", i); } }

void main () {
    int i;
    for(i=0; i < 3; i++) {
        count(i);
    }
}
Looking at the macro count(N), it appears that this macro prints all the numbers from 1 to N inclusive. The main program calls this macro three times as shown. What does the program print?

Solution Infinite loop printing

1
2
3
4
5
...

If we were to change the definition of count from a macro to the following function, what would the program print?

void count(int N) { 
    int i; 
    for(i=1; i<=N; i++) { 
        printf("%d\n", i); 
    } 
}

Solution

1
1
2


Extra Credit

What does each println statement produce?
class A {
    int x = 3;
    int f (int x) { return x+x; }
}

class B {
    int x = 4;
    int f (C c) { 
        c.x = 100; 
        c = new C();
        return x; 
    }
}

class C {
    int x = 5;
}

class Main {
    public static void main (String[] args) {
        int x = 6;
        A a = new A();
        B b = new B();
        C c = new C();
        System.out.println(a.f(x)); // ..............................
        System.out.println(b.f(c)); // ..............................
        System.out.println(c.x);    // ..............................
    }
}

Solution

12
4 
100


Visited times since September 21, 1999 (or the last crash).

sabry@cs.uoregon.edu