오토마타와 컴파일러 04 - 푸시다운 오토마타

유한 오토마타에 무엇이 부족했는가

유한 오토마타는 현재 상태만 기억할 수 있으며, 이전에 처리한 입력의 이력을 추적할 방법이 없다. 이 한계 때문에 괄호 매칭이나 {aⁿbⁿ} 같은 언어를 인식할 수 없었다. 문맥 자유 문법이 이런 언어를 기술할 수 있다는 것을 이전 포스트에서 보았는데, 그렇다면 문맥 자유 문법에 대응하는 계산 모델은 무엇인가? 유한 오토마타에 스택이라는 보조 저장소를 하나 추가한 모델, 바로 푸시다운 오토마타(Pushdown Automaton, PDA)이다.

스택이 부여하는 능력

스택은 후입선출(LIFO) 방식으로 동작하는 자료 구조이다. 푸시다운 오토마타는 유한 오토마타의 모든 구성 요소에 더하여 스택을 하나 가지며, 각 전이에서 스택의 최상단을 읽고, 제거하고, 새로운 기호를 추가할 수 있다. 이 스택은 크기에 제한이 없으므로 이론적으로 무한한 정보를 저장할 수 있다.

과연 스택 하나가 그렇게 큰 차이를 만들어 내는가? 만들어 낸다. {aⁿbⁿ} 언어를 인식하는 과정을 생각해 보면, a를 읽을 때마다 스택에 기호를 push하고, b를 읽을 때마다 스택에서 pop하면 된다. 입력을 모두 읽은 후 스택이 비어 있다면 a와 b의 개수가 같다는 것이 보장된다. 유한 오토마타에서는 원천적으로 불가능했던 카운팅이, 스택 하나의 추가만으로 자연스럽게 가능해지는 것이다.

푸시다운 오토마타의 형식적 정의

푸시다운 오토마타는 여섯 가지 요소로 정의된다.

