[컴파일러] - 어휘 분석 (Lexical analysis) II

1. 토큰(token)

언어 이론에서 알파벳 (alphabet)은 a, b, 1, 2, /와 같은 기호의 유한 집합이다. 알파벳에 속한 기호들의 유한한 나열을 스트링 (string) 또는 단어 (word)라고 한다. 어떠한 알파벳이 a, b, c를 포함한다면, abc는 이 알파벳으로 만들 수 있는 스트링이 된다. 그러나 만약 어떠한 알파벳이 a, b로 구성된다면 abc는 이 알파벳으로 만들 수 있는 스트링이 아니다.

어떠한 스트링 $s$에 대해 $s$의 절댓값 $|s|$는 스트링에 나열된 기호의 수이며, 이를 스트링의 길이라고 한다. 예를 들어, 스트링 "lexical"의 길이는 7이 된다. 언어 이론에서는 길이가 0인 스트링도 존재하는데, 이를 empty string이라고 한다.

언어 (language)는 어떤 알파벳으로 생성할 수 있는 스트링의 집합니다. 어떠한 스트링도 포함하지 않는 공집합과 빈 스트링만을 스트링으로 갖는 집합도 언어가 될 수 있다. 언어의 정의에서 중요한 것은 언어에 포함된 문자열과 해당 문자열이 갖는 의미가 결합 (binding)되지 않는다는 것이다. 즉, 언어의 정의에서는 해당 언어에 속한 스트링은 아무런 의미를 갖지 않는다는 것이다. C언어에서 int가 정수형 타입을 나타낸다는 것은 언어 자체에서 정의되는 것이 아니라, 의미 분석 (semantic analysis) 단계에서 정의되는 것이다.

2. 언어 도메인에서의 연산

어휘 분석을 수행할 때, 언어에 대한 가장 중요한 연산은 합집합 (union), 접합 (concatenation), 클로저 (closure) 연산이다. 각 연산에 대한 정의와 표기는 아래의 [표 1]과 같다.

[표 1] 언어에 대한 각 연산의 정의 및 표기

L을 알파벳 (위에서 설명한 알파벳이 아님)의 집합 {A, B, C, ..., Z, a, b, c, ..., z}이라 하고, M을 숫자의 집합 {0, 1, 2, ..., 9}으로 정의하면, 언어 L과 M에 대한 각각의 연산 결과는 아래와 같다.

L과 M의 합집합은 길이가 1인 모든 알파벳과 숫자이고, L과 M의 접합은 길이가 2면서 첫번째가 알파벳, 두번째가 숫자인 모든 문자열이다. 두 집합은 모두 유한한 크기를 가지며, L과 M의 합집합의 크기는 62이고, L과 M의 접합의 크기는 520이다. 다음으로 L의 Kleene 클로저 연산에 의해 생성된 집합은 빈 문자열과 영어 문자로 생성할 수 있는 모든 문자열을 원소로 갖는 집합이다. 마지막으로 L의 양의 클로저는 영어 문자로 생성할 수 있는 길이가 1이상인 모든 문자열을 원소로 갖는 집합을 생성한다.

3. 정규 표현식 (Regular expression)

정규 표현식은 수학적으로 정의된 기호와 연산을 이용하여 언어를 귀납적으로 정의하기 위한 방법이다. 정규 표현식에서 정의되는 연산은 접합, 클린 클로저, OR이 있으며, 피연산자는 기호의 유한 집합인 알파벳이나 기호가 된다. 접합 연산의 기호는 따로 표기하지 않으며, 클린 클로저 연산은 *, OR 연산은 |로 표기한다. 연산자 우선순위는 클린 클로저(*)가 가장 높으며, 그 다음으로 접합 연산, OR연산 순서이다. C언어에서 정의된 식별자의 집합을 정규 표현식으로 서술하면, 아래와 같은 정규 표현식으로 정의된다.

letter_는 영어 알파벳과 '_' 기호를 원소로 갖는 기호의 유한 집합이며, $digit$는 숫자 기호를 원소로 갖는 기호의 유한 집합이다. 위의 정규 표현식을 해석하면, C언어의 식별자는 가장 앞에 영어 알파벳 또는 _문자가 하나 나오고, 두 번째 문자부터는 영어 알파벳 또는 _문자와 숫자가 0번에서 무한번 반복되는 문자열로 정의된다. 중요한 점은 정규 표현식은 하나의 특정 문자열을 정의하는 것이 아니라, 문자열의 집합인 언어를 정의한다는 것이다. 물론 정규 표현식으로 정의하는 그대로 C언어를 구현한다면, 식별자의 길이가 무한대가 될 수 있으므로 이는 의미 분석 단계나 기타 다른 단계에서 식별자 길이에 제한을 두어야 한다. 이러한 점은 컴파일 과정이 수학적으로 완벽하게 정의될 수 없도록 한다. 아래는 문자 x, y와 정규 표현식을 이용하여 언어를 생성하는 예제이다.

4. 정규 정의 (Regular definition)

정규 정의는 아래와 같은 형태의 정의를 나열한 것이다.

위의 정의에서 ${r}_{i}$는 어떠한 기호의 집합 $L$과 ${d}_{i}$를 합집합하여 생성된 집합에서 생성될 수 있는 정규식 중 하나이고, ${d}_{i}$는 $L$에 없는 새로운 기호이며 각각의 ${d}_{i}$는 서로 다르다. 위에서 언급한 C언어의 식별자는 아래와 같은 정규 정의에 의해 서술된다.