PAPER DESCRIPTION: Programming Languages
PAPER CODE: COMP712
TIME ALLOWED: 1 Hour
TOTAL MARKS: 30
INSTRUCTIONS:
- Answer ALL the questions. This exam script has 5 pages.
- This is a closed book exam.
- Dictionaries and thesaurus are allowed
- All handheld devices are NOT allowed
- You may write your answers below each question or on a separate piece of paper.
- Remember to write your name on your answer sheet.
- No communication with anyone in any form is allowed.
- Don’t sit too close to each other.
Please write your answers on the exam script. If you need more paper, please ask.
Q1: Answer all questions (1 mark each)
(a) What is the second major phase in the design of a compiler? Syntax analyser
(b) Which grammar below is a right-linear grammar: 3
(c) What is a nondeterministic FSM?
One whereby the transition from one state to another cannot be determined until we know what the actual input is.
(d) What underlying machine is needed to support a Type 1 grammar? FSM
(e) Give an example of an effective procedure for deciding if a function is computable or not.
Turing machine or Lambda calculus
(f) In what sense can we say that Prolog is no more powerful than LISP?
They are both turing equivalent
Q2: Evaluate all the LISP forms below and if successful, write down what is returned. If not, write error (1 mark each):
(a) (caddar ‘(a b c d e f g)) error
(b) (numberp 5) T
(c) (append ‘(a (b c)) ‘(d e) (list ‘f)) (a (b c) d e f)
(d) (+ (1+ 1) (or 2 3 4)) 4
(e) (list (list (list (a b c d)))) error
(f) (list (cons ‘a ‘(b c))) ((a b c))
Q3: Answer all questions (2 marks each)
(a) Provide an example to show that the grammar of English is not type 2.
English is context sensitive as shown in sentences like “He likes apple vs *They likes apple”
(b) Give two reasons so many different programming languages are created?
For different purposes and for providing different problem-solving paradigms
(c) Why do we assume that the tape in a Turing Machine is infinite?
The size of the tape should not be a factor for deciding whether a function is computable or not
(d) What are the two major tasks of a lexical analyser?
To generate tokens belonging to that language and to create a symbol table for variable names
(e) Why is a regular grammar not powerful enough for supporting programming languages and what type of Chomsky’s grammar should one use instead?
Regular grammar does not support recursion and one must use at least a type 2 grammar
(f) In a symbol table, what are the pointers P2 and P3 for?
P2 is the pointer to the name string of the variable and P3 is the pointer to the procedure code.
Q4: Write a LISP function, rev-less-two, which given a list will return the reverse of the list but without its last two elements. For example:
(rev-less-two ‘(1 2 b (c 3) d))
(b 2 1)(rev-less-two ‘(2 4 6 8))
(4 2)(rev-less-two ‘(2 4))
()
[2 marks]
(defun rev-less-two (L) (cddr (reverse L)))
1 1
Q5: Write a LISP function, add-all-list, which given a list of lists of numbers will return a list the sum of each list. You may assume the function, add-list, is available which given a list of numbers will return the sum of all the numbers in it. Some examples are given below:
(add-list ‘((8 3) (6 1 2 3) (7 1)))(11 12 8)
(add-list ‘((1 2 3 4))
(10)
[4 marks]
(defun add-all-list (L)
(cond ((null L) nil)
(t (cons (add-list (car L)) (add-all-list (cdr L))))))
1 1 1 1
End of Examination