문법에서 스택 머신까지: CFG와 PDA가 구문 분석을 가능하게 하는 방식

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

문법은 구조를 선언하고 스택은 그 구조를 추적한다

lexer가 문자에서 token stream을 만들면 parser는 그 token들이 언어의 문법에 맞는 계층을 이루는지 확인한다. 결과는 문법을 자세히 보존한 parse tree일 수도 있고, 이후 의미 분석과 코드 생성에 필요한 정보만 남긴 AST일 수도 있다.

아카이브 강의는 이 관계를 context-free grammar와 pushdown automaton이라는 두 관점으로 설명한다. CFG는 문자열이 어떻게 생성될 수 있는지 선언하고, PDA는 입력과 stack을 사용해 문자열이 그 규칙에 속하는지 어떻게 인식할지 보여 준다. 현대적으로 말하면 선언적 명세와 실행 모델의 짝이다.

CFG와 유도

문맥 자유 문법은 보통 다음 네 요소로 쓴다.

G = (V_N, V_T, P, S)

V_N: nonterminal 집합
V_T: terminal 집합
P: production 집합
S: start symbol

예를 들어 다음 문법을 보자.

1. E -> E + E
2. E -> E * E
3. E -> a

a+a*a의 leftmost derivation은 매 단계 가장 왼쪽 nonterminal을 바꾼다.

E => E + E
  => a + E
  => a + E * E
  => a + a * E
  => a + a * a

rule sequence: 1, 3, 2, 3, 3

rightmost derivation은 반대로 가장 오른쪽 nonterminal부터 바꾼다.

E => E + E
  => E + E * E
  => E + E * a
  => E + a * a
  => a + a * a

강의의 한 문장은 sentential form에 nonterminal이 두 개 이상 있어야 한다고 설명하지만 이는 정확하지 않다. sentential form은 start symbol에서 유도된 terminal과 nonterminal의 임의 문자열이다. nonterminal이 하나일 수도, 여러 개일 수도, terminal만 남은 최종 sentence일 수도 있다.

같은 문자열에 두 구조가 생기는 모호성

위 문법은 a+a*a를 a+(a*a)와 (a+a)*a 두 방식으로 해석한다. 같은 terminal 문자열에 서로 다른 parse tree가 두 개 이상 존재하므로 ambiguous grammar다. 동치인 관점으로 서로 다른 leftmost derivation 또는 rightmost derivation이 둘 이상 있다고 말할 수 있다.

아카이브에는 A -> A α A처럼 왼쪽의 nonterminal이 오른쪽에 두 번 나오면 모호하다는 규칙이 적혀 있다. 이것은 모호성의 정의도 아니고 충분조건도 아니다. 반복된 nonterminal은 모호성을 의심하게 하는 모양일 수 있지만, 실제 판단은 같은 문자열에 서로 다른 tree가 생기는지로 해야 한다. “두 개보다 많은 derivation”이라는 표현도 “두 개 이상”으로 고쳐야 한다.

연산 우선순위를 문법에 넣으면 모호성을 제거할 수 있다.

E -> E + F | F
F -> F * G | G
G -> a

이 구조에서 *는 +보다 아래 단계에서 묶이므로 더 높은 precedence를 갖고, 왼쪽 재귀는 같은 연산자의 left associativity를 표현한다. a+a*a의 AST는 다음처럼 간결해진다.

add
├─ a
└─ mul
   ├─ a
   └─ a

parse tree가 E, F, G와 punctuation까지 문법적 증거로 남긴다면 AST는 add, mul, identifier, literal처럼 semantic processing에 필요한 node를 중심으로 설계된다. AST를 단순히 “object code에 필요 없는 subtree를 지운 parse tree”로만 보는 것은 좁다. 실제 compiler는 type, source span, implicit conversion, 합성 node도 AST나 그 다음 IR에 기록할 수 있다.

BNF, EBNF, syntax diagram

같은 문법도 여러 표기법으로 적을 수 있다.

BNF:
<int_dcl> ::= "int" <id_list> ";"
<id_list> ::= <id_list> "," <id> | <id>

EBNF:
<int_dcl> ::= "int" <id> { "," <id> } ";"

EBNF의 { ... }는 repetition, [ ... ]는 optional part를 나타내는 흔한 관례다. 다만 EBNF dialect마다 metasymbol이 다르며, 반복 횟수를 위첨자로 제한하는 강의 표기는 표준 EBNF 전체에 공통된 문법이 아니다. 또한

<exp> ::= <exp> ("+" | "-" | "*" | "/") <exp>

처럼 operator를 한 줄로 합쳐도 grammar가 짧아질 뿐 precedence와 associativity는 해결되지 않는다. syntax 또는 railroad diagram도 같은 규칙을 그림으로 보여 주는 표기이지 모호성을 자동으로 없애는 장치는 아니다.

Top-down과 bottom-up은 반대 방향의 같은 질문이다

top-down parser는 start symbol에서 출발해 leftmost derivation을 구성한다.

1. stack을 start symbol로 초기화한다.
2. top이 nonterminal이면 production의 RHS로 expand한다.
3. top이 terminal이면 현재 input token과 match한 뒤 pop한다.
4. input과 stack의 end marker가 함께 맞으면 accept한다.

bottom-up parser는 입력에서 출발해 rightmost derivation을 거꾸로 재구성한다.

1. input token을 stack으로 shift한다.
2. stack top의 handle, 즉 어떤 production의 RHS를 찾는다.
3. RHS를 LHS nonterminal로 reduce한다.
4. start symbol과 end marker에 도달하면 accept한다.

