3장. 파서

토큰 흐름에서 문장 구조를 발견하기. 문맥 자유 문법, LL(1), LR(1)의 세계.

3.1 들어가며 — 파서가 하는 일

스캐너는 문자열을 단어로 잘라줬다. 이제 파서가 그 단어들을 받아서 “이 단어 흐름이 이 언어의 진짜 문장이 맞나?”를 따져야 한다. 영어로 치면 스캐너는 형태소 분석기, 파서는 문법 검사기다.

파서의 임무는 두 가지로 정리된다.

1. 합법성 판정 — 토큰 흐름이 문법에 맞는 문장인가?
2. 구조 발견 — 맞다면, 어떤 규칙으로 어떻게 만들어졌는가? (이 “어떻게”가 바로 유도, derivation이다.)

이때 사용하는 도구가 문맥 자유 문법(context-free grammar, CFG)이다. 정규 표현식이 스캐너의 무기였다면, CFG는 파서의 무기다. 그리고 두 가지 큰 전략이 있다.

• 탑다운(top-down) 파서 — 트리의 뿌리부터 잎으로 내려가며 “다음에 어떤 규칙을 쓸까?”를 예측한다. 위에서부터 트리를 그리는 사람.
• 바텀업(bottom-up) 파서 — 잎부터 시작해 토큰을 쌓아가다가 “어, 이 패턴은 어떤 규칙의 우변이네”라고 깨달으면 줄여 올린다. 바닥부터 벽돌을 쌓는 벽돌공.

이 장에서는 두 전략의 대표 주자인 LL(1)과 LR(1)을 다룬다. 둘 다 입력 길이에 비례하는 시간(O(n))에 동작하므로 컴파일러에 쓰기 충분히 빠르다.

3.2 문법을 표현하는 법

3.2.1 정규 표현식으로 안 되나?

정규 표현식(RE)은 스캐너에서 잘 통했다. 그럼 그냥 RE로 프로그래밍 언어 전체를 묘사하면 안 될까? 안 된다. 왜?

예를 들어 변수와 + - × ÷ 연산자로 이루어진 수식을 RE로 써 보자.

variable: [a-z]([a-z]|[0-9])*
expr:     variable ((+|-|×|÷) variable)*

이 RE는 a+b×c나 fee÷fie×foe를 잘 매칭한다. 그런데 이 RE는 연산자 우선순위를 표현하지 못한다. a+b×c를 (a+b)×c로 읽을지 a+(b×c)로 읽을지 RE 자신은 모른다.

괄호를 추가해 보자. 시작 괄호와 닫는 괄호 옵션을 잘 배치하면 “괄호로 감싼 식”까지는 어찌어찌 표현할 수 있다. 하지만 중첩된 괄호—a+(b×c) 같은 것—는 절대 RE로 못 표현한다.

3.2.2 문맥 자유 문법(CFG)

CFG의 가장 단순한 예: 양들의 합창.

SheepNoise → baa SheepNoise
            | baa

핵심 용어를 정리하자.

• 생성 규칙(production) — CFG의 각 규칙. 좌변 → 우변 모양.
• 비단말(nonterminal) — SheepNoise처럼 다른 기호로 다시 쓸 수 있는 추상 기호. 보통 이탤릭으로 쓴다.
• 단말(terminal) — baa처럼 더 이상 쪼갤 수 없는 실제 단어. 스캐너가 돌려주는 토큰의 종류와 같다.
• 시작 기호(goal/start symbol) — 유도가 출발하는 비단말. 위 예에서는 SheepNoise.

형식적으로 CFG는 G = (T, NT, S, P)의 4-튜플이다. T는 단말 집합, NT는 비단말 집합, S ∈ NT는 시작 기호, P는 생성 규칙 집합이다.

유도란 무엇인가

유도는 시작 기호에서 출발해 규칙을 거듭 적용해 가면서, 비단말이 모두 사라지고 단말만 남을 때까지 다시 쓰는 과정이다. 중간 단계에 등장하는 (단말 + 비단말) 혼합 문자열을 문장형(sentential form)이라 한다.

예: SheepNoise ⇒ baa SheepNoise ⇒ baa baa. 이러면 “SheepNoise는 baa baa를 유도한다”가 된다.

3.2.3 좀 더 복잡한 예 — 수식

괄호와 사칙연산을 가진 수식 문법을 보자.

1  Expr → ( Expr )
2       | Expr Op name
3       | name
4  Op   → +
5       | -
6       | ×
7       | ÷

