Table of Contents

점과 상태 — 파서가 "어디쯤" 인지 기억하는 법

앞 FIRST / FOLLOW에서 — 파서가 "시작/끝" 을 판단하려고 만들어 두는 치트시트 를 봤죠.
이번엔, 파서가 입력을 읽어 나가며 "내가 지금 어디쯤 왔지?" 를 어떻게 기억하는지 봐요.
(여기도 공식·코드 없이, 느낌 으로만 가요. 😀)

읽다 보면 — "어디까지 읽었나" 표시가 필요해요

파서는 토큰을 왼쪽부터 하나씩 읽어요.
그러다 보면 어떤 규칙을 시작은 했는데 아직 안 끝난 상황이 자꾸 생겨요.

예를 들어 규칙 Expr : Expr '+' Term 을 따라가는 중이라고 해봐요.
Expr 까지는 읽었고, 이제 '+' 가 오기를 기다리는 참이에요.
이 "어디까지 왔는지" 를 어떻게 적어둘까요?

아주 단순한 방법이 있어요 — 규칙 한가운데에 점(•) 을 하나 찍는 거예요.

   Expr → Expr • '+' Term

점 앞 은 이미 읽은 것, 점 뒤 는 아직 읽을 것 이에요.
위 점은 "Expr 까지 읽었고, 다음은 '+'" 를 뜻하죠.

📖 이렇게 점을 찍은 규칙 을 LR 아이템(item) 이라고 불러요.
이름은 거창하지만, 방금 본 "규칙 + 어디까지" 가 전부예요. 앞으로 그냥 "아이템" 이라고 할게요.

점은 토큰을 하나 읽을 때마다 한 칸씩 오른쪽 으로 가요.

   Expr → • Expr '+' Term      (아직 아무것도 안 읽음)
   Expr → Expr • '+' Term      (Expr 까지 읽음)
   Expr → Expr '+' • Term      ('+' 까지 읽음)
   Expr → Expr '+' Term •      (다 읽음 — 이제 한 덩어리로 묶을 차례!)

점이 맨 끝 에 닿으면, 그 규칙을 다 읽은 거예요.
이때가 바로 묶을(reduce) 차례 고요. (FIRST / FOLLOW에서 "끝나면 묶는다" 던 그 순간이에요.)

그런데 — 가능성은 보통 여러 개 예요

여기서 한 발만 더 가요.
파서가 어느 지점에 서 있을 때, 진행 중인 규칙 이 꼭 하나라는 법은 없어요.

a + a * a 를 읽다가, 첫 a 를 Term 까지 봤다고 해봐요. (a 는 이름이니 Factor, 그 Factor 는 Term 이죠.)
바로 그 순간, 두 가지가 동시에 가능해요.

  • "이 Term 하나로 한 덩어리 끝" 일 수도 있고 → Expr → Term •
  • "뒤에 * 무언가 가 더 붙는다" 일 수도 있어요 → Term → Term • '*' Factor
   Expr → Term •                 ← 여기서 끝일 수도
   Term → Term • '*' Factor      ← '*' 가 더 붙을 수도

이렇게 "지금 가능한 아이템들" 을 한 묶음으로 모은 게 — 파서의 상태(state) 예요.

🧭 비유하자면, 상태는 갈림길에 선 내비게이션 화면 같아요.
"여기서 갈 수 있는 길은 이것들" 을 한눈에 보여주는 거죠.
그리고 다음 토큰 이 그중 한 길을 골라줘요 — * 면 더 가고, + 나 입력의 끝이면 묶고요.
("묶어도 되는 다음 토큰" 을 FOLLOW 가 알려준다던 게, 바로 여기서 쓰여요.)

읽을 때마다 — 상태에서 상태로

파서는 토큰을 하나 읽을 때마다 한 상태에서 다른 상태로 옮겨가요.
마치 역에서 역으로 가듯이요.

   (시작 상태) ──읽기──▶ (다음 상태) ──읽기──▶ (다음 상태) ──▶ …

그래서 LR 파서는 사실 "상태들 사이를 옮겨 다니는 기계" 예요.
어느 상태에 있고 + 다음 토큰이 뭔지 — 그 둘이면 다음 행동(더 읽기 / 묶기)이 정해지죠.

📦 이 상태들이 정확히 몇 개고 어떻게 만들어지는지 는 정해진 조립 과정 이 있어요 (점을 옮기고, 빠진 가능성을 채우고…). 좀 기계적인 작업이라, 궁금하면 심화 과정 의 LR 아이템부터 한 단계씩 보면 돼요.
기본 트랙은 여기까지면 충분해요 — "상태 = 지금 가능한 것들의 묶음, 읽으면 옆 상태로 옮겨감" 이 느낌만 챙기면요. 🙂

다음 장

이제 재료가 다 모였어요 — 점(어디까지 읽었나), 상태(지금 가능한 것들), 그리고 FIRST / FOLLOW(시작/끝 치트시트).

이 셋을 합치면 — 파서의 행동 지침서, 즉 파싱 테이블 이 돼요.
그리고 그 표로 a + a * a 를 진짜로 파싱 해볼 거예요. (제일 재밌는 부분이에요 👀)

👉 표로 실제 파싱해보기

👈 이전 장: FIRST / FOLLOW

Edit this page