Table of Contents

파싱 테이블 · 만드는 법

🎓 심화 과정 이에요.
정준 집합에서 상태 12개와 그 사이 전이 를 다 모았죠.
이제 그걸 — 파서가 실제로 보고 움직이는 — 표 한 장 으로 바꿔요. 그게 파싱 테이블 이에요.

📍 사는 곳 · LRParsingTable.CreateParsingTable · …/Parsers/Collections/…

파싱 테이블이란

파서는 입력을 읽다가 매 순간 "지금 뭘 해야 하지?" 를 정해야 해요. 그 답을 미리 다 적어둔 표가 파싱 테이블 이에요.
한마디로 — 파서의 행동 지침서 죠. "지금 어느 상태에 있고(행), 다음 입력 기호가 뭐냐(열) → 그럼 이 행동을 해라" 를 칸마다 적어둔 거예요.

표는 두 부분으로 나뉘어요.

  • ACTION — 열이 단말 + $(입력 끝). 각 칸엔 세 행동 중 하나가 들어가요.
    • shift(이동) — 다음 단말을 읽어 스택에 밀어넣고, 가리키는 다음 상태로 간다. s5 = "읽고 I₅ 로".
    • reduce(묶기) — 어떤 생성규칙의 오른쪽을 다 읽었으니, 그걸 왼쪽 비단말로 묶는다. r2 = "2번 생성규칙으로 묶어라".
    • accept(받아들임) — 입력 전체가 문법에 맞았다. 끝. acc.
  • GOTO — 열이 비단말. 비단말 하나를 묶은 뒤 어느 상태로 갈지예요. (정준 집합 전이표의 비단말 칸 그대로고요.)

💡 shift·reduce, 어디서 봤죠? 상태 장에서 "점 뒤가 단말이면 더 읽고(shift), 점이 끝이면 묶는다(reduce)" 던 그거예요.
그 판단을 모든 상태 × 모든 입력 에 대해 미리 표로 적어두는 게 — 파싱 테이블이에요.

채우는 규칙

표 채우기는, 정준 집합에서 만든 상태들의 아이템 과 전이 를 그대로 옮기는 일이에요. 규칙은 네 개 뿐이에요.

먼저 생성규칙에 번호를 매겨요. (reduce 가 "몇 번으로 묶을지" 를 가리키거든요.)

   1:  Expr   → Expr '+' Term
   2:  Expr   → Term
   3:  Term   → Term '*' Factor
   4:  Term   → Factor
   5:  Factor → '(' Expr ')'
   6:  Factor → id

이제 각 상태 Iᵢ 마다 —

① shift — 점 뒤가 단말 a 인 아이템이 있고 GOTO(Iᵢ, a) = Iⱼ 면 → ACTION[Iᵢ][a] = sⱼ
② goto — 점 뒤가 비단말 A 라서 GOTO(Iᵢ, A) = Iⱼ 면 → GOTO[Iᵢ][A] = j
③ reduce — 완료 아이템 A → α •(점이 끝)이 있으면 → A 의 FOLLOW 에 있는 단말 x 마다 ACTION[Iᵢ][x] = rN (N = 그 생성규칙 번호)
④ accept — Accept → Expr • 가 있으면 → ACTION[Iᵢ][$] = acc

①②는 전이표를 그대로 옮기는 것(단말은 ACTION, 비단말은 GOTO), ③④는 완료 아이템 에서 나와요.

③의 "FOLLOW 에 있는 단말마다" 가 핵심이에요 — "이 규칙으로 묶고 난 다음에 올 수 있는 토큰" 일 때만 묶는 거죠. 상태 장에서 "reduce 는 FOLLOW 일 때" 라던 그 약속이에요.
(이렇게 FOLLOW 로 reduce 칸을 정하는 방식 을 SLR 이라고 불러요 — 충돌 을 보고 난 뒤, SLR 장에서 제대로 다뤄요.)

직접 채워보기

규칙을 우리 상태 몇 개에 직접 적용해 봐요. (정준 집합의 상태·전이표를 옆에 두고요.)

① I₀ 의 ACTION·GOTO — 완료 아이템이 없어 ①②만

I₀ 엔 완료 아이템이 없으니 ①②만 써요.

  • 점 뒤 단말: '('(Factor → • '(' Expr ')')과 id(Factor → • id). 전이표에서 GOTO(I₀,'(') = I₄, GOTO(I₀,id) = I₅ 였죠 → '(' = s4, id = s5
  • 점 뒤 비단말: Expr→I₁, Term→I₂, Factor→I₃ → GOTO: Expr = 1, Term = 2, Factor = 3

② I₂ 의 reduce — 완료 아이템의 FOLLOW 칸에 r2

I₂ 엔 완료 아이템 Expr → Term • (2번 규칙)이 있어요.

  • Expr 의 FOLLOW 는 { $, '+', ')' } 죠 → 그 세 칸에 '+' = r2, ')' = r2, $ = r2
  • 같이 있는 Term → Term • '*' Factor 에서 shift 도 나와요: '*'→I₇ → '*' = s7

③ I₁ 의 accept — $ 칸이 받아들임

I₁ 엔 Accept → Expr • 가 있으니 → $ = acc.
(그리고 Expr → Expr • '+' Term 에서 '+'→I₆ → '+' = s6.)

이런 식으로 12개 상태를 다 채우면 — 표가 완성돼요.

완성된 SLR 파싱 테이블

왼쪽 여섯 열(id ~ $)이 ACTION, 오른쪽 세 열(Expr·Term·Factor)이 GOTO 예요.

상태 id '+' '*' '(' ')' $ Expr Term Factor
I₀ s5 s4 1 2 3
I₁ s6 acc
I₂ r2 s7 r2 r2
I₃ r4 r4 r4 r4
I₄ s5 s4 8 2 3
I₅ r6 r6 r6 r6
I₆ s5 s4 9 3
I₇ s5 s4 10
I₈ s6 s11
I₉ r1 s7 r1 r1
I₁₀ r3 r3 r3 r3
I₁₁ r5 r5 r5 r5

표 읽는 법 — sⱼ = 읽고 Iⱼ 로(shift), rN = N번 규칙으로 묶기(reduce), acc = 받아들임, GOTO 칸의 숫자 = 비단말을 묶은 뒤 갈 상태.
빈 칸 은 그 입력은 여기서 오류 라는 뜻이에요.

다음

표는 다 만들었어요. 그런데 두 가지가 남았어요.

  • 만약 한 칸에 행동이 둘 들어가면 어쩌죠? (상태 장에서 심어둔 그 충돌 씨앗.)
  • reduce 칸을 FOLLOW 로 정한 이 방식(SLR)은 — 어떤 한계가 있고, 어떻게 더 정밀해질까요?

👉 파싱 테이블 · 충돌이란?

👈 이전 장: 정준 집합

Edit this page