최근 수정 시각 : 2025-10-03 16:45:53

Tree-sitter


[[GitHub|
파일:GitHub 아이콘 화이트.svg파일:GitHub 로고 화이트.svg
]]
{{{#!wiki style="min-height: calc(1.5em + 5px); margin: 0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
<colbgcolor=#000,#000><colcolor=#fff,#fff> 관련 인물 톰 프레스턴 워너
서비스 저장소 · GitHub Pages · GitHub Action · GitHub Packages · GitHub Wiki · GitHub Gist · GitHub Copilot
클라이언트 GitHub CLI · GitHub Desktop
오픈 소스 Electron · Atom · Tree-sitter
관련 문서 사건 사고 · GitHub Universe · npm }}}}}}}}}
<colcolor=#fff><bgcolor=#7d8f30> Tree-sitter
파일:Tree-sitter.png
<colbgcolor=#7d8f30> 종류 증분 파서 제너레이터
최초 개발자 맥스 브런스펠드(Max Brunsfeld)
안정 버전 v0.25.10
언어 C, Rust
라이선스 MIT 라이선스
링크 파일:홈페이지 아이콘.svg 파일:GitHub 아이콘.svg파일:GitHub 아이콘 화이트.svg 파일:cargo.rs.png 파일:npm, lnc. n-logo.png
1. 개요2. 역사3. 특징4. Grammar DSL5. TSQuery6. 활용
6.1. 바인딩6.2. 지원 플랫폼6.3. 파생 소프트웨어
7. 기타8. 외부 링크9. 관련 문서

1. 개요

증분식 파서 제너레이터 구현체.

2. 역사

최초 개발자인 맥스 브런스필드는 2013년 GitHub에 입사해 당시 깃헙의 최대 야심작 중 하나였던 Atom 에디터 팀으로 일하기 시작했다.[z][2] 동시에 2013년 11월 6일[3] CC++로 증분 파싱 시스템인 Tree-sitter를 사이드 프로젝트로 개발하다가[4], Atom이 1.0버전 출시를 준비하는 동안 이를 GitHub의 정식 프로젝트로 포함시킨다.

이후 브런스필드는 2018년 1월 8일 당시 CoffeeScript 기반이었던 Atom의 구문 강조 시스템 및 코드 폴딩 기능에 선택적 Tree-sitter 지원을 추가하는 PR을 작성했고[5] 이는 2018년 2월 14일(안정 릴리즈는 2018년 3월 16일) Atom v1.25.0-beta0 버전부터 core.useTreeSitterParsers 플래그를 통한 실험적 기능으로 제공되기 시작해[6][7] 2018년 10월 31일 Atom v1.31 버전부터는 기본 설정으로 완전히 통합되었다.[8]

2019년 1월 5일, 파서 제너레이터 구현체를 C++에서 Rust로 재작성하고, 파서 개발용 CLI 인터페이스까지 Rust로 재작성하며 node-gyp를 통해 별도의 저장소에서 개발되고 있던 tree-sitter-clideprecate시켰다.[9]

GitHub의 새 code search 및 navigation 기능에 GitHub가 개발한 stackgraph와 함께 중점적으로 쓰이고 있다.## linguist의 모든 언어가 지원되는 것은 아니고, 현재 C##, Python#, Ruby#, Elixir#, Rust#, TypeScript# 등의 언어 navigation 기능이 Tree-sitter 파서 기반으로 구현되어 있다.

