SI413: Bottom Up Parsing / CFSM [HW]

Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Consider the grammar, input and partial bottom-up parse shown below. Draw the tree, annotated with LR items, and stack after the next bottom up parsing step. Then do the same for one step more.

Problem 2

The Non-deterministic Characteristic Finite State Machine (CFSM) for the Problem 1 grammar is given below.

Consider the stack below:
```
  b	
  a
  a
-----
STACK
```
Show the sequence of states in an accepting computation in the CFSM for this stack (show me in a state-arrow-state kind of diagram, like the notes show when they "justify" the stack):
How does the state you end up in from (a) tell you that the next move can't be a reduce?
Given the CFSM and the state you ended up in (a), which one(s) of the following actions are possible (depending on the lookahead): shift a, shift b, shift c?

Problem 3

Draw the Non-deterministic CFSM for the grammar

	S -> T$
	T -> aTb | c