(a+b)×c를 만들어 보자. 규칙을 (2, 6, 1, 2, 4, 3)의 순서로 적용한다.

위 표는 최우 유도(rightmost derivation)다 — 매 단계마다 가장 오른쪽 비단말을 다시 썼다. 반대로 가장 왼쪽 비단말을 매번 다시 쓰면 최좌 유도(leftmost derivation)다. 같은 문장을 만들지만 적용 순서가 다르다.

유도는 그래프로 그릴 수 있다. 이 그래프를 파스 트리(parse tree) 또는 구문 트리(syntax tree)라 한다. 트리는 “어떤 규칙을 썼는가”만 표현하고, “어떤 순서로 썼는가”는 표현하지 않는다. 그래서 최좌 유도와 최우 유도가 같은 파스 트리를 낳을 수 있다.

모호함(Ambiguity)이라는 골칫거리

고전적인 예가 매달린 else (dangling else) 문제다.

1  Statement → if Expr then Statement else Statement
2            | if Expr then Statement
3            | Assignment
4            | … 다른 문장들 …

이 문법으로 if Expr₁ then if Expr₂ then A₁ else A₂를 파싱하면, else가 안쪽 if에 붙는 트리 하나, 바깥 if에 붙는 트리 하나, 총 두 개의 다른 의미가 가능하다. 컴파일러는 어떤 게 진짜인지 알 수 없다.

해결책은 문법을 다시 쓰는 것. else의 짝이 되는 if는 “else를 가진 문장만 then 부분에 올 수 있다”는 식으로 제약한다.

1  Statement → if Expr then Statement
2            | if Expr then WithElse else Statement
3            | Assignment
4  WithElse  → if Expr then WithElse else WithElse
5            | Assignment

이렇게 하면 else는 항상 가장 가까운(아직 짝 없는) if와 결합한다. 모호함이 사라졌다.

3.2.4 의미를 구조에 새기기 — 우선순위

앞의 단순 수식 문법으로 a+b×c를 파싱하면 트리의 후위 순회가 (a+b)×c로 평가된다. 우리가 원하는 a+(b×c)가 아니다. 모든 연산자를 한 비단말 Op로 묶었으니 우선순위 정보가 사라진 것이다.

해결책: 우선순위마다 비단말을 따로 만든다. 이게 그 유명한 고전 수식 문법(classic expression grammar)이다.

0  Goal   → Expr
1  Expr   → Expr + Term
2         | Expr - Term
3         | Term
4  Term   → Term × Factor
5         | Term ÷ Factor
6         | Factor
7  Factor → ( Expr )
8         | num
9         | name

이제 a+b×c의 파스 트리는 b×c를 먼저 만들고 그 위에 a+를 얹는 모양이 된다. 후위 순회로 평가하면 정확히 우리가 원하는 표준 우선순위가 나온다. 구조에 의미를 새겼다.

이 패턴은 일반적이다 — 배열 첨자는 산술보다 높은 우선순위, 타입 캐스트는 산술보다 높지만 괄호보다 낮음, 대입은 가장 낮음 같은 규칙도 비단말 추가로 표현한다.

3.2.5 입력 문자열의 유도를 발견하기

지금까지는 문법 G가 주어졌을 때 “문장을 만드는 법”을 보았다. 컴파일러는 거꾸로—입력 문장이 주어졌을 때 “이게 G로부터 어떻게 만들어졌는지”를 발견해야 한다. 이게 파싱(parsing)이다.

파스 트리를 만든다고 생각하자. 뿌리는 시작 기호로 정해져 있고, 잎은 스캐너가 준 토큰들로 정해져 있다. 어려운 부분은 중간을 채우는 것이다.

1. 탑다운: 뿌리부터 시작해 잎쪽으로 트리를 자란다. 매 단계 어떤 비단말에 어떤 규칙을 적용할지 고른다.
2. 바텀업: 잎부터 시작해 뿌리쪽으로 자란다. 매 단계 “현재 잎열의 어떤 부분이 어떤 규칙의 우변에 해당하나”를 찾는다.

3.3 탑다운 파싱

탑다운 파서는 뿌리 = 시작 기호에서 출발해, 트리의 “아래쪽 가장자리(fringe)” 비단말 중 하나를 골라서 어떤 규칙으로 펼칠지(expand) 결정한다. 이 결정이 잘못되면 어떻게 할까? 백트래킹(backtracking)—되돌아가서 다른 규칙을 시도한다. 백트래킹은 비싸다. 그래서 “백트래킹 없이 단번에 맞는 규칙을 고르자”가 탑다운 파싱의 핵심 아이디어다.

