Free Forum
Title: 오토마타론과 컴파일러 이론의 체계적 정리
Writer: Maroik
Views: 446 Updated: [2025-09-13T10:02:00Z]오토마타론 계층 구조
CL ⊊ FSM ⊊ PDA ⊊ TM
오토마타 이론과 컴파일러 이론의 체계적 정리
오토마타 이론 기호 정리
공통 기호
q₀, q₁, q₂...: 상태 (q₀은 시작 상태)
qf, F: 최종/수락 상태
○: 일반 상태 (원)
◎: 최종 상태 (이중원)
→: 상태 전이
⟲: 자기 자신으로 돌아오는 전이
ε (엡실론): "아무것도 안 함" 또는 "빈 문자열"
FSM 전용 기호
q₀ --a--> q₁ // 'a' 읽기로 q₀에서 q₁로 전이
PDA 전용 기호
읽기, 팝/푸시
a, ε/A // 'a' 읽고, 팝 안 하고, 'A' 푸시
b, A/ε // 'b' 읽고, 'A' 팝하고, 푸시 안 함
TM 전용 기호
읽은심볼/쓸심볼, 방향
a/b, R // 'a' 읽고 'b' 쓰고 오른쪽 이동
R: 오른쪽 (Right), L: 왼쪽 (Left)
계산 모델별 능력
CL (조합논리): [논리연산(산술연산)] 순수 함수
add(3, 5) = 8 ✅
sub(add(3, 5), 2) = 6 ✅ (함수 합성으로 가능)
상태/메모리 저장 ❌
CL 예시: AND 게이트
A ────┤ |‾‾‾\
│ | \
│ | |──── Y = A∧B
│ | /
B ────┤ |___/
FSM: [논리연산(산술연산) + 유한 상태] 패턴 인식 + 상태 기반 제어
정규 표현식 "a*b+" 매칭 ✅
균형 괄호 "((()))" ❌ (중첩 구조 불가)
FSM 예시: 정규표현식 "a*b+" 인식
a
q₀ ⟲
│
│b
↓
◎q₁ ⟲ b
PDA: [논리연산(산술연산) + 유한 상태 + 무한 스택] 중첩 구조 인식, 문맥자유 문법 처리
수식 구조 "((3+5)*2)+1" 파싱 ✅ (문법적 올바름 검사)
균형 괄호 "((()))" 검사 ✅
문맥자유 문법 "a^n b^n" 인식 ✅
메모리 접근 제한 ❌ (심볼 조작만)
PDA 예시: 균형 괄호 "((()))" 검사
'(', ε/(
')', (/ε
q₀ ⟲
│
│ε, Z/ε
↓
◎qf
스택 동작:
읽기: ((()))
1. '(' → 스택: [Z, (]
2. '(' → 스택: [Z, (, (]
3. '(' → 스택: [Z, (, (, (]
4. ')' → 스택: [Z, (, (]
5. ')' → 스택: [Z, (]
6. ')' → 스택: [Z]
스택이 비어있거나 바닥 마커만 남으면 수락
TM: [논리연산(산술연산) + 유한 상태 + 무한 테이프] 모든 계산 가능한 문제
헤드
↓
... │□│1│0│1│1│0│□│ ...
←─────────────→
(무한 테이프)
이론적 기본 연산: Read, Write, Move
TM 예시: palindrome "aba" 판별
실행 과정: q₀ → q₁ → q₂ → q₃ → q₀ → (가운데 문자 확인) → qf
a/X,R b/b,R a/Y,L
q₀ ────────→ q₁ ──────────→ q₂ ────────→ q₃
↑ │
│ │Y/Y,L, X/X,L
│ ↓
└──────── 다시 처리할 문자 찾기 ←──────── 시작으로 돌아감
│
│처리할 문자 없음(가운데 문자만 남음)
↓
◎qf
상세한 실행 과정:
읽기: "aba"
1. q₀에서 시작: [a][b][a] ^
2. 'a' 읽음 → q₁: 'a'를 'X'로 마킹 [X][b][a] ^
3. q₁에서 끝까지 이동: [X][b][a] ^ (b 통과, a까지)
4. q₂에서 끝 'a' 발견: 'a'를 'Y'로 마킹 [X][b][Y] ^
5. q₃에서 시작으로 돌아감: [X][b][Y] ^ ('Y'와 'b' 통과)
6. 다시 q₀: 'X' 발견, 다음 처리할 문자는 'b'
7. 'b'는 가운데 문자(더 매칭할 문자 없음) → qf 수락
언어 계층 대응
정규언어(RL) ↔ FSM
문맥자유언어(CFL) ↔ PDA
문맥민감언어(CSL) ↔ LBA
재귀열거언어(REL) ↔ TM
튜링 완전성
이론적 기본: Read, Write, Move (TM의 primitive operation)
실용적 구현: 논리연산(산술연산(SUBTRACT)) + 메모리 접근 + 조건문 + 분기문
어셈블리: sub, mov, cmp, jmp/je/jne
C: 논리연산(산술연산(-)), 포인터, if, goto
계산 모델의 계층적 구조
오토마타 이론 계층
CL: 논리연산(산술연산)
FSM: 논리연산(산술연산) + 유한 상태
PDA: 논리연산(산술연산) + 유한 상태 + 무한 스택
TM: 논리연산(산술연산) + 유한 상태 + 무한 테이프
메모리 구조
CL: 메모리 없음
FSM: 유한 상태
PDA: 유한 상태 + 무한 스택
TM: 유한 상태 + 무한 테이프
각 오토마타의 실제 활용 예시
FSM: 정규표현식 엔진, 네트워크 프로토콜
PDA: JSON/XML 파서, 프로그래밍 언어 구문 분석
TM: 컴파일러 최적화, 정적 분석 도구
이론적 기반
형식언어: 규칙에 맞는 모든 문자열 집합
오토마타 이론: 그 언어를 처리하는 추상기계의 능력 연구
컴파일러 이론: 오토마타 이론의 실제 구현
발전 과정
오토마타 이론 (1940-50년대 이론) → 컴파일러 이론 (1960년대 구현)
계산 모델의 두 갈래
TM (Turing Machine) ≡ LC (Lambda Calculus)
↓ ↓
C, Java, Python Haskell, Lisp
(명령형) (함수형)
Compilation Process
Source Code
→ Preprocessing (Macro processing/file inclusion) → Preprocessed Source
→ Lexical Analysis (Regular Expression/Finite State Machine/Lexer) → Tokens
→ Syntax Analysis (Context-Free Grammar/Pushdown Automaton/Parser) → Parse Tree/AST
→ Semantic Analysis (Type checking, scope analysis, semantic validation) → Annotated AST
→ Intermediate Code Generation (Generate intermediate representation) → IR (Intermediate Representation)
→ Code Optimization (IR-level optimization) → Optimized IR
→ Code Generation (Target code generation) → Target Code
→ Machine-Level Optimization (Peephole optimization, etc.) → Optimized Target Code
Cross-Process Elements
Symbol Table: Identifier information storage that is continuously referenced and updated throughout all stages
Error Handling: Error detection and reporting at each stage (Lexical Errors, Syntax Errors, Semantic Errors, Runtime Errors)
Compiler Phases
Frontend: Preprocessing → Lexical Analysis → Syntax Analysis → Semantic Analysis → IR Generation
Middle-end: Code Optimization
Backend: Code Generation → Machine-Level Optimization
Post-Compilation (External Tools)
→ Assembling (Convert assembly to machine code) → Object File
→ Linking (Combine object files, library linking) → Executable File
→ Loading (Memory loading) → Running Program
C Compilation Example
C Source Code
→ Preprocessing → Preprocessed Source
→ Lexical Analysis (FSM) → Tokens
→ Syntax Analysis (PDA) → Parse Tree/AST
→ Semantic Analysis → Annotated AST
→ Intermediate Code Generation → IR
→ Code Optimization → Optimized IR
→ Assembly Code Generation → Assembly Code
컴파일러의 실용적 가치
CS 이론의 종합: 자료구조, 알고리즘, 오토마타 이론이 모두 녹아있음
SW 개발 필수: 언어 이해도, 최적화, 디버깅 실력 향상
AI/NLP 기초: 토크나이저(FSM), 파서(PDA), 의미분석(TM) 직접 활용
취업 경쟁력: CS 기초 소양의 핵심
결론 컴파일러 이론 = 이론 CS의 실전 종합반
-
Compiler.zip 4,016KB