What is a single expression that represents the following?
What is a single expression that represents the following?
(-|+)? [1-9] [0-9]*
What is a single expression that represents the following?
(-|+)? [1-9] [0-9]*
(-|+|
a
) a
}"ab"
) "ab"
}What does a synthesized lexer look like?
Theory: Let
Try the following tool: https://github.com/yakout/compiler
Theory: For every NFA
RE -- Thompson's construction --> NFA
How to transform NFA to DFA?
![]() |
![]() |
---|
![]() |
![]() |
---|
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | ? |
{1, 2, 3, 4, 6, 7, 8} | B | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | ? | ? |
{1, 2, 4, 5, 6, 7} | C | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | ? |
{1, 2, 4, 5, 6, 7} | C | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | D |
{1, 2, 4, 5, 6, 7} | C | ? | ? |
{1, 2, 4, 5, 6, 7, 9} | D | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | D |
{1, 2, 4, 5, 6, 7} | C | B | C |
{1, 2, 4, 5, 6, 7, 9} | D | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | D |
{1, 2, 4, 5, 6, 7} | C | B | C |
{1, 2, 4, 5, 6, 7, 9} | D | B | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | D |
{1, 2, 4, 5, 6, 7} | C | B | C |
{1, 2, 4, 5, 6, 7, 9} | D | B | E |
{1, 2, 4, 5, 6, 7, 10} | E | ? | ? |
![]() |
![]() |
---|
NFA State | DFA State | a | b |
---|---|---|---|
{0, 1, 2, 4, 7} | A | B | C |
{1, 2, 3, 4, 6, 7, 8} | B | B | D |
{1, 2, 4, 5, 6, 7} | C | B | C |
{1, 2, 4, 5, 6, 7, 9} | D | B | E |
{1, 2, 4, 5, 6, 7, 10} | E | B | C |
Note that
![]() |
![]() |
---|
We need a function
![]() |
![]() |
---|
![]() |
![]() |
![]() |
---|
![]() |
![]() |
![]() |
---|
Another formal definition (also showing how to compute):
d0 := ε-closure({n0})
D := {d0}
W := {d0} // worklist
while W ≠ ∅:
remove q from W
for α in Σ:
T := ∅
for s in q:
T := T ∪ δ_N(s, α)
T' := ε-closure(T)
D' := D ∪ {T'}
δ_D(q, α) = T' // update δ_D
if T' ∉ D:
W := W ∪ {T'}
D := D'
F_D = {q ∊ D | q ∩ F_N ≠ ∅} // define F_D
![]() |
![]() |
---|
d0 := ε-closure({n0})
D := {d0}
W := {d0} // worklist
...
d0 = {0, 1, 2, 4, 7}
W0 = {0, 1, 2, 4, 7}
![]() |
![]() |
---|
remove q from W
for α in Σ:
T := ∅
for s in q:
T := T ∪ δ_N(s, α)
T' := ε-closure(T)
α = a
T = {3, 8}
T' = {1, 2, 3, 4, 6, 7, 8}
![]() |
![]() |
---|
D' := D ∪ {T'}
δ_D(q, α) = T' // update δ_D
if T' ∉ D:
W := W ∪ {T'}
T' = {1, 2, 3, 4, 6, 7, 8}
D = {{0, 1, 2, 4, 7}}
D' = {{0, 1, 2, 4, 7}, {1, 2, 3, 4, 6, 7, 8}}
δ_D({0, 1, 2, 4, 7}, a) = {1, 2, 3, 4, 6, 7, 8}