=========================preview======================
(COMP251)e446d4 - 07final.pdf
Back to COMP251 Login to download
======================================================
COMP 251L2: 2007 Fall Semester Final Exam

Date Monday, Dec 17, 2007 Time 8:30 -11:30pm Instructions: (a) This exam has EIGHT questions.
(b)
Attempt ALL questions.

(c)
Write ALL answers in the given blue book.

(d)
The total mark is 100.


For Prolog questions, you can use the following relations (this does not mean that you have to use them):
/* append(x,y,z) -z is the concatenation of x and y */
append([],X,X).
append([X|Xs],Y,[X|Z]) :-append(Xs,Y,Z).

/* member(x,y) -x is an item in the list y */
member(X,[X|_]).
member(X,[_|Xs]) :-member(X,Xs).

/* \+ G -if G is not true */
\+ G :-G, !, fail.
\+ G.

If you need to use any other relations, you have to de.ne them.
Problem 1 (15 pts) Write an SML function sym = fn: a list -> bool such that sym(x) returns true if and only if for some y, x is y@y.
Problem 2 (10 pts) Write a Prolog program that computes the same relation sym(x) as above.
Problem 3 (5 pts) Write a context-free grammar for generating all strings in a* that have the form WW for some string W.
Problem 4 (15 pts) Consider the following Prolog program
r1: roo(X,[X|Xs]). r2: roo(X,[_|Xs]) :-roo(X,Xs).
r3: roo1(X,Xs) :-roo(X,Xs), !, X < 2. r4: roo1(_,_).
r5: roo2(X,Xs) :-roo(X,Xs), roo1(X,Xs).
Find the .rst answer to each of the following queries by drawing the Prolog search tree for it. In your search trees, label all arcs with rules and MGUs.
1.
roo1(X,[3,1]).

2.
roo1(2,[3,1]).

3.
roo2(X,[3,1]).


Problem 5 (10 pts) Consider the following function in C:
static void yy_flex_strncpy (char* s1, yyconst char * s2, int n )
{
register int i;
for ( i = 0; i < n; ++i )
s1[i] = s2[i];
}

Describe the content of the activation record when the function is called yy_flex_strncpy (a, b, k).
Problem 6 (10 pts) Consider the following Bison .le (we have checked the question carefully and there are no typos):
%{
#define YYSTYPE double
#define YY_NO_UNPUT
using namespace std;
#include <iostream>

int yyerror(char *s);
int yylex(void);
int yyparse();
%}

%token NUM
%left * /
%left - +

%% /* Grammer rules and actions follow */

input: /* empty */ | input line ;
line: \n | exp \n { cout << $1 <<endl; } ;
exp: NUM { $$ = $1; } | exp + exp { $$ = $1 + $2; } | exp - exp { $$ = $1 -$3; } | exp * exp { $$ = $1 * $3; } | exp / exp { $$ = $1 / $2; } ;
%%

/* Additional C++ code */

int main() { return yyparse(); }
int yyerror(char* s)
{
cout<<s<<endl;
return 0;
}

Suppose that we have a scanner that will recognize numbers as token NUM, what are the output when the bison .le is compiled and run on each of the following inputs:
1.
1+2\n

2.
3-1\n

3.
9-2*3\n


Problem 7 (15 pts) Write an SML function conj = fn: a list -> a list -> a list such that conj x y returns the list consisting of the items that are in both x and y. The returned list must not contain any duplicate items. The orde