COMP 80 - Programming Languages - Spring 2008

Sample Questions for Midterm Exam

  1. Describe, in a few sentences what is done in the semantic analysis phase of compilation and how it uses the result of the syntax analysis.

  2. For this question assume that the alphabet is exactly the letters a, b, c. Give a regular expression that generates exactly the strings that have either exactly one a or at least 3 occurrences of b.

  3. You are given the following grammar where the start symbol is S, upper case letters are non-terminals and lower case letters are terminals.
    S --> ab X X
    X --> c X | d Y Y
    Y --> S | e Y | y
    

    Does the string abcdey have a derivation?

    Does the string abdeabcdeyy have a derivation?

    Does the string abcdeyydyy have a derivation?

    Assuming you answered yes for at least one of the above give the parse tree for the string.

  4. Typically programming languages utilize 3 kinds of memory allocation strategies: static, stack based, and heap based. Explain how the heap manager handles requests for allocation and deallocation of memory.

  5. What is a symbol table? Briefly describe what services a symbol table for dynamic scope needs to provide and how these can be implemented.

  6. Discuss the main ideas for compiling switch/case statements. Are they typically more efficient or less efficient than an equivalent if-else-if sequence? Why?

  7. For each of the following ML expressions give the result and its type or in case there is an error explain what it is.
    if (true > false) then 10 else 100;
    
    
    let 
      val x = (4,#"A",5,"mid")
    in
      #4(x)
    end;
    

  8. What is the type of the following ML function? Explain how the type can be inferred.
    fun f(a,b) = (size(b ^ "B") + 1, real(a+1));
    

  9. What is the type of the following ML function? Explain how the type can be inferred.
    fun f(a,b) = a :: hd(b) :: [];
    

  10. Write a ML function log3 that take a positive integer input $n$ and returns the integer $d$ such that $3^d \leq n < 3^{d+1}$. (This is the integer part of the logarithm base 3 of $n$.) So log3(7) returns 1, log3(25) returns 2, log3(28) returns 3, and log3(81) returns 4.

  11. Write a function in ML that takes two sorted integer lists as input and produces a sorted merged list as illustrated by the following examples. The type of the function is:
    val merge = fn : int list * int list -> int list
    
    and when running the function with:
    val a = merge([1,3,5],[2,3,6]);
    val b = merge([10],[1,3,9]);
    
    we get
    val a = [1,2,3,3,5,6] : int list
    val b = [1,3,9,10] : int list
    

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation -no_images -dir TEMPHTML msample.tex

The translation was initiated by Roni Khardon on 2008-02-26


Roni Khardon 2008-02-26