탑다운 파서 골격 알고리즘

root  ← 시작 기호 S에 대한 노드
focus ← root
push(null)
word  ← NextWord()

while (true) do
   if (focus가 비단말) then begin
      A → β₁β₂…βₙ 규칙을 고른다;
      β₁…βₙ을 focus의 자식으로 만든다;
      push(βₙ, βₙ₋₁, …, β₂);
      focus ← β₁;
   end
   else if (word가 focus와 일치) then begin
      word ← NextWord();
      focus ← pop();
   end
   else if (word == eof and focus == null) then
      입력을 받아들이고 root 반환;
   else
      backtrack;
end;

3.3.1 탑다운 파싱을 위한 문법 변환

고전 수식 문법은 그대로 탑다운 파싱에 못 쓴다. 두 가지 문제가 있다.

좌재귀(left recursion) — 영원히 끝나지 않는 함정

예를 들어 Expr → Expr + Term은 좌재귀다. 탑다운 파서가 Expr을 만나면 항상 이 규칙을 적용해 버리고… 또 Expr을 만나고… 무한히. 입력 단어를 한 번도 소비하지 않고 무한 루프에 빠진다.

해결책: 우재귀(right recursion)로 바꾼다. 기계적인 변환이다.

좌재귀 (원본)              →  우재귀 (변환)
Fee → Fee α | β              Fee  → β Fee'
                              Fee' → α Fee'
                                   | ε

고전 수식 문법에 적용하면 다음과 같다.

0  Goal  → Expr
1  Expr  → Term Expr'
2  Expr' → + Term Expr'
3        | - Term Expr'
4        | ε
5  Term  → Factor Term'
6  Term' → × Factor Term'
7        | ÷ Factor Term'
8        | ε
9  Factor → ( Expr )
10        | num
11        | name

이게 우재귀 수식 문법이다. 같은 언어를 표현하지만 탑다운 파싱이 가능하다.

간접 좌재귀(α → β, β → γ, γ → α δ처럼 사이클이 있는 경우)도 위험한데, 이건 쉽게 눈에 안 띈다. 이를 잡는 알고리즘은 비단말에 임의 순서를 매기고, A_i → A_j γ 형태(j < i)를 모두 풀어서 직접 좌재귀로 환원한 뒤 위 변환을 적용한다.

백트래킹 없는 파싱 — FIRST 집합

좌재귀를 없애도 “어떤 규칙을 고를까” 문제는 남는다. 핵심은 한 토큰만 미리 보면(룩어헤드) 답이 정해지는 문법을 만드는 것이다.

FIRST 집합 계산 알고리즘:

// 단말, ε, eof는 자기 자신으로 초기화
for each α ∈ T ∪ {eof, ε} do FIRST(α) ← {α};
for each A ∈ NT do FIRST(A) ← ∅;

while (FIRST 집합이 변하는 동안) do
   for each 규칙 p: A → β₁β₂…βₖ do
      rhs ← FIRST(β₁) - {ε};
      i ← 1;
      while (ε ∈ FIRST(βᵢ) and i ≤ k-1) do
         rhs ← rhs ∪ (FIRST(βᵢ₊₁) - {ε});
         i ← i + 1;
      end;
      if (i == k and ε ∈ FIRST(βₖ)) then
         rhs ← rhs ∪ {ε};
      FIRST(A) ← FIRST(A) ∪ rhs;
   end;
end;

고정점에 도달할 때까지 반복한다.

FOLLOW 집합 — ε 규칙을 위한 보충 정보

