"컴파일러는 우리가 작성한 코드를 어떻게 '언어'로 인식하고, 문법이 맞았는지 틀렸는지 판단할 수 있을까?"
지난 주에는 컴파일러의 전체적인 구조를 훑어봤다. 이번에는 구문 분석(Parsing)의 이론적 뼈대가 되는 형식 문법(Formal Grammar)에 대해 알아볼 것이다.
왜 갑자기 '수학'부터 시작할까?
컴파일러가 다루는 프로그래밍 언어는 우리가 사용하는 자연어와 근본적인 차이가 있다. 그것은 바로 모호성(Ambiguity)이 없다는 점이다. 모든 코드는 단 하나의 의미로만 해석되어야 한다. 이러한 엄밀함과 명확성을 보장하는 도구가 수학이며, 컴퓨터 과학자들은 프로그래밍 언어를 정의하기 위해 수학적 도구들을 도입했다. 그 첫 번째가 바로 집합(Set)이다.
집합 (Set): 원소들의 모임이며, 소속성 외에는 어떤 구조도 가지지 않는다. 언어를 구성하는 가장 기본적인 재료들의 모음으로, 특정 언어가 사용할 기호의 범위를 약속하는 것이다. 이를 알파벳(Alphabet)이라 칭한다.
문자열 (String): 알파벳을 구성하는 기호가 0개 또는 1개 이상 유한하게 나열된 것이다. ab와 ba는 순서가 다르므로 다른 문자열로 취급된다.
언어 (Language): 형식 언어란 특정 알파벳에서 얻은 기호들로 구성된 문자열의 집합이다. 수많은 문자열 조합 중에서, 특정 문법(Grammar) 규칙을 만족하는 유효한 문자열들의 집합을 의미한다.
문법(Grammar)의 해부: 약속은 어떻게 만들어지는가?
컴파일러가 코드를 이해하는 규칙, 즉 문법은 4가지 요소로 구성된 시스템으로 정의된다. 이를 G = (V, Σ, P, S)로 표현한다.
V (Non-terminals, 비단말 기호): 문법 구조를 나타내는 기호이다. <expression>, <statement> 와 같이 다른 것으로 대체되어야 할 중간 단계의 개념을 나타낸다.
Σ (Terminals, 단말 기호): 실제 언어의 기본 기호들이다. 키워드, 연산자, 식별자 등이 여기에 속하며, 더 이상 다른 것으로 바뀔 수 없는 최종 단위이다.
P (Production Rules, 생성 규칙): 비단말 기호를 단말 기호나 다른 비단말 기호로 치환하는 규칙이다. ::= 또는 → 기호를 사용하여 "왼쪽은 오른쪽으로 바뀔 수 있다"고 정의한다.
예: <expr> → <expr> + <term>
해석: "하나의 <expr>는, 또 다른 <expr>와 + 기호, 그리고 하나의 <term>의 조합으로 만들어질 수 있다."
S (Start Symbol, 시작 기호): 파싱을 시작하는 최상위 비단말 기호이다. 모든 유효한 프로그램은 이 시작 기호로부터 생성 규칙을 통해 파생되어야 한다.
문장 생성 과정: 유도(Derive)와 문장(Sentence)
문법의 네 가지 요소를 가지고 실제 문장을 만드는 과정을 유도(Derive)라고 한다. 이는 시작 기호(S)에서 출발하여 생성 규칙(P)을 반복적으로 적용하며 비단말 기호(V)를 모두 단말 기호(Σ)로 바꾸는 과정이다.
<규칙 (P)>
<expr> → <expr> + <term> | <term>
<term> → <term> * <factor> | <factor>
<factor> → (<expr>) | id
<id + id * id 유도 과정>
<expr>
=> <expr> + <term>
=> <term> + <term>
=> <factor> + <term>
=> id + <term>
=> id + <term> * <factor>
=> id + <factor> * <factor>
=> id + id * <factor>
=> id + id * id
최종적으로 만들어진 단말 기호의 나열을 문장(Sentence)이라고 한다. 유도 과정 중 비단말 기호가 남아있는 중간 결과물은 문장 형태(Sentential Form)라고 한다.
촘스키 계층: 문법의 '파워 레벨'을 나누다 (Chomsky Hierarchy)
언어학자 노엄 촘스키는 생성 규칙(P)의 제약 조건에 따라 문법을 4개의 계층으로 분류했다. 이것이 촘스키 계층(Chomsky Hierarchy)**이다. 규칙에 제약이 많을수록 표현력은 약하지만 기계가 해석하기는 더 쉽다.
Type 3: 정규 문법 (Regular Grammar)
규칙 형태: A → a 또는 A → aB 와 같이 오른쪽 선형이거나, A → Ba 와 같이 왼쪽 선형 중 한 가지 형태만 사용한다.
특징: 가장 제약이 강하며 단순한 패턴을 정의한다.
예시 언어: 정규 표현식 (a)*b 와 동일한 S → aS | b 문법은 b, ab, aab 등의 문자열을 생성한다.
해석 기계: 유한 오토마타 (Finite Automata, FA).
Type 2: 문맥 자유 문법 (Context-Free Grammar, CFG)
규칙 형태: A → α (규칙의 왼쪽에 단 하나의 비단말 기호만 와야 한다).
특징: 규칙 적용 시 주변 문맥을 고려하지 않기 때문에 '문맥 자유'라고 부른다. 대부분의 프로그래밍 언어 문법이 여기에 속한다.
예시 언어: { aⁿbⁿ | n ≥ 1 } (a와 b의 개수가 같은 언어), 괄호 짝 맞추기, 중첩된 구문 등을 표현할 수 있다.
해석 기계: 푸시다운 오토마타 (Pushdown Automata, PDA).
Type 1: 문맥 의존 문법 (Context-Sensitive Grammar, CSG)
규칙 형태: αAβ → αγβ (A가 γ로 치환되려면 α와 β라는 주변 문맥이 필요하다). 또한, 생성 규칙 적용 후 문자열의 길이가 줄어들지 않는다 (비축약성).
특징: 문맥에 따라 규칙 적용이 달라져 CFG보다 강력한 표현력을 가진다.
예시 언어: { aⁿbⁿcⁿ | n ≥ 1 } (a, b, c 세 기호의 개수가 모두 같은 언어). CFG는 두 종류의 기호 개수까지만 맞출 수 있다.
해석 기계: 선형 유계 오토마타 (Linear Bounded Automata, LBA).
Type 0: 무제약 문법 (Unrestricted Grammar)
규칙 형태: α → β (규칙의 좌변에 최소 한 개의 비단말이 포함되기만 하면 다른 제약이 거의 없다). 문자열 길이가 줄어드는 축약 규칙도 허용된다.
