CSCI 310 Spring 2008 Exam #2

Instructions: This exam is closed book, closed notes, closed neighbor, open mind. Show all your work in the space provided. If you need more space, use the back of one of the other exam sheets. Read through the entire exam before starting to answer any of the questions in order to answer the easiest questions first and maximize your score. There are 100 points on this exam (assuming I added correctly) not counting any bonus questions. You have 50 minutes to complete this exam. Good luck and have fun!

I. Imperative Languages (70 points)

a. Name the three analysis phases a compiler performs at the start of a compile and briefly describe the function of each.

b. What are two design decisions a language designer has to make when implementing variable names?

c. What strings are represented by the regular expression a{a|b|c}*?

d. Consider the grammar E->E+E | E*E | a | b . Use it to construct two different parse trees for the expression a*a+b.

e. Name two additional properties we can add to our language to remove the ambiguity described in question d. Modify the grammar given there to include these two properties as well.

f. What are the scope and the lifetime of a variable? Give an example where they would be different.

g. What is the dangling else problem? How do most modern programming languages solve the problem?

II. Prolog (30 Points)

a. Write a Prolog program to compute the following function:

b. Write a Prolog program to take a list of letters and to replicate each vowel. This would turn the list “Hello” into Heellooo”.

III. Bonus Questions (10 points)

a. Insert only plus and minus signs between some of the digits 01234567890 to get an expression whose value is 100.

b. If I go halfway to the town (which is 60 km away) at the speed of 30 km/hour, how fast do I have to go for the rest of the way to have the average speed of the entire way 60 km/hour?