Homework
COP-3402, Spring 2024

Please respond with "yes" (in webcourses) once you've completed your VirtualBox and vagrant setup.

Using command-line unix tools only, what set of commands could you use to find which files have the name "message" in a directory or its subdirectories? For example, your file system looks like this:

mydir/
     file1.txt
     subdir/
           message.txt

What command(s) could you use to print the contents of the file having the name "message.txt"?

In our toy compiler, how are numbers represented in the input language?

How are numbers represented in the output language?

What about operators, such as addition, how are they represented in the input and output language and how do they differ?

What does a parser generator, such as bison, do?

What is the input of the parser generator?

What is its output?

• What distinguishes parse trees (aka concrete syntax trees) and abstract syntax trees?
• In the first SimpleC project, what will we use semantic actions in the parser for?

• Convert regular expression (ab|ba)*c to a nondeterministic finite automaton (NFA). Recall that concatenation has higher precendence than alternation.
• Convert the NFA created above into a deterministic finite automaton (DFA).

• Write a derivation of the string "aacdbb" using the following grammar. Recall that the first production's nonterminal is the starting symbol, in this case \(A\).
  1. \(T \to a T b\)
  2. \(T \to V\)
  3. \(V \to c V\)
  4. \(V \to d\)

• Use the following parse table for the above grammar to show each step of the LR parsing algorithm for the string "aacdbb$" where $ is the end of input sentinel. Start on state 0. The numbers after "reduce" are the production numbers from the grammar above. Show the sequence of actions and gotos and optionally show the state stack and/or the derivation or syntax tree.

  State	a	b	c	d	$	T	V
  0	shift 2		shift 3	shift 6		goto 1	goto 4
  1					accept
  2	shift 2		shift 3	shift 6		goto 7	goto 4
  3			shift 3	shift 6			goto 5
  4	reduce 2	reduce 2	reduce 2	reduce 2	reduce 2
  5	reduce 3	reduce 3	reduce 3	reduce 3	reduce 3
  6	reduce 4	reduce 4	reduce 4	reduce 4	reduce 4
  7		shift 8
  8	reduce 1	reduce 1	reduce 1	reduce 1	reduce 1
  State	a	b	c	d	$	T	V

  The beginning of this would be

  state	lookahead	action	stack
  0	(a)acdbb$	(0,a) = shift 2	0 a 2
  2	a(a)cdbb$	(2,a) = shift 2	0 a 2 a 2
  2	aa(c)dbb$	(2,c) = shift 3	0 a 2 a 2 c 3
  3	aac(d)bb$	(3,d) = shift 6	0 a 2 a 2 c 3 d 6
  6	aacd(b)b$	(6,b) = reduce 4 \(V \to d\)	0 a 2 a 2 c 3 V
  3		(3,V) = goto 5	0 a 2 a 2 c 3 V 5

Draw the AST for the following program. Then record the symbol tables in the symbol tables for each scope and annotate the tree with the types of each expression and operator.

int x;

main {
  int x;
  int y;
  y = 2;
  x = y;
  return 0;
}

Show what the call stack would look like when calling factorial(2). In particular show the stacks frames for both factorial(2) and factorial(1), including parameters, local variables, return address (can just use the name of the function), and the pointer to the caller's stack frame. It's sufficient to show the call stack after the second call to factorial, i.e., containing the stack frames work factorial(2) and factorial(1).

factorial(x) {
  if (x <= 1) {
    return 1;
  } else {
    int new_x = x - 1;
    return x * factorial(new_x);
  }
}

How do assigning to a variable and assigning to a pointer differ in assembly in the implementaiton of our SimpleC compiler?

For instance, local variables are stored in an offset from the stack frame, so their values are loaded into memory. What happens with an assignment to a pointer dereference? Show an assembly code example of a pointer dereference.

1. Assuming that y has an offset of -8 from %rbp, what would the AT&T-syntax assembly operation look like for y = 3?
2. if y has an offset of -8 from %rbp and x has an offset of -16, what sequence of AT&T-syntax assembly instructions could be used to implement x = *y?

How can we implement a less-than operator in assembly? For instance, if we want to generate code to evaluate x < y, and we know that x is in register %rax, y is in %rbx, and we want the result to also be stored in %rax, what sequence of assembly instructions could we use?