파싱 테이블 · 충돌이란?
지난 페이지에서 우리는 Expr 문법으로 파싱 테이블 을 완성했어요. 그 표를 잠깐만 다시 떠올려봐요.
한 칸 한 칸에 행동이 딱 하나씩 들어가 있었죠 — s5, r2, goto 3, acc … 그래서 파서는 매 순간 망설임 없이 칸 하나를 찾아 그대로 따라가기만 하면 됐어요.
그런데 만드는 법 페이지 끝에서, 제가 질문 하나를 슬쩍 던져뒀어요.
"만약 한 칸에 행동이 둘 들어가면 어쩌죠?"
이 페이지가 바로 그 이야기예요. 천천히 가봅시다.
먼저 — 표는 왜 "막힘없이" 굴러갔나
파싱 테이블이 하는 일을 한 줄로 줄이면 이거였어요.
지금 상태 + 다음에 올 글자 → 무슨 행동을 할지, 그걸 칸 하나하나에 적어둔 것.
파서는 매 순간 지금 상태 와 다음 글자 로 표에서 칸을 하나 찍고, 거기 적힌 대로만 움직여요.
칸마다 적힌 답이 하나 니까 — 파서는 단 한 번도 고민하지 않아요. 이렇게 고민 없이 척척 굴러가는 성질을 결정적(deterministic) 이라고 불러요.
🔖 결정적(deterministic) — 매 순간 할 행동이 정확히 하나로 정해져 있어서, 파서가 헷갈릴 일이 없는 것.
자, 바로 이 "칸마다 하나" 라는 약속이 깨지면 무슨 일이 벌어질까요?
충돌 — 한 칸에 행동이 둘
어떤 문법은 — 표를 채워가다 보면 한 칸에 행동이 두 개 들어가버려요.
그 칸에 도착한 파서는 그 순간 멈칫해요. "어… 둘 중에 뭘 하라는 거지?"
이렇게 한 칸에 들어갈 행동이 둘 이상이라, 파서가 무엇을 할지 결정하지 못하는 상황 을 충돌(conflict) 이라고 불러요.
🔖 충돌(conflict) — 파싱 테이블의 한 칸에 행동이 둘 이상 들어가, 파서가 결정을 못 하게 된 것.
우리 Expr 문법은 운 좋게 — 사실은 잘 설계돼서 — 충돌이 하나도 없었어요. 그래서 표가 그렇게 깔끔했던 거예요.
하지만 세상의 많은 문법은 그렇지 않아요. 충돌이 어떻게 생기는지, 그 두 가지 종류를 하나씩 봅시다.
종류 ① — shift / reduce 충돌
충돌을 일부러 보여주려고, 우리 Expr 말고 아주 작은 문법 하나를 가져올게요.
S → S '+' S S → a
"S 는 S 더하기 S, 또는 그냥 a" — 덧셈을 나타내는 작디작은 문법이에요.
이 문법으로 상태들을 만들다 보면, 어떤 한 상태 안에 이런 두 아이템이 같이 들어가요. (아이템·상태가 가물가물하면 LR 아이템·상태 장을 떠올려요.)
S → S '+' S • ← 점이 맨 끝. 완료 아이템 → '+'를 보면 reduce (S+S를 S로 접기) S → S • '+' S ← 점 뒤가 '+'. 진행 아이템 → '+'를 보면 shift ('+'를 읽고 더 나아가기)
같은 상태, 같은 다음 글자 + 인데 —
위 아이템은 "reduce 해" 라고, 아래 아이템은 "shift 해" 라고, 서로 다른 행동 을 외쳐요.
그러니 이 상태의 + 칸에는 행동이 둘 들어가버려요.
| 상태 | … | + |
… |
|---|---|---|---|
| (이 상태) | shift / reduce ⚠️ |
한쪽은 shift, 한쪽은 reduce 라서 부딪히는 이 충돌을 — 그대로 shift/reduce 충돌 이라고 불러요.
💡 왜 생겼을까 —
a + a + a를 떠올려봐요. 가운데까지 읽은 파서는 왼쪽a + a를 먼저 한 덩이로 접을지(reduce), 아니면 일단+를 더 받아두고 나중에 정할지(shift) 정해야 해요. 그런데 이 문법은(a+a)+a도,a+(a+a)도 둘 다 맞다 고 해요. 답이 둘이니 파서가 못 고르는 거예요. 이렇게 한 문장을 두 가지로 해석할 수 있는 문법을 모호한(ambiguous) 문법 이라고 불러요. (단, 충돌이 곧 모호함은 아니에요 — 모호하지 않은데도 충돌이 보이는 경우가 있고, 그중 상당수는 표를 더 정밀히 채우면 사라지는 헛충돌 이에요. 바로 다음 얘기죠.)
종류 ② — reduce / reduce 충돌
이번엔 또 다른 작은 문법.
S → A S → B A → a B → a
"a 하나가 A 도 될 수 있고 B 도 될 수 있는" 문법이에요.
표를 만들다 보면, a 를 막 읽은 직후 상태에 이런 두 아이템이 같이 들어가요.
A → a • ← 완료. reduce A→a B → a • ← 완료. reduce B→a
이번엔 둘 다 reduce 예요. 그런데 — 어느 규칙으로 접으라는 거죠? A→a 로? B→a 로?
둘 다 "접어" 인데 접는 대상이 달라서 부딪혀요. 이걸 reduce/reduce 충돌 이라고 불러요.
두 종류를 나란히 두면:
| 충돌 종류 | 한 칸에 부딪히는 것 | 파서의 고민 |
|---|---|---|
| shift / reduce | shift 하나 + reduce 하나 | "더 읽을까, 지금 접을까?" |
| reduce / reduce | reduce 둘 (규칙이 다름) | "어느 규칙으로 접지?" |
[상태] 장에서 심어둔 씨앗
기억나세요? 상태 장에서 — 한 상태 안에는 완료 아이템(점이 끝에 있어 접으려는)과 진행 아이템(점 뒤에 기호가 남아 읽으려는)이 섞여 있을 수 있다 고 했고, 그걸 🌱 충돌 씨앗 이라고 불러뒀어요.
지금, 그 씨앗이 자라서 열매가 된 거예요.
- 한 상태에서 완료 아이템과 진행 아이템 이 같은 글자 를 두고 부딪히면 → shift/reduce 충돌
- 한 상태에서 완료 아이템 둘 이 부딪히면 → reduce/reduce 충돌
상태를 배울 때 "이게 나중에 충돌이 돼요" 하고 미뤄뒀던 그 이야기를, 이제 다 갚은 셈이에요.
그래서 — 충돌이 나면 어떻게 되나
문법에 충돌이 있으면, 그 표는 "칸마다 답이 하나" 라는 약속이 깨져요.
= 그 문법은 그대로는 결정적으로 파싱할 수 없어요. 파서가 그 칸에서 멈춰버리니까요.
빠져나갈 길은 둘이에요.
- 문법을 고친다 — 모호함을 걷어내, 충돌이 아예 안 나게 다시 쓰기.
(우리 Expr 문법이 바로 그렇게 잘 다듬어진 문법이에요. 그래서 표가 깨끗했죠.) - 표를 더 똑똑하게 채운다 — 놀랍게도, 충돌처럼 보이는 것 중 일부는 진짜 충돌이 아니라, 표를 덜 정밀하게 채워서 생긴 헛충돌 이에요. 더 정밀하게 채우면 스르르 사라져요.
그 "더 정밀하게 채운다" 로 가는 여정이 — 바로 다음 페이지(SLR)부터 시작돼요.
만드는 법 페이지에서 reduce 칸을 FOLLOW 로 정했던 그 방식(이름이 SLR 이라고 했죠?)이 왜 헛충돌 을 만드는지부터 보고 — 거기서 lookahead → CLR → LALR 로 정밀도의 사다리를 한 칸씩 올라가며, 그 헛충돌을 어떻게 없애는지 봐요.
다음
- 충돌 = 한 칸에 행동이 둘. shift/reduce 와 reduce/reduce, 두 종류.
- 어떤 충돌은 진짜 고, 어떤 충돌은 표를 덜 정밀하게 채워 생긴 헛충돌 이다 — 다음 장의 핵심.