ε 규칙(예: Expr' → ε)은 까다롭다. FIRST(ε) = {ε}인데, 스캐너는 절대 ε을 돌려주지 않는다. 그럼 언제 ε 규칙을 적용해야 할까? 답: 그 비단말 다음에 올 수 있는 단말들이 보일 때. 이 정보를 FOLLOW 집합이라 부른다.

for each A ∈ NT do FOLLOW(A) ← ∅;
FOLLOW(S) ← {eof};

while (FOLLOW 집합이 변하는 동안) do
   for each 규칙 A → β₁β₂…βₖ do
      TRAILER ← FOLLOW(A);
      for i ← k downto 1 do
         if (βᵢ ∈ NT) then begin
            FOLLOW(βᵢ) ← FOLLOW(βᵢ) ∪ TRAILER;
            if (ε ∈ FIRST(βᵢ))
               then TRAILER ← TRAILER ∪ (FIRST(βᵢ) - {ε});
               else TRAILER ← FIRST(βᵢ);
         end;
         else TRAILER ← FIRST(βᵢ);   // {βᵢ}
      end;
   end;
end;

FIRST⁺ 집합과 백트래킹 없는 조건

FIRST와 FOLLOW를 합쳐 증강 FIRST 집합 FIRST⁺를 정의한다.

FIRST⁺(A → β) = ┌ FIRST(β)              if ε ∉ FIRST(β)
                └ FIRST(β) ∪ FOLLOW(A)  otherwise

그러면 백트래킹 없는 문법의 조건은 단순하다.

FIRST⁺(A → βᵢ) ∩ FIRST⁺(A → βⱼ) = ∅

좌인수 분해(Left Factoring)

모든 문법이 그 자체로 백트래킹이 없는 건 아니다. 함수 호출, 배열 첨자를 추가한다고 해 보자.

11  Factor → name
12        | name [ ArgList ]
13        | name ( ArgList )

세 우변 모두 name으로 시작하므로 FIRST⁺가 겹친다. 해결책: 공통 접두사를 새 비단말로 뽑아낸다.

11  Factor    → name Arguments
12  Arguments → [ ArgList ]
13            | ( ArgList )
14            | ε

이 변환을 좌인수 분해(left factoring)라 한다. 결정은 한 단계 미뤄지고, 그 시점에는 다음 토큰이 [인지 (인지 다른 무엇인지로 깔끔히 갈린다.

3.3.2 재귀 하강 파서(Recursive-Descent)

백트래킹 없는 문법이 있으면 손코딩으로 단순하고 빠른 파서를 만들 수 있다. 재귀 하강 파서는 비단말마다 함수 하나씩—그 비단말을 인식하는 함수다. 함수들끼리 서로를 호출하며 트리를 따라 내려간다. 문법 자체가 코드의 뼈대가 된다.

예를 들어 Expr' → + Term Expr' | - Term Expr' | ε를 인식하는 함수는:

EPrime()
   /* Expr' → + Term Expr' | - Term Expr' */
   if (word == + or word == -) then begin
      word ← NextWord();
      if (Term())
         then return EPrime();
         else return false;
   end
   else if (word == ) or word == eof)
      /* Expr' → ε */
      then return true;
   else begin
      구문 오류 보고;
      return false;
   end;

각 함수는 FIRST⁺를 보고 어떤 우변을 시도할지 정한다. 일치하면 진행, 아니면 오류. 비단말 호출은 그냥 함수 호출. 단말 매칭은 토큰 비교 + NextWord(). 간결하고 직관적이며 빠르다.

오류 메시지를 사람 친화적으로 만들기에도 좋다 — 어디서 무엇을 기대했는지 정확히 그 자리에 코드가 있으니까.

3.3.3 표 기반 LL(1) 파서

재귀 하강을 자동화하면? 같은 일을 표(table)로 푸는 방식이 LL(1) 파서다. 이름의 뜻은:

• Left-to-right scan — 왼쪽에서 오른쪽으로 입력을 읽고
• Leftmost derivation — 최좌 유도를 만들며
• 1 토큰 룩어헤드

골격 LL(1) 파서는 작은 인터프리터에 가깝다.

word ← NextWord();
push eof onto Stack;
push 시작 기호 S onto Stack;
focus ← top of Stack;

loop forever;
   if (focus == eof and word == eof)
      then 성공 보고; break;
   else if (focus ∈ T or focus == eof) then begin
      if focus matches word then begin
         pop Stack;
         word ← NextWord();
      end
      else 단말 불일치 오류;
   end
   else begin   // focus는 비단말
      if Table[focus, word] == (A → B₁B₂…Bₖ) then begin
         pop Stack;
         for i ← k downto 1 do
            if Bᵢ ≠ ε then push Bᵢ onto Stack;
         end;
      end
      else 비단말 확장 오류;
   end;
   focus ← top of Stack;
end;

핵심은 Table[A, w]—비단말 A와 룩어헤드 w를 받아 “이 우변을 써라”를 돌려주는 표. 표 만드는 알고리즘은 다음과 같다.

FIRST, FOLLOW, FIRST⁺ 집합 계산;

for each 비단말 A do
   for each 단말 w do
      Table[A, w] ← error;
   end;
   for each 규칙 p: A → β do
      for each 단말 w ∈ FIRST⁺(A → β) do
         Table[A, w] ← p;
      end;
      if eof ∈ FIRST⁺(A → β)
         then Table[A, eof] ← p;
   end;
end;

문법이 백트래킹 없는 조건을 만족하면 한 칸에 한 규칙만 들어간다. 만족 안 하면 한 칸에 여러 규칙이 충돌—그러면 LL(1)이 아니다.

3.4 바텀업 파싱

바텀업 파서는 잎부터 시작한다. 스캐너가 토큰을 줄 때마다 트리 잎으로 추가하고, “이 잎열의 어느 부분이 어떤 규칙의 우변이지?”를 찾아 그 위에 부모 노드를 얹는다. 이 부모 얹기를 리덕션(reduction)이라 부른다.

바텀업 파싱은 역방향 최우 유도를 만든다. 최우 유도 Goal = γ₀ → γ₁ → … → γₙ = 문장에서, 파서는 γ_n(문장)부터 시작해 γ_n-1, γ_n-2… 순으로 거슬러 올라간다.

3.4.1 LR(1) 파싱 알고리즘

이름의 뜻:

• Left-to-right scan
• Reverse rightmost derivation — 역방향 최우 유도
• 1 토큰 룩어헤드

LR(1) 파서는 스택과 두 표—Action, Goto—를 쓴다. 스택에는 (기호, 상태)들이 쌓인다. 스택 꼭대기의 상태가 “지금까지 본 입력의 요약”을 담고, 다음 토큰(룩어헤드)과 함께 Action 표를 찾아 다음 행동을 결정한다.

가능한 행동은 4가지다.

• shift sᵢ — 룩어헤드를 스택에 넣고 새 상태 sᵢ를 얹는다. (=핸들 후보를 더 모음)
• reduce A → β — 스택 꼭대기 |β|개 (기호, 상태)를 떼어내고, 그 자리에 (A, Goto[새꼭대기상태, A])를 얹는다. (=핸들 발견, 줄임)
• accept — 성공.
• error — 구문 오류.

LR(1) 골격 파서

push $;
push 시작 상태 s₀;
word ← NextWord();

while (true) do
   state ← top of Stack;
   if Action[state, word] == "reduce A → β" then begin
      pop 2×|β| symbols;
      state ← top of Stack;
      push A;
      push Goto[state, A];
   end
   else if Action[state, word] == "shift sᵢ" then begin
      push word;
      push sᵢ;
      word ← NextWord();
   end
   else if Action[state, word] == "accept" then break;
   else Fail();
end;
성공 보고;

예: 균형 잡힌 괄호 문법

1  Goal → List
2  List → List Pair
3       | Pair
4  Pair → ( Pair )
5       | ( )

입력 ( )에 대해 LR(1) 파서가 어떻게 움직이는지 추적해 보자.

두 번 shift, 세 번 reduce, 한 번 accept. 핸들이 항상 스택 꼭대기에 있다는 점이 핵심이다 — 스택 자체가 “핸들이 어디 있는지”의 정보를 압축해서 가지고 다닌다.

잘못된 입력은 어떻게 잡나?

입력 ( ) )를 보자. 두 번째 )를 만나는 순간, 파서는 상태 7에서 )로 가는 칸을 보는데… 거기에 shift도 reduce도 accept도 없다. 즉시 오류 보고. 이게 LR 파서의 강점이다 — 문법적으로 더 진행할 수 없는 그 지점에서 즉시 오류를 잡아낸다.

