Tree-sitter & 증분 파싱 Deep Dive — GLR, 증분 재파싱, CST, Queries, Syntax Highlighting 완전 정복 (2025)

TL;DR

• Tree-sitter는 Max Brunsfeld가 2018년 GitHub에서 시작한 파서 생성기 + 런타임. Atom 에디터의 대체 구문 하이라이팅을 위해.
• GLR 파서: Generalized LR. 모호한 grammar도 처리. 전통 LR/LALR보다 자연스러운 grammar 작성 가능.
• 증분 재파싱: 편집 시 변경된 부분만 재파싱. 10,000 줄 파일에 한 글자 입력해도 1ms. 이것이 핵심 혁신.
• Concrete Syntax Tree (CST): AST가 아닌 모든 토큰을 포함한 트리 — 공백, 주석, 심지어 에러 노드. 에디터가 필요한 것이 바로 이것.
• 에러 복구: 문법 오류가 있어도 parser가 계속 작동. 코드 편집 중에 항상 의미 있는 트리 제공.
• Queries: S-expression 기반 패턴 매칭 언어. "모든 함수 이름 찾아", "모든 메서드 호출 찾아" 같은 쿼리를 선언적으로.
• 적용: Neovim (nvim-treesitter), Helix, Zed, GitHub 코드 검색, Emacs tree-sitter mode, Obsidian.
• 수백 개의 language grammar: Python, JS, Rust, Go, C++, 심지어 Regex, JSON, Bash까지.

1. 파서의 오래된 문제

1.1 왜 파싱이 어려운가

텍스트를 트리로 변환. 간단해 보이지만:

1. 문법이 복잡: 현대 언어의 문법은 수백 규칙.
2. 모호성: x - y - z가 (x-y)-z인가 x-(y-z)인가?
3. 에러 복구: 사용자가 타이핑 중 항상 완성된 코드가 아님.
4. 성능: 편집마다 즉시 반영 필요.
5. 다국어: 한 에디터가 수십 언어.

1.2 전통적 접근들

정규식: 빠르지만 context-free 언어를 파싱 못함. TextMate grammar가 대표적.

Hand-written recursive descent: 유연하고 빠름. 하지만 언어마다 따로 작성. 유지보수 비용 높음.

Parser generators (yacc/bison): LALR 기반. 빠르지만 모호성 불허, grammar 작성 불편.

PEG parsers: 모호성 처리 (choice 우선순위). 하지만 전체 재파싱 필요, 증분 불가.

1.3 Tree-sitter 이전의 에디터

Atom, VS Code (원래): TextMate grammar + 정규식. 빠르지만:

• Context 이해 불가.
• Nested 구조 잘못 하이라이트.
• 에러 있으면 깨짐.
• Semantic 정보 없음.

JetBrains IDE: 자체 hand-written parser per language. 품질 좋지만:

• 각 언어에 전담 팀 필요.
• 느린 언어 추가.

중간이 필요했다: 정규식처럼 빠르고, IDE처럼 정확한 파서.

1.4 Max Brunsfeld와 Tree-sitter

2018년 GitHub에서 Atom 팀의 Max Brunsfeld가 시작. 목표:

1. 증분 파싱: 편집 시 즉시 반영.
2. 언어 독립: Grammar 언어로 새 언어 추가 쉽게.
3. 에러 내성: 깨진 코드도 부분적으로 파싱.
4. 에디터 특화: 구문 하이라이팅, folding, 인덴테이션을 위한 API.

결과: Tree-sitter. 이후 Atom은 죽었지만 Tree-sitter는 Neovim, Helix, Zed, GitHub 전반에서 사용.

2. GLR 파서

2.1 LR의 한계

LR(k) 파서: left-to-right, rightmost derivation, k tokens lookahead.

yacc, bison, ANTLR이 생성. 빠르고 결정론적. 단점: 모호한 grammar 불허.

예: C++의 >>

