Tree-sitter · sunshinemoon

개념

Tree-sitter는 파서 생성기(parser generator) 이면서 동시에 인크리멘털 파싱 라이브러리다. Max Brunsfeld가 GitHub에서 일하면서 만들었고 2018년에 공개됐다. 다른 파서와 달리 (1) 에러가 있는 코드에서도 트리를 만들고 (2) 키 입력마다 변경된 부분만 재파싱하는 게 핵심이다. 이 두 속성이 에디터와 개발 도구에 딱 맞다.

왜 만들어졌나

원래 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()으로 트리 메타데이터만 수정
실제로 다시 파싱해야 할 영역을 계산한다
바뀌지 않은 서브트리는 그대로 재사용
새 트리를 구성할 때 재사용 가능한 노드는 갖다 붙임

결과적으로 작은 수정 후 재파싱은 파일 크기에 관계없이 수 밀리초 수준이다.

파싱 알고리즘: GLR

기반은 LR 파싱이다. 소스를 왼쪽에서 오른쪽으로 읽으면서, 파스 테이블을 참조해 토큰들을 트리 노드로 묶는다.

LR의 문제는 문법이 모호할 때(shift-reduce conflict, reduce-reduce conflict) 실패한다는 것. Tree-sitter는 GLR(Generalized LR) 을 써서 이걸 해결한다.

GLR은 충돌이 생기면 파스 스택을 여러 개로 분기해서 여러 해석을 동시에 탐색하다가, 불가능한 경로를 제거한다. 일반 LR로는 못 다루는 문법을 파싱할 수 있다.

에러 복구

에디터에서 코드는 항상 반만 쓰여진 상태다. 완성된 코드를 가정하는 파서는 쓸 수 없다.

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, 심볼 네비게이션, 하이라이팅에 사용. 문법을 조합(compose)할 수 있는 것도 채택 이유 중 하나
GitHub Copilot — 많은 언어에서 WASM으로 tree-sitter를 호출해 코드 구조를 파악
Zed 에디터 — Max Brunsfeld가 직접 만든 에디터. 구문 강조, 심볼 아웃라인, 구문 노드 단위 선택 확장, 자동 들여쓰기 등이 전부 tree-sitter 기반

다른 파서와 비교

	Tree-sitter	비교 대상
TextMate 문법(정규식)	상태 있음, 중첩 처리	정규식은 stateless — 중첩 구조 처리 못 함
ANTLR	GLR, C11 런타임, 에디터용	LL(*) 기반, 컴파일러용, Java/Python 런타임 필요
PEG (pest, peg.js)	에러 복구 강함	PEG는 결정론적이지만 에러 복구가 사실상 없음
Yacc/Bison	에러에 강함	LR 기반이지만 컴파일러용이라 에러 입력에 실패

지원 언어

공식(tree-sitter org 관리) — C, C++, Python, JavaScript, TypeScript, Rust, Go, Java, Bash, HTML, CSS, Ruby 등 약 30개
커뮤니티 — 200개 이상. tree-sitter-language-pack에 170개 이상이 하나로 묶여 있음

개념