Table of Contents

한눈에 보는 파이프라인

시작하기에서 5줄로 파싱을 돌려봤죠.
그 5줄 안에서는 사실 여러 단계가 순서대로 일어납니다.
이 장에서는 그 전체 흐름(파이프라인) 을 큰 그림으로 봅니다.
세부는 각자 자기 장에서 다루니, 여기선 "지도"만 머리에 넣으세요.

텍스트가 결과가 되기까지

우리 입력 a + a * a가 어떤 길을 걷는지 따라가 봅시다.

   "a + a * a"            ← ① 그냥 글자들의 나열 (텍스트)
        │
        ▼  렉싱 (Lexing)
   [a] [+] [a] [*] [a]    ← ② 의미 있는 조각 = 토큰(token)들
        │
        ▼  파싱 (Parsing)
        Expr              ← ③ 문법 구조 = 파스 트리(parse tree)
       /  |  \
     Expr '+' Term
      |       / | \
     Term  Term '*' Factor
      ...
        │
        ▼  (그 다음 단계들 — 의미 분석, 코드 생성 …)
     실행 / 번역 / 컴파일

각 화살표가 하나의 변환 단계입니다.

① 텍스트 → ② 토큰 : "렉싱(Lexing)"

컴퓨터에게 a + a * a는 처음엔 공백 포함 9글자일 뿐이에요.
첫 단계는 이걸 의미 있는 최소 단위(토큰) 로 쪼개는 겁니다.

  • a → "이름(식별자)" 토큰
  • + → "더하기 연산자" 토큰
  • * → "곱하기 연산자" 토큰
  • 공백 → 버림

이 일을 하는 게 렉서(lexer) 또는 토크나이저(tokenizer) 예요.

② 토큰 → ③ 트리 : "파싱(Parsing)"

이제 토큰들이 문법에 맞게 배열됐는지 확인하고, 그 구조를 트리로 만듭니다.
예를 들어 a + a * a에서 곱하기가 더하기보다 먼저 묶여야 한다는 것(우선순위)도 이 트리 모양으로 드러납니다.

a + a * a   →   a + (a * a)      ← '*'가 더 깊이(먼저) 묶임

이 일을 하는 게 파서(parser) 입니다.
그리고 Janglim이 집중하는 부분이 바로 여기예요.

③ 트리 → 그 다음

파스 트리가 나오면, 그 뒤로는 목적에 따라 갈립니다.
계산기라면 트리를 따라 값을 계산하고, 컴파일러라면 의미를 분석하고 기계어/LLVM IR로 번역합니다.
Janglim이 dogfooding(자기 검증) 용으로 만든 AJ 언어는 여기까지 갑니다.

LR 파서의 숨은 0단계: "테이블 미리 만들기"

위 그림에는 사실 숨은 단계가 하나 더 있어요.
파서는 토큰을 받기 전에, 문법을 분석해서 파싱 테이블(parse table) 이라는 거대한 표를 미리 계산합니다.

이 표는 "지금 이런 상태이고 다음 토큰이 이거라면 → 이렇게 행동하라"를 전부 적어둔 행동 지침서예요.
파싱할 때 파서는 생각하지 않고 이 표만 보고 기계적으로 움직입니다.
그래서 LR 파싱은 빠르고 정확해요.

💡 그래서 LR 파서를 "결정적(deterministic) 파서"라고 불러요. 표의 각 칸에는 행동이 딱 하나로 정해져 있어요. 그래서 파서는 매 순간 갈림길에서 고민하거나 되돌아가지(backtrack) 않고 한 길로만 갑니다. 이렇게 다음 행동이 늘 유일하게 정해지는 파서를 결정적 파서라고 하고, LR이 그 대표예요. (문법에 충돌이 있거나, 여러 갈래를 탐색하는 GLR/LGLR 방식을 쓰면 결정적이 아니게 되는데 — 그건 뒤의 충돌 장에서 다뤄요.)

문법  ──(미리 분석)──▶  파싱 테이블  ──(파싱 때 참고)──▶  결정(shift? reduce?)

이 표를 만들려면 FIRST/FOLLOW, LR 아이템, 정준 집합 같은 개념이 필요합니다.
이 표를 만드는 여정이 곧 매뉴얼의 본론이에요.
우리는 FIRST/FOLLOW부터 시작합니다.

코드의 층(layer) — 살짝만

Janglim 내부는 여러 모듈이 층층이 쌓여 있습니다.
아래로 갈수록 더 기초적인 부품이에요.

  ┌─────────────────────────────────────────────┐
  │  AJ 언어 → 의미분석 → LLVM IR (컴파일러)        │  ← 윗단 (응용)
  ├─────────────────────────────────────────────┤
  │  파서 엔진: 정준 집합 · 파싱 테이블 · 드라이버    │
  ├─────────────────────────────────────────────┤
  │  문법(Grammar) 컨테이너                         │
  ├─────────────────────────────────────────────┤
  │  심볼 · 렉서 · FIRST/FOLLOW · 정규화 · 파스트리  │  ← 핵심 부품 모음
  ├─────────────────────────────────────────────┤
  │  토큰 타입 · 공통 헬퍼                          │  ← 밑단 (기초)
  └─────────────────────────────────────────────┘

재밌는 점: FIRST/FOLLOW가 밑단 근처 에 있죠? 코드 구조상으론 아주 기초 부품이에요. 하지만 개념을 배우는 순서로는 파싱 테이블 직전에 배우는 게 가장 잘 이해됩니다(왜 필요한지가 그때 와닿거든요). 그래서 이 매뉴얼은 코드 층 순서가 아니라 이해 순서로 갑니다. 각 페이지마다 "이 개념은 어느 층/파일"인지는 따로 표시해 둘게요.

전체 모듈 층 지도는 나중에 부록 에서 따로 정리할 거예요.

다음 장

이제 지도를 손에 넣었으니, LR 파싱의 첫 핵심 개념으로 들어갑시다.

👉 FIRST / FOLLOW

Edit this page