[컴파일러] Formal Language & Regular Expression

왜 이걸 배우는지??

컴파일러의 첫 단계인 Scanner(어휘 분석기)는 소스코드를 읽고 토큰을 뽑아낸다. 그런데 "어떤 문자 조합이 유효한 토큰인가"를 판단하는 이론적 기반이 바로 Formal Language와 Regular Expression이다. 즉, 스캐너를 설계하려면 이 개념들이 필요하다.

---

개념 순서: Symbol → String → Language

모든 것은 작은 단위에서 시작해서 점점 쌓인다.

Symbol과 Alphabet

Symbol은 가장 작은 단위다. a, b, 0, 1 같은 개별 문자 하나하나다.

Alphabet(알파벳)은 Symbol들의 유한 집합이다. 수학적으로 Σ (시그마)로 표기한다.

 

Σ₁ = {A, B, C, ..., Z, a, b, c, ..., z}   ← 영어 알파벳 전체
Σ₂ = {0, 1}                                 ← 이진수용 알파벳

C 언어 변수 이름을 정의한다고 하면, 사용 가능한 심볼들의 집합이 곧 그 언어의 Alphabet이다.

String

Symbol들을 이어 붙인 것(concatenation)이 String이다.

Σ = {a, b} 일 때
가능한 string: a, b, aa, ab, ba, bb, aaa, aab, ...

String의 길이는 심볼 개수로 센다. 단, T₂ = {do, case} 처럼 심볼 자체가 여러 글자인 경우 |T₂| = 2다. 글자 수가 아니라 심볼 수를 세는 것이다

특수한 경우로 Empty String(ε, 엡실론)이 있다. 길이가 0인 문자열이다. 어떤 String 앞뒤에 붙여도 결과가 바뀌지 않는다.

u · ε = u
ε · u = u

T* 와 T+

Alphabet Σ가 주어졌을 때, 만들 수 있는 모든 String의 집합을 정의할 수 있다.

Σ⁺ : ε을 제외한 모든 String의 집합 (길이 1 이상) Σ* : ε을 포함한 모든 String의 집합

Σ* = {ε} ∪ Σ⁺

Σ 자체는 유한 집합이지만 Σ*, Σ⁺는 무한 집합이다. 심볼이 하나뿐이어도 자기 자신을 무한히 이어 붙일 수 있기 때문이다.

Language

Σ⁺ 에서 일부만 선택한 부분집합이 Language(언어)다.

C 언어 예시로 보면:

Σ = {A~Z, a~z, 0~9, _}
Σ⁺ = 위 심볼들로 만들 수 있는 모든 string

근데 123_a는 C 언어에서 유효한 변수명이 아님 (숫자로 시작 불가)
→ 유효한 변수명만 모은 집합 = C 언어의 "identifier language"

즉 Language는 "이 언어에서 허용되는 String들의 집합"이다. Σ⁺ 전체가 아니라, 규칙에 맞는 것들만 추려낸 것이다.

 

 

Grammar — 언어를 규칙으로 정의하기

Language를 정의하려면 "어떤 String이 허용되는가"를 기술하는 규칙이 필요하다. 이게 Grammar(문법)다.

Grammar G는 네 가지 요소로 구성된다.

 

G = (Vn, Vt, P, S)

Vn (Non-terminal): 생성 규칙 안에서만 쓰이는 기호. 최종 결과에는 나오지 않는다. 보통 대문자로 표기한다 (예: A, S).

Vt (Terminal): 실제로 String에 나타나는 기호. 최종 결과물이다 (예: a, b, 0).

P (Production rules): 생성 규칙 전체. "A → aB" 형태로 쓴다. "A는 aB로 바꿀 수 있다"는 뜻이다.

S (Start symbol): 어디서 시작하는지. 항상 Non-terminal이다.

예시:

 

S → aA
A → bA
A → b

이 규칙으로 만들 수 있는 string:
S → aA → ab          (길이 2)
S → aA → abA → abb   (길이 3)
S → aA → abA → abbA → abbb  (길이 4)
...
결론: a 뒤에 b가 1개 이상 붙는 패턴 = ab⁺

이처럼 Grammar는 Language를 "생성 규칙"으로 표현하는 방법이다.

 

Regular Expression — 패턴을 간결하게 표현하기

Grammar는 강력하지만 복잡하다. 스캐너처럼 단순한 패턴 인식에는 Regular Expression(정규 표현식)이 더 적합하다.

Regular Expression의 핵심 기호는 세 가지다.

·  (concatenation)  ab    → a 다음에 b
+  (or / union)     a+b   → a 또는 b
*  (Kleene star)    a*    → a가 0번 이상 반복

예시로 읽는 법:

ab*        → a는 반드시 하나, b는 0번 이상
(0+1)*     → 0 또는 1이 0번 이상 = 모든 이진 문자열
(0+1)*00   → 위와 같은데, 반드시 00으로 끝나야 함
a(b+c)*    → a 뒤에 b 또는 c가 0번 이상

 

Regular Expression과 Grammar는 동일한 Language를 표현할 수 있다.

아래 Grammar를 보자:

X → aX
X → b

이걸 풀면

X = aX | b
X = a(aX | b) | b
X = aaX | ab | b
...
결국 X = a*b

즉 "a가 0번 이상 반복된 뒤 b로 끝나는 패턴"이고, Regular Expression으로는 a*b라고 쓴다. Grammar로 표현하던 것을 Regular Expression 한 줄로 줄인 것이다.

 

 

컴파일러와의 연결고리

이 개념들이 컴파일러와 어떻게 이어지는지 정리하면

Regular Expression → Scanner 설계에 쓰인다.

토큰 패턴을 Regular Expression으로 정의한다. 예를 들어 C의 정수 리터럴 패턴은 [1-9][0-9]* 같은 식이다. Scanner는 이 패턴들을 인식해서 토큰으로 잘라낸다.

Grammar → Parser 설계에 쓰인다.

문장 구조(파스트리)를 Grammar의 생성 규칙으로 정의한다. Regular Expression으로 표현 못하는 aⁿbⁿ 같은 패턴 (괄호 쌍 맞추기, 중첩 구조 등)은 Context-Free Grammar가 필요한데, 이게 Parser의 영역이다.

Finite Automata → 이 이론들을 실제로 구현하는 메커니즘이다.

다음 단계인 오토마타 파트로 이어진다.

---

한 줄 요약

Symbol을 모아 Alphabet → 이어 붙여 String → 규칙으로 걸러 Language → 그 규칙을 간결하게 쓴 것이 Regular Expression

스캐너가 int를 예약어로, a를 변수로 인식할 수 있는 건 이 이론 위에서 동작하기 때문이다.