mt1 sol

mt1.md

I am still working on grading the midterms and hope to be done before class. In the meantime, here are some detailed comments on individual questions, based on what I have seen so far; sorry, I have not proofread these comments so there may be mistakes/typos:

1. This was about the use of intermediate languages in compilers and interpreters. Many got parts of this wrong. For example, using int. lang. doesn't improve efficiency; it can even reduce it (because of compiling in two stages rather than directly to machine language). Some people seemed to think that Java is the only language that uses this approach and that byte code is the intermediate language. Not true. C is the most commonly used intermediate language. When a new machine is built these days, they typically only write a C compiler for it because other languages typically have compilers that translate into C. Finally, the approach doesn't make any difference to the user of L because that user only cares about the features available in L, not how it is implemented. Some said that if an intermediate lang. approach is used, chances are L will be implemented on many machines so that makes L more useful for its user. But the same would be true if L was implemented separately (without use of an intermediate lang.) on each machine.

2. This was about one-token-look-ahead. Most people got this. But there were a couple who claimed that if we use concrete (instead of abstract) parse trees, OTLA becomes relevant not just for parsing but also printing and execution (because the tokens are on the tree). Not true. OTLA is simply the way that the parser uses to access the tokens from the input stream. It doesn't have anything to do with whether we are going to keep them in the parse tree or not.

3. This was about the revised grammar for . Most people said the grammar was amibiguous. And it is. Because given a sequence of three statements, "S1; S2; S3", we can create two different trees:

      <stmt seq>                            <stmt seq>
   

   ---------|--------- ---------|--------- | | | | | -------|------- -------|----- | | | | | | | S1 | | | | S3
   | | | | S2 S3 S1 S2

The key point is that although the two trees are different, semantically it doesn't matter which one the parser produces. In both cases, S1 will be executed first, then S2, then S3. Thus this ambiguity is harmless.

4. This was about which of a given set of conditions was context-free/ context-sens./runtime and why. Most people got this. The missing "begin" and the two semi-colons in a row are context-free because they are both violations of the BNF and the parser will catch them without having to refer to any other part of the parse tree. The missing initialization is runtime because it is only at runtime can we be sure whether the variable has been initialized before being used; unless you use Java's conservative approach which requires that every path through the program that can lead to a particular point where a variable value is used must include an initialization of the variable; in that case it is context-sens. Misspelled identifier is context-sens. because we have to compare the where the id is used with its decl. to see the wrong spelling.

5. This asked, for a given set of operations, whether they belonged in the ParseTree class or not and why; and where each would belong in the OO approach. Some people seemed to think the ParseTree class was only relevant to the parser. That is not true. We represent the abstract parse tree as an instance of the ParseTree class and use it during parsing, printing, execution, etc. Anyway, goDown operation belongs in the ParseTree class because you need access to the representation used in order to move the cursor from one node to another. ExecIf and EvalExp don't because they have nothing to do with how a parse tree is represented. getIdVal (probably) belongs in the ParseTree class because we put the id table in the class and so need access to that.

In the OO approach, we don't need the goDown operation because each method in each class has direct access to its children. The ExecIf belongs in the If class, EvalExp in the Exp class, and getIdVal in the Id class.

6. This asked you to write the printWhile procedure/method. The most common mistake here was to mix printing with parsing and including calls to skipToken. The parsing is already complete, the abstract built, and the token stream completely read. So we don't have any skip tokens etc. in printing. Anyway, in the ParseTree class approach, printWhile would look like:

void printWhile(PT& p) { // omitting error checks write("while"); p.goDownLB(); // move to condition printCond(p); p.goUp(); p.goDownMB(); // move to , the body of the looop write("do"); printStmtSeq(p); p.goUp(); write("end;") }

7. The bonus question asked about memory requirements for the array approach vs. the ParseTree class approach vs. the OO approach. Many people seemed to think that objects use a lot of memory. An object size depends on the number (and sizes) of member variables of the class. So if we have something like:

   class SS { Stmt* s; SS* s1; .... }

an instance of SS will just have two words of memory, one for s and one for s1. That is it. It is really small. By comparison, a statement sequence node, in the array representation occupies five words of memory since every row in the array occupies five words. So the OO approach is actually much more efficient. Moreover, in the array approach, we have to declare the array to have a large number of rows because we don't know in advance how big the Core program might be. In the OO approach, we create exactly as many nodes as needed. So for that reason also, this approach is more efficient in memory usage.

What about the ParseTree class approach? A couple of people said we can't answer that because we don't know what representation is actually used in that class! That is indeed right; if you don't actually know what representation is used, we can't tell how much memory is used. For example, it is possible that it uses the Vector class of the C++'s STL which is like an array but it can increase in size as needed. In that case, the problem at the end of the last para (of allocating an unnecessarily big array) can go away. So, in summary, the OO approach is more efficient than the array approach; and the ParseTree class approach might be as bad as the array approach (if it uses the same rep) or may be better.

--Neelam