Pythonで四則演算子を使わない低レベル電卓プログラム

グランバレイ社員のごうだです。

はじめに

最近、コンパイラに興味があり、その勉強の一環としてPythonで四則演算の式をコンパイル（※１）するプログラムを作成してみましたので、そのプログラムの公開と解説を記事にしました。そのため、本タイトルの低レベルというのは低レベルな言語（今回はアセンブリ（※2））を指しています。

※1. コンパイル・・・通常はプログラミング言語で書かれたソースコードを、機械語（※3）や低水準なプログラムに変換することを指します。今回はプログラミング言語のソースコードではなく、単純な四則演算の式（例：1+2*3）をアセンブリに変換しています。

※2. アセンブリ・・・機械語に近い低レベルなプログラミング言語。機械語の命令に1対1で対応しています。アセンブリにはintel記法とAT&T記法の2種類の記法がありますが、今回はintel記法を使っています。

※3. 機械語・・・機械語はマシン語とも呼ばれ、コンピュータが直接理解できる0と1のみで表現されたもの。

ソースコード

今回作成したコードは以下Githubにあげています。

実行環境は以下の通りです。

・x86-64命令セットアーキテクチャ
・Linux（CentOS 7で実行）
・gcc-4.8.5
・Python3.8

Goda-Tetsuya/low-level-calculator

ざっくりとしたコードの流れはこのような感じです。

① 式の読み込み
② 字句解析
③ 構文木作成
④ アセンブリ作成
⑤ 実行ファイル作成
⑥ 実行ファイル実行

本プログラムは四則演算の式を記述したファイルをプログラムに渡すと、その演算した結果が表示されるというものです。

$ echo "1+2*3-4" > expr.txt
$ python3.8 calc.py expr.txt 
Expression: 1+2*3-4
Result: 3

②～④までの字句解析、構文木作成、アセンブリ作成はコンパイラの基礎的な流れになります。

余談ですが、本ソースコードはPythonの四則演算子をいっさい使わないというルールでコーディングしていますので、全く役には立ちませんが不毛な試行錯誤をしています。

それでは解説していきます。

①式の読み込み

式の読み込みはread_file(fname)という関数で行っています。

def read_file(fname):
   expr = ''
   with open(fname, 'r') as f:
       for c in f.read():
           if c == '\n':
               break
           expr = f'{expr}{c}'

   return expr

②字句解析

字句解析とは、文字列を字句（※4）に分割し、それぞれの字句がどういう意味を持つのかを明らかにすることです。今回は四則演算の文字列が対象なので、数値と演算子に分割できればOKです。

今回、字句解析はtokenize(expr)という関数で行っています。

このtokenize関数に式を渡すと、式を数値や演算子で分離します。例えば"1+2*34"という文字を渡すと以下のような戻り値を返します。

[
    { type: 数値, 　num: 1,    op: None },
    { type: 演算子, num: None, op: '+' },
    { type: 数値, 　num: 2,    op: None },
    { type: 演算子, num: None, op: '*' },
    { type: 数値, 　num: 34,   op: None },
]
※字句はディクショナリのように見えますが、実際はクラスのオブジェクトで実装

※4. 字句・・・それ以上、意味的に細かく分割できない文字列のこと。例えば「100」という文字列は100という数値的な意味を持ち、これ以上分割すると「1」, 「0」, 「0」と意味を成さなくなる。そのため、この場合は「100」が字句になる。

③構文木作成

構文木とは、字句の関係性を木構造で表したものです。

上記の例の"1+2*34"を構文木にすると以下のようになります。

なぜ、このような構文木を作成するのかというと、演算子には優先順位があり加算減算よりも乗算除算を先に行わなければならないからです。この構文木では、"2"と"34"を"*"した結果を"1"に"+"にするということを表します。

式には括弧「( )」'を使ってさらに優先度を決めることもできますが、今回のソースコードは括弧には対応していません。

なお、構文木の作成はcreate_tree(tokens)という再帰関数を使っています。

④アセンブリ作成

アセンブリ作成は、ここではあまり深く解説しません（私が勉強中のため）が、数値をCPUのレジスタ（※5）に登録し、各演算子に対応した操作（加算:add、減算:sub、乗算:imul、除算:idiv）を行い、結果を取得するイメージです。

create_asm(tree, asm_name)という関数で、内部的にwrite_asm(node, f)という再帰関数を使って木構造をアセンブリに置き換えています。

また、演算結果はret命令でリターンコードとして返すようにしています。

※5. レジスタ・・・CPUに内臓されている記憶装置。CPUはこのレジスタから直接データを取り出し、演算を行い、その演算結果を再びレジスタに格納するという動作を行っている。また、演算結果の格納だけではなくメモリのアドレスなども格納している。

⑤実行ファイル作成

④で作成したアセンブリファイルをassemble(asm_name, bin_name)という関数内で、gccを使用して実行ファイルに変換しています。

subprocess.run(['gcc', '-o', bin_name, asm_name])

⑥実行ファイル実行

実行ファイル実行はその名の通り、⑤で作られた実行ファイルを実行するのみです。なお、演算結果は実行ファイルのリターンコードから取得できますので、リターンコードをそのまま演算結果としてprintします。

以上です。

最後に

日々の業務ではPythonを使っていますが、低レベルな知識も習得したいと思い、今回このようなプログラムを作成しました。まだまだ勉強中ですが、知れば知るほどCPUやメモリの知識のみならず、プログラミングの歴史や先人の知恵に触れることができ、大変面白いと思っています。（例えば今回使った字句解析や構文木なども先人が考え出したものです。）

ゆくゆくは独自言語のコンパイラを実装してみる！というのが目標です。

※グランバレイにご興味のある方はこちらをご覧ください！