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:     }
   

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

ab*a

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

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)*

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.