PLI Tutorial 2
Lexical analysis 

(Lm.n refers to Louden, Exercise m.n.)

Make sure you have a warking account on dwarf, that you can access dwarf
using an SSH client (from home, establish a VPN connection first), that
you can compile and execute C programs on dwarf, that you have downloaded
and installed PLT Scheme (from http://www.plt-scheme.org/) on your
personal computer, and that you can define and call a Scheme function
using PLT Scheme.

Part A.  C programming.

1. Complete the binary search tree library from Tutorial 1.  Add a
function to print the integers in the tree in increasing order.

Part B.  Scheme programming.

1. If you have not already done so, download PLT Scheme (DrScheme) onto
your PC or onto your H: drive on the University network, read the Scheme
tutorial "Teach Yourself Scheme in Fixnum Days", study some of the
provided examples, and experiment.

2. Define a function (add key value dict) that adds a new (key,value) pair
to the given dictionary, replacing any previous pair with the same key,
and returns the updated dictionary.  See <a
href="../Resources/scheme-examples.txt">examples.scm</a> for initial
definitions of a dictionary management module.

3. Completely rewrite the dictionary management module by new functions
that use a binary search tree instead of linear search through a linear
list.

4. Use nested definitions to implement a tail-recursive definition of a
function that returns the n'th Fibonacci number (F_0=1, F_1=1, F_n =
F_{n-1} + F_{n-2} for n>=2). 

5. Think about how you might use nested definitions to implement a
dictionary management module in an object-oriented, information-hiding
style.  (A solution is provided on the Resources page but please try to 
solve the problem yourself before reading the solution.)

Part C.  Compilation and lexical analysis.

1. A compiler is a program which takes a program text as input.  List as
many other programs as you can that take program texts as input.

2. Discuss what is involved in (a) retargeting a compiler to produce
target code for a new machine and (b) rehosting a compiler to run on a new
machine.  Illustrate these two operations with T-diagrams (Louden, 1.6).

3. Translate the following Tiny program (Louden, Figure 1.4) into an
equivalent sequence of TM  instructions.

	{ Sample Tiny program - computes factorial }
	read x; { input an integer x }
	if x > 0 then 
	   fact := 1;
	   repeat
	      fact := fact * x;
	      x := x - 1
	   until x = 0;
	   write fact { output factorial of x }
        end

4. Write regular expressions for the following sets of strings, 
   or given reasons why no regular expressions can be written:

   a. All strings of lowercase letters that begins and end in a.
   b. All strings of digits that contain no leading zeros.
   c. All strings of digits such that all the 2's occur before
      all the 9's.
   d. All strings of letters, digits and underscores, starting
      with a letter.
   e. All binary numbers representing multiples of 3.
   f. All binary numbers representing prime numbers.

5. Write English descriptions for the sets of strings generated 
   by the following regular expressions:

   a. (a|b)*a(a|b|e) 
       where e denotes an empty string.

   b. (aa|b)*(a|bb)*c?

6.  In the definition of regular expressions, we described the
    precedence of the operations (*, then concatenation, then |), 
    but not their associativity.
    For example, we did not specify whether a|b|c meant (a|b)|c
    or a|(b|c) and similarly for concatenation.  Why was this?

7. Draw a DFA corresponding to the regular expression O (empty set).

8. Draw DFAs for each of the sets of strings in Exercise 1.

9. Draw a DFA for C comments: /* ... */

10. See Tutorial 3.