Tree-sitter(트리시터)를 이용한 파서 제작법

Tree-sitter｜Introduction

GitHub repository

Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited.

Tree-sitter(트리시터)는 파서 생성 툴이다. 자바스크립트 문법으로 쉽게 파서를 만들 수 있다. 또한 여러 언어의 바인딩을 생성할 수 있다.

Tree-sitter는 GitHub(깃허브)에서 atom(아톰) 에디터를 개발할 때 만들었으며, atom 에디터가 지원 종료된 이후에도 tree-sitter는 여러 에디터에서 지원하는 파서다 (neovim, helix, zed 등)

1) tree-sitter 소개 영상

2) tree-sitter 특징

• 쉽다: 자바스크립트 문법으로 파서를 만들 수 있어 기존 방식보다 파서를 만들기 쉽다 (ex. lex+yacc, flex+bison)
• 빠르다: incremental parsing을 지원한다.
• 안정적이다: 문법 오류가 있더라도 Parse tree를 생성할 수 있다 (에디터에서 int main() { 처럼 불완전한 구문이 있더라도 syntax highlighting이 잘 되는 것을 떠올리면 된다)
• 의존성-free: 런타임은 pure C로 작성되어 어떤 어플리케이션이라도 embed할 수 있다 (wasm 빌드도 있다)

3) tree-sitter 예시

• C: https://github.com/tree-sitter/tree-sitter-c
• javascript: https://github.com/tree-sitter/tree-sitter-javascript
• fluent-bit: https://github.com/sh-cho/tree-sitter-fluentbit (made by me)

이외에도 수많은 언어의 파서가 tree-sitter로 만들어져 있다.

fluent-bit tree-sitter는 내가 만든건데, config file의 파서다. 예를 들어 아래와 같은 config file이 있다고 했을 때,

@SET a=1
@SET b=2
@INCLUDE service.conf

[PARSER]
    name       test_api

[INPUT]
    # comments
    name      tail
    path      /var/log/containers/*.log

fluent-bit tree-sitter로 파싱을 해보면 아래와 같은 concrete parse tree를 얻을 수 있다.

config [0, 0] - [12, 0]
  directive [0, 0] - [1, 0]
    directive_set [0, 1] - [0, 8]
      key: key_type [0, 5] - [0, 6]
      value: value_type [0, 7] - [0, 8]
  directive [1, 0] - [2, 0]
    directive_set [1, 1] - [1, 8]
      key: key_type [1, 5] - [1, 6]
      value: value_type [1, 7] - [1, 8]
  directive [2, 0] - [3, 0]
    directive_include [2, 1] - [2, 21]
      pattern: value_type [2, 9] - [2, 21]
  section [4, 0] - [6, 0]
    header: section_header [4, 0] - [5, 0]
      name: section_header_type [4, 1] - [4, 7]
    body: section_body [5, 0] - [6, 0]
      entry [5, 4] - [5, 23]
        key: key_type [5, 4] - [5, 8]
        value: value_type [5, 15] - [5, 23]
  section [7, 0] - [11, 0]
    header: section_header [7, 0] - [8, 0]
      name: section_header_type [7, 1] - [7, 6]
    body: section_body [8, 0] - [11, 0]
      comment [8, 4] - [8, 14]
      entry [9, 4] - [9, 18]
        key: key_type [9, 4] - [9, 8]
        value: value_type [9, 14] - [9, 18]
      entry [10, 4] - [10, 39]
        key: key_type [10, 4] - [10, 8]
        value: value_type [10, 14] - [10, 39]

4) tree-sitter 파서 사용하기

(참고 문서: https://tree-sitter.github.io/tree-sitter/using-parsers)

tree-sitter 파싱 함수는 C API로 노출되어 있기 때문에 각 언어별 바인딩을 사용해 쉽게 사용할 수 있다.

예를 들어 node.js용 바인딩인 node-tree-sitter가 있고, node.js 바인딩으로 tree-sitter Javascript 파서를 사용하는 예시는 아래와 같다.

const Parser = require('tree-sitter');
const JavaScript = require('tree-sitter-javascript');

const parser = new Parser();
parser.setLanguage(JavaScript);

const sourceCode = 'let x = 1; console.log(x);';
const tree = parser.parse(sourceCode);

console.log(tree.rootNode.toString());

// (program
//   (lexical_declaration
//     (variable_declarator (identifier) (number)))
//   (expression_statement
//     (call_expression
//       (member_expression (identifier) (property_identifier))
//       (arguments (identifier)))))

const callExpression = tree.rootNode.child(1).firstChild;
console.log(callExpression);

// { type: 'call_expression',
//   startPosition: {row: 0, column: 16},
//   endPosition: {row: 0, column: 30},
//   startIndex: 0,
//   endIndex: 30 }

C#, Haskell, Rust, Java, ... 등 여러 언어의 바인딩이 구현되어 있고, 전체 목록은 https://tree-sitter.github.io/tree-sitter/#language-bindings에서 확인할 수 있다.

5) tree-sitter 파서 만들기

(참고 문서: https://tree-sitter.github.io/tree-sitter/creating-parsers)

tree-sitter는 자바스크립트를 DSL로 사용해 파서를 만들 수 있다.

5.1) 프로젝트 만들기

mkdir tree-sitter-${YOUR_LANGUAGE_NAME}
cd tree-sitter-${YOUR_LANGUAGE_NAME}

npm init
# 내가 만든 파서가 node에서 사용될 수 있도록 설치한다
npm install --save nan

# tree-sitter CLI 설치
# (1) npm 이용
npm install --save-dev tree-sitter-cli
# (2) homebrew 등 다른 방법으로 설치
brew install tree-sitter

프로젝트 폴더를 만들고 tree-sitter CLI도 설치한다. 참고로 프로젝트명은 웬만하면 tree-sitter-언어 형식으로 만드는 게 좋다.

그 다음, grammar.js 파일을 만들고 내용은 아래처럼 채운다. 단순히 'hello' 문자열만 매칭

module.exports = grammar({
  name: 'YOUR_LANGUAGE_NAME',

  rules: {
    // TODO: add the actual grammar rules
    source_file: $ => 'hello'
  }
});

다음, 아래 명령어로 tree-sitter 파서를 생성한다. 이 명령어는 C 파서 등 여러가지 파일을 생성한다.

tree-sitter generate

이제 파서를 사용해볼 수 있다.

echo 'hello' > example-file
tree-sitter parse example-file

# (source_file [0, 0] - [1, 0])

5.2) Grammar DSL

grammar.js에 문법 규칙을 작성할 때 아래 빌트인 함수들을 사용할 수 있다.

• Symbols ($): 모든 문법 규칙은 $로 시작해야 한다. $.identifier 형식으로 사용할 수 있고, $.MISSING, $.UNEXPECTED는 test 커맨드에서 사용되므로 사용하면 안된다.
• 문자열, 정규식 리터럴 - Terminal symbol은 문자열 또는 정규식 리터럴이다
• sequence: seq(rule1, rule2, ...) - 규칙이 순서대로 등장하는 경우. EBNF에서 symbol을 순서대로 쓸 때와 같다.
• alternatives: choice(rule1, rule2, ...) - 규칙중 하나에 해당될 때. EBNF에서 pipe(|)와 동일하다.
• 등등...

지금까지 간단한 사용법을 알아봤다. 더 자세한 내용은 문서에 자세히 잘 나와 있으니 새로운 tree-sitter 파서를 만들고 싶다면 공부하면서 만들면 된다.