- Authors
- Name
- Youngju Kim
- @fjvbn20031
어휘 분석 - 토큰, 패턴, 정규 표현식
어휘 분석(Lexical Analysis)은 컴파일의 첫 번째 단계입니다. 소스 코드의 문자 스트림을 읽어 의미 있는 단위인 토큰으로 분리하는 과정을 살펴보겠습니다.
1. 어휘 분석기의 역할
어휘 분석기(Lexer, Scanner)는 다음과 같은 일을 합니다.
소스 프로그램 (문자 스트림)
|
v
+------------------+
| 어휘 분석기 | <---> 심볼 테이블
+------------------+
|
v
토큰 스트림 (파서로 전달)
주요 기능
- 토큰 인식: 문자들을 토큰 단위로 묶습니다.
- 공백/주석 제거: 파서에게 불필요한 문자를 걸러냅니다.
- 소스 위치 추적: 에러 메시지를 위한 행 번호와 열 번호를 기록합니다.
- 심볼 테이블 관리: 식별자를 심볼 테이블에 등록합니다.
어휘 분석기를 별도로 분리하는 이유
- 설계의 단순화: 파서가 공백과 주석을 신경 쓸 필요가 없습니다.
- 이식성 향상: 입력 장치 종속적인 처리를 어휘 분석기에 격리합니다.
- 효율성: 토큰 인식에 특화된 기법(유한 오토마타)을 적용할 수 있습니다.
2. 토큰, 패턴, 렉심
이 세 가지 개념은 어휘 분석의 핵심입니다.
토큰(Token)
토큰은 프로그래밍 언어의 어휘 단위를 나타내는 추상적인 이름입니다.
패턴(Pattern)
패턴은 토큰을 구성할 수 있는 문자열의 형태를 기술합니다.
렉심(Lexeme)
렉심은 소스 코드에서 패턴에 매치되는 실제 문자열입니다.
예시
C 소스 코드: printf("Total = %d\n", score);
+----------+--------------------------+---------------------+
| 토큰 | 패턴 | 렉심 예시 |
+----------+--------------------------+---------------------+
| id | 문자로 시작, 문자/숫자 조합 | printf, score |
| num | 숫자 하나 이상 | 42, 3, 100 |
| literal | " 사이의 문자열 | "Total = %d\n" |
| lparen | ( | ( |
| rparen | ) | ) |
| comma | , | , |
| semi | ; | ; |
+----------+--------------------------+---------------------+
토큰의 종류
1. 키워드(Keyword): if, else, while, return, ...
2. 식별자(Identifier): 사용자 정의 이름
3. 상수(Constant): 정수, 실수, 문자열 리터럴
4. 연산자(Operator): +, -, *, /, =, ==, !=, ...
5. 구분자(Delimiter): (, ), {, }, ;, ,, ...
3. 토큰의 속성(Attribute)
하나의 토큰 이름에 여러 렉심이 매치될 수 있으므로, 추가 정보가 필요합니다.
소스 코드: position = initial + rate * 60
토큰 스트림:
<id, "position">
<assign_op, >
<id, "initial">
<add_op, >
<id, "rate">
<mul_op, >
<num, 60>
여기서 두 번째 요소가 속성입니다.
식별자의 속성은 보통 심볼 테이블 엔트리에 대한 포인터입니다. 숫자의 속성은 실제 값이 됩니다.
4. 정규 표현식(Regular Expression)
토큰의 패턴을 정의하는 데 **정규 표현식(regex)**을 사용합니다.
기본 연산
알파벳 Sigma 위에서 정의되는 정규 표현식의 기본 연산은 다음 세 가지입니다.
1. 합집합 (Union): r | s
- r 또는 s에 매치되는 문자열
2. 접합 (Concatenation): rs
- r에 매치되는 문자열 뒤에 s에 매치되는 문자열
3. 클로저 (Closure): r*
- r에 매치되는 문자열의 0번 이상 반복
기본 정규 표현식
표현식 설명 매치 예시
-------------------------------------------------
a 문자 'a' 그 자체 "a"
epsilon 빈 문자열 ""
r | s r 또는 s r이 "a", s가 "b"면 "a" 또는 "b"
rs r 뒤에 s "ab"
r* r의 0번 이상 반복 "", "a", "aa", "aaa", ...
확장 표기법
편의를 위한 약어들이 있습니다.
r+ = r r* (1번 이상 반복)
r? = r | epsilon (0번 또는 1번)
[a-z] = a | b | ... | z (문자 클래스)
[^a-z] = a-z 제외한 문자 (부정 문자 클래스)
. = 임의의 한 문자
정규 표현식 예제
// 정수 리터럴
digit = [0-9]
digits = digit+
integer = digits
// 부동소수점 리터럴
fraction = . digits | epsilon
exponent = (E | e)(+ | - | epsilon) digits | epsilon
float_num = digits fraction exponent
// 식별자
letter = [a-zA-Z_]
identifier = letter (letter | digit)*
// 문자열 리터럴 (큰따옴표 내부에 큰따옴표 제외 문자)
string_lit = " [^"]* "
5. 정규 정의(Regular Definition)
복잡한 정규 표현식을 간결하게 표현하기 위해, 정규 표현식에 이름을 붙여 사용합니다.
// C 언어 식별자의 정규 정의
letter_ -> [a-zA-Z_]
digit -> [0-9]
id -> letter_ (letter_ | digit)*
// C 언어 정수 상수의 정규 정의
digit -> [0-9]
nonzero -> [1-9]
decimal -> nonzero digit*
octal_dig -> [0-7]
octal -> 0 octal_dig*
hex_dig -> [0-9a-fA-F]
hex -> 0 (x|X) hex_dig+
integer -> decimal | octal | hex
주의: 정규 정의에서는 순환 참조가 허용되지 않습니다. 각 이름은 이전에 정의된 이름만 참조할 수 있습니다.
6. 입력 버퍼링(Input Buffering)
어휘 분석기는 소스 코드를 한 문자씩 읽어야 하는데, I/O 비용을 줄이기 위해 버퍼링 기법을 사용합니다.
이중 버퍼(Double Buffering)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| E | = | M | * | C | * | * | 2 |eof| . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
lexemeBegin forward
Buffer 1 Buffer 2
- 두 개의 버퍼를 번갈아 사용하여 연속적인 읽기를 보장합니다.
lexemeBegin: 현재 렉심의 시작 위치forward: 현재 검사 중인 문자 위치- 각 버퍼 끝에 센티넬(sentinel) 문자
eof를 놓아 경계 검사를 단순화합니다.
센티넬을 사용한 forward 포인터 이동
// 센티넬 없는 코드 (매번 2번의 검사)
forward++;
if (forward >= bufferEnd) {
// 다음 버퍼 로드
reloadBuffer();
}
if (*forward == EOF) {
// 입력 끝 처리
terminate();
}
// 센티넬 있는 코드 (보통 1번의 검사)
forward++;
if (*forward == EOF) {
if (forward == bufferEnd) {
reloadBuffer(); // 버퍼 끝의 센티넬
forward = bufferStart;
} else {
terminate(); // 실제 입력 끝
}
}
7. 토큰 인식 예제
간단한 언어의 토큰 인식 과정을 살펴보겠습니다.
관계 연산자 인식
relop -> < | <= | <> | > | >= | =
이를 인식하는 과정을 **전이 다이어그램(Transition Diagram)**으로 표현합니다.
시작 --'<'--> s1 --'='--> [return LE]
|
+--'>'--> [return NE]
|
+--other--> [return LT] (retract)
시작 --'='--> [return EQ]
시작 --'>'--> s2 --'='--> [return GE]
|
+--other--> [return GT] (retract)
retract는 forward 포인터를 한 칸 되돌리는 것을 의미합니다. 예를 들어 < 다음에 =도 >도 아닌 문자가 오면, 그 문자를 다음 토큰의 일부로 처리해야 합니다.
식별자와 키워드 인식
시작 --letter--> s1 --letter|digit--> s1
|
+--other--> [키워드 테이블 확인 후 return]
식별자를 인식한 후 키워드 테이블을 검색하여 키워드인지 확인합니다. if, else, while 같은 예약어는 식별자와 형태가 같으므로, 별도 처리가 필요합니다.
// 키워드 테이블 초기화
Map<String, TokenType> keywords = new HashMap<>();
keywords.put("if", TokenType.IF);
keywords.put("else", TokenType.ELSE);
keywords.put("while", TokenType.WHILE);
keywords.put("return", TokenType.RETURN);
// 식별자 인식 후
String lexeme = getLexeme();
if (keywords.containsKey(lexeme)) {
return new Token(keywords.get(lexeme), lexeme);
} else {
return new Token(TokenType.ID, lexeme);
}
8. 간단한 어휘 분석기 구현
Java로 간단한 어휘 분석기를 구현해 보겠습니다.
public class SimpleLexer {
private String input;
private int pos;
public SimpleLexer(String input) {
this.input = input;
this.pos = 0;
}
public Token nextToken() {
skipWhitespace();
if (pos >= input.length()) {
return new Token(TokenType.EOF, "");
}
char ch = input.charAt(pos);
// 숫자: 정수 리터럴 인식
if (Character.isDigit(ch)) {
return readNumber();
}
// 문자: 식별자 또는 키워드 인식
if (Character.isLetter(ch) || ch == '_') {
return readIdentifier();
}
// 연산자 및 구분자
switch (ch) {
case '+': pos++; return new Token(TokenType.PLUS, "+");
case '-': pos++; return new Token(TokenType.MINUS, "-");
case '*': pos++; return new Token(TokenType.STAR, "*");
case '/': pos++; return new Token(TokenType.SLASH, "/");
case '=':
if (peek() == '=') {
pos += 2;
return new Token(TokenType.EQ, "==");
}
pos++;
return new Token(TokenType.ASSIGN, "=");
case '(': pos++; return new Token(TokenType.LPAREN, "(");
case ')': pos++; return new Token(TokenType.RPAREN, ")");
case ';': pos++; return new Token(TokenType.SEMI, ";");
default:
throw new RuntimeException(
"Unexpected character: " + ch + " at position " + pos
);
}
}
private Token readNumber() {
int start = pos;
while (pos < input.length() && Character.isDigit(input.charAt(pos))) {
pos++;
}
return new Token(TokenType.NUM, input.substring(start, pos));
}
private Token readIdentifier() {
int start = pos;
while (pos < input.length() &&
(Character.isLetterOrDigit(input.charAt(pos)) ||
input.charAt(pos) == '_')) {
pos++;
}
String lexeme = input.substring(start, pos);
TokenType type = Keywords.lookup(lexeme);
return new Token(type != null ? type : TokenType.ID, lexeme);
}
private void skipWhitespace() {
while (pos < input.length() && Character.isWhitespace(input.charAt(pos))) {
pos++;
}
}
private char peek() {
return (pos + 1 < input.length()) ? input.charAt(pos + 1) : '\0';
}
}
실행 예시
입력: "x = 10 + y;"
토큰 스트림:
<ID, "x">
<ASSIGN, "=">
<NUM, "10">
<PLUS, "+">
<ID, "y">
<SEMI, ";">
<EOF, "">
9. 에러 처리
어휘 분석기가 어떤 패턴에도 매치되지 않는 문자를 만났을 때의 에러 처리 전략입니다.
- 패닉 모드(Panic Mode): 매치되는 패턴을 찾을 때까지 문자를 건너뜁니다.
- 문자 삭제: 잘못된 문자를 삭제하고 계속 진행합니다.
- 문자 삽입: 빠진 문자를 삽입합니다 (예: 따옴표 짝 맞추기).
- 문자 교체: 잘못된 문자를 올바른 문자로 교체합니다.
실제 컴파일러에서는 가능한 많은 에러를 한 번에 보고하기 위해 복구 후 분석을 계속합니다.
정리
| 개념 | 핵심 내용 |
|---|---|
| 토큰 | 어휘 단위의 추상적 이름 (id, num, relop 등) |
| 패턴 | 토큰을 구성하는 문자열의 형태 (정규 표현식) |
| 렉심 | 패턴에 매치되는 실제 문자열 |
| 정규 표현식 | 합집합, 접합, 클로저의 3가지 기본 연산 |
| 정규 정의 | 정규 표현식에 이름을 붙여 재사용 |
| 입력 버퍼링 | 이중 버퍼와 센티넬로 효율적 I/O |
| 전이 다이어그램 | 토큰 인식 과정을 상태 전이로 표현 |
어휘 분석은 컴파일의 가장 기초적인 단계이지만, 전체 컴파일 시간의 상당 부분을 차지하므로 효율적인 구현이 중요합니다. 다음 글에서는 정규 표현식을 기반으로 어휘 분석기를 자동 생성하는 유한 오토마타를 다루겠습니다.