Lexical Analysis

Tocken 단위로 나눔

 

		Regular Expressions
		↓
		Lexer Generator
		↓
Source	→	Lexer (Finite Automata)	→	Streams of Tokens

 

---

Finite automata (FSM: Finite State Machine)

state 갯수가 finite

start state는 한개

---

Regular Expressions

Base Cases:

- Symbol

- Epsilon: empty string

 

Induction Cases

- Alternation(M|N)

- Concatenation(MN)

- Repetition(M*) => including zero

 

---

How lexer generator make Lexer from REs?

 

1. change REs to finite autometa(NFA)

2. Link multiple NFA with empsilon or duplicated labels => make one NFA

3. Make each uniquely labeled => make DFA

 

DFA(Deterministic Finite Autometa):  node가 unique하고 epsilon이 없음

NFA(Non-deterministic Finite Autometa): node가 unique하지 않고 epsilon도 있음

=> computer는 DFA만 이해 가능하며 RE를 DFA로 바로 바꾸는 것은 어렵기 때문에 중간에 NFA state를 거침

---

NFA to DFA conversion

edge(s, a)

closure(S). e_closure(S): e으로 연결된 애들은 한 node로 봄

DFAedge(D,a)

 

state s1,s2가 둘다 final이거나 no final인 경우 모든 c에 대해 trans[s1.c] = trans[s2,c]이며 합칠 수 있음

 

Longest match

Rule priority