3. 특징

  • 속도가 매우 빠르다. 특히 백트래킹이 없어 사실상 [math(\mathcal O(n))]에 가까운 속도가 나오는 렉서 기반 신택스 하이라이터 구현체들과 비교해도 별 차이가 없을 정도로 수ms 이내에 파싱이 끝난다. 쿼리 속도 역시 빠른 편. 파서를 JavaScript로 생성하는 것으로 오해하지만 이는 문법 정의 파일이고 실제 생성되는 파서의 코어 로직은 전부 C로 짜여 있다.
  • 증분 파싱을 지원한다. 다시 말해 코드 일부분만이 수정된 경우 해당 부분의 서브트리만 갱신시키고 기존의 파스 트리는 재사용하므로써 속도를 올리는 방식인데, 이는 컴파일러보다 실시간으로 diagnose를 표시해 줘야 하는 린터나 LSP 구현체에 특히 매력적인 장점이다. 일반적으로 대부분의 파서 제너레이터는 complete 파서만 생성하기에 증분 파싱 기능을 지원하려면 파서를 전부 손으로 짜야 하는데, LR 파서를 손으로 짜고 증분 파싱까지 구현하기란 결코 쉬운 난이도가 아니다.
    • 수준급의 error recovery 기능이 내장되어 있다. 에디터 내에서 코드를 실시간으로 수정하다 보면 괄호를 연 채 닫지 않는 등 자연히 파싱 불가능한 상태를 지날 수밖에 없는데, 일반적인 컴파일러의 경우 파싱이 실패할 때마다 그 위치에 error diagnose를 보여주게 될 것이다. 자연히 다른 정적 분석으로 얻어진 정보도 소실될 수밖에 없다. 결국 상용 에디터 채택급의 증분 구현을 위해선 지능적인 에러 회피 전략이 필수적인데, Tree-sitter로 제작된 파서의 경우 파싱에 실패해도 해당 서브트리만 에러 토큰이 들어갈 뿐 코드베이스의 나머지 전체 트리는 영향받지 않는다.
  • 문법 정의가 쉽다. 특히 별도의 메타신택스 또는 자신만의 문법 정의 언어가 있는 YACC, Bison 등의 다른 제너레이터와 다르게 문법을 JavaScript로 작성한다. 정확히는 grammar.js 파일을 몇몇 사전 정의된 함수를 사용해 JS로 작성한 후, Node.js로 이를 실행해 최종 객체를 JSON 형태로 얻어낸 뒤 다시 이를 기반으로 파서를 생성한다. 따라서 JS에 익숙하다면 문법 정의를 작성하기 꽤 쉽다.
    • 문법 객체를 반환하는 내장 함수인 garmmar() 자체가 별도의 언어가 아닌 JavaScript 함수이기 때문에 해당 함수를 감싸는 팩토리를 만들고 유사한 언어 문법을 정의하기 위해 재사용하는 것도 가능하다. 실제로 tree-sitter-csv 등의 경우 CSV, TSV, PSV 세 언어를 공통된 구조로 한번에 정의하고 재사용하기 위해 사용자 정의 팩토리를 활용한다.
  • Scheme 비스무리한 문법의 자체 쿼리 언어TSQuery로 파싱한 트리를 조회할 수 있다. 주로 용도는 요소 그룹핑 및 하이라이팅 등이지만 용도에 따라 정적 분석용이나 기타 인덱싱 용으로도 활용될 수 있다. 쿼리 자체가 파서와 별개이기에 문법 강조를 바꾼다고 파서를 재빌드할 필요 없이 하이라이터 쿼리만 수정하면 되는 것도 장점.
  • 바인딩 활용성이 높다. 코어 라이브러리 자체가 C로 짜여 있기 때문에 C FFI 호환만 되는 언어라면 어느 언어든지 적당한 성능으로 바인딩 이용이 가능하다. 가장 대표적인 예시가 Node.jsElectron 위에서 돌아가는 Atom.

4. Grammar DSL

JavaScript 함수들로 구성된 문법 정의(metasyntax)용 도메인 특화 언어. TreeQL처럼 별도의 언어는 아니고 상술했듯 실행 가능한 JS 함수 목록을 제공하는 것이기에 파서를 생성할 때면 우선 이를 Node.js 환경에서 실행시켜 결과를 JSON 형태로 얻어내는 과정이 한 단계 더 필요하게 되며, 덕분에 사용자 정의 함수를 분리하거나 앞서 사용된 논터미널 규칙을 변수로 참조할 수도 있는 등, 문법 설계에 원하는 매우 높은 자유도를 누릴 수 있다.

