Tree-sitter

[[GitHub| ]]
{{{#!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 · GitHub Mobile
오픈 소스	Electron · Atom · Linguist · Tree-sitter
관련 문서	사건 사고 · GitHub Universe · npm

<colcolor=#fff><bgcolor=#7d8f30> Tree-sitter
<colbgcolor=#7d8f30> 종류	증분 파서 제너레이터
최초 개발자	맥스 브런스펠드(Max Brunsfeld)
안정 버전	v0.25.10
언어	C, Rust
라이선스	MIT 라이선스
링크

1. 개요

2. 역사

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.js와 Electron 위에서 돌아가는 Atom.
• 선언적이다. 파서를 직접 작성할 필요 없이 문법 정의만 고수준 DSL로 쉽게 작성하면 코드가 알아서 생성된다. 단점도 되는데, 파서 제너레이터가 으레 그렇듯 파서 컴비네이터나 손으로 짜는 여타 파서마냥 자유도가 높지는 않다. 휴리스틱한 최적화를 구현하거나 매우 비일반적인 마크업 언어를 파싱하는 데는 어려움을 겪을 수도 있다는 것. 사실상 C로 external scanner 짜는 것 말고는 자체적인 로직을 끼워넣기가 매우 힘들다. 한 가지 hack으로 subrange parsing을 사용하는 방법이 있는데, 가령 tree-sitter-markdown 파서가 이러한 구현을 사용한다.[10] 여러모로 context-free 렉싱이 불가피한 마크업 언어들에서는 파서 짜기가 불편한 것이 사실.

4. Grammar DSL

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

<reference types="tree-sitter-cli/dsl" />

5. TSQuery

• #eq?, #not-eq?: 각각 해당 캡쳐가 특정 렉심과 일치하는지, 일치하지 않는지를 검사한다.
• #any-eq?, #any-not-eq?: 주어진 캡쳐가 반복 매칭 패턴(+, *, ?)일 때, 매칭된 패턴 중 하나라도 일치하는 것이 있는지, 하나라도 일치하지 않는지 검사한다.
• #match?, #not-match?: 특정 정규 표현식과 일치하는지 일치하지 않는지 검사한다.
• #any-match?, #any-not-match?: 반복 패턴에 매칭된 규칙 중 렉심이 하나라도 정규표현식과 일치하는지 일치하지 않는지 검사한다.
• any-of?: 해당 규칙에 매칭된 렉심이 인자로 주어진 문자열 중 적어도 하나와 같은지 검사한다.

#!syntax lisp
(command
  name: (simple_word) @keyword
  arguments: (word_list) @variable
  (#any-of? @keyword
    "unset"
    "variable"))

6. 활용

6.1. 바인딩

• C/C++: 기본 출력. parser.c 파일은 파서 빌드 시 생성되며, 원하는 형식으로 빌드해서 정적/동적 링크할 수 있다.
• Rust: tree-sitter (docsrs)
• JavaScript/TypeScript
• WebAssembly: web-tree-sitter - Rust와 더불어 lib에 존재하는 단 둘뿐인 바인딩이다. 이후 나머지 바인딩은 tree-sitter organization에서 개별적으로 관리된다. WASM API는 기본적으로 Node API와 거의 비슷하다. 단, 일부 API는 구현되어 있지 않다. 가령 file descriptor를 받는 Parser.printdotgraphs() 등.
• Node.js: node-tree-sitter(npm, typedoc)
• Python: py-tree-sitter(PyPI, Sphinx)
• Go: go-tree-sitter(godoc)
• Java: java-tree-sitter (maven, javadoc)
• Kotlin: kotlin-tree-sitter (KDoc)
• Zig: zig-tree-sitter (doc)
• Swift: swift-tree-sitter

6.2. 지원 플랫폼

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

6.3. 파생 소프트웨어

• ast-grep - Tree-Sitter AST를 대상으로 패턴 매칭 형식의 쿼리/치환을 수행하는 CLI.
• rust-sitter - JavaScript 대신 Rust를 사용해 문법을 정의할 수 있게 해주는 레이어.
• syncat - cat 명령어와 동일하지만 Tree-sitter 문법 기준으로 터미널 내에서 신택스 하이라이팅을 지원한다.
• rust-code-analysis - 다중 언어 정적 분석기
• difftastic - AST 인식 diff 하이라이터 구현체
• tweag/topiary/

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. 외부 링크

• tree-sitter-cli (npm)
• tree-sitter-grammars

9. 관련 문서

• 파싱
• 구문 트리
• Zed