Compiler - Lexical Analysis (어휘 분석기)
Compiler
컴파일러란?
A compiler is a program that translates computer code in one language into another language.
어떤 언어의 코드 전체를 다른 언어로 바꿔주는 것을 자동으로 수행하는 소프트웨어
컴파일러를 배워야 하는 이유?
컴퓨터는 오직 binary code만 읽을 수 있다. 하지만, 우리가 코딩하는 프로그램은 human-friendly에 치우쳐져 있다.
따라서, 코드를 바이너리 코드로 바꿔주는 과정이 필요하다.
Compiler translates a “high-level” source program into a “low-level” target program.
Interpreter: 한 줄씩(line-by-line) 실행하며 번역
컴파일러와 인터프리터의 차이점
| 구분 | 컴파일러 | 인터프리터 |
|---|---|---|
| Workflow | 전체 코드 번역 후 실행 | 한 줄씩 번역하며 실행 |
| Execution time | 빠름 | 느림 |
| Debugging | 전체 코드 분석 후 오류 출력 | 실행 중 오류 발생 시 즉시 출력 |
| Output program | 기계어 파일 생성 | 별도 기계어 파일 없음 |
| Usage of memory | 번역 후 실행이므로 효율적 | 실행할 때마다 번역 필요 |
| Example | C, C++ | Python, JavaScript |
Structure of Compilers
다음은 컴파일러의 구조이다.
- Front-end: Lexical Analyzer, Syntax Analyzer, Semantic Analyzer
- Back-end: Intermediate Code Generator, Code Optimizer, Code Generator
Analysis: 소스 프로그램을 해석하여 내부 표현을 생성하는 과정
Synthesis: 내부 표현을 바탕으로 타겟 프로그램을 생성하는 과정
이번 포스트는 Lexical Analyzer (Scanner) 를 다룬다.
Lexical Analysis (Scanner)
1. 컴파일러 구조 내에서의 Lexical Analyzer
▪ 역할
- 소스 프로그램을 문자 스트림에서 토큰(Token)으로 분리
- 파서(Parser)에게 토큰을 전달
- 심볼 테이블(Symbol Table)에 식별자 등록
2. 토큰(Token), 패턴(Pattern), 렉심(Lexeme)
▪ Token
- 의미 단위
- 형식:
<token_name, value>
▪ Pattern
- 토큰을 구성하는 문자열 규칙 (정규 표현식 사용)
▪ Lexeme
- 실제 소스 코드에서 토큰 패턴과 매칭되는 문자열
▪ Token 종류 예시
| 종류 | 설명 | 예시 |
|---|---|---|
| Keyword | 예약어 | if, else |
| Identifier | 사용자 정의 이름 | a, val |
| Constant | 숫자 상수 | 3.14, 10 |
| Operator | 연산자 | =, ==, * |
| Punctuation | 구두점 | (, ), , |
| Whitespace | 공백, 탭, 개행 등 | \t, \n, ' ' |
3. 정규 언어와 정규 표현식
▪ Alphabet (Σ)
- 문자들의 유한 집합 (예:
{0, 1},{a, b, c})
▪ String
- Σ로 이루어진 유한 길이의 문자열
▪ Language
- 문자열들의 집합
▪ 정규 표현식 (RE)
- ∅: 빈 집합
- ε: 빈 문자열
- a ∈ Σ: 단일 문자
- 조합 규칙:
r1 | r2: r1 또는 r2r1 r2: r1 뒤에 r2r*: r을 0회 이상 반복
▪ 예시
0|1: 0 또는 1(0|1)*: 0과 1의 임의 반복1*1: 1 또는 11 또는 111 등
4. 정규 표현식 → Finite Automata
▪ FA (Finite Automaton)
- 정규 언어를 인식하는 추상 기계 모델
▪ DFA (Deterministic FA)
- 상태 전이가 유일함
- ε-transition 없음
▪ NFA (Non-deterministic FA)
- 상태 전이가 여러 개일 수 있음
- ε-transition 허용
▪ DFA와 NFA는 표현력이 같음
5. NFA와 DFA 구현 (스캐너 생성 절차)
▪ 전체 흐름
Token 패턴 → 정규 표현식 (RE)
→ NFA (Thompson’s Construction)
→ DFA (Subset Construction)
→ Transition Table → Scanner 코드
▪ Thompson’s Construction
- RE를 NFA로 바꾸는 구조적 방법
- ε-transition 기반 구성
▪ Subset Construction
- NFA → DFA 변환
- 상태 집합을 하나의 DFA 상태로 간주
6. DFA 실행 방식
state ← start
while (input not EOF):
state ← transition[state, input_char]
if (state is final):
Accept
else:
Reject
7. 토큰 판별 규칙 (Longest Match & Priority)
▪ Rule 1: 가장 긴 토큰이 우선
• 예: **는
▪ Rule 2: 우선순위 적용
• 예: if는
▪ 구현 의사코드
while s ≠ "":
idx = 0
for i in range(1, len(s)+1):
if s[0:i] in token_patterns:
idx = i
if idx == 0:
raise Error("No matching token")
else:
classify(s[0:idx])
s = s[idx:]