Directions

You have until the start of class on 10 April to hand in this extended quiz. The answers to the questions must be typed to be accepted. No late submissions will be accepted. If any outside sources are used they must be cited. Each question is weighted equally.

Questions

1. Illustrate with an example code fragment that shows that record variants can be used to usurp an otherwise type safe language.

2. In two or more paragraphs, discuss the role of inheritance of implementation and inheritance of interface during multiple inheritance in Java? You may want to support your answer with code fragments.

3. Explain the differences between arrays in C++ and arrays in Java. Your discussion should consider at least 5 similarities and differences. Illustrate each difference with a code fragment.

4. If possible using only the algorithm I showed you in class, remove the left recursion from the following grammar, if not explain why you cannot remove the left recursion. (Note: Any symbol not on the left hand side of any production is a terminal symbol)

C -> Q * C | C @ Q | d | e

Q -> Q & F | Q # F | F | C

F - > a | b | c

5. If possible using only the algorithm I showed you in class, remove the left recursion from the following grammar, if not explain why you cannot remove the left recursion. (Note: Any symbol not on the left hand side of any production is a terminal symbol)

Z -> Y % X | Z ( Y ) | 6 | 9

X -> Z * X | X / Y | W

W -> a | b | D

6. Write a method in Java that takes an array of elements and returns a new array that has the duplicate elements removed. The size of the returned array must be the same as number of unique elements of the original array. The code should work for an array of elements any type except the types that are built into the language (e.g. int, float etc.)

7. Consider the following class in C++:

class Example {

private:

int i;

// …

};

Is it ever possible to change the value of the instance variable i in the class Example from outside a method in that class? If not, explain why not. If so, illustrate with a code example and explain that code example.

8. Prove that the following grammar is ambiguous

<A> - > <A> @ <A> | <id>

<id> - > a | b | c

9. Rewrite the following grammar expressed in EBNF to be in BNF

g -> [ l ] { a b } <m>

l -> z { z }

m -> x [ y ] z

10. Given the following BNF:

<exp> -> { <list> } | ( <list> ) | [ <list> ] | <char>

<list> -> <list> , <exp> | <exp>

<char> -> a | b | c | d | e

Show the parse tree (if possible) for

( ( [ a , b, { c } ] , e ) c, { b } )

11. Give the EBNF specification for the language L that is made up of the chars a,b and c such that sentences in the language have the form

L : sqs^R

where

· s is a string of any combination of the characters a and b

· s^R is just that same string s reversed

· q is an odd number of c's followed by either an even number of b's or an even number of a’s.

12. Translate the following grammar expressed in EBNF into BNF

<goal> -> { a b [ <bar> ] } [<foo>] (<bar> | <baz>)

<bar> -> b [ e ] f

<foo> -> d { d e}

<baz> -> g { g }

13. In class we discussed two definitions of Object Orientation. One typically attributed to Bjarne Stroustrup, the author of C++ and the other attributed to Allan Kay, the author of Smalltalk. Discuss in a few paragraphs whether C++ and Java would be characterized as Object Oriented by each of these definitions. Be specific and illustrate your discussion with code fragments to prove your point.

14. Write a program in Java that takes all the strings given as arguments concatenates them and then tokenizes the result using vowels as delimiters. Each token should be printed to the standard output. (Hint: There is a constructor for the StringTokenzer class that takes both the String to be tokenized as well as a string of the characters that act as delimiters.