Drawtomata
Open the tool

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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Linz, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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

✓ matches

Aho, 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