COMP712 Tutorial #5: Lexical Analysis
1. Identify all the terminal words of Lisp in the following Lisp program.
(defun funny (n)
(cond ((zerop n) 1)
( t (* n (funny (1- n))))))
s.leftbracket, s.defun, s.rightbracket, s.cond, s.zerop, s.number, s.t, s.*, s.1-.
2. Why is it a good idea to pre-hash reserved words in the symbol table?
If you don’t do so, you will need to have a list of all reserved words and whenever you read a name, you have to check from the list if it is a reserved word. If not, you go to the symbol table. This is highly inefficient since the list of words will be quite long and the number of variables used in a program is usually a lot. However, if you pre-hash it into the symbol table, and whenever you read a name, you can immediate hash it to the symbol table and find out what it is. If it is a reserved word, it will be in the table and if not, it is a user-defined name.
3. S.name and s.integer are two generic syntactic classes of a programming language. Give another example of a generic syntactic class.
s.string or s.real
4. Given the symbol table entry below, (i) how many variables are hashed to that location and (ii) discuss what happens when the lexical analyser reads x in the program below:
Begin
“x”
/
/
flags
/
:
:
Begin real x;
:
:
where flags are: declared: yes; type: s.x; reserved, block level: 0; offset: 0.
(i) 2 – look at the nametable. There is a chain from “x” to another variable whose namestring is not given. By the way, “/” means no pointer.
(ii) This is a trick question – Many of you believe that you would need to insert a new descriptor for x. Think again – when x is hashed into the table, an entry is found. You need to read the entry and see what it is. It says “x is a reserved word!”. If so, you can’t use it as a user-defined name. Your compiler should generate an error message (Instead of x, think of declaring “integer integer;”).
5. Name an important attribute of a hash code.
The algorithm should generate an efficient exhaustive sequence – ideally, every location should be probed exactly once before the table is declared full.
6. A symbol table can hold more than one descriptor for each variable. Why is this the case?
This is because the same name can be used again as a new variable in other parts of the program.
7. What can you say about X?
“x”
flags
/
X is the name of a procedure. This is because P3 is not empty.
8. If a language, L, is implemented with a symbol table as shown below, what can you say about L? What is an alternative approach for providing storage for variables?
L does not allow recursive function definition – read static allocation in the lecture slides. The other alternative is to use dynamic allocation.
10. What are the two key routines used during the lexical analysis phase?
A routine that reads in the characters and another that looks up the word in the symbol table.
11. Write a function, Drop-x, that given a number, x, and a list will return the list with the first x elements removed. X is a number between 0 and 3.
> (drop-x 0 ‘(a b c d))
(a b c d)
> (drop-x 2 ‘(a b c d))
(c d)
> (drop-x 3 ‘(a b))
nil
;; given X is so small, a straightforward test of what x is will do the job.
;; however I put test for zero last so that it will return the list for any
;; other X.
(Defun drop-x (x L)
(cond ((= x 1) (cdr L))
((= x 2) (cddr L))
((= x 3) (cdddr L))
(t L)))
12. Write a function, RDrop-x, that given a number, x, and a list will return the list with the last x elements removed. X is a number between 0 and 3.
> (drop-x 0 ‘(a b c d))
(a b c d)
> (drop-x 2 ‘(a b c d))
(a b)
> (drop-x 3 ‘(a b))
nil
(Defun rdrop-x (x L)
(cond ((= x 1) (reverse (cdr (reverse L))))
((= x 2) (reverse (cddr (reverse L))))
((= x 3) (reverse (cdddr (reverse L))))
(t L)))
Or, use the function you have already defined:
(defun rdrop-x (x L)
(reverse (drop-x x (reverse L)))