Final review (incomplete)

The final exam will be on paper. You can bring a 5x7 inch notecard fill with notes front and back. You will see questions like you see on this review.

Combinational logic

Diagram an OR gate out of NAND gates. Here is the diagram for a NAND gate:

Using AND/OR/NOT gates, diagram a 4-way MUX. Here are the diagrams for AND/OR/NOT:

Write the integer version of the binary number (in 8-bit 2’s complement) 01101000. Do the same with 11101110. Now find the negation of 00101000, and write in binary form.

Using AND/OR/NOT gates, diagram a 2-bit adder. Label the “overflow” bit.

Sequential logic

Using AND/OR/NOT and the DFF gate, diagram a Bit gate. Recall a Bit has an input, a load bit, and an output.

Describe the role of the PC gate.

Using a RAM8 gate (and no other RAM gates), diagram a RAM32 gate. Label the other gates you use.

Explain why we have Register gates in a modern machine and do not just use RAM for everything.

Assembly language

Write a chunk of assembly code that computes:

if RAM[5] >= RAM[4] then
RAM[0] = -10
else
RAM[0] = RAM[4] + RAM[5]
end


Give the value that RAM[0] contains after this code executes:

@2
D=A
@0
MD=D-1
A=D-1
MA=M+1


VM language

Assuming the stack pointer starts at 275, what is the value of the stack pointer (i.e., RAM[0]) after these operations:

push constant 0
push constant 10
push constant 20
eq
if-goto L1
push constant 30
label L1
pop local 1
sub
push constant 40
neg
push constant 50


Write the code needed to call the function f1 with three arguments: 1, 5, 2.

Write assembly code that performs the “push constant 20” operation.

Write assembly code that performs the “if-goto L1” operation.

Grammars, lexers, parsers, tree visitors

Describe the input and output of a “lexer.”

Describe the input and output of a tree visitor (for a translator, like we did for Sprinkles->VM).

(design a grammar for very small syntax examples)

(given a parse tree and some visitor functions, find the final output after visiting the tree from the root)