CA Tech Lounge Advent Calendar 2023の20日目の記事です。
本記事は書籍から学んだインタプリタについてその概要とそれを実装に落とし込む考え方について記述しています。
詳細なコードはぜひ公式のものを見てみてください👀
はじめに・自己紹介
私はCA Tech Lounge 2期生でバックエンドの勉強をしている大学生です。
専門は機械学習ですが、CS系の学部・学科ではないため自分でCSの勉強をしてみようかなと思いインタプリタを作ってみました！
そもそもなんでインタプリタなの？と思われる方もいると思うのですが、これはCS系を専攻している友人が授業でインタプリタ・コンパイラを作成しているという話を聞いて興味を持ったからです！ちょうどGoを勉強中なのでWriting An Interpreter In Goはちょうどど真ん中な本でした。
本の概要としてはGo言語を使用してMonkeyという独自の言語のインタープリタを実装していくものになります。コードは本に付属しているので、本に書いてあるアイデアをまとめてインタープリタについて紹介する記事にできればと思います！
「インタプリタ」って？？
インタプリタって何??って思われる方もいると思うのでインタプリタについて説明します。
インタプリタの概要
インタプリタは簡単に言えばソースコードを機械が処理可能にするためのものです。インタプリタは1行ずつ翻訳を行いながら実行していくものになります。その中では、コードをトークンに変換し、それを木構造に落とし込むという過程が含まれています。詳細は後ほど！
こちらはイメージ図であり「機械語に翻訳する」というのは誤りです。詳しくはこちらの方の記事を見てください。
https://qiita.com/ko1nksm/items/cdb6744ea72d46934c56
詳細
入力が(2-1)*4+3である場合についてそれぞれの動作などを確認してみましょう。
字句解析
字句解析では、ソースコードを小さな意味のある単位であるトークンに分割します。ソースコードを前から順に一文字ずつ読み込み、それぞれの文字や文字列がどのような意味を持つのかを解析します。具体的には、各文字が識別子（変数名や関数名など）、キーワード（if、let, returnなどの予約語）、リテラル（数値や文字列リテラル）、演算子（+、-、*、/など）、区切り文字（セミコロンやカンマなど）などを識別します。
流れ
構文解析
構文解析では字句解析によって得られたトークンをもとにして抽象木(Abstracted Syntax Tree)を作成します。構文解析の目的は、ソースコードが言語の文法に従っているかどうかを確認し、プログラムの意味を正確に解釈するための構造、抽象木(AST)を構築することです。
ASTは、ソースコードの文法的な構造を反映する木構造のデータ形式で、プログラムの構成要素（変数宣言、代入、制御構造等）とその関係を表します。
再帰下降構文解析は、構文解析を行うための一つのアプローチで、最上位の文法規則から開始して、入力されたトークン列に対して文法規則を再帰的に適用していきます。
流れ
- 括弧の処理
- 最初に入力を左から読み進め、左括弧 ( を見つけます。
- 括弧内の式 (2-1) に対して再帰的に構文解析を行い、その部分式のASTを構築します。
- 基本式の構築
- 括弧内には 2-1 という式があります。2 と 1 は数値トークンで、- は減算演算子トークンです。
- これらのトークンから、- を親ノードとし、2 と 1 を子ノードとするASTのサブツリーを構築します。
- 演算子の優先順位と結合性
- 残りの部分に対して、演算子の優先順位と結合性に基づいてASTを構築します。
- 乗算 * は加算 + よりも優先順位が高いので、次に * と 4 を含むサブツリーを構築します。
- 最終的に、加算 + と 3 を含むノードを構築します。
- ASTの完成
- 上記のステップで構築されたサブツリーを結合して、最終的なASTを完成させます。
- このASTは、入力された式の構造的な表現となります。
評価
Evaluatorは、Parserによって生成されたASTを評価し、プログラムの結果を生成します。
ASTを再帰的に歩き回り（tree-walking）、各ノードを評価します。この過程で、算術演算が実行され、変数に値が割り当てられ、式が評価されます。
流れ
- まず 2-1 を評価し、結果は 1 になります。
- 次に、1*4 を評価し、結果は 4 になります。
- 最後に、4+3 を評価し、結果は 7 になります。
これにより、入力された式 (2-1)*4+3 の評価結果として 7 を得ることができます。
感想
実際に自分が自分が普段書いているコードがどのようにして実行されているのかを知ることができて面白かったです。解説も丁寧な本なのでぜひCS専攻でなくてもオススメしたいです！英語版で読んだのでいいリーディング練習にもなりました。ぜひ皆さんも英語版で！！
この本のコンパイラ版、"Writing A Compiler In Go"もあるので、こちらにも取り組んでみようと思います。
参考
- Interpreter
英語版：Writing An Interpreter In Go
日本語版：Go言語でつくるインタプリタ - Compiler
英語版：Writing A Compiler In Go
日本語版：今の所日本語版はなし🥲