Chapter 11

意味解析

takl
takl
2020.12.22に更新

意味解析という題でいいのかわかりませんが…。expand という関数を作ったのですが、これにあれやこれや詰め込みすぎてしまいました。一度に雑に解説します(すみません)。expand のコードはここです。

大雑把にいうと expand という関数は構文木をより抽象的な形に変換する関数です。

parse の入力が (if cond con alt) だったとすると、出力は

{
   kind: "array", ...
   data: [
     { kind: "variable", text: "if", ... },
     { kind: "variable", text: "cond", ... },
     { kind: "variable", text: "con", ... },
     { kind: "variable", text: "alt", ... }
   ]
}

のようになります。expand はこれを更に

{
  kind: "if", ...
  cond:  { kind: "variable", text: "cond", ... },
  con:  { kind: "variable", text: "con", ... },
  alt:  { kind: "variable", text: "alt", ... },
}

のように書き換えます。

色々なことをやるのですが、箇条書きにすると以下のようなことをします。

  • expand() の形式を kind: "unit" である object に変換します(ソース)
  • expandkind: "number" の入力を kind: "number に変換します(ソース)
  • expandkind: "variable" の入力を、そのスコープで定義された変数か調べます
    • 定義されていない変数であったら、診断メッセージを出力します
    • 定義されていたら definition メンバにその定義のあるノードへの参照を代入します
    • ソース
  • expand(if FORMS ...) の形式を expandIf で変換します
    • expandIfif のトークンの kindkeyword に書き換えます
    • expandIf(if COND CON ALT) という形式でなければ診断メッセージを出力します
  • (defun FORMS ...) の形式はexpandDefunで変換されます
    • expandDefundefun のトークンの kindkeyword に書き換えます
    • expandDefun は入力が (defun NAME (PARAMS ...) EXPR ...) という形式でなければ診断メッセージを出力します
      • NAME が variable でなければ診断メッセージを出力します
      • NAME が variable であれば NAME のトークンを function に書き換えます
      • NAME を toplevelScope に登録します
      • PARAMS ... がすべて variable でなければ診断メッセージを出力します
    • expandDefun は 新たにスコープを作成し、引数を登録します
    • 再帰を扱えるように変なトリックを仕掛けています
  • expand(FN FORMS ...) の形式をexpandCallで変換します
    • expandIfFN のトークンの kindfunction に書き換えます

重要なのは以下です。

  • 出力された AST のすべてのノードに firstToken と lastToken がある
    • これによりカーソル位置から AST のノードを検索できる
  • 途中で生成された local の scope をすべて記録してあり、 scope もまた firstToken と lastToken を持っている
    • これによりカーソル位置から scope を検索できる
  • 変数はその定義への参照を持つ
  • ある程度型はつけてしまっている
  • トークンの kind を書き換えている
    • これにより文脈に依存した色付けができる

色付けはこのような感じになります。