CS75 Written Homework Assignments

I do not accept late homework assignments for a grade, but I encourage you to try all written homework problems even if you do not submit them; written assignments will help you understand the lecture material and will give you some idea of the types of questions that are likely to appear on exams.

You are welcome to work in small groups on written homework assignments. However, if you do so, I suggest first trying to solve all the problems individually, then meeting as a group to come up with a final solution together (rather than having each member solve a subset of them individually); it is good to test your understanding of the material by trying to solve every homework problem on your own first. If you work in a group, please submit a single solution with all of your names on it, so that it is clear with whom you collaborated and so that I do not have to grade several identical solutions.

HW5: Due Thursday, April 7th at the beginning of class

  1. Grab a copy of the Stack Machine code, read the documentation, and try running the example stack machine programs. The code is here: ~newhall/public/cs75/smach/

  2. Convert (by hand) each C-- code fragment listed below to equivalent stack machine code (you should create a .stk file with the smach instructions and run your solution on the stack machine to verify that it is correct).
    Code fragments:
    (1) write (9 + 2 * 4);
    (2) int x;      // these are global variables
        int y;
        x = 8;
        y = 9;
        x = y + x;
        write x;
        write y;

  3. Read through the project part 3 assignment before class on Tuesday.

  4. This question is about how the symbol table is used by the compiler to compile the C-- program listed below. Don't worry if if you do not know how to generate code for this program yet, just focus on how the symbol table needs to be updated and how and when symbol table information is used by the compiler.

    1. For each line in the C-- program below, explain any modifications to the symbol table that are made by the compiler when processing it (what specifically needs to be added/removed/modified?). Also, indicate if the compiler uses a symbol table entry when processing that line (specifically, which entry and what information from the entry does the compiler need?).
    2. What fields are needed in a symbol table entry? Show an example of four different types of symbol table entries that would appear in the symbol table when compiling the program below. Make sure to show each entry's field values and indicate which field values are used and how they are interpreted.
    lineno  code
    ------  ------   
    1:     int x;
    2:     int array[10];
    3:     int foo(int y) {
    4:          int b;
    5:          b = x;
    6:          y = b;
    7:          {
    8:             int y;
    9:             y = x;
    10:            write y;
    11:         }
    12:         write y;
    13:         return b;
    14:    }
    15:     int main() {
    16:         x = 5;
    17:         array[2] = foo(x);
    18:         write array[2];
    19:     }

HW4: Due Tuesday, Feb 29 at the beginning of class

  1. Consider the following grammar:
    S ---> aSbS | bSaS | epsilon
    1. Is the grammar LL(1)? Show how you determined whether or not it is LL(1).
    2. Create a parse table for the grammar. Show how you determined what each parse table entry contains.

  2. Convert the following grammar to LL(1) (show your work):
    S ---> (L) | a
    L ---> L, S | S
    Using the re-written form of this grammar:
    1. compute the FIRST and FOLLOW sets
    2. show the parse table
    3. show the parse tree for the string ( a , ( a , a ) )

HW3: Due Tuesday, Feb. 8 at the beginning of class

Convert the following regular expression to an NFA, and then convert the NFA to a DFA by applying the algorithms we discussed in class:
I want to see an NFA as constructed by your applying the algorithm we talked about in class, and I want to see all steps in your applying the NFA to DFA algorithm. Don't just eyeball this and turn in an NFA and DFA for ab*a, which I'm sure you can all do. Instead, I want you to show me that you can apply the algorithms to this simple example.

HW2: Due Thursday, Feb. 3 at the beginning of class

Do the following problems from Chapter 3 of the book:
  1. 3.5
  2. 3.6
  3. 3.7 a, b, c, d, f, h, i.

If you cannot come up with a regular expression for a language, then see if you can come up with a finite automaton that recognizes the language. In addition, you may invent and use some short hand notation for cases where the next character can be any member of a large alphabet. For example, suppose I want a regular expression for valid C identifiers, then it is okay to say that L represents any alphabetic character and D any digit character and the r.e. can be expressed as:

( L | _ )( L | _ | D)*
If you use this type of short hand, then make sure to define all special symbols you use. You should not, however, define new operations on r.e. from existing ones; your regular expressions should be built from Kleene star, concatenation, and union only.

HW1: Due Thursday, Jan. 27, at the beginning of class

  1. Turn in solutions to the following problems from Chapter 2 of the book:
    1. 2.1
    2. 2.2 a, b, c, d
    3. 2.3 a, b, c, d
    4. 2.4 b, d

  2. As an extra challenge, try problem 2.5.
    If you do not know binary number representation, here is a brief description
    (X^K is notation for X raised to the Kth power):
    binary numbers are base 2 numbers consisting of strings of 0's and 1's 
      decimal numbers are base 10 numbers consisting of strings of {0,1,...,9}
      base 3 numbers consist of strings of {0, 1, 2}
      base 4 numbers consist of string os {0, 1, 2, 3}, and so on 
    for any base number:
      the lowest order digit counts the number of base^0 occurrences in the value
      (either 0 occurrences, or 1 occurrence, or ... , or base-1 occurrences)
      the 2nd lowest order digit counts the number of base^1 occurrences in the value
      the 3rd lowest order digit counts the number of base^2 occurrences in the value
      and so on
    For example:
    the number 101 in decimal has a value of 1*10^2 + 0*10^1 + 1*10^0 = 101
    the number 101 in binary has a value of 1*2^2 + 0*2^1 + 1*2^0  =  5  
    the number 101 in base3 has a value of  1*3^2 + 0*3^1 + 1*3^0  =  10 
    To represent the decimal value 23 in:
    base 10:  2*10^1 + 3*10^0   is  23
    base 4:  1*4^2 + 1*4^1 + 3*4^0  is  113
    base 2:  1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 1*2^0  is 10111
    For this problem, the two terminals in the grammar are 11 and 1001, which are the decimal values 3 and 9.

  3. Try out the simple compiler from Chapt. 2:

    Copy the simple compiler code (the infix to postfix compiler from Chapt. 2) from ~newhall/public/cs75/simplecompiler/ to one of your subdirectories. Try compiling and running it with different infix expression input. By skimming through chapt. 2 of the book and by reading through the simple compiler's source code you will get an idea of how you will organize and implement your C compiler. In addition, the main function has some commented-out memory access errors. You may want to try uncommenting these errors, re-making, and then running with valgrind to get some idea of how valgrind works.