Midterm 2 key available

I've graded today's midterm and posted a key.

Overall you did well.  Maybe it was a bit too easy, but I'm satisfied that it showed you had a grasp of the material.  I don't think judging finer gradations of how deeply you understand one topic or another was something I could reasonably expect from a one-hour exam that covered so much material.

Sample final exam questions

We can discuss these in class on Wednesday, but you might want to try to work them out yourself in advance.

The first two are from a take-home exam.  Questions for take-home exams are written with the assumption that people can use search engines and compiler tools, and without quite the time constraint of an in-class exam.

---

1. Suppose class B extends (is a subclass of) class A, and we have a method M with the following Java signature:
B M(B o)
or, in Cool syntax
M(B o): B

The Java and Cool type systems do not allow passing an A object to M, but they do allow assigning the return value of M to a variable of type A. Why?

Be brief but clear and concrete. Don't tell me it is because it would be a violation of the type rules; I want to know why those type rules are in Java and Cool.

---

2. Storage for a Java variable of type int is allocated in the stack (activation record), as is storage for other primitive values like booleans. However, while references to objects are stored in the stack, storage for the objects themselves (including for example Int objects) is allocated in the heap. Why the difference? Be clear, precise, and brief.

---

The next question makes more sense if you are familiar with stack architectures and stack-oriented virtual machines (e.g., JVM), which we did not talk about this term. Nonetheless you may be able to figure it out.

---

3. Some of you generated code for the stack-oriented Java virtual machine, and some of you generated code for a physical processor with registers. If you generated Java byte code, you had to calculate the maximum number of stack slots required for expression evaluation. It is relatively simple to translate stack-oriented code into register-oriented code, provided you have as many available registers as the maximum required stack depth. Briefly describe how, and illustrate with an example of translation from postfix or stack-oriented code to register  oriented code for the expression

a + b − (c + d).

---

I'll try to make up a few new questions before Wednesday, since my stash of (suitable) old questions seems pretty small.  Ideally I would like to cover type checking, code generation, data flow analysis, and register allocation.  Realistically, in a 50-minute exam, I will not be able to cover everything, and it will difficult to craft questions that require some real understanding and yet can be answered quickly.  Probably there will be less of the "explain why" kind of question and more of the "generate code for this" kind of question, though there may be some of each.

Reminder - LALR(1) quiz tomorrow (Friday)

Remember, tomorrow (26 Feb) I will give a quiz (short midterm) so you can show that you've mastered the LR(0) and LALR(1) parsing material that gave you trouble on the first midterm. 

Midterms are graded

... and will be handed back at the end of class on Monday.

Scores overall are pretty low, and what I learned from grading them is that we really aren't done with LR parsing  (LR(0) and especially LALR(1)) yet.  Some of you are close to mastering it, some are pretty lost, and many are somewhere in between. 

Why do I even care?  After all, we've got nice programs like bison and cup to do this for us.  But I do care, because LR parsing is an exemplar of a couple important algorithmic patterns:

• Treating a back-tracking problem (searching for a parse tree) as a non-deterministic search (sending angels out to scout different possible parses) and then, because the number of branches we need to explore is finite, folding them together into a deterministic algorithm (just like the subset construction from NFA to DFA).  This is a powerful pattern that has other applications. 
• Applying a set of rules (adding new items (productions) in a CFSM state) until none of the rules change anything.   We'll see this again in data flow analysis, and it appears in other domains as well.  Often we can look at a problem this way or in other ways, but this way is simpler and clearer.  For example, although most textbooks describe computation of "first" and "follow" sets in other ways, the simplest description is in terms of a set of recursive set inequalities that can be applied over and over until nothing changes. 

Could you grok this just as well without mastering the details of LALR(1) parse table construction?  Maybe ... but I think it helps.  As an analogy, consider that you studied and were expected to really understand red-black trees in data structures, even though there are perfectly good implementations of red-black trees available to you in libraries.    But red-black trees illustrate important concepts about maintaining balance within an acceptable bound and rebalancingwith local operations.  You'll forget the details, but the concepts stick partly because you mastered those details once. You'll forget the details of LALR(1) parsing approximately Wednesday of spring break (and so will I, and then relearn it once again next time I teach it), but the important concepts will stick better if you force yourself to really, really understand it inside and out for at least a little while. 

Old midterms

The questions we did on the board today come from 2006. 

• Midterm 2006 
• Midterm key, 2006 

You might want to start with the version without the key, and only then look at the key.

There are a few older midterms available too ... but no keys for them.

• Midterm 2005 
• Midterm 2001 

I haven't reviewed these older midterms and am not sure how closely they match what we've been doing this term.  I used to spend more time on LL parsing, which I passed over quite quickly this term so that we could start building the parser sooner.

By the way, I was asked whether you should know how to construct First and Follow sets.  Yes, please do.  Note that First is used in LALR(1) parsing as well as LL parsing.  Follow is not used in LALR(1), but the lookahead sets we calculate are closely related, and you should be able to convince yourself that the lookahead set for an LALR(1) item is always a subset of the corresponding Follow set.

Another sample midterm question

I already mentioned this in lecture, and you may remember it ... but it's worth thinking through.  This question was required for students in CIS 561 and optional extra credit for students in CIS 461.

L is the set of all sequences of one or more decimal digits in which each digit appears at most once.  For example, "0152" is in L, and "520" is in L, but "9525" is not in L  (because 5 is repeated).

Is L a regular language?  If it is not regular, why not? If L is regular, how many states are in the smallest DFA that recognizes L?

Sample grammar question from a previous midterm

Here's a question I asked on the midterm in 2006.  It's probably a pretty good indication of the sort of thing you should be able to do on the midterm this year. 

Consider the following grammar. (The terminal symbols are $ (end-of-file), i , “+”, and “;”.  "epsilon"  is used to mark an empty right-hand-side.)

Pgm ::= Block $
Block ::= Block E Sep
Block ::= E Sep
E ::= E "+" i
E ::= i
Sep ::= ";"
Sep ::= epsilon

Part a (5 points): Which of the following strings are accepted by the grammar?
i + i ; i + i
i i i ; i i
; i ; i
i + + i ;
i + i + i ;

Part b (15 points): Show that the grammar is not LR(0), but an LR(0) conflict is resolved using LALR(1) lookahead.  (Just show enouggh states to show how one conflict in the LR(0) machine is resolved in the LALR(1) machine.)

Schedule: Two midterms and no final?

I will attend a workshop in Germany during finals week.  In principle I could ask someone to proctor a regular final exam and scan and email the exams to me, and I could grade them from Germany ... but it would be a rush job, and too much could go wrong (e.g., some huge blunder in an exam question and me not there to explain what I meant).  So ... what to do?

The best I can think of is two midterms instead of a midterm and a final --- and then put a bit of space between the second midterm and the final project due date, so they don't interfere too much.  I'm thinking final project due Monday of dead week, second midterm on Wednesday or Friday.  Comments?  Better ideas?