# 0. 요약
> ✅ **전체적인 흐름**
> RE
> → (Thompson's Construction)
> → NFA
> → (Subset Construction)
> → DFA
> → Table 구현
> → Lexer
> 🤓☝️ **Lexer Overview**
> Lexer는 문자열을 Token으로 변환한다.
> Token이란 문법적으로 의미를 갖는 최소 단위 문자열인데,
> Lexeme(어휘소)는 토큰의 실제 값을 의미한다.
> Lexer는 파싱에서 더 간결한 입력을 받게 하기 위해,
> 또 어휘 분석이 구문 분석보다 쉬운 문제이기 때문에 구현된다.
> chomsky hierarchy에서 regular이 lexer의 입력,
> context-free가 parser의 입력이다.
> Lexer는 lexical (단어 수준) 오류를 잡지만, syntactic (문법 수준) 오류는 잡지 않는다.
> syntactic 오류는 parser에서 잡는다
> Ad-hoc Lexer의 예시를 보며 Lexer 디자인의 요구사항을 정리할 수 있다.
> Ad-hoc은 구현이 복잡하고 비효율적이다.
> Lexer Design 시에는 아래 사항이 요구된다.
> 1. 토큰의 명확한 정의
> 2. 문자열의 Token 구분
> 3. 효율적인 Token 분리
## 0.0 필수 암기
- **Lexer의 역할**: `string → Token list` (실제 시그니처는 `string → Result<Token list, Info>`)
- **Token = 문법적으로 의미를 갖는 최소 단위 문자열**
- Token 종류: ID / NUM / PAREN / IF / OP / SEMICOLON 등
- Lexeme = Token의 실제 값 (string)
- Info = `{ FilePath; Line; Col }` (에러 위치 표시용)
- **Lexer가 잡는 오류 vs Parser가 잡는 오류 구분**
- **어휘 오류 → Lexer** (예: `1x23` 같이 token 자체가 정의 안 된 문자열)
- **문법 오류 → Parser** (예: `of (b == 0) ...` — `of`는 ID로 잘 파싱됨, 단지 문법이 틀린 것)
- **Chomsky 계층**: Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable
- **Regular = Lexer**, **Context-Free = Parser**
## 0.1 RE (Regular Expression) 정의
|표기|정의|예시|
|---|---|---|
|$\epsilon$|$L(\epsilon) = {""}$|빈 문자열|
|$a$|$L(a) = {"a"}$|한 글자|
|$R \cdot S$|$L(R) \cdot L(S)$|concatenation|
|$R\|S$|$L(R) \cup L(S)$|alternation|
|$R^*$|$L(\epsilon) \cup L(R) \cup L(R^2) \cup \cdots$|0회 이상 반복|
|$(R)$|$L(R)$|grouping|
- **우선 순위**: `* > · > |`
- `ab|cd*` = `(ab)|(c(d*))`
- **Syntactic Sugar**
- $R^+ = RR^*$ (1회 이상)
- $R? = \epsilon | R$ (있어도 되고 없어도 됨)
- $[0-9], [a-z], [A-Z]$
## 0.2 FSM 5-tuple
$(\Sigma, S, s_0, \delta, F)$
- $\Sigma$: alphabet 집합
- $S$: state들의 **유한** 집합
- $s_0 \in S$: 시작 state
- $\delta: S \times \Sigma \to S$: transition 함수
- $F \subseteq S$: 종료 state들의 집합 (공집합 가능)
## 0.3 NFA & DFA 5-tuple
둘 다 $(\Sigma, S, s_0, \delta, F)$로 정의되며, 차이는 **transition 함수 $\delta$** 에만 있음.
| |NFA|DFA|
|---|---|---|
| $\delta$ |$S \times (\Sigma \cup {\epsilon}) \to \wp(S)$|$S \times \Sigma \to S$|
| 전이 결과 |여러 state 가능 (집합)|하나의 state|
| $\epsilon$-transition |있음|없음|
## 0.4 Thompson's Construction (RE → NFA) 5가지 규칙
모든 결과 NFA는 **start state 1개, final state 1개**를 가짐.
1. **$\epsilon$**: `(○) --ε--> (◎)`
2. **$a$ (단일 문자)**: `(○) --a--> (◎)`
3. **$RS$ (concatenation)**: `R의 final` --ε--> `S의 start`, R의 start가 새 start, S의 final이 새 final
4. **$R|S$ (alternation)**: 새 start에서 R, S의 start로 ε 두 갈래, R, S의 final에서 새 final로 ε
5. **$R^*$ (Kleene star)**: 새 start --ε--> R의 start, R의 final --ε--> R의 start (반복), 새 start --ε--> 새 final (0번), R의 final --ε--> 새 final
## 0.5 Subset Construction (NFA → DFA) 핵심
- **$\epsilon$-Closure(s)**: $s$로부터 $\epsilon$-transition만으로 도달 가능한 모든 state의 집합 (자기 자신 포함)
- **새 state = 옛 state들의 부분집합** (그래서 이름이 Subset Construction)
- **새 transition**: 어떤 새 state에서 문자 $a$로 갈 수 있는 곳 = $\epsilon\text{-Closure}(\delta(\text{집합}, a))$
- **Initial**: NFA의 $s_0$를 포함한 새 state
- **Final**: NFA의 final state를 하나라도 포함한 새 state
- **NFA state 개수가 $n$이면 DFA state 개수는 최대 $2^n$개**
---
# 1. LEXER OVERVIEW
> 🤓☝️
> Lexer는 문자열을 Token으로 변환한다.
> Token이란 문법적으로 의미를 갖는 최소 단위 문자열인데,
> Lexeme(어휘소)는 토큰의 실제 값을 의미한다.
> Lexer는 파싱에서 더 간결한 입력을 받게 하기 위해,
> 또 어휘 분석이 구문 분석보다 쉬운 문제이기 때문에 구현된다.
> chomsky hierarchy에서 regular이 lexer의 입력,
> context-free가 parser의 입력이다.
> Lexer는 lexical (단어 수준) 오류를 잡지만, syntactic (문법 수준) 오류는 잡지 않는다.
> syntactic 오류는 parser에서 잡는다
## 1.1 컴파일러 구조 내의 Lexer
### 1.1.1 컴파일러의 3단계 구조
```mermaid
flowchart LR
A([Source Program]) --> FE
IR1([IR Program])
IR2([IR Program])
BE --> C([Target Program])
subgraph Compiler
FE[Front-End] --> IR1 --> ME[Middle-End] --> IR2 --> BE[Back-End]
end
style A fill:#e74c3c,color:#fff
style C fill:#e74c3c,color:#fff
style IR1 fill:#e74c3c,color:#fff
style IR2 fill:#e74c3c,color:#fff
style FE fill:#1a5c3a,color:#fff
style ME fill:#1a5c3a,color:#fff
style BE fill:#1a5c3a,color:#fff
```
### 1.1.2 Front-End 내부 구조
```mermaid
flowchart LR
A([Source Program]) --> Lexer
T([Tokens])
AST1([AST])
AST2([AST])
IR([IR Program])
subgraph FrontEnd[Front-End]
Lexer --> T --> Parser --> AST1 --> SA[Semantic Analyzer] --> AST2 --> IRT[IR Translator]
end
IRT --> IR
style A fill:#e74c3c,color:#fff
style T fill:#e74c3c,color:#fff
style AST1 fill:#e74c3c,color:#fff
style AST2 fill:#e74c3c,color:#fff
style IR fill:#e74c3c,color:#fff
style Lexer fill:#1a5c3a,color:#fff
style Parser fill:#1a5c3a,color:#fff
style SA fill:#1a5c3a,color:#fff
style IRT fill:#1a5c3a,color:#fff
```
> 즉, Compiler 내 Front-End 내 첫 번째 요소인 Lexer를 다루게 될 것.
## 1.2 Lexer의 역할
| 항목 | 내용 |
| ---------- | ----------------------------------------- |
| **역할** | 문자열을 토큰(Token)의 나열로 변환 |
| **처리** | 공백, 주석 제거 |
| **이론적 기반** | 오토마타 이론 |
| **입력** | `if (b == 0) a = b;` |
| **출력** | `if` `(` `b` `==` `0` `)` `a` `=` `b` `;` |
## 1.3 Lexer의 추상적 정의
### 1.3.1 기본 시그니처
> Source Program (string) → Lexer → Token list
```fsharp
val lexer: string -> Token list
```
### 1.3.2 최종 시그니처 (에러 처리 포함)
> 토큰 정의 기반 재정의
```fsharp
type Lexeme = string
type Info = { FilePath: string; Line: int; Col: int }
type Token =
| ID of Lexeme * Info
| NUM of Lexeme * Info
| LPAREN of Info | RPAREN of Info | EQ of Info | ASSIGN of Info
// | ...
module FrontEnd =
val lexer: string -> Result<Token list, Info>
```
- `Result<A, B>`: 성공이면 `A`, 실패면 `B` (자바로 치면 `Either<List<Token>, Info>`)
- 실패할 때 어디서 실패했는지(`Info`)를 반환해야 하므로 단순 `Token list`가 아니라 `Result`로 감쌈
## 1.4 렉서의 출력, Token: 문법적으로 의미를 갖는 최소 단위 문자열
### 1.4.1 정의
**문법적으로 의미를 갖는 최소 단위 문자열**
- 단순히 character 단위로 자르면 안 됨
- 예: `if`는 `i`, `f` 두 글자가 아니라 한 덩어리(`if`)가 token
- `==`도 마찬가지로 한 덩어리
### 1.4.2 분류
|종류|설명|예시|
|---|---|---|
|ID|함수, 변수, 타입 등의 **이름**|`a`, `b`|
|NUM|정수 값의 표현|`0`|
|PAREN|열고 닫는 괄호|`(`, `)`|
|IF|`if`문 키워드|`if`|
|OP|비교, 대입 등 **연산자**|`==`, `=`|
|SEMICOLON|Statement의 마지막 표시|`;`|
|...|...|...|
### 1.4.3 Token 타입 정의 (1차 시도)
```fsharp
type Token =
| ID of string
| NUM of string
| PAREN of string
| IF of string
| OP of string
| SEMICOLON of string
// | ...
let tokens =
[ IF "if"; PAREN "("; ID "b"; OP "=="; NUM "0"; PAREN ")";
ID "a"; OP "="; ID "b"; SEMICOLON ";" ]
```
### 1.4.4 Token 타입 재정의 (Lexeme 분리)
> **Lexeme(어휘소): Token의 실제 값**
```fsharp
type Lexeme = string
type Token =
| ID of Lexeme
| NUM of Lexeme
| LPAREN | RPAREN | IF | EQ | ASSIGN | SEMI
// | ...
let tokens =
[ IF; LPAREN; ID "b"; EQ; NUM "0"; RPAREN;
ID "a"; ASSIGN; ID "b"; SEMI ]
```
#### 1.4.4.1 달라진 점
- `LPAREN`, `RPAREN`, `IF`, `EQ`, `ASSIGN`, `SEMI`는 값이 **고정**이라 따로 lexeme을 저장할 필요 없음 (`(`는 그냥 `(`)
- 첫 번째 방식은 어차피 고정인데 따로 저장하니까 불필요한 메모리 + 비교 비용 증가
- 그래서 tokens에서도 문자열이 아니라 **타입 자체로 표현**됨
### 1.4.5 주석/공백은 토큰에 포함시키는가?
- 문법적으로 **의미가 있다면 token에 포함**
- 예: Python의 `INDENT`, `DEDENT`
- **일반적으로는 token에서 제외**
## 1.5 Lexer의 의의 (Lexical Analysis를 하는 이유)
1. 다음 단계(Parsing)에서 더 간결한 입력을 받을 수 있음
- `char list` vs `Token list` → 후자가 훨씬 다루기 좋음
2. 어휘 분석이 구문 분석보다 더 쉬운 문제
- Chomsky 계층
Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable
- Lexer는 Regular, Parser는 Context-Free 다룸
```
// Chomsky Hierarchy
recursively enumerable
└─ context-sensitive
└─ context-free ← Parser가 받아들이는 입력
└─ regular ← Lexer가 받아들이는 입력
```
## 1.6 Lexer 동작 예제
### 1.6.1 정상 입력
```
입력: if (b == 0) a = b;
출력: [ IF; LPAREN; ID "b"; EQ; NUM "0"; RPAREN;
ID "a"; ASSIGN; ID "b"; SEMI ]
```
### 1.6.2 어휘 오류
> **어휘 (lexical)**: 단어 수준. "이게 우리 언어의 단어인가?"
```
입력: if (b == 1x23) a = b;
출력: Error occurred at Line: 1, Col: 10!
```
- `1x23`은 NUM도 ID도 아님 → 정의되지 않은 token
- **어휘 오류는 무조건 Lexer에서 잡아야 한다.**
### 1.6.3 문법 오류 (Lexer는 통과시킴)
> **문법 (syntactic)**: 문장 수준. "이게 문장 구조에 맞는가?"
```
입력: of (b == 0) a = b;
출력: [ ID "of"; LPAREN; ID "b"; EQ; NUM "0"; RPAREN;
ID "a"; ASSIGN; ID "b"; SEMI ]
```
- `of`는 ID로 인식되어 token으로 잘 만들어짐
- 의미상으로는 `if`여야 하는데 `of`인 게 잘못이지만, 그건 **문법 오류**
- **문법 오류는 Parser에서 잡는다.**
## 1.7 여기까지 정리
- Lexer는 **문자열을 Token의 나열로 분해**하는 과정
- Token은 **문법적으로 의미를 갖는 최소 단위 문자열**
- Lexical Analysis는 **Parsing을 보다 수월하게** 하도록 도와줌
→ 그럼 Lexer를 어떻게 구현할까?
---
# 2. REGULAR EXPRESSION
## 2.1 Lexer 구현 요구사항
### 2.1.1 C23의 Integer [[constant]]
- 정수는 숫자로 시작
- 근데 소수점이나 지수 $e$는 없음
- 앞에 진수 표기(0x15, 0b101 이런 거)는 됨
- 뒤에 타입 표기(123U, 123L, 123UL 이런 거)는 됨
- 숫자 사이에 `'` 넣을 수 있음 = [[digit seperator]]
- 당연히 값 계산할 때는 무시
### 2.1.2 Ad-hoc Lexer (C23 Integer constant 처리 Lexer)
- Left-to-Right: 왼쪽부터 읽는다는 소리임
- Lookahead 필요: 뒤 내용 봐야 한다는 소리임
- 다시 시작할 수도 있음: invalid하면 다시 해석
```python
def get_int_token(s, pos):
start = pos # [1] 토큰 시작 위치 저장
# Check prefix
if s[pos] == '0' and s[pos+1] in 'xX':
pos += 2
chars = hex_chars # [2] 16진수 시작 (0x...)
elif s[pos] == '0' and s[pos+1] in 'bB':
pos += 2
chars = bin_chars # [3] 2진수 시작 (0b...)
else:
chars = dec_chars # [4] 기본은 10진수
# Read chars
while s[pos] in chars or s[pos] == '\'':
pos += 1 # [5] 숫자 계속 읽기 (digit separator 포함)
# 나중에 끝 위치가 pos가 됨
# Check floats
if s[pos] in '.eE':
return Invalid(start) # [6] float, e면 int 아님 → rollback
# Check suffix
while s[pos] in 'uUlL':
pos += 1 # [7] suffix (unsigned, long 등)
# Return
return Token(INT, s[start:pos]) # [8] 최종 토큰 생성
```
### 2.1.3 Ad-hoc Lexer의 문제점
1. 복잡한 구현
1. 한 종류 token 분석하는데 이미 분기가 많음
2. 비효율
1. invalid한 순간 바로 처음으로 돌아가야 하니까...
### 2.1.4 Lexer Design 요구사항
1. `기능` 문자열을 Token으로 구분할 수 있어야 함
2. `명확성` Token을 명확히 정의할 수 있어야 함
3. `효율성` 효율적으로 Token 분리
1. 각 문자열을 $O(1)$번 만큼 보는 게 목표
## 2.2 `요구사항2` Token을 어떻게 정의 & 표현해야 할까? → Grammar
> 문자열을 Token으로 구분해야 하는데, 이때 필요한 것은 명확성이다.
> 어떤 문자열이 토큰이고, 어떤 문자열이 토큰이 아닌가?
> 즉, 토큰 문자열을 어떻게 '정의'하고 '표현'해야 하는지가 새로운 문제다.
> 해결: Grammar을 통해 정의 및 표현한다.
### 2.2.1 Token 문자열의 정의 문제
- 예시
- `NUM of Lexeme * Info`
- NUM의 lexeme은 문자열이지만, **모든 문자열이 NUM의 lexeme인 것은 아님**.
- 즉, "어떤 문자열이 NUM이고, 어떤 문자열이 아닌가?"를 **명확히 정의**해야 함.
→ Token 문자열을 어떻게 (1) **정의**하고 (2) **표현**할까?
### 2.2.2 Token 정의의 도구: Language
> Token을 정의한다 = 그 Token의 Language를 정의한다
- **Language**: 특정 **규칙**을 만족하는 **문자열의 집합**
- **Alphabet**: 언어를 구성하는 **글자들의 집합**
- 예: `{0, 1}` — 이진수의 alphabet
- **Grammar**: 언어를 이루고 있는 **규칙들의 집합**
- 좌변 → 우변: 좌변을 우변으로 유도
```
// Grammar의 예시
<두 글자 이상 이진수> → 1 <한 글자 이상 이진수>
(두 글자 이상이면 첫 자리는 1만 올 수 있다)
<이진수 문자열> → <이진수 문자열> 0
<이진수 문자열> → <이진수 문자열> 1
(문자열 뒤에 0 또는 1이 붙을 수 있다)
```
### 2.2.3 Grammar: 4-tuple로 정의하기
문법은 4-tuple $(T, NT, S, P)$:
- $T$: **Terminal**들의 집합 (= Alphabet)
- 보통 소문자로 표기
- $\epsilon \in T$ (empty string, 길이 0인 특수 문자)
- 예: `{0, 1}`
- $NT$: **Non-terminal**들의 집합
- 아직 완성되지 않은 중간 상태
- 보통 대문자로 표기
- 예: `{<이진수 문자열>, ...}`
- $S$: 문자열 생성 시작을 나타내는 **특별한 기호** ($S \in NT$)
- $P$: 문법 **생성 규칙**들의 집합
- 예: `{<이진수 문자열> → <이진수 문자열> 0, ...}`
```
// 예시: C23의 Integer Constant Grammar
<integer_constant> ::= <hex_constant>
| <bin_constant>
| <dec_constant>
| ...
<dec_constant> ::= <dec_constant_nosuffix>
| <dec_constant_nosuffix> <int_suffix>
| ...
<int_suffix> ::= uL
| ...
<dec_constant_nosuffix> ::= 1 <digit>
| 2 <digit>
| ...
<digit> ::= 0 | 1 | 2 | ...
```
## 2.3 ⚠️ `요구사항2` Token을 효율적으로 정의하려면? → Regular Grammar
> Grammar을 통해 Token을 정의 및 표현하기로 했다.
> 이때 컴퓨터가 인식할 수 있는 가장 단순한 종류의 언어, RL과 RL을 구성하는 RG를 도입한다.
### 2.3.1 Regular Language
- 컴퓨터가 인식할 수 있는 **가장 단순한 종류의 언어**
- Token이 반드시 RL이어야 하는 건 아니지만, **RL로 정의할 수 있으면 좋음** (Lexer를 효율적으로 만들 수 있음)
### 2.3.2 Regular Grammar
Regular Grammar $(T, NT, S, P)$는 다음 두 성질 중 **하나**를 만족하는 문법:
#### 2.3.2.1 RG의 성질: Left-regular grammar (left-linear grammar)
$P$의 모든 규칙이 다음 세 형태 중 하나:
- $A \to \epsilon$ (NT에서 입력 없이 끝낼 수 있음)
- $A \to a$ (NT에서 a 한 글자 읽고 끝)
- $A \to Ba$ ⚠️(NT B에서 a를 읽고 NT A로 — NT가 **왼쪽**)
#### 2.3.2.2 RG의 성질: Right-regular grammar (right-linear grammar)
$P$의 모든 규칙이 다음 세 형태 중 하나:
- $A \to \epsilon$
- $A \to a$
- $A \to aB$ ⚠️(a를 읽고 NT B로 — NT가 **오른쪽**)
→ **단순한 형태만 허용** 하는 게 핵심.
> ⚠️ 3/23 수업에서 추가 설명해주신다고 했는데 뭐였는지 기억이 안 남
```
// 예시: C23의 Integer Constant Regular Grammar
<integer_constant> ::= 1 <dec_constant>
| 2 <dec_constant>
| ...
<dec_constant> ::= 0 <dec_constant>
| 1 <dec_constant>
| ...
| 9 <dec_constant>
| epsilon
| u <unsigned_suffix>
| ...
```
→ 가능은 한데 **너무 복잡함**.
요구사항 2의 '명확성'에 '가독성'을 더해서,
더 읽기 좋은 표현은 없을까?
## 2.4 RG의 복잡성을 보완하는 최종 Token 정의 방법 → Regular Expression
> RG는 단순하지만, 사람이 읽기에는 가독성이 떨어진다.
>
> RG로 표현된 언어는 그에 해당하는 RE가 있고,
> RE에 대해 이를 표현하는 RG도 있다.
> *L(RE)* RE가 받아들이는 **문자열의 집합** = 언어
>
> 즉, 둘은 동치인데 가독성 이슈로 RE를 사용한다고 보면 된다.
### 2.4.1 RE의 정의
- **문자열의 패턴**을 나타내는 방법
- Regular grammar보다 **사람이 이해하기 훨씬 쉬움**
- $L(RE)$: RE가 받아들이는 **문자열의 집합** (= 언어)
- RE는 **귀납적**으로 정의됨 → 차근차근 따라가야 함
### 2.4.2 RE의 귀납적 정의 — Base Case
| RE | 의미 | $L$ |
| ---------- | -------------------- | -------------------- |
| $\epsilon$ | 길이가 0인 문자열 패턴 | $L(\epsilon) =$ {""} |
| $a$ | alphabet `a` 한 글자 패턴 | $L(a) =$ {"a"} |
### 2.4.3 RE의 귀납적 정의 — Inductive Case
#### 2.4.3.1 Concatenation: $R \cdot S$
$L(R \cdot S) = {r \cdot s \mid r \in L(R), s \in L(S)} = L(R) \cdot L(S)$
- 두 RE $R, S$에 대해, $L(R)$과 $L(S)$의 문자열이 **연결된** 패턴.
- $\cdot$ 는 **자주 생략**됨 (예: `RS`)
- 예: $L(ab) = {"ab"}$
#### 2.4.3.2 Alternation: $R \mid S$
$L(R \mid S) = L(R) \cup L(S)$
- $L(R)$, $L(S)$ 둘 중 **하나에 속하는** 패턴.
- 예: $L(a \mid b) = {"a", "b"}$
#### 2.4.3.3. Kleene Star: $R^*$
$L(R^*) = L(\epsilon) \cup L(R) \cup L(R^2) \cup \cdots$
> $R^n$ = $R$을 $n$회 concatenate
- $L(R)$에 속하는 문자열의 **0회 이상 반복**.
- 예: $L(a^*) =$ {"", "a", "aa", "aaa", ...}
- **빈 문자열 포함** 주의!
#### 2.4.3.4 Group: $(R)$
$L((R)) = L(R)$
- 우선순위 조정용
- 예: $L((a)) =$ {"a"}
### 2.4.4 RE 각 Case 간의 우선 순위
$\ast \ > \ \cdot \ > \ \mid$
- 예: `ab|cd*` 의 가능한 해석 후보
- `(ab)|(c(d*))` ← **정답**
- 우선순위에 따라 `*`이 가장 강하므로 `d*` 먼저, 그 다음 `c·d*` (concat), 마지막으로 `ab | (cd*)`.
### 2.4.5 RE 예제
1. $(0|1)^* 0$의 의미: 모든 이진 문자열 중 마지막 문자가 0인 것들의 집합
1. $L(0|1) = {"0", "1"}$
2. $L((0|1)^*) = {"", "0", "1", "00", "01", "10", "11", \dots}$
3. 위에 `0`을 concat: ${"0", "00", "10", "000", "010", "100", "110", \dots}$
4. → **모든 이진 문자열 중 마지막 문자가 0인 것들의 집합**
2. Alphabet `{"a", "b"}`, a가 짝수 번 등장하는 RE: $b^*(a(b^*)a(b^*))^*$
1. b는 어디든 자유롭게 등장 가능 (a 개수에만 집중하면 됨)
2. 핵심 아이디어: "a 두 개"를 한 덩어리로 묶어서 반복
→ 한 덩어리에 a가 2개씩 들어있으면, 몇 덩어리든 a 총 개수는 항상 짝수
3. "a 두 개 덩어리"를 RE로 표현:
- 맨 앞에 b가 올 수 있음: b*
- 첫 번째 a: a
- a 사이에 b가 올 수 있음: b*
- 두 번째 a: a
- 뒤에 b가 올 수 있음: b*
→ 한 덩어리: a(b*)a(b*)
(앞쪽 $b^*$는 덩어리 바깥에서 따로 처리)
1. 이 덩어리를 0번 이상 반복: (a(b*)a(b*))*
→ a 개수: 0, 2, 4, 6, ... (항상 짝수) ✅
2. 맨 앞에도 b가 자유롭게 올 수 있게 b*를 앞에 붙임:
→ b*(a(b*)a(b*))*
3. 검증:
- 0번 반복: b* → "", "b", "bb", ... (a 0개)
- 1번 반복: b*ab*ab* → "aa", "aba", "baab", ... (a 2개)
- 2번 반복: b*ab*ab*ab*ab* → "aaaa", "abaaba", ... (a 4개)
→ 모든 경우 a 개수가 짝수 ✅
1. 내가 썼던 답: $((b^*)a(b^*)a(b^*))^*$ . 이것도 맞다고 함.
### 2.4.6 RE의 Syntactic Sugar
> Syntactic Sugar: 기능을 추가하진 않지만 **편의**를 위해 도입된 문법
| 표기 | 의미 | 기본 RE로 표현 |
| -------------- | ----------------------- | ----------------- |
| $R^+$ | 1회 이상 반복 | $RR^*$ |
| $R?$ | 선택적 존재 (있어도 없어도 됨) | $\epsilon \mid R$ |
| $[0\text{-}9]$ | ${0, 1, \dots, 9}$ 중 하나 | {0, 1, ..., 9} |
| $[a\text{-}z]$ | ${a, b, \dots, z}$ 중 하나 | {a, b, ..., z} |
| $[A\text{-}Z]$ | ${A, B, \dots, Z}$ 중 하나 | {A,B, ..., Z} |
### 2.4.7 Regular Grammar = Regular Expression
- Regular grammar로 표현된 언어는 **그에 해당하는 RE가 있고**,
- RE에 대해 **이를 표현하는 Regular grammar가 있음**
→ **두 표현은 동치**. 증명은 생략.
예시: C23의 Integer Constant RE (c.f. RG로 표현했던 거)
$(0|([1-9]('?[0-9])^*))(u|U)?(ll|LL|l|L)?$
해석:
- `0` 또는
- `[1-9]` 다음에 `(' 가 있어도 되고 없어도 되고 + [0-9])` 의 0회 이상 반복
- 그 뒤에 `u` 또는 `U` (선택적)
- 그 뒤에 `ll` / `LL` / `l` / `L` (선택적)
(같은 내용을 grammar로 쓰면 페이지 한가득. RE로 쓰면 한 줄.)
## 2.5 Token을 RE로 정의하기
> §2.1.4에서 Lexer Design의 요구사항으로 '문자열을 토큰으로 구분하는' 기능과
> 그 기능의 추가적인 요구사항으로 토큰 정의의 명확성, 토큰 분리의 효율성이 등장했다.
>
> 토큰을 '명확하게' 정의하기 위한 고민의 과정이 §2.2 ~ §2.4다.
>
> §2.2에서는 토큰을 정의하기 위해 G를 들여왔고,
> §2.3에서는 Grammar 중에서도 컴퓨터가 받아들이는 가장 단순한 형태인 RL의 RG를 선택했다. 다만 RG는 가독성이 떨어진다는 문제가 있었다.
> §2.4에서는 이 문제를 해결하는 RE(RG와 동치)를 도입했다.
>
> 이렇게 토큰 정의 방식이 확정되었으니, 실제 코드를 보자.
### 2.5.1 코드
```fsharp
type Token =
| ID of Lexeme * Info
// alphabet_ + (alphanumeric_)*
// 첫 글자: 문자/_ 이후: 문자/숫자/_ 0개 이상
// → [a-zA-Z_][a-zA-Z0-9_]*
| NUM of Lexeme * Info
// non-zero numeric + numeric*
// → [1-9][0-9]*
| LPAREN of Info | IF of Info
// | ...
```
### 2.5.2 식별자(ID) Token
- **첫 글자**: alphabet + underscore
- $([a\text{-}z] \mid [A\text{-}Z] \mid \_)$
- $\text{letter} = [a\text{-}z] \mid [A\text{-}Z]$ 로 정의하면 → $(\text{letter} \mid \_ )$
- **그 이후**: alphanumeric + underscore
- $(\text{letter} \mid [0\text{-}9] \mid \_)^*$
- $\text{digit} = [0\text{-}9]$ 로 정의하면 → $(\text{letter} \mid \text{digit} \mid \_)^*$
- **ID Token RE**: $(\text{letter} \mid \_)(\text{letter} \mid \text{digit} \mid \_)^*$
## 2.6 `요구사항1` Token을 어떻게 구별할까? → FSM
> §2.1.4에서 짚은 Lexer Design 요구사항 중 **'토큰 정의의 명확성'(요구사항 2)** 은 Grammar → Regular Grammar → Regular Expression의 과정을 통해 **RE로 확보되었다.**
>
> 하지만 남은 요구사항이 있다. '문자열을 토큰으로 구분한다'(요구사항 1, 기능) 는 토큰의 '정의'만으로는 해결할 수 없다.
>
> 왜 정의만으로는 부족한가?
> '정의한다'와 '판별한다'는 다른 일이다.
> 정의는 "이 언어에 속하는 문자열은 이런 패턴이다"라고 기술하는 것이고,
> 판별은 임의의 문자열을 받아서 "이게 그 언어에 속하는가?"를 계산해내는 것이다.
>
> RE는 패턴으로, 정의만 제공한다.
> 즉, RE는 명세서이지 실행기가 아니다.
>
> 우리에게 필요한 건 RE라는 명세서를 보고
> "이 문자열이 명세에 맞는지" 자동으로 판단해주는 기계(인식기)다.
### 2.6.1 RG/RE의 문제점: 언어를 '정의만' 함
> 예시:
> $(0|([1-9]('?[0-9])^*))(u|U)?(ll|LL|l|L)?$를 만족하는 `155991ull`이 있음.
> 이때, `155991ull`이 C23의 Integer Constant 언어에 속하는가?
> → 정의만 보고는 알 수 없고, **인식기**가 필요.
→ 문자열이 그 언어에 속하는지 어떻게 판별할까?
### 2.6.2 해결: 직관적 아이디어
`else`가 키워드일 때 `elsea`라는 입력을 만나면:
```
e → "e가 있네"
el → "el이 있네"
els → "els가 있네"
else → "else인가?"
elsea → "아니었군.. (else 키워드는 아니고 ID구나)"
```
각 시점마다 **"지금까지 읽은 게 어떤 상태인가"** 를 추적해야 함.
→ 이게 바로 **Finite State Machine (FSM)** 의 아이디어.
### 2.6.3 해결: Finite State Machine (FSM)
#### 2.6.3.1 SM과 FSM
- 각각의 서로 다른 순간을 **서로 다른 "상태"**로 구분
- 아무것도 안 읽은 상태
- `e`를 읽은 상태
- `el`을 읽은 상태
- ...
- 각 상태는 **문자 하나를 읽을 때마다 변함**
- **State Machine**: 상태(State)와 상태 사이의 전이(Transition)를 나타내는 장치
- **Finite State Machine**: *유한한* State를 갖는 State Machine
```
// 예시: else를 인식하는 FSM
e l s e a
(s0) ───→ (s1) ───→ (s2) ───→ (s3) ───→ ((s4)) ───→ (s5)
↑
// 화살표: 시작 상태
// 이중 원: 종료 상태 (accepting state)
```
#### 2.6.3.2 FSM의 형식적 정의
FSM은 5-tuple $(\Sigma, S, s_0, \delta, F)$:
- $\Sigma$: **Alphabet**들의 집합
- $S$: **State**들의 **유한** 집합
- $s_0$: 시작 상태 ($s_0 \in S$)
- $\delta$: state의 transition 함수 ($\delta: S \times \Sigma \to S$)
- "현재 상태 + 입력 문자 → 다음 상태"
- $F$: 종료 상태들의 집합 (공집합 가능)
> 예제 (위 else FSM의 형식적 표현)
- $\Sigma = \{a, e, l, s\}$
- $S = \{s_0, s_1, s_2, s_3, s_4, s_5\}$
- $s_0$: initial state
- $\delta = {(s_0, e) \to s_1,\ (s_1, l) \to s_2,\ (s_2, s) \to s_3,\ (s_3, e) \to s_4,\ (s_4, a) \to s_5}$
- $F = {s_4}$
## 2.7 정리
- Token은 **Regular Language 범위에 속하도록** 정해짐
- **Regular Grammar**로 Token 문자열을 **정의**
- **Regular Expression**으로 보다 **읽기 편하게** Token 문자열을 표현
- Regular Grammar / Expression은 Token을 **정의만 할 뿐 판별하진 못함**
→ 판별을 위해서는 **FSM**이 필요
---
# 3. `요구사항1` 토큰 구별을 위한 RE → FSM
> RE → FSM의 예제를 먼저 확인하고,
> 이 예제를 수행하는 데 사용하는 알고리즘 TC에 대해 다룬다.
>
> TC는 RE를 FSM 중에서도 NFA로 변환하는 알고리즘.
> 다만, NFA는 비효율적이라는 문제가 있다.
> 왜? ε를 허용해 ε-transition이 있고,
> ε-transition이 있으니 한 상태에서 갈 수 있는 상태가 여럿 있을 수 있기 때문이다.
>
> 이를 해결하기 위해 NFA → DFA 알고리즘인 SC를 도입한다.
> DFA는 결국 NFA에서 ε와 ε로 인한 영향들을 줄인 구조다.
>
> SC의 아이디어는 ε로 갈 수 있는 상태 집합인 ε-closure의 도입에서 시작하는데,
> 이는 ε-closure로 상태를 묶어나가면서 ε와 ε-transition을 없애기 위한 시도.
>
> 이 아이디어를 기반, ε-closure + worklist 패턴으로 SC는 구현된다.
> 예제로 다루었던 `(0|1)*0`도 훨씬 쉽게 변환할 수 있다.
## 3.1 RE → FSM 예제
### 3.1.1 단일 문자 $a$
![[스크린샷 2026-04-26 오후 11.12.22.png]]
### 3.1.2 Kleene Star $a^*$
![[스크린샷 2026-04-26 오후 11.12.25.png]]
### 3.1.3 $(0|1)^*0$
![[스크린샷 2026-04-26 오후 11.12.28.png]]
### 3.1.4 아이디어: $\epsilon$의 활용
![[스크린샷 2026-04-26 오후 11.12.31.png]]
- "공백 문자"는 있든 없든 같음
## 3.2. RE → NFA(Non-deterministic Finite Automata) 알고리즘: Thomson's Construction
### 3.2.1 TC의 정의
- RE → NFA
- **귀납적으로 정의된 알고리즘** (RE 자체가 귀납적으로 정의되므로)
- 각 RE 케이스에 대해 다음 두 가지를 만족시키는 방법 제시:
1. RE를 FSM으로 표현 가능
2. 표현된 FSM은 **start state 1개, final state 1개**를 가짐 (이래야 다음 단계에서 합성 가능)
### 3.2.2 TC의 귀납적 정의 — Base Case $\epsilon$ & **$a$
![[스크린샷 2026-04-26 오후 11.07.04.png]]
### 3.2.3 TC의 귀납적 정의 — Inductive Case
![[스크린샷 2026-04-26 오후 11.07.37.png]]
RE $R$과 RE $S$에 대해
#### 3.2.3.1 Concatenation $RS$
![[스크린샷 2026-04-26 오후 11.07.41.png]]
> R의 final state에서 S의 start state로 $\epsilon$-transition.
> 새 start = R의 start, 새 final = S의 final.
#### 3.2.3.2 Alternation $R|S$
![[스크린샷 2026-04-26 오후 11.07.44.png]]
#### 3.2.3.3 Kleene Star $R^*$
![[스크린샷 2026-04-26 오후 11.07.48.png]]
RE $R$에 대해
![[스크린샷 2026-04-26 오후 11.07.51.png]]
RE $R^*$에 대한 FSM
### 3.2.3 TC의 성질
> 📝 $\epsilon$-transition?
> $\epsilon$을 입력으로 받아 생기는 transition
1. 각 state에 대해 최대
1. 2개의 $\epsilon$-transition과
2. 1개의 알파벳 transition이 존재
2. 시간/공간 복잡도 $O(n)$ ($n$: RE의 크기)
### 3.2.4 NFA의 정의
NFA는 5-tuple $(\Sigma, S, s_0, \delta, F)$로 정의:
- $\Sigma$: Alphabet 집합
- $S$: State들의 **유한** 집합
- $s_0$: 시작 state ($s_0 \in S$)
- $\delta$: state의 transition을 나타내는 함수.
- $\delta : S \times (\Sigma \cup {\epsilon}) \to \wp(S)$
- $S$의 Power set $\wp(S)$으로 감
- $F$: 마지막 상태들의 집합
→ 한 transition으로 **여러 state**에 갈 수 있음 (Non-deterministic)
> 예제: $(0|1)^*0$의 NFA (Thompson's Construction 결과)
![[스크린샷 2026-04-26 오후 11.07.59.png]]
- 9개 state ($s_0$~$s_8$)를 가진 NFA가 만들어짐. 핵심 구조:
- $s_0 \xrightarrow{\epsilon} s_1$
- $s_1$에서 $\epsilon$으로 $s_2$ (0 분기) 또는 $s_4$ (1 분기)로 갈라짐
- $s_2 \xrightarrow{0} s_3$, $s_4 \xrightarrow{1} s_5$
- $s_3, s_5$에서 $\epsilon$으로 $s_6$로 모임
- $s_6 \xrightarrow{\epsilon} s_7$ (반복 탈출), $s_6 \xrightarrow{\epsilon} s_1$ (반복)
- $s_0 \xrightarrow{\epsilon} s_7$ (Kleene star skip)
- $s_7 \xrightarrow{0} s_8$ (마지막 0)
## 3.3 NFA의 문제 — 비효율성
### 3.3.1 문제 상황 → $\epsilon$-transition으로 인해 비효율적
![[스크린샷 2026-04-26 오후 11.08.09.png]]
> NFA는 한 시점에 **여러 상태에 동시에 있을 수 있다**.
> 입력 글자를 하나 읽을 때마다 "현재 가능한 상태"의 집합이 바뀐다.
RE $(0|1)^*0$의 NFA로 문자열 `0010010`이 언어에 속하는지 확인할 때
규칙:
- 입력 글자 하나 읽고 → 그 글자 화살표를 따라 이동
- 도착한 상태들에서 ε로 갈 수 있는 모든 곳까지 추가로 따라감
- 1+2의 결과가 "지금 있는 상태들"
1. 0단계: 시작 (입력 읽기 전)
- 시작점은 s₀
- s₀에서 ε로 이동
- s₀ → s₁ → s₂, s₄
- s₀ → s₇ (위쪽 큰 곡선)
- 지금 있는 상태들: { s₀, s₁, s₂, s₄, s₇ }
- 남은 입력: `0010010`
2. 1단계: 0 읽음
- 0 화살표가 있는 상태: s₂(→s₃), s₇(→s₈)
- 이전 단계 상태들: { s₀, s₁, s₂, s₄, s₇ }
- 입력 읽고 도착한 곳: { s₃, s₈ }
- 거기서 ε로 이동
- s₃ → s₆ → s₇
- s₃ → s₆ → s₁ → s₂, s₄
- 지금 있는 상태들: { s₁, s₂, **s₃**, s₄, s₆, s₇, **s₈** }
- s₈ (accept 상태) 포함 → 여기서 멈췄으면 accept
- 남은 입력: `010010`
3. 2단계: 0 읽음
- 0 화살표: s₂(→s₃), s₇(→s₈)
- 이전 단계 상태들: { s₁, s₂, s₃, s₄, s₆, s₇, s₈ }
- 도착한 곳: { s₃, s₈ }
- ε 이동
- s₃ → s₆ → s₇
- s₃ → s₆ → s₁ → s₂, s₄
- ε 이동까지 합치면: { s₁, s₂, **s₃**, s₄, s₆, s₇, **s₈** }
- s₈ 포함 → 멈췄으면 accept
- 남은 입력: `10010`
4. 3단계: 1 읽음 ← 이미지가 보여주는 시점
- 1 화살표가 있는 상태: s₄(→s₅) 뿐
- 이전 단계 상태들: { s₁, s₂, s₃, s₄, s₆, s₇, s₈ }
- 입력 읽고 도착한 곳: { s₅ } (파란색)
- 거기서 ε 이동
- s₅ → s₆ → s₇
- s₅ → s₆ → s₁ → s₂, s₄
- 지금 있는 상태들: { s₁, s₂, s₄, **s₅**, s₆, s₇ }
- s₈ 빠짐 → 여기서 멈췄으면 reject (001은 1로 끝나서 매칭 X)
- 남은 입력: 0010
### 3.3.2 해결하려면 → DFA (Deterministic Finite Automata)를 만들어야 함
> epsilon transition 때문에
> 한 transition을 통해 여러 state에 갈 수 있는 NFA는 비효율적
>
> 그렇다면, 한 transition을 통해 하나의 state에만 갈 수 있는 건 어떨까?
#### 3.3.2.1 FSM, NFA, DFA
| | DFA | NFA |
| --------------------- | ----------------------- | ------------------------------------------------------------------- |
| **$\delta$** | $S \times \Sigma \to S$ | $S \times (\Sigma \cup {\epsilon}) \to \wp(S)
lt;br>💡 $\epsilon$을 포함 |
| 한 transition의 결과 | **state 1개** | **state 집합** (0개 이상) |
| $\epsilon$-transition | ❌ 없음 | ✅ 있음 |
| 같은 입력에 다른 결과? | ❌ 항상 똑같음 | ✅ 여러 갈래 가능 |
```
// NFA & DFA
FSM (Finite State Machine)
/ \
NFA DFA
(Non-deterministic) (Deterministic)
```
#### 3.3.2.2 DFA의 정의
- 5-tuple $(\Sigma, S, s_0, \delta, F)$로 정의
- $\Sigma$: Alphabet 집합
- $S$: State들의 **유한** 집합
- $s_0$: 시작 state ($s_0 \in S$)
- $\delta$: $S \times \Sigma \to S$ ($\epsilon$ 없음, 결과는 단일 state)
- $F$: 마지막 상태들의 집합
→ 한 transition으로 **하나의 state**에 감 (Deterministic)
> 💡 NFA에서 $\epsilon$-transition을 없애가며 DFA를 만들면 좋겠다!
## 3.4 NFA의 해결 — Subset Construction (NFA → DFA)
### 3.4.1 SC 도입 아이디어 — $\epsilon$-closures의 도입
- $\epsilon$-transition으로 도달 가능한 모든 *state*를 묶어서 **새로운 FSM의 한 state**로 정의.
- 묶인 *state*를 뭐라고 할까?
- $\epsilon$-Closure(s)
- state $s \in S$로부터 $\epsilon$-transition만으로 도달 가능한 모든 state들의 집합
- (자기 자신 포함).
### 3.4.2 ⚠️ SC 알고리즘 — 직관 (예제: $(0|1)^*0$)
1. 시작
1. 입력값 X
2. $\epsilon$-Closure(${s_0}$) = ${s_0, s_1, s_2, s_4, s_5, s_6, s_7}$ ← 새 *state* $q_0$
2. 1단계
1. 입력값 `0`
2. $q_0$에서 0으로 갈 수 있는 곳? $\delta(q_0, 0) = {s_3, s_8}$
3. $\epsilon$-Closure(${s_3, s_8}$) = ${s_1, s_2, s_3, s_4, s_6, s_7, s_8}$ ← 새 *state* $q_1$
4. 새 *state* 집합의 $\epsilon$-transition?
1. $\epsilon$-transition$(\{s_3, s_8\}) = \{e_1, e_2, e_3, e_4, e_6, e_7, e_8\}$
2. ⚠️ e가 뭐임? 새 상태였나...
여기까지 나갔을 때, 새로운 FSM의 현재 모습
⚠️ 왜 왼쪽에 $s_0$이 없는 것인지? DFA는 $\epsilon$이 없어서?....
> 그럼 이렇게 변환한다고 했을 때,
> Initial / Final State는 어떻게 결정할까?
>
> 새 **state**가 NFA의 *initial state*를 포함하면 → DFA에서도 initial
> 새 **state**가 NFA의 *final state*를 포함하면 → DFA에서도 final
### 3.4.3 SC 알고리즘 — 정의
$\text{NFA } (\Sigma, S, s_0, \delta, F) \to \text{DFA } (\Sigma, Q, q_0, \Delta, F')$
### 3.4.4 SC 알고리즘 — 코드
```pseudo
// 초기화 -----------------------------------------------
// DFA initial state에 NFA initial state의 ε-Closure 대입
q₀ ← ε-Closure({s₀}) ✅
// DFA state 집합에 DFA initial state 넣음
Q ← {q₀}
// 워크리스트에 DFA initial state 넣음
WorkList ← {q₀}
// DFA의 함수 집합은 일단 빈 걸로 세팅
Δ ← {}
// 워크리스트 --------------------------------------------
while (WorkList ≠ ∅) do 💼
// 워크리스트가 공집합이 되면 멈춤
// 모든 DFA 상태에 대해 모든 입력 글자를 다 따져볼 때까지 돌면서 확인
WorkList, q ← pop(WorkList) 💼
// 워크리스트에서 DFA state 하나 빼서 q에 저장, 워크리스트도 업데이트
for (a ∈ Σ) do
// 알파벳 집합 Σ에 있는 a에 대해
q' ← ε-Closure(δ(q, a)) ✅
// q'에 q에서 a로 갈 수 있는 곳의 ε-Closure 대입
if (q' ≠ ∅) then
// 만약 q'가 비어있지 않으면
// 비어있음 == q에 있는 어떤 상태에서도 a로 갈 길이 없다 == 스킵
if (q' ∉ Q) then
// 새 state를 발견하면
// 만약 q'가 Q에 포함되어 있지 않으면
// 만약 지금까지 발견한 DFA 상태들의 모음 Q에
// q'가 아직 안 들어갔다면 == 처음 보는 집합이라면
Q ← Q ∪ {q'}
// Q에는 Q와 q'의 합집합 대입
WorkList ← WorkList ∪ {q'} 💼
// 워크리스트에는 워크리스트와 q'의 합집합 대입
// 처음 보는 집합이 아니라면, 무한루프 가능
Δ(q, a) ← q'
// 새 state를 발견하든, 발견하지 않든
// q에서 a로 갈 수 있는 DFA의 상태들을 q'로 저장
// 즉, 화살표를 그림
```
### 3.4.5 SC 알고리즘의 구성 — ε-Closure ✅
```psuedo
Subset Construction (큰 알고리즘)
├─ 내부에서 호출 ─→ ε-Closure Algorithm ✅ (작은 알고리즘)
└─ 내부 구조 패턴 ─→ WorkList Algorithm 💼 (일반 패턴)
└─ 예시 ─→ BFS
```
```psuedo
// ε-Closure Algorithm
ε-Closure(s) ← {s}
while (true) do
if (δ(ε-Closure(s), ε) == ε-Closure(s)) then break
ε-Closure(s) ← ε-Closure(s) ∪ δ(ε-Closure(s), ε)
```
- FSM은 유한한 state를 가짐
- NFA state 개수가 $n$개면 만들 수 있는 subset 개수는 **최대 $2^n$개**
- 따라서 새 state는 유한 → 알고리즘 종료 가능
### 3.4.6 SC 알고리즘의 구성 — WorkList 💼
```psuedo
Subset Construction (큰 알고리즘)
├─ 내부에서 호출 ─→ ε-Closure Algorithm ✅ (작은 알고리즘)
└─ 내부 구조 패턴 ─→ WorkList Algorithm 💼 (일반 패턴)
└─ 예시 ─→ BFS
```
```pseudo
// WorkList Algorithm example - BFS
WorkList ← {start}
visited ← {}
while WorkList ≠ ∅ do
WorkList, node ← pop(WorkList)
if node ∉ visited then
visited ← visited ∪ {node}
// Do something here
for neighbor ∈ neighbors(node) do
WorkList ← WorkList ∪ {neighbor}
```
- 처리해야 할 것들의 목록을 관리하면서,
새로 발견된 것을 추가하고,
더 이상 새 것이 없으면 종료
- **예시: BFS**
→ 이 패턴을 적용한 것이 Subset Construction.
### 3.4.7 SC 알고리즘 예제 — $(0|1)^*0$
#### 3.4.7.1 시작 NFA 구조
![[스크린샷 2026-04-26 오후 11.07.59.png]]
#### 3.4.7.2 Init
$q_0 = \{s_0, s_1, s_2, s_4, s_7\}, \quad Q = \{q_0\}, \quad \text{WorkList} = [q_0]$
Transition Table
| | 0 | 1 |
| ----------------------------------- | --- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | | |
#### 3.4.7.3 q₀ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_0, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\} = q_1$
q0 -> q1 화살표
$\text{WorkList} = [q_1]$
Transition Table
| | 0 | 1 |
| --------------------------------------------- | ----- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | | |
#### 3.4.7.4 q₀ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_0, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = \{s_1, s_2, s_4, s_5, s_6, s_7\} = q_2$
q0 -> q2 화살표
$\text{WorkList} = [q_1;\ q_2]$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.5 q₁ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_1, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = q_1$
q1 -> q1 화살표
$\text{WorkList} = [q_2]$
Transition Table
| | 0 | 1 |
| --------------------------------------------- | ----- | ----- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.6 q₁ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_1, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = q_2$
q1 -> q2 화살표
$\text{WorkList} = [q_2]$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | | |
#### 3.4.7.7 q₂ 처리 (pop) — 입력 0
$\varepsilon\text{-Closure}(\delta(q_2, 0)) = \varepsilon\text{-Closure}(\{s_3, s_8\}) = q_1$
q2 -> q1 화살표
$\text{WorkList} = []$
Transition Table
| | 0 | 1 | |
| --------------------------------------------- | ----- | ----- | --- |
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ | |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ | |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | $q_1$ | | |
#### 3.4.7.8 q₂ 처리 — 입력 1
$\varepsilon\text{-Closure}(\delta(q_2, 1)) = \varepsilon\text{-Closure}(\{s_5\}) = q_2$
q2 -> q2 화살표
$\text{WorkList} = [ \text{ } ]\ \Rightarrow\ \text{종료}$
Transition Table
| | 0 | 1 |
|---|---|---|
| $q_0 = \{s_0, s_1, s_2, s_4, s_7\}$ | $q_1$ | $q_2$ |
| $q_1 = \{s_1, s_2, s_3, s_4, s_6, s_7, s_8\}$ | $q_1$ | $q_2$ |
| $q_2 = \{s_1, s_2, s_4, s_5, s_6, s_7\}$ | $q_1$ | $q_2$ |
#### 3.4.7.9 결과
![[스크린샷 2026-04-26 오후 11.08.25.png]]
Transition Table
| | 0 | 1 |
| --------------------------------------------------- | ----- | ----- |
| $q_0 = {s_0, s_1, s_2, s_4, s_7}$ (initial) | $q_1$ | $q_2$ |
| $q_1 = {s_1, s_2, s_3, s_4, s_6, s_7, s_8}$ (final) | $q_1$ | $q_2$ |
| $q_2 = {s_1, s_2, s_4, s_5, s_6, s_7}$ | $q_1$ | $q_2$ |
> **initial state**: $q_0$ (NFA의 initial state $s_0$을 포함하므로)
> **final state:** $q_1$ (NFA의 final state $s_8$을 포함하므로)
→ 3개 state짜리 깔끔한 DFA. 입력 `0010010`을 따라가며 final state로 끝나는지 확인하면 됨.
---
# 4. Lexer의 구현
## 4.1 현재까지의 흐름 정리 → 질문 2가지
- Lexer는 문자열을 Token의 나열로 변환
- Token은 RL/RE로 정의
- Token을 구별하기 위해 RE를 DFA로 변환
→ 남은 질문
1. DFA는 어떻게 구현하는가?
2. Lexer는 DFA를 어떻게 사용하는가?
## 4.2 `질문1` DFA는 어떻게 구현하는가? → 2D Array
- **2D Array (Table)** 로 구현 (행: state, 열: 알파벳)
- 매 transition마다 $O(1)$ 시간 복잡도
- 길이 $n$짜리 입력에 대해 $O(n)$만에 Token 판별
- 공간 복잡도: $O(|S| \cdot |\Sigma|)$
## 4.3 `질문2` Lexer는 DFA를 어떻게 사용하는가? → 코드 참고
```f#
type Token =
| ID of Lexeme * Info
| NUM of Lexeme * Info
| LPAREN of Info | RPAREN of Info | EQ of Info | ASSIGN of Info
// | ...
```
> 우리는 지금까지 "RE 하나로 하나의 Token을 인식하는 법"만 배웠는데?
> = 우리는 한 종류 토큰만 다룰 줄 아는데?
## 4.3 `질문2` 여러 Token을 동시에 판별하는 방법
지금까지는 한 종류 Token만 판별 가능. 여러 종류는?
- $R_T$: Token $T$에 대한 RE
- $L$: Lexer의 RE
$L = R_{T_1} | R_{T_2} | R_{T_3} | \cdots = R_{ID} | R_{NUM} | R_{LPAREN} | \cdots$
→ 모든 Token RE들을 `|`로 합쳐 하나의 큰 RE를 만들고, 이 RE를 DFA로 변환하면 됨.
## 4.4 고민거리들
### 4.4.1. DFA가 비효율적인 경우
$a(b|c)^*$를 TC + SC 그대로 돌리면 state 4개 ($s_0, s_1, s_2, s_3$).
하지만 직접 그리면 state 2개로 충분: `(s0) --a--> ((s1))`, $s_1$에 b, c self-loop.
### 4.4.2 Table 기반 구현이 비효율적
- 테이블 접근하려면 메모리 주소 계산 필요: `base + (column size)*row + col`
- 메모리 접근 비용
### 4.4.3 Token의 끝 판단 (Maximal Munch)
- `intx=0;`를 어떻게 나누는가? → `intx`, `=`, `0`, `;`
- RE $ab|(ab)^c$가 있고 입력이 `ababab`라면? `ab`인지 $(ab)^c$의 일부인지...
### 4.4.4 Keyword vs Identifier 구분
- `int`는 keyword이지만, identifier RE `[a-zA-Z]+`로도 매칭됨
### 4.4.5 Fortran 77의 공백 문제
Fortran 77에서는 공백이 의미 없음 (`VAR1` == `VA R1`).
```
DO 5 I = 1,25 ← I가 1부터 25까지 도는 DO 루프
DO 5 I = 1.25 ← DO5I 변수에 1.25 할당
// 문자 `.`, `,`까지 봐야 알 수 있음
```
### 4.4.6 PL/I의 키워드 = 변수명 가능 문제
```
IF ELSE THEN THEN = ELSE; ELSE ELSE = THEN
```
→ 코드의 의미(context)를 봐야 ELSE에 대한 판단 가능
### 4.4.7 정리: 핵심 논리만 기억하자
> 지금까지 배운 것들이 전부가 아님. 대학 교과목에서 배워야 하는 것은 각 단원의 **핵심 논리**.
> Lexer 단원에서 기억해야 하는 것: **"Lexer는 RE로 만들어진다"**
## 4.5 정리
- DFA는 table로 구현
- Lexer는 Token들의 RE를 `|`로 연결한 후 DFA로 변환하여 구현
- Lex: 자동 Lexer 생성기
- 실용적인 구현 이슈들이 다수 존재 (최소화, maximal munch, keyword 처리, lookahead 한계 등)