COMP 80 - Programming Languages
- Spring 2008

Sample Questions for Midterm Exam

- 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.
- 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`. - 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.

- 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.
- What is a symbol table?
Briefly describe what services a symbol table for dynamic scope needs to
provide and how these can be implemented.
- 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?
- 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;

- 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));

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

- Write a ML function
`log3`that take a positive integer input and returns the integer such that . (This is the integer part of the logarithm base 3 of .) So`log3(7)`returns`1`,`log3(25)`returns`2`,`log3(28)`returns`3`, and`log3(81)`returns`4`. - 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 getval a = [1,2,3,3,5,6] : int list val b = [1,3,9,10] : int list

This document was generated using the
**LaTeX**2`HTML` 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