문법 정의는 grammar.js 파일에 들어 있다. 해당 파일은 파서 생성에 필요한 문법 객체를 반환하는 하나의 commonjs 모듈을 이루며, 이는 grammar() 함수에 파싱 규칙을 정의한 객체를 전달해서 얻을 수 있다. 개별 규칙은 rules 객체의 개별 프로퍼티로써 정의되는데, 프로퍼티 이름이 해당 규칙의 이름이 되고 프로퍼티 값은 하나의 인자(주로 $)를 받아 패턴을 반환하는 함수의 형태이다.

대표적인 함수 목록은 다음과 같다. external scanner 설정을 하지 않는 한 렉서와 파서 레벨을 구분하지 않음에 주의.
  • seq(): 인자로 전달된 모든 규칙을 순서대로 파스한다.
  • choice(): 인자로 전달된 규칙 중 하나에 매칭한다. 흔한 파서 콤비네이터의 altBNF 문법의 |와 비슷하다.
  • repeat(): 인자로 전달된 규칙이 0번 이상 반복되는 패턴에 매칭한다. 정규 표현식*를 떠올리면 좋다.
    • repeat1(): 인자로 전달된 규칙이 1번 이상 반복되는 패턴에 매칭한다. 정규 표현식+를 떠올리면 좋다.
    • optional(): 인자로 전달된 규칙 또는 공문자열에 매칭한다. 위의 repeat과 비슷하게 생각하면 0번 또는 1번 반복한다고 표현할 수 있다. 정규 표현식?를 떠올리면 좋다.
  • prec(): 생성 규칙 충돌이 일어날 때, 정적인 우선순위를 강제로 지정할 수 있다.
    • prec.left()/prec.right(): 각각 좌결합(left-associativity), 우결합(right-associativity) 우선순위를 지정한다. 이항 연산 구문의 파싱이나 반복 구문의 파싱 등에서 사용된다.

5. TSQuery

Grammar DSL은 파서 문법을 정의하기 위한 언어이고, 해당 파서로 파싱된 CST 트리를 쿼리하기 위해서는 S-표현식 기반의 쿼리 언어를 사용한다. 이는 tree-sitter parse 명령을 실행했을 때도 보여지는 문법과도 비슷한데, 이 경우 sexpr의 함수 부분이 alias가 완료된 구문 규칙의 이름이며, 대괄호 사이에 span 정보가 오고 나머지 인자 위치에 해당 트리의 자식 노드들이 놓여진다. 쿼리의 경우 각각의 패턴이 구문 규칙의 이름을 정하고, 패턴 내에 인자로 주어진 다른 패턴이 있다면 자식 노드로 재귀적으로 매칭한다.

이외에도 인자란에 조건절을 추가할 수 있는데, 조건절은 자식 노드가 아니라 상위 스코프에서 캡쳐한 노드에 대해(주로 렉심) 검사한다.
  • #eq?, #not-eq?: 각각 해당 캡쳐가 특정 렉심과 일치하는지, 일치하지 않는지를 검사한다.
  • #any-eq?, #any-not-eq?: 주어진 캡쳐가 반복 매칭 패턴(+, *, ?)일 때, 매칭된 패턴 중 하나라도 일치하는 것이 있는지, 하나라도 일치하지 않는지 검사한다.
  • #match?, #not-match?: 특정 정규 표현식과 일치하는지 일치하지 않는지 검사한다.
  • #any-match?, #any-not-match?: 반복 패턴에 매칭된 규칙 중 렉심이 하나라도 정규표현식과 일치하는지 일치하지 않는지 검사한다.
  • any-of?: 해당 규칙에 매칭된 렉심이 인자로 주어진 문자열 중 적어도 하나와 같은지 검사한다.

예를 들어, 코드에서 "unset" 또는 "variable" 명령 구문만 찾고 하이라이트하고 싶다면 다음과 같이 쿼리할 수 있다.
#!syntax lisp
(command
  name: (simple_word) @keyword
  arguments: (word_list) @variable
  (#any-of? @keyword
    "unset"
    "variable"))

6. 활용

6.1. 바인딩