vector<vector<int>> v;  // <<VS>> 중첩? 또는 shift 연산자?

LR은 이를 처리 못함 → C++ parser가 복잡해짐.

2.2 GLR의 아이디어

Generalized LR (Tomita, 1986). 아이디어: "모호한 지점에서 여러 파서 상태를 동시에 유지".

Parser state 1: <vector<int>> (템플릿)
Parser state 2: >> (shift)

두 가설이 동시에 진행. 한 쪽이 불가능해지면 소거. 결국 한 쪽만 생존.

2.3 성능

LR의 결정론적 파싱은 O(n). GLR은 **worst case O(n^3)**이지만 실제 언어에서는 대부분 O(n) — 모호성이 드물기 때문.

Tree-sitter의 실측: JavaScript, Python 같은 언어도 수 MB/s 파싱 속도.

2.4 DFA + Stack

내부 구현: 각 상태가 DFA. Stack이 여러 개 (GSS — Graph Structured Stack).

Input:  a + b - c
        ↓
DFA state 5 (expression)
  ├─ Stack 1: add_expr
  └─ Stack 2: unary_expr  (- 가 unary일 경우)

GSS는 공통 prefix를 공유 → 메모리 효율.

2.5 Conflict Resolution

모호성이 남으면 grammar에 precedence와 associativity를 명시:

// tree-sitter grammar.js
rules: {
    expression: $ => choice(
        $.binary_expression,
        $.unary_expression,
    ),
    binary_expression: $ => prec.left(1, seq($.expression, '+', $.expression)),
}

prec.left(1, ...)는 "이 규칙은 left-associative, precedence 1".

3. 증분 재파싱

Tree-sitter의 가장 혁신적 기능.

3.1 문제

사용자가 편집하면 다시 파싱해야 한다. 10,000줄 파일 + 한 글자 편집 = 10,000줄 재파싱?

Vim/Emacs 구 syntax는 그냥 전체 재파싱 또는 정규식 기반 빠른 재검사. 품질 vs 속도의 트레이드오프.

3.2 Tree-sitter의 해결

편집된 범위와 주변만 재파싱. 핵심 알고리즘:

1. 편집 정보: {start_byte, old_end_byte, new_end_byte}.
2. 옛 트리의 해당 범위 노드를 무효화.
3. 변경 지점부터 재파싱 시작.
4. 파서가 옛 트리의 노드를 재사용하려 시도:
   • 영향 안 받은 부분은 그대로.
   • 영향 받은 부분만 새로 계산.
5. 새 트리 반환.

TSTree *new_tree = ts_parser_parse(parser, old_tree, input);

old_tree가 있으면 증분, 없으면 전체 파싱.

3.3 효과

10,000 줄 Python 파일, 중간에 한 글자:

• Full reparse: ~30 ms.
• Incremental: ~1 ms (30배 빠름).

1 ms는 사용자가 못 느끼는 속도. 에디터가 "실시간"처럼.

3.4 왜 이게 가능한가

편집이 지역적이기 때문. 대부분 편집은:

• 한 함수 안에서.
• 한 expression 안에서.
• 한 토큰 안에서.

파싱 트리의 대부분은 변경되지 않음. Tree-sitter가 이 불변성을 활용.

3.5 구현 상세

각 노드에 편집 후에도 유효한지 표시. 유효하면 재사용, 그렇지 않으면 재파싱.

위치 업데이트: 편집 후 각 노드의 byte offset이 바뀔 수 있다. Tree-sitter는 이를 lazy하게 계산.

경계 케이스: 편집이 토큰 경계를 넘나들면 주변까지 재파싱.

3.6 API 사용

const parser = new Parser();
parser.setLanguage(JavaScript);

let sourceCode = 'let x = 5;';
let tree = parser.parse(sourceCode);

// 편집: let x = 5; → let y = 5;
sourceCode = 'let y = 5;';

// 편집 정보 제공
tree.edit({
    startIndex: 4,        // 'x' 위치
    oldEndIndex: 5,
    newEndIndex: 5,
    startPosition: { row: 0, column: 4 },
    oldEndPosition: { row: 0, column: 5 },
    newEndPosition: { row: 0, column: 5 }
});

// 증분 재파싱
const newTree = parser.parse(sourceCode, tree);

4. Concrete Syntax Tree (CST)

4.1 AST vs CST

AST (Abstract Syntax Tree): 의미 있는 노드만.

let x = 5;
→ Variable(name: "x", value: Number(5))

• 공백, 세미콜론 제거.
• 컴파일러에 필요한 최소 정보.
• 원본 코드 복원 불가.

CST (Concrete Syntax Tree): 모든 토큰 포함.

let x = 5;
→ Program
  └─ LexicalDeclaration
      ├─ 'let'
      ├─ VariableDeclarator
      │   ├─ 'x'
      │   ├─ '='
      │   └─ NumericLiteral: '5'
      └─ ';'

• 모든 공백/주석 위치 기록.
• 트리에서 원본 복원 가능.
• 에디터에 필요.

4.2 Tree-sitter는 CST

이유: 에디터는 모든 문자를 표시해야 한다. 공백, 주석, 연산자 기호 — 전부 syntax highlighting 대상.

Compiler의 AST와 에디터의 CST는 다른 목적. Tree-sitter는 에디터 중심.

4.3 Anonymous Nodes

CST에는 익명 노드도 많음:

'let' (anonymous: keyword token)
'=' (anonymous: operator token)
';' (anonymous: punctuation)

Grammar에서 이름 붙이지 않으면 자동 익명. 하이라이팅에 사용.

4.4 Named Nodes

주요 구조는 명명된 노드:

function_declaration
  identifier (함수 이름)
  formal_parameters
  statement_block

Tree-sitter API로 쉽게 접근:

const funcs = tree.rootNode.descendantsOfType('function_declaration');
funcs.forEach(f => {
    const name = f.childForFieldName('name').text;
    console.log(name);
});

4.5 Field Names

명명된 자식에 field name 부여 가능:

// grammar.js
function_declaration: $ => seq(
    'function',
    field('name', $.identifier),
    field('parameters', $.formal_parameters),
    field('body', $.statement_block),
),

코드에서:

funcNode.childForFieldName('name')
funcNode.childForFieldName('body')

인덱스 대신 이름으로 접근 → 더 명확.

5. 에러 복구

5.1 왜 중요한가

사용자가 타이핑 중엔 항상 완성된 코드가 아님:

def foo(
    x, y
# 아직 닫는 괄호 없음

전통 파서는 여기서 중단. Syntax highlighting이 완전히 깨짐.

5.2 Tree-sitter의 에러 복구

"깨진" 코드도 계속 파싱. 복구 전략:

1. ERROR 노드: 파싱 실패 범위를 ERROR 노드로 감싸고 계속.
2. MISSING 노드: 필요한 토큰이 없으면 가상 노드 삽입.
3. Skipping: 이해 불가 토큰 건너뛰기.

5.3 예시

def foo(x, y  # 괄호 안 닫힘
    return x + y

Tree-sitter 트리:

function_definition
  'def'
  identifier: 'foo'
  parameters
    '('
    identifier: 'x'
    ','
    identifier: 'y'
    MISSING ')'   ← 가상 노드
  ':'
  block
    return_statement
      ...

파싱이 계속 — 함수 이름, 파라미터, body 모두 인식. MISSING ')'로 에러 표시.

5.4 에디터에 주는 이점

편집 중 매 순간 유효한 트리. Syntax highlighting, indentation, folding이 깨지지 않음.

이것이 사용자 경험의 핵심 — 에러 나자마자 전체 화면이 흑백이 되는 끔찍함을 방지.

5.5 구현

에러 복구는 heuristic. Tree-sitter의 접근:

• 최소 거리 복구: 가능한 최소한의 삽입/삭제로 유효한 트리.
• Beam search: 여러 복구 후보 중 가장 좋은 것.

이것이 Tree-sitter grammar 작성이 단순히 "BNF 적기"보다 어려운 이유 — 에러 복구 동작도 테스트해야.

6. Grammar 정의

6.1 grammar.js

Tree-sitter grammar는 JavaScript 파일:

// grammar.js for a simple language
module.exports = grammar({
    name: 'my_lang',

    rules: {
        source_file: $ => repeat($._statement),

        _statement: $ => choice(
            $.function_declaration,
            $.expression_statement,
        ),

        function_declaration: $ => seq(
            'fn',
            field('name', $.identifier),
            field('parameters', $.parameter_list),
            field('body', $.block),
        ),

        parameter_list: $ => seq(
            '(',
            optional(seq($.identifier, repeat(seq(',', $.identifier)))),
            ')',
        ),

        block: $ => seq(
            '{',
            repeat($._statement),
            '}',
        ),

        expression_statement: $ => seq($._expression, ';'),

        _expression: $ => choice(
            $.binary_expression,
            $.identifier,
            $.number,
        ),

        binary_expression: $ => prec.left(1, seq(
            $._expression,
            choice('+', '-', '*', '/'),
            $._expression,
        )),

        identifier: $ => /[a-zA-Z_][a-zA-Z0-9_]*/,
        number: $ => /\d+/,
    },
});

6.2 주요 연산자

• seq(a, b, c): 순차 매칭.
• choice(a, b, c): 대안 매칭.
• repeat(a): 0번 이상 반복.
• repeat1(a): 1번 이상 반복.
• optional(a): 있어도 되고 없어도 됨.
• prec(n, rule): 우선순위.
• prec.left(n, rule): 좌결합 우선순위.
• prec.right(n, rule): 우결합 우선순위.
• field('name', rule): 필드 이름.

6.3 Regular Expressions

토큰 레벨에 정규식 사용:

identifier: $ => /[a-zA-Z_][a-zA-Z0-9_]*/,

주의: 정규식은 너무 복잡하면 안 됨. Tree-sitter가 DFA로 변환.

6.4 External Scanner

Grammar로 표현 어려운 경우 (e.g., Python indentation): C로 작성한 scanner:

// src/scanner.c
enum TokenType {
    INDENT,
    DEDENT,
};

void *tree_sitter_python_external_scanner_create() { ... }
bool tree_sitter_python_external_scanner_scan(...) { ... }

Python의 indent 규칙처럼 context-sensitive 결정이 필요할 때.

6.5 컴파일

tree-sitter generate

grammar.js → C 파서. 최적화된 DFA table을 생성.

tree-sitter test

테스트 실행. test/corpus/ 디렉토리의 예제 코드로.

7. Query — S-expression 기반

7.1 왜 Query인가

"트리를 순회하며 특정 패턴 찾기"는 매우 흔한 작업. Tree-sitter는 선언적 쿼리 언어를 제공.

7.2 기본 문법

(function_declaration
  name: (identifier) @function.name)

@function.name: capture. 매칭된 노드에 이 이름을 붙임.

실행 결과:

Match 1: @function.name = "foo"
Match 2: @function.name = "bar"

7.3 Predicates

조건 추가:

(identifier) @var
(#match? @var "^[A-Z]")

대문자로 시작하는 identifier만.

7.4 Alternation

(method_declaration
  name: (identifier) @method
  (#any-of? @method "init" "main"))

여러 값 중 하나.

7.5 Complex Patterns

(class_declaration
  name: (identifier) @class
  body: (class_body
    (method_definition
      name: (property_identifier) @method)))

"class 안의 method 찾기". 중첩 구조도 자연스럽게.

7.6 Application

Syntax highlighting:

(function_declaration name: (identifier) @function)
(identifier) @variable
(string) @string
(comment) @comment

각 capture가 하이라이트 이름. 에디터가 테마의 해당 색상 적용.

Code folding:

[
  (function_declaration)
  (class_declaration)
  (if_statement)
] @fold

이 노드들은 접을 수 있다.

Indentation:

(function_declaration body: (_) @indent)

이 body는 indent 증가.

Code navigation (Go to definition):

(function_declaration name: (_) @definition.function)
(call_expression function: (_) @reference.call)

8. Syntax Highlighting

8.1 Highlight Queries

queries/highlights.scm 파일에 tree-sitter query:

; Keywords
"fn" @keyword
"if" @keyword
"else" @keyword
"return" @keyword

; Functions
(function_declaration name: (identifier) @function)
(call_expression function: (identifier) @function.call)

; Variables
(parameter name: (identifier) @variable.parameter)
(let_declaration pattern: (identifier) @variable)

; Literals
(string_literal) @string
(number_literal) @number
(boolean_literal) @boolean

; Comments
(comment) @comment

; Operators
["+" "-" "*" "/"] @operator

8.2 Highlight Group

@keyword, @function, @variable 같은 이름이 highlight group. 에디터가 각 group에 색상 매핑.

표준 group (Neovim 기준):

• @variable, @variable.parameter, @variable.builtin.
• @function, @function.call, @function.builtin.
• @type, @type.builtin.
• @keyword, @keyword.operator, @keyword.return.
• @string, @string.escape.
• @number, @boolean.
• @comment, @comment.todo.
• @operator, @punctuation.bracket.

8.3 에디터 통합

Neovim (nvim-treesitter):

require'nvim-treesitter.configs'.setup {
    ensure_installed = {"python", "rust", "javascript"},
    highlight = { enable = true },
    indent = { enable = true },
}

Helix: 기본 내장. tree-sitter-<lang> 자동 로드.

Zed: 기본 내장. Tree-sitter가 전체 syntax highlighting 담당.

Emacs (Emacs 29+): treesit 내장 모드.

8.4 정규식 vs Tree-sitter

TextMate grammar:

match: "\\bfunction\\s+([a-zA-Z_]+)"
capture 1: entity.name.function

"function 뒤의 이름이 function name". 정규식 기반. 잘 동작하지만:

let fn = function() {};  // function은 키워드지만 선언 아님

→ TextMate는 혼동. Tree-sitter는 문법 구조를 알아서 정확히 분류.

8.5 성능

놀라운 점: Tree-sitter 정규식보다 느리지 않다. 증분 재파싱 덕분에 실질적 오버헤드가 거의 없음.

그리고 더 정확한 하이라이팅. Trade-off가 거의 없음.

9. 에디터별 구현

9.1 Neovim

nvim-treesitter: 가장 성숙한 구현. 수백 언어 지원.

기능:

• Syntax highlighting.
• Indentation (indent queries).
• Text objects (function, class를 텍스트 객체로).
• Incremental selection.
• Folding.

플러그인 생태계:

• nvim-treesitter-textobjects: 함수/클래스 선택.
• nvim-treesitter-refactor: 변수 이름 변경, 정의로 이동.
• nvim-ts-autotag: HTML 태그 자동 닫기.

9.2 Helix

Tree-sitter가 기본 내장. 설치 시 모든 지원 언어가 자동.

# languages.toml
[[language]]
name = "rust"
scope = "source.rust"
injection-regex = "rust"

매우 단순한 설정. 기본값이 합리적.

9.3 Zed

Rust + GPU 렌더링 에디터. Tree-sitter가 핵심:

• 실시간 하이라이팅.
• 사용자 정의 theme.
• Multi-buffer 검색.

9.4 Emacs

Emacs 29부터 tree-sitter 내장. 오래된 font-lock 대체.

(use-package treesit
  :config
  (setq major-mode-remap-alist
    '((python-mode . python-ts-mode)
      (javascript-mode . javascript-ts-mode))))

*-ts-mode가 tree-sitter 버전.

9.5 VS Code?

VS Code는 TextMate grammar를 여전히 사용. Tree-sitter를 공식 도입하지 않음.

이유:

• 기존 인프라 크기.
• Monaco editor 재작성 필요.
• LSP가 대부분 semantic 기능 담당.

하지만 일부 extension이 tree-sitter 사용.

10. GitHub 검색

10.1 Code Search 재설계

2022년 GitHub가 Code Search를 재구축 — 기존 Elasticsearch에서 새 엔진으로.

핵심: tree-sitter로 모든 public 코드를 파싱해서 semantic search.

10.2 Semantic Index

단순 텍스트 검색이 아니라:

• 함수 정의.
• 클래스 이름.
• Type 참조.
• Import 구문.

Tree-sitter로 파싱 → symbol 추출 → 역 인덱스.

search: "def parse_args"
→ 모든 언어에서 "parse_args 함수 정의" 반환

전통 grep은 "def parse_args"라는 텍스트만 찾지만, GitHub는 함수 정의로 인식.

10.3 스케일

수억 개의 repository × 수십억 줄의 코드를 tree-sitter로 파싱. 파싱 결과를 분산 검색 인덱스에.

Tree-sitter의 성능 덕분에 이것이 가능. 다른 파서 대부분은 이 스케일에서 너무 느림.

10.4 LLM과의 결합

2023+ GitHub Copilot, Chat이 tree-sitter 정보를 컨텍스트로 사용. "이 함수를 수정해줘" 같은 요청에 tree-sitter가 함수 경계를 정확히 전달.

11. LSP와의 관계

11.1 역할 분담

Tree-sitter:

• 빠른 파싱.
• Syntax 트리 제공.
• 하이라이팅, folding, indentation.
• Context-free (파일 단위).

LSP:

• Semantic 분석 (타입, 의미).
• Cross-file reference.
• Refactoring (rename).
• Diagnostics.

11.2 함께 사용

현대 에디터:

• Tree-sitter가 즉시 하이라이팅 (파싱 즉시).
• LSP가 천천히 semantic 정보 제공 (타입 추론 이후).

둘이 독립적으로 작동. Tree-sitter가 "syntactic layer", LSP가 "semantic layer".

11.3 보완 관계

LSP 없는 언어: Tree-sitter가 훌륭한 fallback. 기본 navigation, 하이라이팅 제공.

Tree-sitter 없는 경우: 정규식 하이라이팅 + LSP semantic tokens. 품질 낮음.

둘 다 있으면 최상.

12. 성능

12.1 파싱 속도

Tree-sitter 공식 벤치마크:

• JavaScript: ~30 MB/s.
• Python: ~20 MB/s.
• Rust: ~15 MB/s (복잡한 문법).

10,000 줄 파일(~500 KB) 파싱: ~20 ms (초기), ~1 ms (증분).

12.2 메모리

트리 노드당 ~40 바이트. 10,000 줄 파일 = ~2 MB 트리. 현대 컴퓨터에 무시 가능.

12.3 시작 시간

Parser (.so 파일) 로드: ~1 ms per language. 수십 언어 모두 로드해도 100 ms 미만.

12.4 비교

TextMate (정규식): 매우 빠름 (스캔만), 하지만 대용량 파일에서 선형 비용.

PEG (Parsimonious 등): Tree-sitter와 유사 속도, 하지만 증분 없음.

ANTLR: 빠르지만 자바/플랫폼 의존, 증분 약함.

LALR yacc/bison: 매우 빠름, 하지만 에러 복구 어려움, grammar 제약.

Tree-sitter는 "속도 + 증분 + 에러 복구"라는 조합이 독특.

13. 커스텀 Grammar 작성

13.1 예: 간단한 DSL

// grammar.js
module.exports = grammar({
    name: 'configlang',

    rules: {
        source_file: $ => repeat($.statement),

        statement: $ => choice(
            $.assignment,
            $.comment,
        ),

        assignment: $ => seq(
            field('name', $.identifier),
            '=',
            field('value', $._value),
        ),

        _value: $ => choice(
            $.string,
            $.number,
            $.boolean,
        ),

        string: $ => /"[^"]*"/,
        number: $ => /\d+(\.\d+)?/,
        boolean: $ => choice('true', 'false'),
        identifier: $ => /[a-zA-Z_][a-zA-Z0-9_]*/,
        comment: $ => seq('#', /.*/),
    },
});

13.2 개발 워크플로우

tree-sitter init              # grammar 프로젝트 시작
# grammar.js 작성
tree-sitter generate          # C 파서 생성
tree-sitter test              # 테스트
tree-sitter parse example.cfg # 실제 파싱

13.3 테스트

// test/corpus/basic.txt
==================
simple assignment
==================
x = 10

---

(source_file
  (assignment
    name: (identifier)
    value: (number)))

Input → expected tree. Tree-sitter가 자동 검증.

13.4 문서화

tree-sitter highlight example.cfg

하이라이팅 결과를 터미널로 보여줌. 색상 확인.

tree-sitter playground

웹 기반 playground. Browser에서 실시간 파싱.

13.5 배포

Grammar를 GitHub에 공개 → 에디터가 tree-sitter-<language> 이름으로 자동 인식.

14. Tree-sitter를 쓰는 창의적 프로젝트

14.1 ast-grep

Grep의 semantic 버전. 정규식 대신 AST 패턴으로 검색.

ast-grep --pattern 'if (!$VAR) throw $$$' --lang js

"null check 없이 throw하는 패턴" 같은 복잡한 검색 가능.

14.2 Semgrep / Comby

유사한 도구들. Tree-sitter 또는 자체 파서로 structural search.

보안 스캐닝, 코드 리팩토링에 활용.

14.3 difftastic

구조 기반 diff. Tree-sitter로 파싱 후 tree diff. 단순 line diff보다 정확.

difft old.py new.py

함수 이름 변경, 코드 이동이 정확히 표현됨.

14.4 GitHub Copilot Chat

내부적으로 tree-sitter로 "현재 함수", "현재 클래스"를 감지해 LLM 컨텍스트로.

14.5 Zed AI

Zed 에디터의 AI 통합. 편집 중인 코드의 tree-sitter 컨텍스트를 LLM에 보냄.

14.6 JetBrains AI (실험)

Tree-sitter로 일부 언어를 파싱 (기존 JetBrains 파서 보완). 특히 minor 언어.

15. 한계와 함정

15.1 Grammar 작성의 어려움

"Grammar를 쓰면 끝"이 아니다:

• 에러 복구 동작 튜닝.
• Precedence 충돌 해결.
• 성능 최적화.
• Edge case 테스트.

각 언어의 tree-sitter grammar 저장소를 보면 수천 개 테스트가 있음.

15.2 정확성 vs 속도

Tree-sitter는 "에디터에 충분한 정확성"을 목표로. Compiler 수준의 정확한 파서보다는 부정확할 수 있다.

예: Python 3.12의 match statement — tree-sitter-python이 처음 나올 때 잘 지원 안 했음.

15.3 Language Evolution

언어 문법이 바뀌면 grammar 업데이트 필요. 보통 언어 커뮤니티가 관리하지만 지연 가능.

15.4 제약된 grammar

GLR이 많은 걸 수용하지만 극도로 context-sensitive한 언어는 어려움. C++ 같은 경우 여전히 hand-written parser만큼 정확하지 못할 수 있음.

15.5 메모리 (대용량)

수 MB 파일을 tree-sitter로 파싱하면 트리가 수백 MB. 에디터는 보통 파일 크기 제한을 둠.

16. 학습 리소스

공식:

• https://tree-sitter.github.io/tree-sitter/ — 공식 문서.
• GitHub tree-sitter/tree-sitter 레포.

논문:

• Masaru Tomita, "Efficient Parsing for Natural Language" (1986) — GLR 원저.
• Max Brunsfeld의 Strange Loop 2018 발표 — Tree-sitter 소개.

튜토리얼:

• "Creating Parsers" (공식 guide).
• Tree-sitter playground (https://tree-sitter.github.io/tree-sitter/playground).

소스 코드:

• tree-sitter-javascript, tree-sitter-python, tree-sitter-rust 등.
• 다른 언어 grammar를 보며 배우기.

블로그:

• Max Brunsfeld의 GitHub 블로그.
• Helix, Neovim 개발자들의 글.

17. 요약 — 한 장 정리

┌─────────────────────────────────────────────────────┐
│             Tree-sitter Cheat Sheet                  │
├─────────────────────────────────────────────────────┤
│ 핵심:                                                  │
│   증분 파싱 (incremental)                             │
│   GLR 파서 (모호성 처리)                              │
│   에러 복구 (깨진 코드도 파싱)                         │
│   CST (모든 토큰 포함)                                │
│                                                       │
│ GLR:                                                  │
│   모호한 grammar 허용                                  │
│   여러 파서 상태 동시 유지                             │
│   대부분 언어 O(n), worst O(n^3)                     │
│   Graph Structured Stack                             │
│                                                       │
│ 증분 재파싱:                                           │
│   편집 정보: start, old_end, new_end                 │
│   영향 없는 노드 재사용                                │
│   10K 줄 파일, 1 char 편집: ~1 ms                    │
│   30배 이상 빠름                                      │
│                                                       │
│ CST vs AST:                                           │
│   CST: 모든 토큰, 에디터용                             │
│   AST: 의미 노드만, 컴파일러용                         │
│   Tree-sitter는 CST                                  │
│                                                       │
│ 에러 복구:                                             │
│   ERROR 노드                                          │
│   MISSING 노드                                        │
│   Heuristic 복구                                     │
│   편집 중 항상 유효한 트리                             │
│                                                       │
│ Grammar 정의:                                         │
│   grammar.js (JavaScript)                            │
│   seq, choice, repeat, optional                      │
│   prec, prec.left, prec.right                        │
│   field('name', rule)                                │
│   external scanner (C)                               │
│                                                       │
│ Query (S-expression):                                 │
│   (function_declaration                              │
│     name: (identifier) @func)                        │
│   #match?, #any-of? predicates                       │
│   Highlighting, folding, indentation                 │
│                                                       │
│ 적용:                                                  │
│   Syntax highlighting                                │
│   Folding                                            │
│   Indentation                                        │
│   Text objects                                       │
│   Navigation                                         │
│   Refactoring                                        │
│                                                       │
│ 에디터:                                                │
│   Neovim (nvim-treesitter)                           │
│   Helix (내장)                                        │
│   Zed (내장)                                          │
│   Emacs 29+ (treesit)                                │
│                                                       │
│ 기타 사용자:                                           │
│   GitHub Code Search                                 │
│   ast-grep, difftastic                               │
│   Semgrep, Comby                                     │
│   Copilot Chat                                       │
│                                                       │
│ LSP와 역할:                                            │
│   Tree-sitter: 즉각 syntax (파일 단위)                │
│   LSP: semantic (cross-file, 타입)                   │
│   둘이 보완                                            │
└─────────────────────────────────────────────────────┘

18. 퀴즈

이 글이 도움이 됐다면 다음 포스트도 확인해 보세요:

• "Language Server Protocol Deep Dive" — LSP가 tree-sitter와 어떻게 함께 쓰이는지.
• "LLVM Compiler Infrastructure" — 완전한 컴파일러 파이프라인.
• "Git Internals Deep Dive" — GitHub의 다른 핵심 기술.
• "Regex Engines Internals" — 정규식의 한계와 tree-sitter의 대안.