3.4.2 LR(1) 표 만들기

이제 본론이다. Action과 Goto 표를 어떻게 자동 생성할까? 답은 LR(1) 아이템(item)이라는 자료구조와 그것들의 정규 컬렉션이다.

아이템의 의미는 점의 위치에 따라 셋 중 하나다.

1. 가능성(possibility) — [A → •βγ, a]: 점이 맨 왼쪽. “이제 β를 인식하면 A로 가는 길이 시작된다.”
2. 부분 완성(partially complete) — [A → β•γ, a]: 점이 가운데. “β까지 인식했고, γ가 남았다.”
3. 완성(complete) = 핸들 — [A → βγ•, a]: 점이 맨 오른쪽. “룩어헤드가 a라면 βγ를 A로 줄일 핸들이다.”

파서의 각 상태는 LR(1) 아이템들의 집합이다. 모든 상태의 모음을 정규 컬렉션(canonical collection) CC = {cc₀, cc₁, …, ccₙ}이라 한다. 이것이 핸들 인식 자동기(handle-recognizing DFA)의 모델이다. (서브셋 구성을 NFA→DFA 변환에서 본 것과 비슷한 발상이다.)

두 핵심 함수: closure와 goto

closure(s): 아이템 집합 s에 “함의되는” 아이템들을 모두 추가한다. [A → β • Cδ, a]가 s에 있고 C가 비단말이라면, C의 모든 우변에 대한 시작 아이템 [C → •γ, b]를 추가해야 한다. 단, b는 FIRST(δa)에 들어가야 한다.

