형식 언어 기초: 문법·정규식·유한 오토마타가 만나는 지점

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

왜 컴파일러가 언어를 집합으로 보는가

프로그램은 문자 파일이지만 compiler front end는 그 문자가 허용된 문자열의 집합에 속하는지 단계적으로 판단한다. 식별자·숫자 같은 토큰은 정규 언어로, 중첩 괄호와 문장 구조는 주로 문맥 자유 언어로 모델링한다. 형식 언어는 이 경계를 감각이 아니라 수학적인 객체로 다루는 도구다.

가장 작은 구성 요소

• 알파벳 Σ: 유한한 기호 집합. 예: {a, b}
• 문자열: Σ의 기호를 유한하게 이어 붙인 것
• 빈 문자열 ε: 길이가 0인 문자열
• Σ*: Σ로 만들 수 있는 모든 유한 문자열. ε을 포함한다.
• Σ+: 하나 이상의 기호로 된 문자열. 일반적으로 Σ+ = Σ* - {ε}
• 언어 L: Σ*의 부분집합

언어를 “문장을 만드는 규칙”으로 정의할 수도 있고 “문장을 받아들이는 기계”로 정의할 수도 있다. 이 두 관점을 연결하는 것이 grammar와 automaton이다.

문법의 정확한 정의

문법은 보통 G = (N, T, P, S)로 쓴다.

• N: nonterminal 집합
• T: terminal 집합, N과 겹치지 않는다
• P: production 규칙 집합
• S: 시작 nonterminal

일반적인 production α → β에서 왼쪽 α는 비어 있지 않고 적어도 하나의 nonterminal을 포함해야 한다. 이 조건이 빠지면 단순 문자열 치환과 생성 문법을 구분하기 어렵다. S ⇒* w는 0회 이상의 규칙 적용으로 terminal 문자열 w를 만들 수 있다는 뜻이고, L(G) = {w ∈ T* | S ⇒* w}다.

Chomsky 계층을 경계 중심으로 읽기

표는 포함 관계를 보여주는 학습 지도이지 실제 언어 구현을 한 칸에 가두는 분류표는 아니다. 프로그래밍 언어의 문법 뼈대는 CFG로 적어도, typedef 이름 구분·타입 호환·선언 전 사용 같은 규칙은 symbol table과 semantic analysis가 함께 처리한다. Type 1의 세부 정의에는 ε 허용 조건 등 교재별 관례가 있으므로 “항상 길이 증가” 같은 한 문장으로 축약하면 예외가 생긴다.

정규 언어의 세 가지 얼굴

정규 언어는 다음 세 방식으로 같은 표현력을 갖는다.

1. 정규 문법이 문자열을 생성한다.
2. 정규식이 문자열 집합을 기술한다.
3. DFA 또는 NFA가 문자열을 인식한다.

예를 들어 identifier를 다음처럼 잡아 보자.

letter (letter | digit)*

오른쪽 선형 문법은 다음처럼 쓸 수 있다.

ID   → letter REST
REST → letter REST | digit REST | ε

오토마타로는 첫 글자를 읽은 뒤 accepting state에 들어가고, 이후 letter나 digit마다 같은 상태로 되돌아간다. 셋 중 어느 표현을 선택해도 언어 자체는 같다. 정규식은 사람이 쓰기 좋고, NFA는 조합하기 좋으며, DFA는 입력 문자마다 다음 상태 하나를 빠르게 찾기 좋다.

문법에서 오토마타로

오른쪽 선형 문법의 각 nonterminal을 상태로 생각한다.

• A → aB: 상태 A에서 문자 a를 읽고 B로 이동
• A → a: a를 읽고 새 accepting state로 이동
• A → ε: A 자체를 accepting state로 표시

반대 방향으로 finite automaton의 transition A --a→ B를 A → aB로 바꾸고 accepting state에는 ε production을 추가하면 정규 문법을 얻는다. 이 변환은 lexer generator가 “pattern을 실행 기계로 바꾸는 과정”을 이해하는 토대다.

정규식 표기의 함정

오래된 이론 자료의 +는 문맥에 따라 union을 뜻하기도 하고, 현대 정규식의 r+처럼 1회 이상 반복을 뜻하기도 한다. 글에서는 혼동을 피하려고 union을 |, positive closure를 postfix +로 구분한다.

또 transition 함수 δ는 보통 한 기호를 처리한다. 전체 문자열을 처리한 결과는 extended transition δ*로 쓰는 것이 정확하다. DFA에서는 δ*: Q × Σ* → Q, NFA에서는 δ*: Q × Σ* → 2^Q가 된다.

닫힘 성질이 실용적인 이유

정규 언어는 union, intersection, complement, difference, concatenation, Kleene star 등 여러 연산에 대해 닫혀 있다. 예를 들어 두 DFA의 상태를 쌍으로 묶는 product construction은 교집합이나 합집합 lexer 규칙을 기계적으로 만든다. complement는 모든 입력에 transition이 정의된 완전 DFA에서 accepting/non-accepting 상태를 뒤집어야 한다. 빠진 transition을 그냥 무시한 DFA라면 먼저 sink state를 추가해야 한다.

정규 언어가 못 하는 것

finite automaton은 유한 상태만 기억한다. 따라서 임의 깊이의 괄호 균형이나 aⁿbⁿ처럼 제한 없이 증가하는 개수를 정확히 맞추지 못한다. 이 지점에서 stack을 가진 pushdown automaton과 CFG가 필요하다. 반대로 숫자·키워드·식별자처럼 국소적인 문자 패턴에 stack을 쓰는 것은 불필요하게 복잡하다.

컴파일러 front end의 경계

characters --regular language / finite automata--> tokens
tokens     --context-free grammar / parser-------> syntax tree
tree       --symbol and type rules---------------> checked program

핵심은 모든 문제를 가장 강한 기계로 푸는 것이 아니다. 필요한 기억의 크기에 맞는 표현을 선택하고, 정규식·문법·의미 규칙 사이의 책임 경계를 분명히 하는 것이다.