아래 언어/런타임별 바인딩을 기본으로 지원한다. 비공식 바인딩 지원은 아래 문단 참고.

6.2. 지원 플랫폼

  • Atom
  • Neovim - 2018년부터 Tree-sitter를 적극적으로 도입하기 시작했다.# 현재는 다소 unstable하지만 내장된 Lua API가 있고#, 대부분의 엔드 유저들은 nvim-treesitter를 사용해 :TSInstall만으로 구문 강조, 코드 폴딩, 심볼 검색 등등 기능을 사용하거나 추가적인 확장을 만들 수 있다.
  • Helix
  • Zed - 브런스펠드가 GitHub 퇴사 후 합류해 개발 중인 Rust 기반 에디터.
  • Emacs#
  • GitHub#

6.3. 파생 소프트웨어

7. 기타

  • DOT 시각화 기능이 내장되어 있다. 메인 파서 라이브러리에서 각 트리를 DOT으로 출력할 수 있는 ts_tree_print_dot_graph() 함수가 있고, tree-sitter CLI에서도 --dot 옵션을 주어 전체 파스 트리를 DOT으로 렌더링할 수 있다.
    • 이외에도 ts_parser_print_dot_graphs()함수를 사용하면 LR 파싱 스텝을 DOT으로 렌더링해 지정한 파일에 출력한다. CLI의 경우 파싱시 --debug-graph 플래그를 주면 log.html 파일에 파싱 스텝을 SVG로 렌더링해서 출력한다.

8. 외부 링크

9. 관련 문서


[z] Max joined the Atom team in 2013 after working at Pivotal Labs. While driving Atom towards its 1.0 launch during the day, Max spent nights and weekends building Tree-sitter, a blazing-fast and expressive incremental parsing framework that currently powers all code analysis at GitHub. Before leaving to start Zed, Max helped GitHub's semantic analysis team integrate Tree-sitter to support syntax highlighting and code navigation on github.com. #@[2] Max Brunsfeld is an engineer on GitHub's Atom team. Tree-sitter - a new parsing system for programming tools[3] Commit 84c5bceb818127fd7728655fb209a1be92e53fde - Nov 6, 2013[4] Today, I'm gonna be talking about a piece of software I've been working on for almost 4 years now, called Tree-sitter. I worked on it as a side project for a long time and now I'm working on it as part of some project of GitHub. Tree-sitter: a new parsing system for programming tools - GitHub Universe 2017 - Dec 21, 2017[5] This pull request adds a new config setting to Atom: core.useTreeSitterParsers, which defaults to false. If you set that setting to true, when editing files written in certain languages, Atom will use a new parsing system called Tree-sitter to provide improved syntax highlighting and code folding. Allow Tree-sitter parsers to be used for syntax highlighting and code folding #16299 - Jan 8, 2018[6] Support greatly improved syntax highlighting and code folding with a next-generation parsing system called tree-sitter. See the pull request for details about opting in to try it out. 1.25.0-beta0 release - Feb 14, 2018[7] For syntax highlighting and code-folding, an incremental parsing system, called tree-sitter, is available in beta form. Tree-sitter is a C library used via bindings to higher-level languages. Tree-sitter currently is disabled by default but can be turned on via the User Tree Sitter Parsers setting. What's new in GitHub's Atom text editor - Mar 16, 2018[8] At GitHub, we want to explore new ways of making programming intuitive and delightful, so we've developed a parsing system called Tree-sitter that will serve as a new foundation for code analysis in Atom. Tree-sitter makes it possible for Atom to parse your code while you type—maintaining a syntax tree at all times that precisely describes the structure of your code. We've enabled the new system by default in Atom, bringing a number of improvements. Atom understands your code better than ever before - Oct 31, 2018[9] In this PR, I'm moving the functionality of tree-sitter-cli into this repository. Instead of implementing the CLI in JavaScript like before, it will now be in Rust. In addition, I'm porting the C++ compiler library (used by the CLI) to Rust, and consolidating it into the CLI crate. Include CLI functionality in the main repo, using Rust instead of C++ #260 - Jan 5, 2019