近況 2019-12-31

 2019年12月31日 投稿 日記

今月の活動について (knowbug リリース、網羅性検査の記事、HSP3 の記事、X-BNF 言語など)

knowbug

https://github.com/vain0x/knowbug/commits/master?after=593608afcccaff5849d014578eeaf8cefbf7115c+34

網羅性検査

スペースによるパターンマッチの網羅性検査

静的型付き言語の便利な点の1つとして、パターンマッチに漏れがなく網羅的であることがコンパイル時に検証されることがあります。本稿ではパターンマッチの説明から始め、「スペース」という概念を用いてパターンマッチの網羅性を検査するアルゴリズムの大ざっぱな雰囲気を述べます。また、その試験実装を作ったので公開します。

この記事は 2019年12月の 言語実装アドベントカレンダー の21日目です。

  • アドベントカレンダーに記事を投稿した。
  • 先月は LSP/DAP の記事を書く、と予告したけど、仕上がらなかったのでこっちに。
  • 記事ではあまり触れてない裏目標として以下の2つがある。
  • 1つ目は Web/monaco-editor 上で自作言語の処理系を動かすこと。
  • Rust で書いたパーサや型検査・網羅性検査を WebAssembly にコンパイルして動かしている。
  • wasm-bindgen/wasm-pack といったライブラリのおかげで簡単にできる。これも後で記事にしたい。
  • 2つ目は、ロスレス構文木を使うこと。
  • 近況記事シリーズでしばしば触れている rust_analyzer 風に、パースの結果としてロスレスな (元のソースコードの空白なども含めて完全にデータを維持する) 構文木にする手法を試した。
  • わりと感覚が掴んできたし、パースからエラー報告を分離できる利点に気づいた。
  • 例えば網羅的でない match 式の match キーワードの位置にエラーを出しているが、「match キーワードの位置」をパース時に見つけておく必要がない。エラーが出た後に構文木の上を走査して位置を特定している。
  • これのせいで時間的にギリギリになった面もある。

X-BNF 言語

https://github.com/vain0x/xbnf-lang

  • 拡張 BNF 言語を解析して FIRST 集合や FOLLOW 集合を計算するアプリを作った。
  • 再帰下降パーサを生成するコードジェネレータにする予定だったが、詰まっている。
  • パーサはほぼ規則的に書いているつもりだったから、規則的に生成できると思いこんでいたが、思いの外不規則だったことに気づいた。

その他

関連記事