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