どうも、新 1 年生の爆発オチです。 皆さん、「プログラミング」ってやってますか？この記事を見ている人なら最低でもやったことはあると思います。
プログラミングでは、「プログラミング言語」と呼ばれる特殊な言語を使ってモノを制作しますよね？じつは、もとを辿ればアレも人が制作したモノなのです。当然プログラミング言語を作るのは難しいわけですが、つくりが簡単な言語は意外にもあっさりと出来てしまいます。
というわけで、今日は、簡易的なインタプリタ型[1] のプログラミング言語の制作方法を、段階的に作っていくことで ざ～っくりと解説してみようと思います。
0. はじめに
0.1
今回の制作では、以下に示すような言語を作ることができます。 (画像) この自作言語で書いたプログラムで、カメを自由に動かす (タートルグラフィクス) ことを目標とします。
0.2 環境
今回の制作では、以下の環境を用います。
- 言語: Python 3.12
- OS: Windows 11 (mac だとたいへん)
1. 計算式の実行 : 逆ポーランド記法
1.1 逆ポーランド記法とは
それではさっそく手を動かして作っていきましょう。プログラムを動かすときに難しいのは、「文章の意味を解釈して実行しなければならない」ということです。作りては、「こことここの括弧が対応して...」「実行順序はこうで...」と考えながらプログラミングするわけですが、できたプログラムはただ文字が並んだテキスト。これの意味を上手いこと解釈しないと動かすことはできません。
そのうえで、まず最初の壁は「計算式の解釈」です。ふつうの計算式は「括弧の中が先」「掛け算・割り算が先」など、様々なルールがあります。先程言ったように、プログラムとはただの文字列ですから、このルールを満たす実行機械を作るのは簡単ではありません。
(画像)
そこで登場するのが「逆ポーランド記法」です。
一般的な計算式... ここでは足し算を例に取りましょう。足し算の式を書くときには、「足す数 + 足される数」というふうに書きます。足し算の操作対象となる数 (これを被演算子という) 用意して、そこに「+」という操作を適用することが足し算なのです。また、この「+」のように、どのような操作を行うかを表す記号を「演算子」といいます。
ところが、逆ポーランド記法では、「足す数 足される数 +」のように書きます。つまり、被演算子を先に置き、最後に演算子を書くのです。例えば
(画像)
1.2 逆ポーランド記法の実行 : スタック
なぜ逆ポーランド記法で計算式を記述するとよいのかというと、計算順序の解析が不要になるためです。そのために、ひとつのテクニックを使います。それは「スタック」というデータ構造です。 スタックとは、複数のデータを入れられる配列のような構造です。ただし、データを追加するときは入れてあるデータの上に積み、取り出すときは一番上のデータから取り出します。箱を積み上げていってる[2] 様子を想像するとイメージしやすいでしょう。
(画像)
スタックを用いて、逆ポーランド記法の計算式の解釈を行うと、面白いことが起こります。「前から 1 単語ずつ見ていく」 「被演算子が来たらスタックに積み上げる」 「演算子が来たら、スタックから値を2つ取り出して演算して、結果をスタックに積む」というルールに従って値の操作を行うと、逆ポーランド記法の計算式の答えを求めることができてしまうのです。
(画像)
ここでポイントなのは、一般的な計算式なら計算順序を考えなければならなかったところ、逆ポーランド記法 + スタック だと前から実行するだけで、計算できてしまうことです。どのような複雑な計算式でも、逆ポーランド記法にすれば前から操作していけば勝手に答えを求められます。
1.3 逆ポーランド記法計算機の実装
前から見ていくだけで実行できるというのは非常にありがたい性質です。先述のように、プログラムは「ただの文字列」で与えられますから、計算式の実行には、「ひとつの文字列をトークン(語句)に分解」 → 「演算順序の決定」 → 「演算」 という手順を踏む必要がありますが、逆ポーランド記法の式では前から実行すると絶対に正しい結果になるので、「演算順序の決定」をゴッソリ省けます。前から順番の一択です。
(画像)
というわけで、実際に動くコードを作っていきましょう。まずは「文字列→トークン」への分解作業です。
しかし、ここもラクしちゃいましょう。今回の言語は、「トークンはもともとスペース区切りにしておく」 ということにします。Python には、文字列を区切り文字で区切ってリストにするメソッドがあるので、この操作も1行で済ませられます。
# トークンに分割 (今回はスペースで分けるだけなので簡単)
prog_in_tokens: list[str] = program.split(" ")
「演算」のほうでは、トークンリストから今見ているトークンを取り出して、
プログラムを実行環境に食わせたら、即実行してくれるタイプのプログラミング言語 ↩︎
Stack: [動] [他] 積み上げる https://ejje.weblio.jp/content/stack ↩︎
