Your Name:
Analysis of Programming Languages Final Examination Sample Answers, Spring 2022
The test consists of 7 problems worth a total of 100 points.
1. (10%) Java classes ultimately evolved from C struct types. In what important ways are classes and structs (also known as records) different ? (Please confine yourself to semantics; if you do mention syntax, it should only be in order to explain semantics.)
Copyright By PowCoder代写 加微信 powcoder
Answer: Here are four important ways. In addition to data members, which C structs have, Java classes also contain class methods, including one or more constructors that are used when objects of the class are created; this can be used to ensure that the object is in a consistent and well-defined state. Members of a Java class can be declared ¡°private¡± making them off-limits to code outside the class. Java classes can inherit from other classes using ¡°extends.¡± Java does not allow class objects to exist directly as values; Java class objects can only be manipulated via references (that is, all class variables and parameters in Java are references).
2. (25%) The next three questions concern the the figure below, which represents an S- expression. Here, each cell has a car pointer on the left and a cdr pointer on the right. Symbols are just written as words without any cell.
(a) (10%) Write down the s-expression represented by the figure. Answer: (car (cons (quote (a b)) (quote (c))))
(b) (5%) Write down the s-expression that results from its evaluation Answer: (a b)
(c) (10%) Write a diagram of the cons-cell structure representing the resulting value.
3. (20%) Write a Scheme function named ¡°setify¡± which removes all repetitions in a list (thus making it a ¡°set¡±). Thus (setify ‘(a b a c d a d c)) should return (a b c d) (it doesn¡¯t matter if your function returns them in a different order). Then use this function to define a union function which takes two lists and returns the set of elements in their union. Thus (union ‘(a b c) ‘(c b f)) returns (a b c f).
(HINTS: You may use the built-in member function. Note if the first element of a list is contained in the rest of the list, you do not want to include it in the result; otherwise you do. Once setify is written, union is a one-liner using another built-in Scheme function.)
(define (settify L)
((null? L) ())
((member (car L) (cdr L)) (settify (cdr L)))
(#t (cons (car L) (settify (cdr L))))))
(define (union L1 L2)
(settify (append L1 L2)))
4. (10%) Each of the C functions below has a bug. Identify the bug and explain why its a bug. Suggest a fix that preserves the idea of the function.
char* triple(char* s) { char x[100];
strcpy(x, s);
strcat(x, s); // This function concatenates s onto the end of x
strcat(x, s);
Answer: triple() is returning a pointer to a local variable. The location at that address is on the call stack and will likely be overwritten by later calls. This is a dangling pointer bug. A reasonable fix would be to allocate x dynamically by replacing
char x[100];
// Allocate enough space for 3 copies and a null terminator
char *x = (char*) malloc(strlen(s)*3+1);
void longing() { char* l = “long”;
strcpy(l, “longer”);
Answer: longing() is copying to an address in the program¡¯s global section, which is where all string constants are. The global section of programs is read-only. The compiler allows this, but the program probably crashes at runtime. A reasonable fix is again to allocate l dynamically.
5. (15%) Draw the stack of activation records for the following C program after the second call to the function B. Also, what happens to the stack after that point?
void B(int);
void C(int);
int gval = 0; // global
void main() { gval = 1;
void B(int val) { if(val < 4) {
void C(int val) { gval = val + 1;
(NOTE: A more complete drawing here might also show the control links and return addresses in each activation record. But a key point is that gval is not part of any activation record.
Answer: The stack will continue growing as B() and C() call each other recursively until C() increments gval to 4 and calls B(), which will then return without calling C() and the stack will ¡°unwind¡± back to main().
6. (10%) Explain why a left-recursive grammar like the one shown below can¡¯t be parsed with a recursive-descent parser. Write a version of this rule in EBNF and explain how recursive-descent parsing works in that case.
expr ¡ú expr + term | term
Answer: The problem is that the recursive descent function for expr() will immedi-
ately call itself, leading to an infinite recursion. The EBNF version is: expr ¡ú term {+term}
This can be handled by writing the expr() function so that it calls term() and then loops while the current token is the +, calling getToken() and then term().
7. (10%) Consider the following Scheme function, ¡°r¡±. Assume that the argument passed to l is always an association list.
(define (r e l)
(cond ((null? l) '())
((equal? e (car (car l)))
(cons (car (cdr (car l))) (r e (cdr l))))
(#t (r e (cdr l)))))
(a) (5%) Compute the value of (r 'a '((a b) (q v) (a e))). Show how the re-
cursive calls work to compute the answer.
Answer: The function returns the value (b e). The recursive calls to the function are:
(r 'a '((a b) (q v) (a e))),
(r 'a '((q v) (a e))),
(r 'a '((a e))), (r 'a '()),
The fourth (last) call returns (), the third call returns (e) because (equal? ¡¯a ¡¯(a e)) is true. The second call also returns (e), and the first call returns (b e).
(b) (5%) What does this function do in general (again, assuming l is an association list)?
Answer: By using tail recursion, the function generates the list of all values in the association list l which match the key e. Only the values are returned, not the pairs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com