# 1. Lexer
NFA는
1. RE를 쪼개서
2. 각 부분 만들고
1. 만들 땐 문자열이 다 화살표로 들어가도록
2. 앞뒤로 epsilon transition 넣어서 start / accept 1개씩 되도록 해둬야 편함
3. 합치면 됨
NFA를 DFA로 변환할 때는 transition table 그리면서
```
① DFA 초기 상태 q0 = ε-Closure({NFA의 s0})
② WorkList = {q0}, Q = {q0}
③ WorkList에서 상태 하나 pop
④ 각 알파벳 a에 대해: (표 그려두고 따라가기)
q' = ε-Closure( δ(현재DFA상태, a) )
→ δ(현재DFA상태, a) = 현재 DFA상태에 속한 모든 NFA상태에서 a로 가는 상태들의 합집합
→ q'가 새 상태면 Q, WorkList에 추가
→ Transition Table에 기록
⑤ 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\}$ | | |
둘 모두 주의할 사항
1. start, accpting state 표기
> 📌 **전체 흐름**: RE → (Thompson's Construction) → NFA → (Subset Construction) → DFA → Transition Table
## 1. RE (Regular Expression)
### 1.1 정의 (빠른 참조)
| 표기 | 의미 |
| ------ | ---------------------- |
| `ε` | 빈 문자열 |
| `a` | 문자 a 하나 |
| `RS` | R 다음 S (concatenation) |
| `R\|S` | R 또는 S (alternation) |
| `R*` | R 0회 이상 반복 |
| `R+` | R 1회 이상 (`RR*`와 동일) |
| `R?` | R 0 또는 1회 |
**우선순위**: `*` > `·` (concat) > `|`
### 1.2 📝 문자열 작성 문제 접근법 (예제 (1)번 유형)
**패턴 분해 → 구체적 대입** 순서로 접근.
`(ab|ac)*` 예시:
- `*`는 0회 이상이므로 **ε(빈 문자열)도 포함됨** → 반드시 하나 쓸 것
- 반복 단위가 `ab` 또는 `ac` 하나씩임을 파악
`(0|1)*1100 1+` 예시:
- `(0|1)*` 부분은 어떤 이진 문자열도 가능 (비어있어도 됨)
- 반드시 `1100` 포함, 끝은 `1`이 1개 이상
- 답: `11001`, `011001`, `111001`, `110011`, `0011001` ...
> ⚠️ **주의**: `*`가 붙은 부분은 ε도 유효 문자열임을 잊지 말 것. 5개 이상 요구할 때 길이 변화를 주면서 패턴을 다양하게 보여줄 것.
## 2. Thompson's Construction (RE → NFA)
### 2.1 정의
Thompson's Construction으로 만들어진 NFA는 항상 **start state 1개, final state 1개**.
### 2.2 📝 5가지 규칙 (그리기 패턴)
#### ① ε
```
(s) --ε--> ((f))
```
#### ② 단일 문자 a
```
(s) --a--> ((f))
```
#### ③ Concatenation RS
- R의 final state에서 S의 start state로 ε 연결
- R의 start → 새 start, S의 final → 새 final
```
(s_R) --[R]--> (f_R) --ε--> (s_S) --[S]--> ((f_S))
```
#### ④ Alternation R|S
- 새 start에서 R, S 각각의 start로 ε 두 갈래
- R, S 각각의 final에서 새 final로 ε
```
ε→ (s_R) --[R]--> (f_R) --ε
(new_s) < > ((new_f))
ε→ (s_S) --[S]--> (f_S) --ε
```
#### ⑤ Kleene Star R*
- 새 start → R의 start (ε)
- R의 final → R의 start (ε, 반복)
- 새 start → 새 final (ε, 0회)
- R의 final → 새 final (ε)
```
(new_s) --ε--> (s_R) --[R]--> (f_R) --ε--> ((new_f))
| ↑_______________| ↑
└──────────────────────────────────────────────ε
```
### 2.3 📝 시험 예제 스타일에서 NFA 그리는 순서
1. RE를 **괄호 단위로 파싱** → 가장 안쪽부터 규칙 적용
2. 각 sub-expression에 상태 번호 부여 (s0, s1, s2 ...)
3. 조합 규칙으로 연결
`(ab|ac)*` 접근 예시:
```
① 'a' → (s0) --a--> (s1)
② 'b' → (s2) --b--> (s3)
③ 'ab' = concat → (s0) --a--> (s1) --ε--> (s2) --b--> (s3)
④ 'c' → (s4) --c--> (s5)
⑤ 'ac' = concat → (s6) --a--> (s7) --ε--> (s4) --c--> (s5)
⑥ 'ab|ac' = alternation → 새 start s8, 새 final s9
s8 --ε--> s0 (ab쪽 시작)
s8 --ε--> s6 (ac쪽 시작)
s3 --ε--> s9
s5 --ε--> s9
⑦ '*' 적용 → 새 start s10, 새 final s11
s10 --ε--> s8, s10 --ε--> s11
s9 --ε--> s8 (반복), s9 --ε--> s11
```
> 💡 **팁**: 상태 번호는 증가 순서대로 기계적으로 부여. 헷갈리면 sub-NFA를 박스로 먼저 그리고 나중에 연결.
## 3. Subset Construction (NFA → DFA)
### 3.1 핵심 개념 정의
- **ε-Closure(S)**: 상태 집합 S에서 ε-transition만으로 도달 가능한 모든 상태 (자기 자신 포함)
- **DFA의 각 상태 = NFA 상태들의 부분집합**
- NFA 상태 n개 → DFA 상태 최대 2ⁿ개
### 3.2 📝 Subset Construction 절차 (테이블 채우는 방법)
**단계별 접근 (가장 중요!)**:
```
① DFA 초기 상태 q0 = ε-Closure({NFA의 s0})
② WorkList = {q0}, Q = {q0}
③ WorkList에서 상태 하나 pop
④ 각 알파벳 a에 대해:
q' = ε-Closure( δ(현재DFA상태, a) )
→ δ(현재DFA상태, a) = 현재 DFA상태에 속한 모든 NFA상태에서 a로 가는 상태들의 합집합
→ q'가 새 상태면 Q, WorkList에 추가
→ Transition Table에 기록
⑤ WorkList가 빌 때까지 반복
```
**Final state 판별**: DFA 상태가 NFA의 final state를 **하나라도 포함**하면 DFA에서도 final
### 3.3 📝 ε-Closure 계산 요령
- **자기 자신을 반드시 포함**
- ε 화살표를 따라 **전이적으로** 닫힘 (A→B→C 이면 A의 ε-Closure에 C도 포함)
- 더 이상 새 상태가 나오지 않을 때까지 반복
예시 계산:
```
NFA에서 s0 --ε--> s1, s1 --ε--> s2, s2 --ε--> s3 (이후 없음)
ε-Closure({s0}) = {s0, s1, s2, s3}
```
### 3.4 📝 DFA 변환 실전 예제: `(0|1)*110 01+` 스타일
**(0|1)* 부분이 있는 RE는 거의 항상 초기 DFA 상태에 여러 NFA 상태가 묶임에 주의**
```
(0|1)* 패턴 → ε-Closure({s0})가 start와 loop 상태들 전부 포함
```
시험에서 NFA가 주어지면 이렇게 접근:
|단계|할 일|
|---|---|
|1|ε-Closure({s0}) 계산 → q0 확정|
|2|q0에서 각 알파벳으로 가는 NFA 상태 찾기|
|3|그 결과에 ε-Closure 적용 → 새 DFA 상태|
|4|새 상태 나올 때마다 테이블 행 추가|
|5|모든 행이 채워질 때까지 반복|
### 3.5 ✨ 자주 나오는 패턴별 DFA 형태
#### `(ab|ac)*` 유형 (알파벳 2종, alternation+star)
- DFA 상태 수가 적음 (3~4개)
- 루프 구조 (매칭 완료 후 다시 처음으로 돌아오는 self-loop 또는 back-edge)
- final state = initial state (0회도 허용하기 때문)
#### `(0|1)*11001+` 유형 (이진 패턴 매칭)
- **KMP 느낌**으로 DFA를 이해하면 편함
- "실패했을 때 어디로 돌아가는가"가 핵심
- 상태 수: 고정 패턴 길이 + 알파벳 루프 상태들
#### `(0*|10*)*` 유형 (중첩 star)
- 매우 많은 ε-transition → NFA가 복잡해도 DFA는 단순할 수 있음
- ε-Closure가 커지는 경우: 초기 상태 집합이 매우 많은 NFA 상태 포함
- DFA가 사실상 모든 입력을 받아들이는 구조인지 먼저 직관적으로 파악
> ✨ **(A급)** DFA 최소화(Minimization): 구분 불가능한 상태들을 합치는 과정. 시험에 나온다면 "같은 future behavior를 가지는 상태들은 합칠 수 있다"는 원리로 접근. 같은 final/non-final이고, 같은 입력에 대해 같은 클래스로 가면 합칠 수 있음.
## 4. Transition Table 작성
### 4.1 정의
DFA를 2D 배열로 표현. **행 = 상태, 열 = 알파벳**.
### 4.2 📝 테이블 작성 규칙
q0 = s0의 epsilon closure
Q = q0
worklist = q0
[[#1. Lexer]]의 3.4.7 참고.
| | 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\}$ | | |
### 4.3 📝 Dead State 처리
DFA에서 갈 수 없는 전이는 **dead state(∅)**로 표기. 명시적으로 쓸 수도 있고 `-`로 생략 가능. 교수님 스타일 따를 것 (예제 참고).
> ✨ **(A급)** Dead State를 명시적으로 추가하면 **완전 DFA(Complete DFA)**가 됨. 이 경우 모든 상태에서 모든 알파벳에 대한 전이가 정의됨. 구현 시에는 complete DFA가 더 유리 (조건 분기 불필요).
### 4.4 📝 Subset Construction 결과를 테이블로 옮기는 요령
Subset Construction 과정에서 테이블을 **그 자리에서 바로 채워나가면** 됨. 별도 작업이 아니라 SC 알고리즘의 출력 그 자체임.
SC 과정 중 테이블 업데이트 타이밍:
```
q에서 a로 가는 q' 확정
→ 테이블 [q][a] = q' 기록
→ q'가 새 상태면 행 추가
```
## 5. DFA 구현 & Lexer 활용
### 5.1 DFA 구현 방법
- **2D Array (Table)** 로 구현
- 전이 1회 = O(1), 길이 n 입력 = **O(n)**
### 5.2 여러 Token 동시 인식
모든 Token의 RE를 `|`로 연결 → 하나의 큰 RE → DFA 변환
```
L = R_ID | R_NUM | R_LPAREN | R_IF | ...
```
> ✨ **(A급)** 이 방식으로 만든 DFA에서 **여러 RE가 동시에 매칭**될 경우 우선순위 처리 필요. 일반적으로 **Keyword > Identifier** 우선순위 적용 (예: `int`는 ID가 아닌 keyword로 처리).
### 5.3 ✨ Maximal Munch (A급 포인트)
> "항상 가능한 한 가장 긴 token을 선택한다"
- `intx = 0` → `intx`가 하나의 ID token (int + x가 아님)
- DFA가 더 이상 진행 불가한 지점 직전의 마지막 accepting state까지를 하나의 token으로 인식
### 5.4 ✨ RE → NFA → DFA → Table 전체 흐름 요약 (A급)
```
RE
↓ Thompson's Construction (규칙 5개 암기)
NFA (start 1개, final 1개)
↓ Subset Construction (ε-Closure + WorkList)
DFA (상태 = NFA 상태들의 부분집합)
↓ Transition Table
2D Array (행=상태, 열=알파벳, O(1) 전이)
↓ Lexer
입력 문자열에서 Token 추출
```
## 🗂 빠른 체크리스트 (시험 직전)
- [ ] RE 우선순위 기억: `*` > concat > `|`
- [ ] `R*`는 ε도 포함 → 빈 문자열이 유효 멤버
- [ ] Thompson's Construction 5가지 규칙 손으로 그릴 수 있음
- [ ] ε-Closure: 자기 자신 포함 + 전이적 닫힘
- [ ] Subset Construction: q' = ε-Closure(δ(q, a))
- [ ] DFA final state: NFA final state를 **하나라도** 포함하면 final
- [ ] Transition Table: 행=상태, 열=알파벳, initial/final 표시
- [ ] Dead state는 `-` 또는 `∅`로 표기
---
# 2. Parser
nullable, first, follow 그냥 한 표로
| NT | NULLABLE | FIRST | FOLLOW |
| --- | -------- | ----- | ------ |
| | | | |
이 방식 적용할 때는 그냥 직관적으로 문법 읽어가면서 ㄱㄱ
nullable은 우변에 t 껴있으면 바로 F
first는 우선 기준 NT가 좌변에 있는 것들 다 보기
우변 맨앞에 t 껴있으면 바로 넣고, nt 뒤에 t가 있으면 앞에 있는 nt nullable인지 보기
우변 nt가 좌변 nt로 와있는 곳들 타고타고 내려가면서 체크해보면 됨
| 규칙 형태 | 귀결 |
| --------------------------------------------------------------------------------- | ------------------------------------------------------ |
| $A \to \alpha \gamma \beta \delta$, $\text{NULLABLE}(\beta) = \text{true}$ | $\text{FIRST}(\delta) \subseteq \text{FOLLOW}(\gamma)$ |
| $A \to \alpha \gamma \beta \delta$, $\text{NULLABLE}(\beta\delta) = \text{true}$ | $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(\gamma)$ |
follow가 좀 복잡한데, 이건 기준 NT가 우변에 포함된 경우 보기
그런 경우가 없다 = 그냥 바로 $
그련 경우가 있다 = 우변 NT 뒤에 있는 T 보기 근데 뒤에 뭐가 없으면 바로 $, 뭐가 있으면... T일 경우에는 그거 넣기.
그리고 기준NT가 우변 포함되어 있는데 그걸 타고 또 좌변NT가 우변NT인경우로 올라가면서도 체크해야 함.
LL(1) Parsing Table == select표
| | + | - | * | / | [id] | [num] | ( | ) | $ |
| --- | ------- | ------- | ------- | ------- | ------ | ------- | ----- | --- | --- |
| S | | | | | S→E | S→E | S→E | | |
| E | | | | | E→TE' | E→TE' | E→TE' | | |
| E' | E'→+TE' | E'→-TE' | | | | | | E'→ | E'→ |
| T | | | | | T→FT' | T→FT' | T→FT' | | |
| T' | | | T'→*FT' | T'→/FT' | | | | T'→ | T'→ |
| F | | | | | F→[id] | F→[num] | F→(E) | | |
- **Row**: focus (non-terminal)
- **Column**: lookahead (terminal)
- **Entry**: 선택할 production
- **빈 칸**: 오류(Error)
이 형식임
이거 채울 때는 NULLABLE/FIRST/FOLLOW 기반으로 채우면 됨
$ 포함하는 걸 잊지 말자 epsilon 대신 $가 있다고 보면 됨
![[스크린샷 2026-04-29 오후 12.32.54.png]]
NT를 파싱하려고 하는데, 그 다음에 오는 lookahead T의 정보를 기반으로 규칙을 골라야 하는 상황
기준 NT가 좌변에 있는 것들을 먼저 본다. 그 중에 T가 우변에 있는 것들을 봄. 이 경우에는 일단 집어넣으면 됨.
근데 딱 봤을 때 좌변의 기준 NT에 대한 우변에 기준 T가 없다. 이러면 기준NT가 우변에 있는 더 상위?;; 의 문법들로 넘어가면 됨. 그 상위 문법에 갔더니 우변에 기준T가 있다. 그럼 시작했던 하위문법을 넣어주면 됨.
$도 마찬가지. 이건 특히 어려운데, epsilon이 우변인 문법의 상위 문법으로 올라가면서 상위 문법에도 epsilon이 유지되는지? 보면 된다. 유지된다면 추가하는게 맞는데, 아니면 비워둬야겠지.
LR(0) 파싱을 위한 Viable Prefix 상태 다이어그램
1. 단일 transition에 대한 NFA들 먼저 그리기
2. 그거 이은 여러 transition에 대한 NFA 그리기
1. $A \to \alpha.B\beta$와 $B \to . \gamma$라는 두 Production이 있다면 이어줄 수 있다 (epsilon)
2. $S' \to S$라는 **특별한 production**을 하나 추가한다. 아래 2개 이어주면 됨.
1. $S' \to .S$
2. $S' \to S.$
3. 얘도 1번 규칙에 해당할 수 있음. $S \to . \text{blahblah}$ 가 있다면 $S' \to .S$ 에서 뻗어나오는 epsilon transition으로 $S \to . \text{blahblah}$에 연결 가능.
3. Subset Construction으로 NFA to DFA 변환
1. [[#3.2 📝 Subset Construction 절차 (테이블 채우는 방법)]] 알고리즘 기반
2. Transition table [[#4. Transition Table 작성]] 채우고
3. 그리기
4. DFA 상태들에는
1. $I_n$ 형태의 넘버링이 있어야 하고
2. 안에 마커 포함된 문법 규칙들 있어야 한다
3. epsilon transition 없어야 함
| 최종 상태의 item 형태 | 의미 | 결정 |
| -------------------------------- | -------------------------- | ---------- |
| $A \to \alpha . \beta$ (`.`이 중간) | 아직 불완전한 prefix | **Shift** |
| $A \to \gamma .$ (`.`이 맨 끝) | 완전한 production = handle 발견 | **Reduce** |
이거 그린 다음에 LR(0) Action/Goto Table 그릴 수 있음
- Action: T 기준 (왔을때 뭐할지) (당연히 $ 포함)
- SN: shift to 상태 N
- 마커가 중간에 있으면 일단 shift
- 상태 N = 현재 상태에서 해당 terminal을 읽었을 때 가는 상태
- **RN: reduce to 문법 N** (문법 넘버링은 줄거임)
- 마커가 맨 끝에 있으면 일단 reduce
- 문법 N = 현재 상태의 item이 어떤 production 번호인지
- RN이 하나로 결정되면 LR(0)이기 때문에 (Lookahead 0개 봄) T와는 관련없이 다 같은 RN으로 작성
- A: accept
- Goto: NT 기준 (ㄹㅇ 어디갈지)
- GN: go 상태 N
이 다음에 이제 Conflict 확인 가능
conflict 종류는
1. shift/reduce -> 얘가 문제에 나옴. FOLLOW를 도입한 SLR(1)으로 해결 가능하니까.
1. 그냥 Action 테이블에 SN / RN이 같이 있으면 문제가 되는 것. 한 칸에 뭐든 하나만 있어야 함.
2. 여기서 이제 FOLLOW 셋 구하라는 문제가 나올 거임.
1. 이건 아까처럼 그냥 문법 보고 NULLABLE/FIRST/FOLLOW 찾아보고 FOLLOW만 쓰면 되는데, 직관적으로 NULLABLE/FIRST 스킵하고 FOLLOW만 적는 것도 가능할듯.
2. reduce/reduce
DFA 바로 그리기
![[스크린샷 2026-04-29 오후 1.36.46.png]]
| 구분 | 표현 | reduce 조건 |
| ---------- | ---------------------- | ---------------------- |
| LR(0) item | `L → [id] .` | 무조건 reduce |
| SLR(1) | `L → [id] .` (DFA는 동일) | `token ∈ FOLLOW(L)` |
| LR(1) item | `L → [id] . , =` | lookahead가 정확히 `=`일 때만 |
| LR(1) item | `L → [id] . ,
| lookahead가 정확히 `
일 때만 |
LR(1) 그리기
## LR(1) Viable Prefix DFA 구성 규칙
────────────────────────────────────────────────────────
### 1단계. 단일 transition NFA 그리기
각 LR(1) item (A → α . X β , a) 에 대해:
X 를 읽으면 → (A → α X . β , a) 로 전이
\[O] (A → α . X β , a) ──X──► (A → α X . β , a)
X 는 terminal이든 NT든 상관없음. 그냥 dot을 한 칸 오른쪽으로.
────────────────────────────────────────────────────────
### 2단계. ε-transition으로 NFA 이어붙이기
#### 규칙 1. dot 다음이 NT이면 ε-transition 추가
(A → α . B β , a) 가 있고, B의 production B → γ 가 있다면:
**b ∈ FIRST(β · a) 인 모든 b에 대해**
\[O] (A → α . B β , a) ──ε──► (B → . γ , b)
왜 FIRST(β · a)?
B 를 다 읽고 난 뒤 다음에 올 수 있는 첫 terminal 을 구해야 함.
B 뒤에는 β 가 오고, β 뒤에는 a 가 오니까 → FIRST(β · a)
※ dot 다음이 terminal이면 ε-transition 없음. 1단계 transition만.
#### 규칙 2. Augmented start rule 추가
S' → S 라는 production을 하나 추가하고,
시작 item: (S' → . S , $)
S 가 NT 이므로 규칙 1 적용:
β = ε, a = $ → FIRST(ε · \$) = {$}
→ S 의 모든 production S → γ 에 대해
\[O] (S' → . S , $) ──ε──► (S → . γ , $)
---
# 3. Semantics
symbol table 양식
![[스크린샷 2026-04-29 오후 1.04.40.png]]
이런 식으로...
같아 보이는 symbol이 어느 줄에 binding되는지는 그냥 각각
1. n번 줄의
2. 어떤 스코프의 symbol에 바인딩된다고 쓰면 됨
undeclared identifier: 코딩을 할줄안다면 풀수있다. 선언이 안 되었거나, 더 안쪽 스코프에서 선언되었고 그게 끝났거나.
type error 발생 줄: 코딩을 할줄안다면 풀수있다. 그냥 알아듣게만 쓰면 됨.