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:
  
Begin Read(X); Write(X,X+X); END

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:

load A -> R0
add R0 R0 -> R0
load C -> R1
add R0 R1 -> R0
load D -> R1
mul R0 R1 -> R1
load E -> R2
div R1 R2 -> R0
store R0 -> F

Sol:

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

a	load A -> R0
b	add R0 R0 -> R1
c	load C -> R2
d	add R1 R2 -> R3
e	load D -> R4
f	mul R3 R4 -> R5
g	load E -> R6
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