🔖

Tree-sitter を利用して電卓プログラムを作成してみた

2022/05/07に公開

parser

treesitter

tech

最近度々話題になり気になっていた tree-sitter を試してみました。

tree-sitterとは

パーサージェネレータツールであり、漸進的分析ライブラリだそうです。
tree-sitterについては Vimのすゝめ改 - Tree-sitter について | 株式会社創夢 — SOUM/misc が詳しいです。

シンタックスハイライトに用いることを目的として作られていることもあり、parseした結果は Concrete Syntax Tree になっています。
そのため、コメントのように Abstract Syntax Tree では除外される要素も構文木に含まれています。

Parser作成手順の学習

Tree-sitter｜Creating Parsers を参考に parser 作成の流れを学習する。

cliをインストール

cargo install tree-sitter-cli

tree-sitter init-config

grammarを作成

helloという文字列を受理するgrammarを作成。

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

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

add grammar · tanzaku/tree-sitter-practice@12a778c

grammarからソース生成

tree-sitter generate

を実行してgrammarからソース生成する。このコマンドにより以下のファイルが自動生成された。

binding.gyp
bindings/node/binding.cc
bindings/node/index.js
bindings/rust/build.rs
bindings/rust/lib.rs
package.json
src/grammar.json
src/node-types.json
src/parser.c
src/tree_sitter/parser.h

execute tree-sitter generate · tanzaku/tree-sitter-practice@05f1aba

parse

tree-sitter parseでparseしてみる。

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

実行結果は以下の通り。正常にparseされCSTが表示されているようだ。

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

ちなみに、わざとエラーを発生させたらこうなった。

(source_file [0, 0] - [1, 0]
  (ERROR [0, 5] - [0, 6]
    (ERROR [0, 5] - [0, 6])))
example-file    0 ms    (ERROR [0, 5] - [0, 6])

add source file · tanzaku/tree-sitter-practice@301c6de

test追加

test/corpusディレクトリにテスト追加した。
テストは下記のフォーマットで作成するようだ。

===============
hello statement <- テスト名
===============

hello <- テストの入力

---

(source_file) <- expected

テストの実行は下記コマンドで行う。

tree-sitter test

add test · tanzaku/tree-sitter-practice@1dd9ed0

電卓作成

Parser作成の流れはある程度理解できたので、ここからは電卓を作成していく。

電卓のgrammar作成

それっぽくgrammarを書いた。
update grammar · tanzaku/tree-sitter-practice@c494237
fix grammar · tanzaku/tree-sitter-practice@9989d3e

tree-sitter generateを実行すると、以下のエラーが発生。

➜  tree-sitter-practice git:(main) ✗ tree-sitter generate
Unresolved conflict for symbol sequence:

  '+'  _expression  •  '+'  …

Possible interpretations:

  1:  '+'  (binary_expression  _expression  •  '+'  _expression)
  2:  (unary_expression  '+'  _expression)  •  '+'  …

Possible resolutions:

  1:  Specify a higher precedence in `binary_expression` than in the other rules.
  2:  Specify a higher precedence in `unary_expression` than in the other rules.
  3:  Specify a left or right associativity in `unary_expression`
  4:  Add a conflict for these rules: `unary_expression`, `binary_expression`

文法の曖昧さを解消

文法が曖昧なので怒られいるようだ。
具体的には+1 + 2 という式を以下のどちらで解釈すべきか、という点で曖昧になってしまっている。

(+(1 + 2))
((+1) + 2)

precで優先度を指定することで曖昧性を除去した。
デフォルトの優先度は0なので、それより高い1を指定。
fix grammar · tanzaku/tree-sitter-practice@d1fc7fb

再度tree-sitter generateを実行。今度は別のエラーが発生。

➜  tree-sitter-practice git:(main) ✗ tree-sitter generate
Unresolved conflict for symbol sequence:

  _expression  '+'  _expression  •  '+'  …

Possible interpretations:

  1:  (binary_expression  _expression  '+'  _expression)  •  '+'  …
  2:  _expression  '+'  (binary_expression  _expression  •  '+'  _expression)

Possible resolutions:

  1:  Specify a left or right associativity in `binary_expression`
  2:  Add a conflict for these rules: `binary_expression`

今回は 1 + 2 + 3 を以下のどちらで解釈するか（左結合か右結合か）が曖昧だと怒られている。

((1 + 2) + 3)
(1 + (2 + 3))

prec.leftで左結合を優先するように指定。その他色々やってエラー解消。
fix an error · tanzaku/tree-sitter-practice@73a77be

コメント対応

コメントのようにどこにでも現れる要素はextrasに指定するらしい。
今回は簡単のため{と}で囲った部分をコメントとした。

コメントのgrammarは以下の定義になっている。
tree-sitter-cのgrammar定義を見ると、コメント部分全体を1トークンとして扱うためにtoken関数を用いていたので、それに倣ってtoken関数を使っている。

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

    extras: $ => [
        /\s|\\\r?\n/,   // extrasを定義する場合は、空白にマッチするパターンを明示的に指定する必要がある
        $.block_comment
    ],

    rules: {
        source_file: $ => $._statement,

        block_comment: $ => token(seq('{', /[^}]*/, '}')),

下記のようなテストケースを追加した。CSTなのでコメント部分も明示的にノードが構築されていることがわかる。

===============
comment
===============

x=2**{コメントテスト}3+1

---

    (source_file
      (assignment
        (identifier)
        (binary_expression
          (binary_expression
            (number)
            (block_comment) <- コメントノード
            (number))
          (number))))

support comment · tanzaku/tree-sitter-practice@d676012

wasm

tree-sitter/lib/binding_web at master · tree-sitter/tree-sitter を参考にした。

ファイルの準備

tree-sitter-practice.wasm
tree-sitter build-wasm コマンドで生成
tree-sitter.js, tree-sitter.wasm
Release v0.20.6 · tree-sitter/tree-sitter からダウンロード

力尽きたので細かい話は省略。下記コミットでwasmを呼び出すプログラムを追加しているので、cloneして実行すれば試すことができる。
wasm · tanzaku/tree-sitter-practice@2b020bc

終わりに

tree-sitterの作法がわかっていないので、正しい方法か自信がないです。ちょっと変だなというところがあったらご教示いただけると幸いです。