CSCI 310 Spring 2004, Final Exam Review Questions

1. Regular expressions
   1. Give a regular expression for an identifier in minijava
   2. Give a regular expression for comments in minijava

2. Suppose we have token A matching regular expression "abc", token B matching regular expression "abc*" in our grammar. On input abcc, which token is matched? Why?

3. What is an ambiguous grammar? Why are they bad when used to design or implement programming languages?

4. Define Left-recursive and right-recursive as they pertain to grammars.

5. Consider this excerpt of our MiniJava grammar:

   E -> E op E
   E -> E [E]
   E -> id | integerLiteral
   op -> + | - | *
   

   1. Construct the First and Follow sets for this grammar
   2. Can this grammar be parsed by an LL(0) parser? If not, rewrite the grammar so that it can be parsed by an LL(0) parser.
   3. Construct the State diagram and shift/reduce table for compiling the above grammar by an LR(0) grammar.
   4. Can this grammar be parsed by an LR(0) parser? Can it be parsed by an SLR parser? If not, rewrite the grammar so that it can be parsed by an SLR parser.

6. A common syntax error is a mis-spelled reserved word. How would you modify your scanner and/or parser to specifically catch misspellings of reserved words? As long as you catch them, could you just go ahead an continue compiling (and in fact output an executable)? (If so, explain how; if not, explain why not.)

7. Our compiler operates in several passes -- parser, symbol table construction, type checker, IRT construction, code generation. This is convenient, but is it necessary? Explain any features of MiniJava that require multiple passes.

8. The Token class generated by sablecc includes fields with the line number and position for each token. Assuming you do not build an abstract syntax tree, but instead pass the entire parse tree onto the later passes of the compiler, explain how you could build a Visitor class that goes through the parse tree and assigns a line number to each expression and statement node in the parse tree.

9. Explain the issues involved in typechecking

   x = this.foo(1, 3, false);
   

   (i.e. describe all the things you must check for correctness.)

10. Explain the use of the static link in the Activation Record.

11. Suppose you language could have functions as a return type -- i.e. a method could return a function as a return value. Describe the issues involved in implmenting this in a compiler.

12. Translate: x = a+ 5 into an IR Tree.

13. Suppose you did not implement any operator precedence in your grammar. How will this impact your implementation of IR Trees?

14. Data I use in my research is given to me in a form that is easy for humans to read and write, but not very convenient for the processing I do on it. Therefore, these data files get translated into a different format. The human readable format looks like the following:

    SUBJECT ID : S10
    
     CRITERIA 2304 : operations
     CATEGORY 4240 : does not apply
     CARDS:  4 6 7 10 13 14 15 16 18 19 21 23 26 
     CATEGORY 4241 : objects in the operation
     CARDS:  5 11 17 22 25 
     CATEGORY 4242 : coding features to change the object
     CARDS:  8 9 12 20 24 
     CATEGORY 4243 : names of the operation
     CARDS:  1 2 3 
    
     CRITERIA 2305 : things i learned in computer science
     CATEGORY 4244 : CS I
     CARDS:  1 3 5 7 8 9 10 13 17 20 
     CATEGORY 4245 : CS II
     CARDS:  2 11 12 14 16 18 19 21 24 25 26 
     CATEGORY 4246 : Data Structures
     CARDS:  4 22 
     CATEGORY 4247 : haven't learned
     CARDS:  6 15 23 
    
     CRITERIA 2306 : places i usually define things, make things, create
     CATEGORY 4248 : does not apply
     CARDS:  4 6 7 10 15 23 
     CATEGORY 4249 : defined outside of method
     CARDS:  2 5 11 14 17 18 19 25 
     CATEGORY 4250 : made or constructed inside method
     CARDS:  1 3 8 9 12 13 16 20 21 22 24 26 
    *
    SUBJECT ID : S09
    
     CRITERIA 2300 : things at same level in terms of abstraction when you write a program
     CATEGORY 4227 : synonyms for function
     CARDS:  1 2 3 
     CATEGORY 4228 : broad terms looking at program from high level
     CARDS:  5 7 15 
     CATEGORY 4229 : things you might see within a method
     CARDS:  8 9 12 16 19 20 21 24 
     CATEGORY 4230 : things you would see in a class
     CARDS:  11 17 18 25 
     CATEGORY 4231 : things that don't fit in the others
     CARDS:  4 6 10 13 14 22 23 26 
    

    Each set of data for a subject begins with the keyword SUBJECTID a ':' and then some string that starts with S or E and is followed by integers. The data is then grouped by CRITERIA, with several CATEGORYs in the criteria, each having a set of CARDS. The data for a particular subject ends when either we hit an asterisk, in which case it will be followed by another subject, or if we hit the end-of-file, in which case there is no more data.

    The format we want to put the data in is:

    4240,S10,2304,does not apply,00010110010011110110101001
    4241,S10,2304,objects in the operation,00001000001000001000010010
    4242,S10,2304,coding features to change the object,00000001100100000001000100
    4243,S10,2304,names of the operation,11100000000000000000000000
    4244,S10,2305,CS I,10101011110010001001000000
    4245,S10,2305,CS II,01000000001101010110100111
    4246,S10,2305,Data Structures,00010000000000000000010000
    4247,S10,2305,haven't learned,00000100000000100000001000
    4248,S10,2306,does not apply,00010110010000100000001000
    4249,S10,2306,defined outside of method,01001000001001001110000010
    4250,S10,2306,made or constructed inside method,10100001100110010001110101
    

    In this comma-separated format, the line holds the category number, the subject id, the category name, and a 26-length vector of 0's and 1's indicating which cards are in the category described by this line.
    1. Give a grammar to describe the human-readable format.
    2. Assuming you have a parser that can handle your grammar and produces code and a visitor structure like sablecc, how would you write a visitor to convert the parsed data into the comma-separated format?

15. Rewrite the trees in this file and this file to remove ESEQs.