A link to ome class exercises from previous semesters

```
1. Draw a deterministic finite automaton and the transition table for the
regular expression [ab[c]+]*d

2(a) Write a scanner transition table that recognizes the regular
expression // ((/|lambda) NOT(/))* //

2(b) Add "actions" to the table such that the "//" delimiters get
discarded. Allowable actions are "t" for toss, "a(c)" for append character
c.

3(a) Draw a finite automaton for the regular expression (AB)+, given the
automata:

A: ->[O A O]->
B: ->[O B O]->

3(b) The automaton created in (a) is not necessarily optimal. Explain, in
general terms, what steps are necessary to optimize it. Explain what
"optimal" means in this case.

4. Mark all that is true

o Scanners can be implemented using finite automata
o All finite automata can be expressed through transition tables
o An error entry in the transition table corresponds to a mistake in the
regular expression
o A finite automaton basically helps identify correct tokens. To obtain
the value of the tokens, additional actions need to be performed during
transitions
o Deterministic finite automata are FA's with unambiguous transitions

5. Write a program fragment for the production Expr-list in standard and
extended BNF. Explain how repeated grammar elements are handled in both
cases

6. Build the parse table for MICRO (p 115)

7. Parse the MICRO program:

using the stack based parsing algorithm. Draw the sequence of parse
stacks. (p 116)

8. Parse the following program using the G1 grammar (p 156) assuming an
LR(0) parser, and mark the shift and reduce operations:

begin SimpleStmt; SimpleStmt; end\$

9. Explain how the above example is parsed using the action and goto table
on page 143

10. Create the CFSM and the tables for grammar G1 on page 156

11. Why is calling actions routines more natural for LL parsing ?

12. Why is the handling of the semantic stack more natural for LR parsing ?

13Perform the local list scheduling algorithm on the following basic block
of code:

mul R0 R1 -> R1
div R1 R2 -> R0
store R0 -> F

Sol:

mul/div = 2 cycles
memory = 3 cycles
other = 1 cycle

b	add R0 R0 -> R1
d	add R1 R2 -> R3
f	mul R3 R4 -> R5
h	div R5 R6 -> R7
i	store R7 -> F

priority assigning graph:

a13
|
|
|
b10 c12
|  /
| /
|/
d9  e10
|  /
| /
|/
f7  g8
| /
|/
h5
|
i3

scheduling:

S(op)	op	delay	Fin
1	a	3	4
2	c	3	5
3	e	3	6
4	b	1	5
5	d	2	7
6	g	3	9
7	f	2	9
8	-	-	-
9	h	2	11
10	-	-	-
11	i	3	14
12	-	-	-
13	-	-	-
14

```