mizdra's poem

雑なこと (日記/技術ポエム/メモ/…) を書くブログです. 真に受けないでください.

2018-12-10

ゆかりスロット

www.mizdra.net

1ヶ月前に作ったアプリをゆゆ式 Advent Calendarで紹介したらバズってTwitterのトレンドに載ったり*1, 有名な漫画家の方々に遊んでもらったりした*2*3 *4. とにかく自分の想像以上に色んな人に遊んでもらえたようで驚いてる. SNSの拡散力はすごいですね.

shiki

自作言語「shiki」とそのインタプリタ開発の話. 今日はGo言語でつくるインタプリタの1章3節〜2章4節を読んだ. 読んだ際のメモを以下に貼っておく.

  • 1章
    • 字句解析について
    • テスト駆動で簡単なトークンから字句解析していく
    • 小さく始めるに当たって, それぞれの文字をどのような粒度でトークンとして扱うかについて決める
    • 数字や複合文字などは1文字ずつ空白まで読むようにする
    • 言語によって空白や改行を無視するなどの戦略を決める
      • その言語にとって意味を持つか持たないかを考えると良い
    • 2文字トークンを実装する際には先読みを用いると良い
    • 言語によるパースの難易度の違いはソースコードを解釈する際に, どの程度先まで読む必要があるかに依存する
  • 2章
    • パーサとは「入力を入力を表すあるデータ構造へと変換する」もので, 変換の過程で入力が期待された構造に従っているかをチェックする
    • 抽象構文木の「抽象」とは
      • セミコロン, 改行文字, ホワイトスペース, 波括弧などのASTとして不要なものを排除するため
    • 今回は「前章で作成した字句解析器の出力」を入力とし, 「インタプリタが要求する仕様を満たすような独自のAST」を出力とする
    • 本書では構文解析法の違いについて詳細に立ち入らない
      • ドラゴンブックなどを参考にする
      • パーサの高速化や正当性に関する形式的な証明, エラーリカバリ, 構文誤りの検出なども行わない

2章はパーサの作り方について書かれているのだけど, 大抵パーサの実装は複雑になりがちなため, 「学習目的のため作成するパーサにどういう機能を実装し, 逆にどういう機能は実装しないのか」について注意深く書かれている点が面白かった. 本書の冒頭の「はじめに」の章でも語られているが, 本書は一貫して「インタプリタがどう動いているか知りたい人向けの, 特定の理論や数学的な知識を前提としない, 学習目的のインタプリタを作る方法」について書かれており, その思想が2章によく反映されている. 例えばletによる代入文やifなどによる制御構文は扱うが, パーサの高速化や正当性に関する形式的な証明, エラーリカバリ, 構文誤りの検出などは扱わない. それらが無くともインタプリタの仕組みを理解するのに十分なので, 意図的に省かれている. それらを省く際にその理由も同時に説明していていて, 何というか, 安心して読めるような内容になっていて良い.

*1:人によってカスタマイズされているので一概には言えないけど, 少なくとも僕のアカウントから見たトレンドには載っていた.

*2:https://twitter.com/mikamikomata/status/1071833085031763968

*3:https://twitter.com/_namori_/status/1071834010211409921

*4:https://twitter.com/1093yuiko/status/1071854769793187841