표로 실제 파싱해보기
드디어 — 지금까지 모은 걸 다 합쳐서, a + a * a 를 진짜로 파싱 해봐요. (제일 재밌는 부분이에요 👀)
재료는 다 있어요: 점·상태(어디까지·지금 가능한 것들)와
FIRST / FOLLOW(시작·끝 치트시트). 이 둘로 만든 파싱 테이블(행동 지침서) 이 매
순간 "이렇게 해라" 를 알려줄 거예요.
파서가 하는 건 딱 두 가지 — shift 와 reduce
파서는 매 순간 둘 중 하나 만 해요.
- shift(밀어넣기) — 다음 토큰을 하나 읽어서 스택 에 쌓아요.
- reduce(묶기) — 스택 맨 위 몇 개가 어떤 규칙의 오른쪽 과 딱 맞으면, 그걸 왼쪽 비단말 로 묶어요. (= 트리 가지 하나 완성!)
🍽️ 스택 은 접시 더미 같은 거예요 — 맨 위에만 올리고(shift), 맨 위에서만 빼요(reduce).
파서가 "지금까지 읽고 묶은 것" 을 여기에 쌓아둬요.
그럼 언제 shift 하고 언제 reduce 할까요? — 그걸 파싱 테이블 이 정해줘요.
"지금 이런 상태이고 다음 토큰이 이거면 → shift / reduce 해라." (표를 만드는 법은
심화 과정에 있어요. 여기선 표가 시키는 대로 따라가 봐요.)
a + a * a 를 끝까지 따라가기
a 는 이름이니 단말 id 고요. 입력의 끝은 $ 로 표시할게요.
한 줄씩 가봐요 — 행동 칸이 바로 표가 시킨 거예요.
| # | 스택 | 남은 입력 | 행동 |
|---|---|---|---|
| 1 | (비었음) | a + a * a $ |
a 를 shift |
| 2 | a |
+ a * a $ |
reduce Factor → id |
| 3 | Factor |
+ a * a $ |
reduce Term → Factor |
| 4 | Term |
+ a * a $ |
reduce Expr → Term |
| 5 | Expr |
+ a * a $ |
+ 를 shift |
| 6 | Expr + |
a * a $ |
a 를 shift |
| 7 | Expr + a |
* a $ |
reduce Factor → id |
| 8 | Expr + Factor |
* a $ |
reduce Term → Factor |
| 9 | Expr + Term |
* a $ |
* 를 shift |
| 10 | Expr + Term * |
a $ |
a 를 shift |
| 11 | Expr + Term * a |
$ |
reduce Factor → id |
| 12 | Expr + Term * Factor |
$ |
★ reduce Term → Term '*' Factor |
| 13 | Expr + Term |
$ |
★ reduce Expr → Expr '+' Term |
| 14 | Expr |
$ |
accept 🎉 |
스택이 shift 로 자라고, reduce 로 묶이며 줄어드는 게 보이죠?
맨 끝엔 Expr 하나만 남았어요 — 입력 전체가 하나의 식 으로 묶인 거예요.
보세요 — a * a 가 + 보다 먼저 묶였어요
★ 표시한 12번 줄을 다시 보세요.
a * a 가 한 Term 으로 묶인 다음에야, 13번 에서 + 가 묶였죠.
즉 — * 가 + 보다 더 먼저, 더 깊이 묶였어요. 곱셈 우선순위 가 저절로 지켜진 거예요!
(한눈에 보는 파이프라인에서 약속했던 "곱하기가 더하기보다 먼저 묶인다" 가 바로
이거예요.)
완성된 트리로 보면 한눈에 들어와요.
Expr ├─ Expr │ └─ Term │ └─ Factor │ └─ a ├─ + └─ Term ← a * a 가 여기 한 덩어리로! ├─ Term │ └─ Factor │ └─ a ├─ * └─ Factor └─ a
맨 위 Expr 은 (왼쪽 a) + (오른쪽 a * a) 예요. a * a 가 오른쪽 깊은 곳에 한 덩어리로 묶여
있죠? — 표가 그렇게 이끈 거예요.
끝 — accept 🎉
스택에 Expr 하나만 남고 입력이 $(끝)에 닿았을 때, 표가 마지막으로 accept(받아들임) 라고 말해요.
"입력 전체가 문법에 맞는 하나의 Expr 이다" — 파싱 성공!
그럼 틀린 입력은요? (예:
a + + a)
파싱 도중 표의 칸이 비어 있는 곳을 만나면 — "여기선 할 수 있는 게 없다" → 그게 문법 오류 예요. 바로 다음 장에서 이a + + a를 직접 따라가 봐요.
다 왔어요 — 거의 🎉
성공하는 길은 이게 전부예요 — 읽고(shift), 맞으면 묶고(reduce), 표가 시키는 대로, accept 까지.
딱 하나 남았어요 — 위에서 흘린 그 질문, 틀린 입력(a + + a)이 오면 어떻게 될까 예요. 표가 그것마저
어떻게 걸러내는지 보고 기본 과정을 마무리해요.
👈 이전 장: 점과 상태