closure(s)
   while (s가 변하는 동안)
      for each 아이템 [A → β • Cδ, a] ∈ s
         for each 규칙 C → γ ∈ P
            for each b ∈ FIRST(δa)
               s ← s ∪ {[C → •γ, b]}
   return s

goto(s, x): 상태 s에서 기호 x를 인식하면 어떤 상태가 되는가? s 안에서 점 바로 뒤에 x가 있는 아이템들을 골라서 점을 x 너머로 옮긴 뒤 closure를 취한다.

goto(s, x)
   moved ← ∅;
   for each 아이템 i ∈ s
      if i가 [α → β • x δ, a]의 모양이면
         moved ← moved ∪ {[α → βx • δ, a]};
   return closure(moved);

정규 컬렉션 CC 만들기

cc₀ ← closure({[S' → •S, eof]});
CC ← {cc₀};

while (새 집합이 CC에 추가되는 동안)
   for each 처리되지 않은 ccᵢ ∈ CC
      mark ccᵢ as processed;
      for each 점 뒤에 등장하는 기호 x in ccᵢ
         temp ← goto(ccᵢ, x);
         if temp ∉ CC
            then CC ← CC ∪ {temp};
         ccᵢ에서 temp로 x에 의한 전이를 기록;
      end
   end

CC는 monotonic하게 자라고, LR(1) 아이템 수가 유한하므로 반드시 끝난다. (이론적 상한은 2^|아이템|지만, 실제로는 훨씬 작다.)

표 채우기

CC가 완성되면, 각 ccᵢ가 표의 한 행이 된다. 아이템 모양에 따라 entry를 채운다.

for each ccᵢ ∈ CC
   for each 아이템 I ∈ ccᵢ
      if I == [A → β • c γ, a] and goto(ccᵢ, c) == ccⱼ
         then Action[i, c] ← "shift j";       // 단말 c
      else if I == [A → β •, a]
         then Action[i, a] ← "reduce A → β";
      else if I == [S' → S •, eof]
         then Action[i, eof] ← "accept";
   end
   for each 비단말 n
      if goto(ccᵢ, n) == ccⱼ
         then Goto[i, n] ← j;
end

괄호 문법은 11개 상태(cc₀..cc₁₁)와 12개 entry로 끝난다. 작지만 알고리즘의 모든 면을 보여주는 좋은 예다.

3.4.3 표 구성에서 발생하는 오류 — 충돌(Conflict)

같은 칸 Action[i, a]에 두 개 이상의 행동이 들어가면 충돌이다.

shift-reduce 충돌

고전적인 매달린 else 문법으로 LR(1) 표를 만들어 보면 어떤 상태에서 다음 두 아이템이 동시에 나타난다.

1. [Stmt → if expr then Stmt •, else]   // reduce
3. [Stmt → if expr then Stmt • else Stmt, else]  // shift

룩어헤드 else를 만나면 reduce할지 shift할지 모호하다. 이게 shift-reduce 충돌이다. 모호한 문법의 직접적 증상이다.

관습적 해결: shift를 우선시한다. 그러면 else가 가장 가까운 if에 묶이는 결과가 된다.

reduce-reduce 충돌

두 규칙이 같은 우변을 가지면 (예: A → γδ와 B → γδ) 핸들을 줄일 때 어느 좌변으로 줄일지 모호하다. 같은 룩어헤드에 두 reduce 행동이 들어가면 reduce-reduce 충돌이 된다. 이것 역시 문법의 모호함을 가리킨다 — 컴파일러 작성자가 문법을 다시 써야 한다.

3.5 실전에서 만나는 문제들

3.5.1 오류 복구(Error Recovery)

지금까지 본 파서들은 오류를 만나면 즉시 멈춘다. 한 번 컴파일에 한 개의 오류만 보고한다는 뜻이다. 실전에서는 한 번에 가능한 한 많은 오류를 잡고 싶다 — 안 그러면 프로그래머가 “고치고-컴파일하고-한 줄 위에서 또 막힘”을 100번 반복해야 한다.

흔한 전략: 동기화 토큰(synchronizing word)으로 점프하기. Algol 계열 언어에서는 보통 세미콜론(;)을 동기화 토큰으로 쓴다. 오류를 만나면 다음 ;까지 스캐너를 진행시키고, 파서 상태를 “문장이 막 끝난 것처럼” 리셋한 뒤 계속한다.

• 재귀 하강 파서: 그냥 토큰을 버리다가 ; 만나면 statement 함수에서 return. C의 setjmp/longjmp를 쓰면 더 깔끔.
• LR(1) 파서: 좀 복잡하다. 입력에서 ;까지 진행한 뒤, 스택을 거꾸로 훑으며 Goto[s, Statement]가 유효한 상태 s를 찾는다. 그 위쪽을 모두 버리고 Statement 상태를 푸시해 다시 출발.

표 생성기에 “오류 생성 규칙(error production)”을 명시하면 자동 생성도 가능하다. 단, 오류가 한 번이라도 발생한 컴파일 단위는 최적화나 코드 생성을 시도하면 안 된다—구문 오류 너머에 의미 있는 코드는 없다.

3.5.2 단항 연산자(Unary Operators)

고전 수식 문법은 이항 연산자만 다뤘다. 절댓값 ||같은 단항 연산자를 추가해 보자. 절댓값은 × ÷보다 우선순위가 높지만 괄호보다는 낮아야 한다.

0  Goal   → Expr
1  Expr   → Expr + Term
2         | Expr - Term
3         | Term
4  Term   → Term × Value
5         | Term ÷ Value
6         | Value
7  Value  → || Factor
8         | Factor
9  Factor → ( Expr )
10        | num
11        | name

새 비단말 Value를 도입했다. ||x - 3은 (||x) - 3으로 파싱되고, |||x는 거부된다 (수학적으로 무의미하니까). 하지만 ||(||x)는 허용된다.

같은 발상으로 C의 **p(이중 역참조) 같은 것도 처리할 수 있다 — Value → * Value를 추가하면 된다. 이항 ×와 단항 *가 같은 토큰이지만, 문맥에 따라 문법이 둘을 분리해서 처리한다.

3.5.3 문맥 의존 모호함(Context-Sensitive Ambiguity)

한 단어가 두 의미를 가지면 구문 모호함이 생긴다. FORTRAN, PL/I, Ada는 함수 호출과 배열 인덱스를 모두 괄호 ()로 표기했다. fee(i, j)는 함수 호출인가 2차원 배열 접근인가? 답은 fee의 선언된 타입에 달려 있다 — 이건 구문 정보가 아니다.

문법으로 표현하면:

FunctionReference → name ( ArgList )
ArrayReference    → name ( ArgList )

두 우변이 똑같다 → reduce-reduce 충돌 확정.

해결책 두 가지:

1. 구문에서는 합치고 나중에 푼다: 두 우변을 한 비단말로 합쳐서 일단 파싱하고, 의미 분석 단계에서 선언 정보를 보고 함수 호출/배열 참조로 분기.
2. 스캐너가 구분한다: 선언이 사용보다 먼저 온다는 규칙(define-before-use)이 있으면, 파서가 심볼 테이블을 채워가며 스캐너에게 “fee는 함수다”/“배열이다”를 알려주는 식. 그러면 스캐너가 function-name과 variable-name을 다른 토큰 종류로 분류해서 돌려준다.

두 번째가 더 깔끔하다. C가 배열에 []를 쓰고 함수에 ()를 쓰는 건 이런 모호함을 처음부터 차단하기 위한 설계 결정이다.

3.5.4 좌재귀 vs 우재귀

탑다운 파서는 좌재귀를 못 다루고 우재귀를 써야 한다. 바텀업 파서는 둘 다 가능하다. 그럼 LR(1)에서는 어느 쪽을 고를까?

스택 깊이

좌재귀가 스택을 덜 쓴다. 5원소 리스트를 예로 보자.

(a) 좌재귀:                    (b) 우재귀:
List → List elt                 List → elt List
     | elt                            | elt

좌재귀: elt₁ shift, 즉시 List로 reduce. elt₂ shift, List elt₂를 List로 reduce… 스택은 항상 깊이 2 정도. 평균 깊이 ≈ 5/3.

우재귀: 5개의 elt를 모두 stack에 쌓은 뒤, elt₅를 List로 reduce하고, 그 다음 거꾸로 합쳐 올라간다. 최대 깊이 5, 평균 깊이 ≈ 10/3.

긴 명령문 리스트(수백 개의 직선 코드)에서 우재귀는 스택을 수백 칸 잡아먹지만 좌재귀는 두세 칸이면 끝. 가능하면 좌재귀를 쓰자.

결합성(Associativity)

좌재귀는 자연스럽게 좌결합을 만들고 우재귀는 우결합을 만든다. 리스트라면 무관하지만 산술 연산에서는 결정적이다.

x₁ + x₂ + x₃ + x₄ + x₅

좌재귀 → ((((x₁+x₂)+x₃)+x₄)+x₅) — 좌→우 평가.
우재귀 → (x₁+(x₂+(x₃+(x₄+x₅)))) — 우→좌 평가.

부동소수점 산술에서는 두 결과가 다를 수 있다 (덧셈이 결합법칙을 만족하지 않으니까). x₁ - x₂ + x₃의 경우 좌결합은 (x₁-x₂)+x₃로 우리가 원하는 답을 주지만, 우결합은 x₁-(x₂+x₃)로 잘못된 답을 준다. 뺄셈이 섞이면 좌결합이 정답이다.

3.6 고급 주제

3.6.1 문법 최적화

구문 분석이 컴파일 시간의 큰 부분을 더 이상 차지하진 않지만, 파스 트리가 작을수록 reduce/expand 횟수도 줄어 빨라진다. 작은 최적화가 가능하다.

고전 수식 문법의 a+2×b는 14개 노드짜리 트리를 만든다. Factor는 자식이 하나뿐인 “쓸데없는 중간층”을 만든다. Factor의 우변들을 Term의 우변으로 펴서 합치면 한 층을 없앨 수 있다.

4  Term → Term × ( Expr )
5       | Term × name
6       | Term × num
7       | Term ÷ ( Expr )
8       | Term ÷ name
9       | Term ÷ num
10      | ( Expr )
11      | name
12      | num

Term의 우변이 3배로 늘었지만 트리가 한 층 얇아진다. LR(1) 파서에서 reduce 횟수가 줄고, 파싱이 빨라진다.

일반적으로 우변이 단일 기호인 “쓸모없는 생성 규칙(useless production)”은 접어 없앨 수 있다. 단, 표 크기는 늘 수 있으니 트레이드오프다.

3.6.2 LR(1) 표 크기 줄이기

고전 수식 문법의 LR(1) 표는 32×8 정도다. 큰 언어에서는 수천×수백이 된다. 줄이는 법:

1. 같은 행/열 합치기 — 표에서 동일한 행/열들을 발견하면 한 번만 저장하고 매핑한다. 행 인덱스를 한 번 더 거치는 비용은 있지만 메모리는 크게 절약된다.
2. 문법 줄이기 — num과 name처럼 통합 가능한 단말은 한 토큰 종류 val로 합치고, ×와 ÷는 muldiv로, +와 -는 addsub로 합친다. 행과 열이 동시에 줄어든다. 단, 스캐너가 협조해서 같은 syntactic 카테고리를 돌려줘야 한다.
3. 표를 직접 코드로 인코딩 — 골격 파서 + 표 대신, 각 상태를 if-else 분기로 펼친 함수로 만든다. 메모리 접근이 사라지고 명령어 캐시 친화적이다. 사람이 읽기는 어렵지만 빠르다.
4. 다른 구성 알고리즘 쓰기 — SLR(1)(Simple LR)은 룩어헤드 없이 FOLLOW 집합으로 처리해 표가 더 작다. LALR(1)(Lookahead LR)은 LR(1) 아이템들을 “핵심 아이템” 기준으로 합쳐 SLR(1)과 같은 크기의 표를 만든다. 받아들이는 문법 클래스가 약간 좁지만 거의 모든 실용 언어를 다룬다. (yacc/bison이 LALR(1)이다.)

3.7 정리하며

거의 모든 컴파일러는 파서를 가진다. 수십 년의 연구 끝에 결정론적 LR(1)/LALR(1)/SLR(1) 표 생성기가 표준이 되었고, yacc, bison, ANTLR 같은 도구가 흔하다.

두 큰 흐름을 비교하자.

실용적 조언:

• LR(1) 도구가 손에 있다면 그걸로 시작하라. 처음부터 만들지 마라.
• 키워드를 식별자로 허용하는 등 문법이 까다로우면 재귀 하강이 유연하다. (PL/I, 옛날 FORTRAN…)
• 오류 메시지에 진심이면 재귀 하강이 좋다.

대부분의 프로그래밍 언어 구문은 LR(1) 또는 LL(1) 형태로 표현 가능하다. 그래서 일반화된 O(n³) 알고리즘(Earley, CYK 등)은 컴파일러에 잘 안 쓰인다 — 정밀하지만 너무 느리다.