【No.1】１時間で完成するミニ言語処理系

言語処理系が作りたいけど、難しそう

プログラミング言語を触っていると、言語処理系（？）が作りたくなりますよね。
ですが、「なんとなく難しそう」と思っておられる方も多いと思います。

それに、作成するのに時間がかかりそうです。
実際、まつもとゆきひろ氏がRubyを開発したときは、"Hello World"ができる処理系を作るまでに半年もかかったようです。（まつもとゆきひろ『言語のしくみ』日経BP社、p51）

難しくて時間もかかる、そうなるとなかなか手が出にくいですよね。

小さく作って、すくすく育てる

そこで、Rubyのような本格的な言語処理系をいきなり作るのではなく、まずは小さくて簡単な処理系を作って楽しもうというのが今回の記事の趣旨です。

この小さい処理系に、どんどん機能を追加して「育ててゆく」ことで、それなりに高機能な言語処理系を作ろうと考えています。

そのため、この処理系のプログラムは「変更に強い」ものである必要があります。
そこで、設計のテクニックを駆使したり、頻繁にリファクタリングを行うことで、変更に強い処理系を目指します。

また、テスト駆動で作ってゆく予定です。

※なお、可能な限り便利なツール（パーサジェネレータとか）は使用しない方針です。
　完成させることだけが目的ではないからです。

デザインパターン「Interpreter」

まず、この記事では1時間で言語処理系を作成します。
言語処理系といっても1時間で完成するものですから、極めて小規模なものです。

参考として使用する本は、「数学ガール」で有名な結城浩氏の『Java言語で学ぶデザインパターン入門　第３版』（以下、結城本）です。

「言語処理系の本じゃないじゃん！」と思われる方もいるかもしれませんが、言語処理系の本ってメチャクチャ難しいですよね。
おそらく、気軽に読めるものではないです（笑）

それに対して、この本は約40ページで「インタプリタ」を作っています。
40ページといっても、みっちり文字（＆謎の記号）が詰まっているわけではないです。
数学ガールのプログラミング版みたいな感じで、スラスラ読めます。ほんとにスゴイ本です。

題名を見ても分かるように、「インタプリタ」みたいなものを作ることでプログラミングの設計を改善するデザインパターンの1種（Interpreterパターン）として紹介されています。

「本格的な言語処理系」とは距離があるものではありますが、まずは簡単なものから作ってみましょう。

以下では、これから作成する処理系の概要を記載しています。

言語処理系の構成

今回は、字句解析器、構文解析器、実行部の３つから構成される言語処理系を作成します。

ざっと、以下のような感じの構成です。

字句解析器：ソースコードを「トークン」の列に変換
構文解析器：「トークンの列」を木構造（抽象構文木）に変換
実行部：木構造の要素をたどりながら、実行する

字句解析器

字句解析器は、ソースコードを「トークン」の列に変換する「装置」のようなものです。
結城本では以下のような超シンプルなものとなっています。

1. ソースコード（文字列）は、単語が空白で区分されている
2. 文字列を空白で区分して、文字列を要素とする配列を作る
   （結城本p392のContextクラスのコンストラクタが字句解析に相当する機能を持つ）

また、結城本や他の本（※）には、外部からのメソッド呼び出しによって、トークン列の要素を提供するメソッドが準備されています。
（※千葉滋『２週間でできる！スクリプト言語の作り方』技術評論社）

今回はそれらを模倣しました。

構文解析器

• 文法規則（BNF）
  今回は結城本のBNFをそのまま使用します。
  最初から自作して苦労＆失敗するより、今は模倣して様子を見ることにします。
  いつか自作できればいいのです。

<program> ::= program <command list>
<command list> ::= <command>* end
<command> ::= <repeat command> | <primitive command>
<repeat command> ::= repeat <number> <command list>
<primitive command> ::= go | right | left

（結城浩『Java言語で学ぶデザインパターン入門　第３版』SBクリエイティブ、p381）

• 構文解析の手法
  再帰下降構文解析が簡単そうなので、これを使用します。

実行部

未定です。

参考文献

結城浩『Java言語で学ぶデザインパターン入門　第３版』SBクリエイティブ、2021年.