CS 432

Fall 2018
Mike Lam, Professor
a|(bc)*

Regular Expressions
and
Finite Automata
Compilation

Current
focus "Back end"

Source code Tokens Syntax tree Machine code

char data[20];
7f 45 4c 46 01
int main() { 01 01 00 00 00
float x 00 00 00 00 00
= 42.0; ...
return 7;
}

Lexing Parsing Code Generation

& Optimization

"Front end"
Lexical Analysis
●
Lexemes or tokens: the smallest building blocks of a
language's syntax
●
Lexing or scanning: the process of separating a character
stream into tokens

total = sum(vals) / n char *str = "hi";

total identifier char keyword

= equals_op * star_op
sum identifier str identifier
( left_paren = equals_op
vals identifier "hi" str_literal
) right_paren ; semicolon
/ divide_op
n identifier
Discussion question
●
What is a language?
Language
●
A language is "a (potentially infinite) set of
strings over a finite alphabet"
Discussion question
●
How do we describe languages?

xyy xy
xy xyy
xyyzzz xyz xy xyy
xyz xyyz xyz xyyz
xyzz xyzz xyzz xyyzz
xyyzz xyyzz xyzzz xyyzzz
xyyz xyzzz (etc.)
xyzzz xyyzzz
(etc.) (etc.)
Language description
●
Ways to describe languages
– Ad-hoc prose
●
“A single ‘x’ followed by one or two ‘y’s followed by
any number of ‘z’s”
– Formal regular expressions (current focus)
●
x(y|yy)z*
– Formal grammars (in two weeks)
●
A→xBC
●
B→y|yy
●
C→zC|ε
Languages
Chomsky Hierarchy of Languages

Recursively enumerable

Context-sensitive

Context-free
Most useful
Regular for compilers

●
Alphabet:
– Σ = { set of all characters }
●
Language:
– L = { set of sequences of characters from Σ }
Regular expressions
●
Regular expressions describe regular languages
– Can also be thought of as generalized search patterns

●
Three basic recursive operations:
– Alternation: a|b Lowest precedence
Additionally: ε is a
– Concatenation: ab regex that matches
the empty string
– ("Kleene") Closure: a* Highest precedence

●
Extended constructs:
– Character sets/classes: [0-9] ≡ [0...9] ≡ 0|1|2|3|4|5|6|7|8|9
– Positive closure: a2 ≡ aa a3 ≡ aaa a+ ≡ aa*
– Grouping: (a|b)c ≡ ac|bc
These are not covered extensively in your textbook!
Discussion question
●
How would you implement regular expressions?
– Given a regular expression and a string, how would you
tell whether the string belongs to the language described
by the regular expression?
Lexical Analysis
●
Implemented using state machines (finite state automata)
– Set of states with a single start state
– Transitions between states on inputs (w/ implicit dead states)
– Some states are final or accepting

a a|b ab
a a a b

b
Lexical Analysis
●
Deterministic vs. non-deterministic
– Non-deterministic: multiple possible states for given sentence
– One edge from each state per character (deterministic)
– Multiple edges from each state per character (non-deterministic)
– Empty or ε-transitions (non-deterministic)

a a

Deterministic (DFA)
Non-deterministic (NFA)
Deterministic finite automata
a
●
Formal definition
S: set of states
Σ: alphabet (set of characters) s1 s2

δ: transition function: (S, Σ) → S S = { s1, s2 }

s0: start state Σ={a}
δ = { (s1,a → s2), (s2,a → Ø) }
SA: accepting/final states s0: = s1

S = { s2 }
A
●
Acceptance algorithm
s := s0 Alternative δ representation:
for each input c: a
s := δ(s,c) s1 s2

return s ∈ SA s2 Ø
 Non-deterministic finite automata
●
Formal Definition
– S, Σ, s0, and SA same as DFA
– δ: (S, (Σ ∪ {ε})) → [S]
– ε-closure: all states reachable from s via ε-transitions
●
Formally: ε-closure(s) = {s} ∪ { t ∈ S | (s,ε→t) ∈ δ }
●
Extended to sets by union over all states in set

●
Acceptance algorithm
T := ε-closure(s0)
for each input c:
N := {}
for each s in T:
N := N ∪ ε-closure(δ(s,c))
T := N
return |T ∩ SA| > 0
Summary
DFAs NFAs
●
S: set of states ●
δ may return a set of states
●
Σ: alphabet (set of characters) ●
δ may contain ε-transitions
●
δ: transition function: (S, Σ) → S
●
δ may contain transitions to
multiple states on a symbol
● s0: start state
● SA: accepting/final states accept():
T := ε-closure(s0)
accept(): for each input c:
s := s0 N := {}
for each input c: for each s in T:
N := N ∪ ε-closure(δ(s,c))
s := δ(s,c)
T := N
return s ∈ SA
return |T ∩ SA| > 0
Lexical Analysis
●
Examples:
a|b ab
a a b
a

a
b
Lexical Analysis
●
Examples:
a|b ab a*
a a b
a

b
aa*|b
ab*
a(bc|c*)
a
b
Lexical Analysis
●
Examples:
a|b ab a*
a a b
a

b
aa*|b
a
ab*
a b
a(bc|c*)
a c
a
c
b b

c
Equivalence
●
A regular expression and a finite automaton are equivalent
if they recognize the same language
– Same applies between different REs and between different FAs
●
Regular expressions, NFAs, and DFAs all describe the
same set of languages
– "Regular languages" from Chomsky hierarchy
●
Next week, we will learn how to convert between them
Application
●
PA2: Use Java regular expressions to tokenize Decaf files
– Process the input one line at a time
– Generally: one regex per token type
– Each regex begins with “^” (only match from beginning)
– Prioritize regexes and try each of them in turn
– When you find a match, extract the matching text
– Repeat until no match is found or input is consumed
– Less efficient than an auto-generated lexer
– However, it is simpler to understand
– (Our approach to PA3 will be similar)
Activity
●
Construct state machines for the following
regular expressions:

x*yz* 1(1|0)* 1(10)* (a|b|c)(ab|bc)

(dd*.d*)|(d*.dd*) ← ε-transitions may make this one slightly easier