Drawtomata / Verified against the textbook
Verified against the textbook
Each example below is a worked example from the course books. The textbook answer sits next to what Drawtomata computes with the same code the tool uses. The same checks run in the test suite on every change, and again in your browser when this page opens.
15 of 15 match when the site was built
Automata
Subset construction on the NFA for (a|b)*abb
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 3.21, Fig. 3.35
(a+b)*abb
- Textbook
- 5 DFA states (A to E), final state E
- Drawtomata
- 5 DFA states (A to E), final state E
Minimizing the DFA of Fig. 3.36
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 3.40
the 5-state DFA above
- Textbook
- 4 states: A and C are merged
- Drawtomata
- 4 states: A and C are merged
aⁿbⁿ is not regular: w = aᵖbᵖ defeats every split
✓ matchesLinz, An Introduction to Formal Languages and Automata, Ch. 4 (pumping lemma)
p = 1 to 6
- Textbook
- no split survives for any p
- Drawtomata
- no split survives for any p
Parsing
FIRST and FOLLOW of the expression grammar
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 4.30
E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
- Textbook
- FIRST(E) = {(, id}; FOLLOW(E) = {$, )}; FOLLOW(T) = {$, ), +}; FOLLOW(F) = {$, ), *, +}
- Drawtomata
- FIRST(E) = {(, id}; FOLLOW(E) = {$, )}; FOLLOW(T) = {$, ), +}; FOLLOW(F) = {$, ), *, +}
LL(1) parsing table of the expression grammar
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 4.32, Fig. 4.17
E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
- Textbook
- LL(1), 13 entries, M[E', )] = E' → λ
- Drawtomata
- LL(1), 13 entries, M[E', )] = E' → λ
Predictive parser output on id + id * id
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Fig. 4.21
id + id * id
- Textbook
- E → T E'; T → F T'; F → id; T' → λ; E' → + T E'; T → F T'; F → id; T' → * F T'; F → id; T' → λ; E' → λ; accept
- Drawtomata
- E → T E'; T → F T'; F → id; T' → λ; E' → + T E'; T → F T'; F → id; T' → * F T'; F → id; T' → λ; E' → λ; accept
LR(0) items and SLR table of the expression grammar
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Fig. 4.31 and Fig. 4.37
E -> E + T | T T -> T * F | F F -> ( E ) | id
- Textbook
- 12 item sets (I0 to I11), SLR table has no conflicts
- Drawtomata
- 12 item sets (I0 to I11), SLR table has no conflicts
Moves of the SLR parser on id * id + id
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Fig. 4.38
id * id + id
- Textbook
- s5, r F → id, r T → F, s7, s5, r F → id, r T → T * F, r E → T, s6, s5, r F → id, r T → F, r E → E + T, accept
- Drawtomata
- s5, r F → id, r T → F, s7, s5, r F → id, r T → T * F, r E → T, s6, s5, r F → id, r T → F, r E → E + T, accept
S → L = R | R is not SLR, but it is LALR
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 4.48
S -> L = R | R L -> * R | id R -> L
- Textbook
- SLR: 1 conflict, on =; LALR: no conflicts
- Drawtomata
- SLR: 1 conflict, on =; LALR: no conflicts
LR(1) and LALR states of S → C C, C → c C | d
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Examples 4.54 and 4.58
S -> C C C -> c C | d
- Textbook
- 10 LR(1) states, 7 LALR states
- Drawtomata
- 10 LR(1) states, 7 LALR states
Compiler
Annotated parse tree for 3 * 5 + 4 n
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 5.2, Fig. 5.3
3 * 5 + 4 n
- Textbook
- L.val = 19
- Drawtomata
- L.val = 19
Syntax tree for a - 4 + c built by semantic rules
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 5.11, Fig. 5.11
a - 4 + c
- Textbook
- p1 = Leaf(id, a); p2 = Leaf(num, 4); p3 = Node(-, p1, p2); p4 = Leaf(id, c); p5 = Node(+, p3, p4)
- Drawtomata
- p1 = Leaf(id, a); p2 = Leaf(num, 4); p3 = Node(-, p1, p2); p4 = Leaf(id, c); p5 = Node(+, p3, p4)
Phases of a compiler on position = initial + rate * 60
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Fig. 1.7
position = initial + rate * 60
- Textbook
- tokens <id,1> <=> <id,2> <+> <id,3> <*> <60>; optimized: t1 = id3 * 60.0 ; id1 = id2 + t1
- Drawtomata
- tokens <id,1> <=> <id,2> <+> <id,3> <*> <60>; optimized: t1 = id3 * 60.0 ; id1 = id2 + t1
Three-address code for a = b * - c + b * - c
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Section 6.2, Fig. 6.10
a = b * -c + b * -c
- Textbook
- t1 = minus c ; t2 = b * t1 ; t3 = minus c ; t4 = b * t3 ; t5 = t2 + t4 ; a = t5
- Drawtomata
- t1 = minus c ; t2 = b * t1 ; t3 = minus c ; t4 = b * t3 ; t5 = t2 + t4 ; a = t5
Leaders of the code that sets a 10×10 matrix to the identity
✓ matchesAho, Lam, Sethi, Ullman, Compilers (2nd ed.), Example 8.5
17 three-address instructions
- Textbook
- leaders 1, 2, 3, 10, 12, 13 (6 basic blocks)
- Drawtomata
- leaders 1, 2, 3, 10, 12, 13 (6 basic blocks)
Books
- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd edition.
- P. Linz, An Introduction to Formal Languages and Automata.