トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

Go言語でつくるインタプリタ

[Go]

Go言語でつくるインタプリタ

買ってみた。全部はできないかもしれないけどちょいと触ってみるぞ。

  1章 字句解析

  • 1章が終わった段階でのディレクトリ構成は以下のような感じ
    • token.go の中にまずは全てのキーワード(fn, let, if, else, return)などを登録しておく
    • lexer.go にて、入力されたテキストをトークンに分解する
.
├── README.md
├── lexer
│   ├── lexer.go
│   └── lexer_test.go
├── main.go
├── repl
│   └── repl.go
└── token
    └── token.go

メモ

  • インタプリタはソースコードを2回変換する
    • ソースコード → トークン列 → 抽象構文木(AST)
      • 1章では字句解析、つまり「ソースコード → トークン列」までの手順をやる
  • 字句解析の手順
  1. 読み取りたいトークンを含むプログラム文書を作る
  2. テストに読み取らせる(lexer_test.go)
  3. 失敗
  4. 字句解析に使うトークンをtoken.goで定義する
  5. 解析処理をlexer.goで定義する
  6. テストが通り成功!
  • 所感
    • 意外に簡単な処理で字句解析できるのだとびっくり

  2章 構文解析

メモ

  • インタプリタはソースコードを2回変換する
    • ソースコード → トークン列 → 抽象構文木(AST)
      • 2章では構文解析、つまり「トークン列 → 抽象構文木(AST)」までの手順をやる
  • Pratt構文解析
    • コンピュータサイエンスでは、Prattパーサは、文法規則ではなくトークンとセマンティクスを関連付ける改良された再帰的降下構文解析器です。ヴォーン・プラットは、1973年の論文「Top down operator precedence」で最初に記述され、彼の監督下でマスターズ・テーゼでより深く扱われました。 Prattは、もともとCGOLプログラミング言語を実装するようにパーサーを設計しました。 Douglas Crockfordはこの技術を使ってJSLintを構築しました。
  • 構文解析のための構造
    • Node, Statement, Expressionインターフェイスを作る
    • 全てのインターフェイスはNodeを保持するようにする
    • これらの構造はすべてast.goの中に定義する

文(Statement) の構文解析

  • Monkey言語はlet, returnしか文を持たないので、それを解析するパーサーを書く
    • 補足しておくと、それ以外の文はすべて式文(ExpressionStatement)と解釈される

’’’文(Statement)が保持する要素'''

式(Expression) の構文解析

  • Monkey言語の他の殆どの要素は式であるので、それを解析していく
  • 式(Expression)の解析の際、最も困難なのはネストした演算子とその優先順位であろう。Pratt構文解析はそれを解決する。
    • 具体的にはTokenに対応するParserを用意しておき、前置演算子・中置演算子・後置演算子のジャンルごとにそれを解析する

それぞれの演算子のイメージ

  • 前置演算子
    • +5 , -5, !bool など
  • 中置演算子
    • (5 + 5), (5 - 5), (5 * 5), (5 / 5) など
  • 後置演算子
    • inc++, dec-- など、Rubyの後置ifなどもこれに入るのだろうか
    • Monkey言語には後置演算子はない、なのでインクリメントはできない

  3章 評価

  4章 インタプリタの拡張

お名前: コメント: