Tree-sitter: 인크리멘털 파싱 라이브러리
개념
Tree-sitter는 파서 생성기(parser generator) 이면서 동시에 인크리멘털 파싱 라이브러리다. Max Brunsfeld가 GitHub에서 일하면서 만들었고, 2017~2018년에 공개됐다.
원래 Atom 에디터에서 시작했다. 당시 에디터들은 TextMate 문법 기반의 정규식으로 구문 강조를 했는데, 이건 상태가 없어서(stateless) 중첩 구조나 복잡한 코드에서 자꾸 깨졌다. 그래서 진짜 파싱 기반 접근이 필요했고, 동시에 타이핑 중에도 끊김 없이 돌아야 했다.
GitHub는 2018년부터 tree-sitter를 채택해서 코드 하이라이팅, 심볼 네비게이션, semantic diff 등에 쓰고 있다.
CST vs AST
Tree-sitter는 AST가 아니라 CST(Concrete Syntax Tree) 를 만든다.
- AST: 컴파일러용. 괄호, 콤마, 공백 같은 구조 토큰을 날린다. 실행 의미에만 집중.
- CST: 에디터용. 모든 토큰의 정확한 위치를 유지한다. 공백이나 주석도 트리에 남는다.
에디터는 "이 심볼이 소스 파일의 몇 번째 줄 몇 번째 컬럼에 있는지"를 알아야 하기 때문에 CST가 필요하다. AST로는 이게 안 된다.
인크리멘털 파싱
기존 방식은 키 입력 → 파일 전체 재파싱. 파일이 크면 버벅인다.
Tree-sitter 방식:
- 이전 파싱 결과(구문 트리)를 유지한다
- 텍스트가 바뀌면
ts_tree_edit()으로 트리 메타데이터만 수정 ts_subtree_get_changed_ranges()로 실제로 다시 파싱해야 할 영역을 찾는다- 바뀌지 않은 서브트리는 그대로 재사용(
ReusableNode) - 새 트리를 구성할 때 재사용 가능한 노드는 갖다 붙인다
결과적으로 작은 수정 후 재파싱은 파일 크기에 관계없이 수 밀리초 수준이다.
파싱 알고리즘: GLR
기반은 LR 파싱이다. 소스를 왼쪽에서 오른쪽으로 읽으면서, 파스 테이블(2D 배열)을 참조해서 토큰들을 트리 노드로 묶는다.
LR의 문제는 문법이 모호할 때(shift-reduce conflict, reduce-reduce conflict) 실패한다는 것. Tree-sitter는 GLR(Generalized LR) 을 써서 이걸 해결한다.
GLR은 충돌이 생기면 파스 스택을 여러 개로 분기한다. 여러 해석을 동시에 탐색하다가, 불가능한 경로를 제거하는 식이다. 최대 6개 버전을 동시에 유지하고, 에러 비용이 낮은 걸 선택한다.
에러 복구
에디터에서 코드는 항상 반만 쓰여진 상태다. 완성된 코드를 가정하는 파서는 쓸 수 없다.
Tree-sitter는 파싱 실패 시:
- 유효하지 않은 구간을
ERROR노드로 감싼다 - 필수 토큰이 없으면
MISSING노드를 삽입한다 - 여러 복구 경로를 GLR로 병렬 탐색해서 가장 나은 것을 고른다
덕분에 문법 오류가 있어도 트리가 만들어지고, 에디터 기능이 계속 동작한다.
문법 작성: grammar.js
Tree-sitter 문법은 JavaScript로 작성한다. tree-sitter generate로 C 파서를 생성한다.
module.exports = grammar({
name: "my_language",
rules: {
// 첫 번째 규칙이 시작 심볼
source_file: $ => repeat($.statement),
statement: $ => choice(
$.assignment,
$.expression_statement,
),
assignment: $ => seq(
field('name', $.identifier),
'=',
field('value', $.expression),
),
// 우선순위로 연산자 결합 방향 지정
expression: $ => choice(
prec.left(1, seq($.expression, '+', $.expression)),
prec.left(2, seq($.expression, '*', $.expression)),
seq('(', $.expression, ')'),
$.number,
),
}
});
주요 함수:
| 함수 | 역할 |
|---|---|
seq(a, b, c) |
순서대로 매칭 |
choice(a, b) |
하나 선택 |
repeat(rule) |
0회 이상 |
optional(rule) |
0~1회 |
prec.left(n, rule) |
좌결합 우선순위 n |
prec.right(n, rule) |
우결합 우선순위 n |
field('name', rule) |
자식 노드에 이름 부여 |
token(rule) |
명시적 터미널 토큰 |
언더스코어로 시작하는 규칙(_expression)은 트리에서 숨겨진다. 파싱엔 쓰이지만 노이즈를 줄이고 싶을 때 유용하다.
쿼리 문법
트리에서 패턴을 찾을 때 S-expression 기반 쿼리를 쓴다.
; 기본 패턴
(binary_expression (number_literal) (number_literal))
; 캡처 (@name으로 노드에 이름 붙이기)
(function_definition
name: (identifier) @function.name) @definition.function
; 리터럴 토큰 매칭
(binary_expression operator: "!=")
; 대안 (alternation)
[ "if" "while" "for" ] @keyword
[ "+" "-" "*" ] @operator
; 개수 한정자
(decorator)* @decorators
(comment)+ @comments
(string)? @optional_str
; 텍스트 조건
((identifier) @var
(#eq? @var "foo"))
((identifier) @name
(#match? @name "^[A-Z]"))
앵커(.): 인접 관계를 강제한다.
; 첫 번째 자식만
(. (identifier) @first)
; 마지막 자식만
(identifier) @last .)
; 바로 옆에 붙어있는 형제 노드만
((identifier) @a . (identifier) @b)
쿼리는 효율적인 상태 머신으로 컴파일되어 트리를 한 번만 순회한다.
실제 사용처
Neovim: nvim-treesitter 플러그인이 구문 강조, 코드 폴딩, 들여쓰기, 언어 중첩(HTML 안의 JS 등)을 tree-sitter로 처리한다. Neovim 0.5부터 코어에 내장.
GitHub: github/semantic 프로젝트에서 semantic diff, 심볼 네비게이션, 코드 하이라이팅에 사용. JavaScript 안에 TypeScript 문법을 C 문법 위에 쌓는 식으로 문법을 조합(compose)할 수 있는 것도 채택 이유 중 하나.
GitHub Copilot: 많은 언어에서 WASM으로 tree-sitter를 호출해 코드 구조를 파악한다.
Zed 에디터: Max Brunsfeld(tree-sitter 만든 사람)가 직접 만든 에디터. 구문 강조, 심볼 아웃라인, Alt+Up/Down으로 구문 노드 단위 선택 확장, 자동 들여쓰기 등 전부 tree-sitter 기반.
다른 파서와 비교
vs TextMate 문법(정규식): 상태가 없어서 중첩 구조를 처리 못한다. Tree-sitter는 이 한계를 극복하려고 만들어졌다.
vs ANTLR: ANTLR은 LL(*) 알고리즘 기반으로 컴파일러 제작에 적합하다. Tree-sitter는 GLR 기반으로 에디터에 더 맞다. ANTLR은 Java/Python 런타임이 필요하고, tree-sitter는 순수 C11이라 어디든 임베드하기 쉽다.
vs PEG (pest, peg.js): PEG는 결정론적이고 모호성이 없지만, 에러 복구가 사실상 없다. Tree-sitter는 GLR 덕분에 에러 복구가 핵심 기능이다.
vs Yacc/Bison: 둘 다 LR 기반이지만, Yacc/Bison은 컴파일러용이라 에러 입력에서 그냥 실패한다.
지원 언어
공식(tree-sitter org 관리): C, C++, Python, JavaScript, TypeScript, Rust, Go, Java, Bash, HTML, CSS, Ruby 등 약 30개.
커뮤니티: 200개 이상. tree-sitter-language-pack에 170개 이상이 하나로 묶여 있다.