SATySFiで作成する構文解析器

SATySFi Conf 2023 https://connpass.com/event/295734/ での発表

Transcript

1. SATYSFIで作成する構文解析器 金子尚樹 (@puripuri2100) SATYSFI Conf 2023 2023 年 10 月 22 日
2. 1/17 自己紹介 インターネットネーム： puripuri2100 筑波大学情報科学類 2 年 satysfi-code-printer や satysfi-ruby などのパッケージの作成 satysfi-base のメンテ・コントリビュート SATySFi Advent Calendar (2018 - 2022) の主催 SATySFi Conf (2020 - 2023) の主催 SATySFi Slack の管理
3. 2/17 今日の発表の概要 今！ SATySFi 他のフォーマットを解析するのがアツい！！！！！
4. 2/17 今日の発表の概要 今！ SATySFi 他のフォーマットを解析するのがアツい！！！！！ puripuri2100 の中で
5. 2/17 今日の発表の概要 今！ SATySFi 他のフォーマットを解析するのがアツい！！！！！ puripuri2100 の中で 最近大量に構文解析ライブラリを作っているので紹介したい
6. 2/17 今日の発表の概要 今！ SATySFi 他のフォーマットを解析するのがアツい！！！！！ puripuri2100 の中で 最近大量に構文解析ライブラリを作っているので紹介したい 便利なのでみんな使ってね！
7. 構文解析とは 構文解析とは
8. 構文解析とは 3/17 概要 構造を持ったテキストを解析して対応するデータ構造を生成すること
9. 構文解析とは 3/17 概要 構造を持ったテキストを解析して対応するデータ構造を生成すること 木構造や配列を持つ文字列の例（JSON フォーマット） 1 { 2 "foo" : "foo", 3 "bar" : { 4 "bar1" : [1,2,3], 5 "bar2" : [ 6 {"baz1" : 123, "baz2" : -1.2}, 7 {"baz3" : null, "baz4" : true} 8 ] 9 } 10 }
10. 構文解析とは 4/17 構文解析が必要な場面 外部とプログラムがデータをやり取りするときに便利 どの OS に存在しているインターフェースとしてのファイル・テキスト もちろんエンコーディングに関しては別の問題があるが、最近は UTF8 前提 にしても良さそう 人がプログラムにデータを渡すときにもファイルやテキストを介して行う コンパイラにソースコードを与えるときや設定ファイルを与えるとき
11. 構文解析とは 5/17 テキストからデータへの変換の例 1 { 2 "foo" : "foo", 3 "bar" : [{"baz1" : 123}, {"baz2" : null}] 4 }
12. 構文解析とは 5/17 テキストからデータへの変換の例 1 { 2 "foo" : "foo", 3 "bar" : [{"baz1" : 123}, {"baz2" : null}] 4 } 1 Value([ 2 (`foo`, String(`foo`)); 3 (`bar`, List([ 4 Value(`baz1`, Int(123)); 5 Value(`baz2`, Null); 6 ])); 7 ])
13. 構文解析とは 6/17 構文解析の流れ 一番単純な解析方法は k 個先読みの再帰下降パーサ 以下のような処理を行う関数を組み合わせて作っていく
14. 構文解析とは 6/17 構文解析の流れ 一番単純な解析方法は k 個先読みの再帰下降パーサ 以下のような処理を行う関数を組み合わせて作っていく (a) トークンのリストを受け取る
15. 構文解析とは 6/17 構文解析の流れ 一番単純な解析方法は k 個先読みの再帰下降パーサ 以下のような処理を行う関数を組み合わせて作っていく (a) トークンのリストを受け取る (b) 他の同様な解析用の関数を規則に応じて順に呼び出してデータの列を 作り、それらをまとめて一つのデータを作る
16. 構文解析とは 6/17 構文解析の流れ 一番単純な解析方法は k 個先読みの再帰下降パーサ 以下のような処理を行う関数を組み合わせて作っていく (a) トークンのリストを受け取る (b) 他の同様な解析用の関数を規則に応じて順に呼び出してデータの列を 作り、それらをまとめて一つのデータを作る (c) 生成したデータと残りのトークンのリストの 2 つを返す
17. 構文解析とは 6/17 構文解析の流れ 一番単純な解析方法は k 個先読みの再帰下降パーサ 以下のような処理を行う関数を組み合わせて作っていく (a) トークンのリストを受け取る (b) 他の同様な解析用の関数を規則に応じて順に呼び出してデータの列を 作り、それらをまとめて一つのデータを作る (c) 生成したデータと残りのトークンのリストの 2 つを返す トークンのリストの終端と規則の終端が一致したら終了
18. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する
19. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ]
20. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] これがこう 1 List([ 2 String(`1`); 3 List([String(`2`), String(`3`), String(`4`)]), 4 String(`あ`) 5 ])
21. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] BNF で書くと 1 list ::= <LCurlyBraces> <items> <RCurlyBraces> 2 items ::= <item> <Comma> <items> | <item> 3 item ::= <string> <list> 4 string ::= <空白文字とカンマと角括弧以外の全て> <string> 5 LCurlyBraces ::= [ 6 RCurlyBraces ::= ] 7 Cooma ::= ,
22. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] 関数を定義に合わせて一つずつ作って相互に呼び出す
23. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] 1 let-rec parse-list tokens = 2 match tokens with 3 | '[' :: xs -> 4 let (items, xs) = parser-items xs in 5 match xs with 6 | ']' :: xs -> List(items) ^:: (parse-list xs) 7 | _ -> panic () 8 | x :: xs when is-WS x -> parse-list tokens 9 | _ -> panic ()
24. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] 1 and parse-items tokens = 2 let (item, xs) = parse-item tokens in 3 match xs with 4 | ',' :: xs -> item ^:: (parse-items xs) 5 | x :: xs when is-WS x -> parse-items xs 6 | _ -> (item, xs)
25. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] 1 and parse-item tokens = 2 match tokens with 3 | '[' :: xs -> parse-list tokens 4 | x :: xs when is-WS x -> parse-item xs 5 | _ -> parse-string tokens
26. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] 1 and parse-string tokens = 2 match tokens with 3 | '[' :: _ -> ('', tokens) 4 | ',' :: _ -> ('', tokens) 5 | x :: xs when is-WS x -> ('', tokens) 6 | x :: xs -> x ^^ (parse-string xs) 7 | [] -> ('', [])
27. 構文解析とは 7/17 構文解析の例 カンマ区切りのリスト（入れ子有り）を解析する例。空白は無視する 1 [1, [2, 3, 4], あ] リストを解析する関数を呼び出す 解析の終端と入力の終端と一致しているかの検査を行う 1 let parser tokens = 2 let (lst, xs) = parse-list tokens in 3 match xs with 4 | [] -> lst 5 | _ -> panic ()
28. SATYSFIで書かれた構文解析器の紹介 SATYSFIで書かれた構文解析器の紹介
29. SATYSFIで書かれた構文解析器の紹介 8/17 なぜ SATYSFIで構文解析器を書くのか 世界には便利なフォーマットが溢れているから json toml csv xml bibtex 既存の資産を手軽に利用したい 外部のファイルを読み込めるプリミティブと組み合わせて最強に read-file : string -> string list
30. SATYSFIで書かれた構文解析器の紹介 9/17 構文解析器を作るための方法の紹介 再帰関数とパターンマッチ 先ほど紹介した方法
31. SATYSFIで書かれた構文解析器の紹介 9/17 構文解析器を作るための方法の紹介 再帰関数とパターンマッチ 先ほど紹介した方法 base ライブラリの parser パッケージ パーサーコンビネータという「よくあるパターンに合わせて関数を組み合わ せて組み上げる」手法 Haskell の Parsec ライブラリがよく似ている
32. SATYSFIで書かれた構文解析器の紹介 9/17 構文解析器を作るための方法の紹介 再帰関数とパターンマッチ 先ほど紹介した方法 base ライブラリの parser パッケージ パーサーコンビネータという「よくあるパターンに合わせて関数を組み合わ せて組み上げる」手法 Haskell の Parsec ライブラリがよく似ている 正規表現で括り出し 一番手軽だが正確性に欠ける 正規表現で表すことができる言語の範囲は小さい
33. SATYSFIで書かれた構文解析器の紹介 9/17 構文解析器を作るための方法の紹介 再帰関数とパターンマッチ 先ほど紹介した方法 base ライブラリの parser パッケージ パーサーコンビネータという「よくあるパターンに合わせて関数を組み合わ せて組み上げる」手法 Haskell の Parsec ライブラリがよく似ている 正規表現で括り出し 一番手軽だが正確性に欠ける 正規表現で表すことができる言語の範囲は小さい 自分は再帰関数とパターンマッチで頑張るのが好き
34. SATYSFIで書かれた構文解析器の紹介 10/17 作った構文解析ライブラリたち satysfi-json
35. SATYSFIで書かれた構文解析器の紹介 10/17 作った構文解析ライブラリたち satysfi-json satysfi-csv
36. SATYSFIで書かれた構文解析器の紹介 10/17 作った構文解析ライブラリたち satysfi-json satysfi-csv satysfi-xml
37. SATYSFIで書かれた構文解析器の紹介 10/17 作った構文解析ライブラリたち satysfi-json satysfi-csv satysfi-xml satysfi-bibtex-parser
38. SATYSFIで書かれた構文解析器の紹介 10/17 作った構文解析ライブラリたち satysfi-json satysfi-csv satysfi-xml satysfi-bibtex-parser satysfi-code-printer
39. SATYSFIで書かれた構文解析器の紹介 11/17 satysfi-json JSON フォーマットのパース JSON フォーマットへの変換 JSON5 という拡張フォーマットも解析できるようになっている satysfi-aux ファイルにデータを埋めこむときとかに便利（黒魔術） GitHub リポジトリ https://github.com/puripuri2100/SATySFi-json
40. SATYSFIで書かれた構文解析器の紹介 12/17 satysfi-csv CSV フォーマットのパース CSV フォーマットへの変換 改行文字やダブルクオーテーションのエスケープ、区切り文字の変更にも 対応 CSV ファイルを表に変換する csvtable パッケージの裏側に使ってもらっ てる https://satyrographos-packages.netlify.app/packages/csvtable GitHub リポジトリ https://github.com/puripuri2100/SATySFi-csv
41. SATYSFIで書かれた構文解析器の紹介 13/17 satysfi-xml XML フォーマットのパース XML フォーマットへの変換 CDATA セクション (<![CDATA]]>) や参照形式などにも対応 将来的にはこれを使って SVG の解析と自動描画や HTML の解析なども行 いたい GitHub リポジトリ https://github.com/puripuri2100/SATySFi-xml
42. SATYSFIで書かれた構文解析器の紹介 14/17 satysfi-bibtex-parser BibTeX フォーマットのパース アクセント記号にも対応 パースだけをするので、 BiByFi などの参考文献管理用ライブラリへの変換 は個別に必要 最近作ったのでまだ satyrographos に登録できていない …… GitHub リポジトリ https://github.com/puripuri2100/SATySFi-bibtex-parser
43. SATYSFIで書かれた構文解析器の紹介 15/17 satysfi-code-printer 厳密には少し違うが、内部で解析的な何かをするので紹介する コードを綺麗に組版するためのライブラリ 各言語の構文を表す正規表現やマッチするかの判定をする関数を引数に与 える (a) マッチする部分を取得して色を付けてフォントを変える (b) マッチした部分の残りを再度判定関数などに渡す (c) 繰り返す このスライドのコードの組版もこれを使っている GitHub リポジトリ https://github.com/puripuri2100/satysfi-code-printer
44. SATYSFIで書かれた構文解析器の紹介 16/17 今後解析できるようにしたいフォーマット markdown toml yaml
45. SATYSFIで書かれた構文解析器の紹介 16/17 今後解析できるようにしたいフォーマット markdown toml yaml 設定ファイルを解析できると文書についての設定を外部化できたりして面白 そうではあるが、一応 JSON 形式を解析できるので優先度は低い
46. SATYSFIで書かれた構文解析器の紹介 16/17 今後解析できるようにしたいフォーマット markdown toml yaml 設定ファイルを解析できると文書についての設定を外部化できたりして面白 そうではあるが、一応 JSON 形式を解析できるので優先度は低い markdown を解析し SATySFi の文書中に埋めこむことができたらとても面 白いので取り組みたいと思っている。将来的には本体の markdown 機能を 廃止してより抽象かされた機能にできるかも … ？
47. 17/17 まとめ SATySFi でも構文解析ができる 様々なライブラリを作っており、徐々に便利になっている satysfi-json satysfi-csv satysfi-xml satysfi-bibtex-parser satysfi-code-printer 将来的には markdown や svg などにも挑戦していきたい