CSE 428, Spring 98: Solution of the Final Exam =============================================================================== Exercise 1. 1) The grammar is not ambiguous 2) a) * is left-associative b) -> is right-associative c) * has precedence wrt to -> 3) The trees are the following (we abbreviate the names of the syntactical categories for graphical reasons) T T /|\ /|\ / | \ / | \ Tte -> T Tte -> T | | | /|\ Tfa Tte Tfa / | \ /|\ | | Tte -> T / | \ Tfa Tva | | ( T ) | | Tfa Tte /|\ Tva alpha | | / | \ | Tva Tfa Tte -> T gamma | | | | beta Tva Tfa Tte | | | gamma Tva Tfa | | alpha beta ------------------------------------------------------------------------------- Exercise 2. We write the function in Pascal: function GCD(x,y:integer):integer; begin while not(x=y) do if x > y then x := x-y else y := y-x; GCD := x end ------------------------------------------------------------------------------- Exercise 3. 1) The output is 5 2) The output is 7 ------------------------------------------------------------------------------- Exercise 4. 1) ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c 2) ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c 3) ('a -> 'b -> 'c -> 'd) -> 'b -> 'a * 'c -> 'd ------------------------------------------------------------------------------- Exercise 5. fun insert emptybt x = consbt(x,emptybt,emptybt) | insert (consbt(y,lst,rst)) x = if x = y then t else if x < y then consbt(y,insert lst x,rst) else consbt(y,lst,insert x rst) ------------------------------------------------------------------------------- Exercise 6. eliminates([],[]). eliminates([X|L],M) :- member(X,L), eliminates(L,M). eliminates([X|L],[X|M]) :- not(member(X,L)), eliminates(L,M). ------------------------------------------------------------------------------- Exercise 7. The following is a possible solution template class list : public node{ private: list *next; public: list(T x){info = x; next = NULL;} list(T x, list *n){info = x; next = n;} T head(){return info;} list *tail(){return next;} friend class btree; }; template class btree : public node{ private: btree *leftsubt; btree *rightsubt; list *append(list *l1, list *l2){ if (l1 == NULL) return l2; return new list(l1->head(),append(l1->tail(),l2)); } public: btree(T x){ info =x; leftsubt = NULL; rightsubt = NULL; } btree(T x,btree *l, btree *r ){ info = x; leftsubt = l; rightsubt = r; } list *invisit(){ if (this == NULL) return NULL; return append(leftsubt->invisit(), new list(info, rightsubt->invisit()) ); } };