아카이브가 “bottom-up이 선호된다”고 단정한 부분은 현재의 보편 법칙이 아니다. hand-written recursive descent, PEG, LL generator, LR 계열은 언어와 도구의 요구에 따라 모두 사용된다.

유한 오토마타에 stack을 더하는 이유

finite automaton은 상태 수가 유한하므로 임의 깊이의 괄호나 0^n1^n의 두 개수를 무한히 비교할 기억이 없다. 그렇다고 “FA는 count를 전혀 못한다”는 말도 정확하지 않다. 짝수/홀수나 특정 수를 법으로 한 나머지처럼 유한 상태로 압축 가능한 count는 처리할 수 있다. 불가능한 것은 제한 없이 커지는 관계를 기억하는 일이다.

nondeterministic PDA는 다음 일곱 요소로 나타낸다.

P = (Q, Σ, Γ, δ, q0, Z0, F)

• Q: state 집합
• Σ: input alphabet
• Γ: stack alphabet
• q0: start state
• Z0: initial stack symbol
• F: final states

전이 함수의 정확한 형식은 다음과 같다.

δ: Q × (Σ ∪ {ε}) × Γ -> P(Q × Γ*)

강의 표기에는 오른쪽의 powerset이 빠져 있지만 곧이어 한 입력에서 여러 (next state, replacement stack string) 쌍을 제시한다. 바로 그 가능성의 집합이 nondeterminism이다.

configuration (q, w, α)는 current state, 아직 읽지 않은 input, stack content를 뜻한다. stack top을 왼쪽에 쓴다면

(q, aω, Zα) ⊢ (q', ω, γα)

는 (q', γ)가 δ(q,a,Z)의 한 선택일 때 입력 a를 소비하고 top Z를 γ로 바꾼다는 뜻이다. γ=ε이면 pop이다. ε-transition은 입력을 소비하지 않으며 입력이 모두 끝난 뒤에만 가능한 것이 아니라 어느 시점에도 일어날 수 있다.

final state와 empty stack

PDA의 acceptance에는 대표적으로 두 정의가 있다.

• final-state acceptance: 입력을 모두 읽고 final state에 도착
• empty-stack acceptance: 입력을 모두 읽고 stack을 비움

nondeterministic PDA에서는 두 방식이 같은 context-free language class를 인식하지만 construction은 다르다. 새 bottom marker와 새 start state, final state에서 stack을 비우는 drain state를 추가하면 한 방식을 다른 방식으로 바꿀 수 있다.

0^n1^n 예제는 0을 읽을 때 stack에 0을 쌓고 1을 읽을 때 하나씩 pop한다. 다만 아카이브의 구체적 machine은 start state 자체를 final state로 두고 acceptance를 zero-or-more transitions로 정의했다. 그러면 빈 입력 ε도 시작 configuration에서 이미 accept된다. 따라서 적힌 n>=1이 아니라 그 정의대로는 n>=0이 맞다.

회문 예제는 입력 앞부분을 stack에 넣고 어느 지점에서 center marker를 삽입한 뒤 aSa 또는 bSb를 S로 줄인다. 이 선택은 입력만 보고 중간 지점을 미리 알 수 없기 때문에 nondeterministic PDA의 직관을 잘 보여 준다.

CFG와 NPDA가 같은 언어 부류를 표현하는 이유

CFG에서 empty-stack NPDA를 만드는 construction은 놀랄 만큼 직접적이다.

• state는 하나만 둔다.
• stack은 start symbol S로 시작한다.
• production A -> α마다 ε-transition으로 stack top A를 α로 expand한다.
• terminal a가 input과 stack top에 함께 있으면 둘을 match하고 pop한다.

δ(q, ε, A) contains (q, α)   for every A -> α
δ(q, a, a) contains (q, ε)   for every terminal a

이 machine은 leftmost derivation을 stack 위에서 흉내 낸다. 따라서 여기서 쓰는 표기는 앞서 정의한 final-state L(P)가 아니라 empty-stack language L_e(P)라고 구분하는 편이 정확하다. “L(CFG)=L(PDA)”도 한 grammar 객체와 한 machine 객체가 같다는 뜻이 아니라, CFG가 생성하는 language family와 NPDA가 인식하는 language family가 모두 CFL이라는 뜻이다.

반대 construction에서는 [q Z r] 같은 nonterminal을 만들어 “state q에서 stack symbol Z를 제거하고 state r에 도착하는 계산”을 문법 한 조각으로 표현한다. transition이 여러 stack symbol을 push하면 중간 state들을 잇는 production을 만든다. 수식은 길지만 핵심은 stack 동작의 전후 조건을 grammar symbol로 옮기는 것이다.

아카이브 trace에는 state 집합에 없는 p가 마지막 state로 등장하거나, empty stack으로 끝나는 trace와 달리 accept transition이 s를 push하는 것으로 적힌 오탈자도 있다. 전자는 정의된 state로, 후자는 ε replacement로 고쳐야 configuration이 일관된다.

마무리

CFG와 NPDA의 동등성은 parser가 왜 grammar와 stack을 함께 사용하는지 설명한다. grammar는 가능한 tree를 선언하고, stack machine은 아직 닫히지 않은 구조를 기억한다. 그러나 일반 CFG/NPDA에는 여러 선택지가 있다. 다음 단계의 LL과 LR parsing은 FIRST, FOLLOW, lookahead, item automaton을 사용해 그 nondeterminism을 실제 프로그램이 실행할 수 있는 결정으로 바꾼다.