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.

- 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/`

- 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;

- Read through the project part 3 assignment before class on Tuesday.
- 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.
- 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?).
- 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: }

- Consider the following grammar:
S ---> aSbS | bSaS | epsilon

- Is the grammar LL(1)? Show how you determined whether or not it is LL(1).
- Create a parse table for the grammar. Show how you determined what each parse table entry contains.

- 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:- compute the FIRST and FOLLOW sets
- show the parse table
- show the parse tree for the string ( a , ( a , a ) )

I want to see an NFA as constructed by your applying the algorithm we talked about in class, and I want to seeab*a

- 3.5
- 3.6
- 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.

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

- 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. - 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.