유한 오토마타와의 차이는 스택 알파벳 Γ의 추가와 전이 함수의 변경이다. 전이 함수 δ는 현재 상태, 입력 기호(또는 ε), 스택 최상단 기호를 입력으로 받아 다음 상태와 스택에 push할 기호를 결정한다. 즉, δ(q, a, X) = (q', Y)는 "상태 q에서 입력 a를 읽고 스택 최상단이 X이면, 상태 q'로 전이하면서 X를 Y로 교체한다"는 의미이다.

수락 조건에는 두 가지 방식이 있다. 수락 상태에 도달하여 수락하는 방식(final state acceptance)과, 스택이 비었을 때 수락하는 방식(empty stack acceptance)이다. 이 두 방식은 인식할 수 있는 언어의 범위가 동일하며, 하나를 다른 하나로 변환할 수 있다.

PDA의 동작 예시

{aⁿbⁿ | n ≥ 1} 언어를 인식하는 PDA를 구체적으로 살펴보자.

상태: {q₀, q₁, q₂}
입력 알파벳: {a, b}
스택 알파벳: {A, Z₀}
시작 상태: q₀
수락 상태: {q₂}
초기 스택: Z₀

전이:
  δ(q₀, a, Z₀) = (q₀, AZ₀)    -- 첫 번째 a: A를 push
  δ(q₀, a, A)  = (q₀, AA)      -- 이후의 a: A를 push
  δ(q₀, b, A)  = (q₁, ε)       -- 첫 번째 b: A를 pop
  δ(q₁, b, A)  = (q₁, ε)       -- 이후의 b: A를 pop
  δ(q₁, ε, Z₀) = (q₂, Z₀)     -- 입력 종료, 스택 바닥 도달: 수락

입력 aaabbb를 처리하는 과정을 추적하면, a를 읽을 때마다 스택에 A가 쌓이고(AAA), b를 읽을 때마다 A가 하나씩 제거된다. 세 번째 b를 읽은 후 스택에는 초기 기호 Z₀만 남으므로 수락 상태로 전이하여 입력을 수락한다. 만약 a와 b의 개수가 다르면 스택에 A가 남거나, 스택이 비었는데 b를 더 읽어야 하는 상황이 되어 수락에 실패한다.

PDA와 CFG의 동치

정규 표현식과 유한 오토마타가 동치였던 것처럼, 문맥 자유 문법과 푸시다운 오토마타도 동치이다. 어떤 언어가 문맥 자유 문법으로 생성될 수 있는 것과 푸시다운 오토마타에 의해 인식될 수 있는 것은 같은 조건이다.

이 동치는 양 방향의 변환으로 증명된다. CFG에서 PDA로의 변환은 비교적 직관적이다. 시작 기호를 스택에 넣고, 스택 최상단이 비단말이면 해당 생성 규칙의 오른쪽을 스택에 push하고, 단말이면 입력과 매칭하여 pop하는 방식이다. 이는 사실상 최좌 유도를 시뮬레이션하는 것이다. 반대 방향, PDA에서 CFG로의 변환은 더 복잡하지만 역시 가능하다.

이 동치 관계는 이론적인 정리에 그치지 않는다. 컴파일러의 파서가 본질적으로 푸시다운 오토마타라는 사실을 이해하면, 파서의 설계와 동작 원리를 훨씬 깊이 파악할 수 있다. 파서가 스택을 사용하여 중첩된 구조를 추적하는 것은 PDA의 동작 방식 그 자체인 것이다.

결정적 PDA와 비결정적 PDA

유한 오토마타에서 DFA와 NFA의 인식 능력이 동일했던 것과 달리, 푸시다운 오토마타에서는 결정적 PDA(DPDA)와 비결정적 PDA(NPDA)의 능력이 다르다. 이것은 중요한 차이이다.

비결정적 PDA는 모든 문맥 자유 언어를 인식할 수 있지만, 결정적 PDA는 문맥 자유 언어의 진부분집합인 결정적 문맥 자유 언어(DCFL)만 인식할 수 있다. 예를 들어 {wwᴿ | w ∈ {a,b}*}(회문 언어)는 문맥 자유 언어이지만 결정적 문맥 자유 언어가 아니다. 문자열의 중간 지점을 결정적으로 판별할 수 없기 때문이다.

과연 이 구분이 실무에서 의미가 있는가? 매우 의미가 있다. 실용적인 파서는 결정적이어야 한다. 비결정적 파서는 여러 가능성을 동시에 탐색해야 하므로 효율적인 구현이 어렵다. 이 때문에 프로그래밍 언어의 문법은 결정적 PDA로 파싱할 수 있도록, 즉 LL이나 LR 문법의 범주에 들어가도록 설계되는 것이 일반적이다.

PDA의 한계 — 문맥 의존 언어

스택이 강력한 도구임에도 불구하고, 스택만으로는 모든 언어를 인식할 수 없다. 대표적인 예가 {aⁿbⁿcⁿ | n ≥ 0}이다. a, b, c의 개수가 모두 같은 문자열을 인식하려면, a의 개수를 세면서 동시에 이 값을 b와 c에 대해 검증해야 한다. 스택을 사용하면 두 종류의 기호 사이 관계(a와 b)는 추적할 수 있지만, 세 종류의 기호 사이 관계를 동시에 추적하는 것은 불가능하다.

이런 언어는 문맥 의존 언어(Context-Sensitive Language)에 해당하며, 인식하려면 선형 유한 오토마타(Linear Bounded Automaton)라는 더 강력한 모델이 필요하다. 다행히 프로그래밍 언어의 구문 구조는 대부분 문맥 자유 문법으로 충분히 기술할 수 있으므로, 컴파일러의 파싱 단계에서는 PDA에 기반한 파서로 충분한 것이다.

다음 포스트에서는 지금까지 다룬 이론이 실제 컴파일러에서 어떻게 조합되는지, 컴파일러의 전체 단계와 구조를 살펴본다.