Tree-sitter

<colbgcolor=#7d8f30><colcolor=#fff> Tree-sitter
종류	증분 파서 제너레이터
최초 개발자	맥스 브런스펠드(Max Brunsfeld)
안정 버전	v0.25.2
언어	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에 익숙하다면 문법 정의를 작성하기 꽤 쉽다.
• Scheme 비스무리한 문법의 자체 쿼리 언어인 TSQuery로 파싱한 트리를 조회할 수 있다. 주로 용도는 요소 그룹핑 및 하이라이팅 등이지만 용도에 따라 정적 분석용이나 기타 인덱싱 용으로도 활용될 수 있다. 쿼리 자체가 파서와 별개이기에 문법 강조를 바꾼다고 파서를 재빌드할 필요 없이 하이라이터 쿼리만 수정하면 되는 것도 장점.
• 바인딩 활용성이 높다. 코어 라이브러리 자체가 C로 짜여 있기 때문에 C FFI 호환만 되는 언어라면 어느 언어든지 적당한 성능으로 바인딩 이용이 가능하다. 가장 대표적인 예시가 Node.js와 Electron 위에서 돌아가는 Atom.

4. 활용

4.1. 지원 플랫폼

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

4.2. 파생 소프트웨어

• ast-grep
• rust-sitter - JavaScript 대신 Rust를 사용해 문법을 정의할 수 있게 해주는 레이어.
• syncat - cat 명령어와 동일하지만 Tree-sitter 문법 기준으로 터미널 내에서 신택스 하이라이팅을 지원한다.

5. 관련 문서

• 파싱
• 추상 구문 트리