C言語での電卓の作り方～「コンパイラ」を読んでみた～

2019-11-02追記

yoctoのサンプルプロジェクトようにこの記事のコードを使って試していたらいくつかバグがありましたので修正しました。
具体的には本記事のコードでマイナスがうまく扱えていませんでした。
例えば、

./calc "3 - 3 + 3"

のような計算がうまくできていませんでした。

修正したコードを含めたものを

github.com

に挙げております。
記事中のコードはそのままとしておりますので参考にされる方はご注意ください。

記事本文

随分と前の話ですが、「小飼弾のコードなエッセイ」を読んで、「C言語でもevaりたい」という記事を書きました。

mcommit.hatenadiary.com

そちらの記事でも書きましたが、この本の最初のエッセイに、

「堂々とevaろう。でもevaりすぎにご用心。」

というエッセイがあって、evalの便利さについて語られているのですが、私が書いた記事ではC言語でevalっぽいことをしてみるという記事を書いていました。

その際に、eval的なことをせずに、C言語でガリガリと電卓を書いてみたのですが、結果としてあまりうまく書けていませんでした。

特に演算子の優先順位に対応できておらず、また対応させる為にはかなり面倒なコードを書かないといけないと思っていました。※あるいはflexやbisonを使えば比較的行数も少なくは実装はできますが。

このevalの記事を書いたのは3年以上前の話なのですが、最近になって(挫折していた)コンパイラ自作の勉強を再開してみて、C言語でもう少しまともに電卓を書く方法が分かったので記事として書いておきたいと思います。

2019-11-02追記
記事本文
書いてみた電卓プログラム(C言語)
なぜ電卓プログラムを書いてみたか？
- 文字列(式）の解析について
  - なぜ挫折したのか？
感想
構文解析の実装
余談

書いてみた電卓プログラム(C言語)

コード

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>

int vals[32];
int vals_len = 0;

char exps[32];
int exps_len = 0;

void push_value(int exp);
void pop_value(int *exp);
void push_exp(char exp);
void pop_exp(char *exp);

int calc(char *str);
int exec_calc(char exp, int val1, int val2);
int val_strlen(char *str);

int test_calc(void);
int main(int argc, char **argv) {
    int ret;
    // =====================================================
    // calc test
    // =====================================================
    ret = test_calc();
    if (ret == 0) {
        fprintf(stdout, "All test passed...\n");
    }
    return 0;
}

int calc(char *str) {
    int result;
    char *pos;
    int ret;
    int len;
    int tmp, val1,val2;
    char exp;

#if DEBUG
    fprintf(stdout, "str:%s\n", str);
#endif

    pos = str;
    while(*pos) {
        switch (*pos) {
        case '(':
            push_exp(*pos);
            pos++;
            break;
        case ')':
            while(0 < exps_len) {
                pop_exp(&exp);
                if (exp == '(') {
                    // TODO かっこの対応チェックはしていない
                    break;
                }
                pop_value(&val2);
                pop_value(&val1);
                ret = exec_calc(exp, val1, val2);
                push_value(ret);
            }
            pos++;
            break;
        case '*':
        case '/':
        case '+':
        case '-':
            push_exp(*pos);
            pos++;
            break;
        case ' ':
            // 空白はスキップ
            pos++;
            break;
        default:
            if (isdigit((int)*pos)) {
                // 数字部分の文字列長を求める
                len = val_strlen(pos);
                tmp = atoi(pos);
#if DEBUG
                fprintf(stdout, "tmp:[%d]\n", tmp);
#endif
                push_value(tmp);
                if (exps_len) {
                    // 演算子の優先度をチェック
                    if ((exps[exps_len -1] == '*') || (exps[exps_len -1] == '/')) {
                        pop_value(&val2);
                        pop_value(&val1);
                        pop_exp(&exp);
                        ret = exec_calc(exp, val1, val2);
                        push_value(ret);
                    }
                }
                pos += len;
                continue;
            } else {
                fprintf(stderr, "syntax error [%c]\n", *pos);
                return -1;
            }
        }
    }

    while(0 < exps_len) {
        pop_exp(&exp);
        if (exp == '(') {
            // TODO かっこの対応チェックはしていない
            continue;
        }

        pop_value(&val2);
        pop_value(&val1);
        ret = exec_calc(exp, val1, val2);
        push_value(ret);
    }

    pop_value(&result);
    return result;
}

int exec_calc(char exp, int val1, int val2) {
    int result;

#if DEBUG
    fprintf(stdout, "calc: %d %c %d \n", val1, exp, val2);
#endif

    switch (exp) {
    case '+':
        result = val1 + val2;
        break;
    case '-':
        result = val1 - val2;
        break;
    case '*':
        result = val1 * val2;
        break;
    case '/':
        result = val1 / val2;
        break;
    default:
        fprintf(stderr, "Unkown exp [%c]\n", exp);
        break;
    }

#if DEBUG
    fprintf(stdout, "calc result:[%d]\n", result);
#endif
    return result;
}

int val_strlen(char *str) {
    int len = 0;
    while(isdigit((int)*str)) {
        len++;
        str++;
    }
    return len;
}

void push_value(int val) {
    vals[vals_len] = val;
    vals_len++;
    return;
}

void pop_value(int *val) {
    *val = vals[vals_len - 1];
    vals_len--;
    return;
}


void push_exp(char exp) {
    exps[exps_len] = exp;
    exps_len++;
    return;
}

void pop_exp(char *exp) {
    *exp = exps[exps_len - 1];
    exps_len--;
    return;
}

int test_calc(void) {
    int ret;
    ret = calc("2 * 2 * 3");
    assert(ret == 12);

    ret = calc("2 * 8 / 2");
    assert(ret == 8);

    ret = calc("(1 + 3) * 8 / 2 + 5");
    assert(ret == 21);

    ret = calc("(1 + 3) * 8 / 2 + 5 * (3 + 3)");
    assert(ret == 46);

    ret = calc("((1 + 2) * 3) + (2 * 5)");
    assert(ret == 19);

    ret = calc("((1 + 2) * 3) + (2 * 5) - 9");
    assert(ret == 10);

    ret = calc("((1 + 2) * 3) + (2 * 5) - 19");
    assert(ret == 0);

    ret = calc("((1 + 2) * 3) * ((2 * 5) - 19)");
    assert(ret == -81);

    ret = calc("((1 + 2) * 3) * ((2 * 5) - 10)");
    assert(ret == 0);
    return 0;
}

コンパイルと実行



$gcc -Wall -o calc

$./calc

デバッグ用の出力をする場合は



$gcc -Wall -o calc -DDEBUG

で計算の途中経過が表示されます。

内容について

calc関数が文字列を解析して計算を行う関数です。
呼び出し方は、test_calcを参考にしてください。

上記のコードは簡単なテストコードを含めて200行と少し、電卓本体だけで180行程度になります。

テストケースは思いつきレベルなので、いろいろ試してみたら失敗する式もあるかもしれませんが、何も勉強せずにかいた電卓よりまともな電卓としてかけたと思います。

電卓の本質は、

演算子の優先順位を考慮した処理を書くこと
スタックをうまく使うこと

につきるような気がします。

ちなみに上記の電卓は、整数のみを対象としており、式の文字列がおかしい場合などの考慮はしておりません。要するにエラーチェックなど、電卓の本質的でないと思える部分は適当に書いていますのでその辺はあまり突っ込まないでください(m_m)

解析に使うスタックの要素数も32固定としております。

なぜ電卓プログラムを書いてみたか？

最近になって、挫折していたコンパイラ自作の勉強を久しぶりに再開して、コンパイラの権威でいらっしゃる中田育男先生の「コンパイラ」を読んでみました。

上記の電卓のコードは、書籍にかかれていたスタックを使った構文解析の復習兼検証という意味で書いてみました。

スタックを使うだけで、ガリガリと文字列解析をすることなく電卓の計算が実装できることを知らなかったので「コンパイラ」は読んでみてすごく勉強になりました。

コンパイラ (新コンピュータサイエンス講座)

作者: 中田育男
出版社/メーカー: オーム社
発売日: 1995/06/01
メディア: 単行本
購入: 7人クリック: 44回
この商品を含むブログ (13件) を見る

文字列(式）の解析について

上記の書籍「コンパイラ」の「第2章コンパイラの簡単な例」に数式の後置記法を使った構文解析について書かれています。
私達が日常的に使っている数式は演算子が数と数の間に来る「中間記法」という記法になるのですが(例 1+2, 3-1 +や-は1や2の間にかかれる)、後置記法では
1+2→12+
3-1→31-
のように数の後ろに演算子を書きます。

後置記法はプログラムで計算をするのに適しているので、式の解析においては、中間記法を後置記法に変換しつつ計算を行うやり方について本書で説明されています。
※そういえばlispは(+ 1 3)のように前置記法ですが、式を解析するプログラムを書く場合同様に扱いやすい表現になりますね。

なぜ挫折したのか？

電卓の実装からは少し話がそれますが、コンパイラを自作する上で私が挫折していたのは、何を隠そう「構文解析」の部分でした。
「構文解析」はコンパイラにおけるフロントエンドとも呼ばれるフェーズで、コンパイラ製作のかなり入口付近で挫折していたことになります（あぁすごく恥ずかしい・・・)

構文解析で私が挫折していた理由ですが、

実装してみたもののこれが正解なのか分からない
抽象構文木(AST)を作る理由(目的)が理解できていない
抽象構文木を作らずに構文解析を行っている人(ソース)もあって何が正しいのかわからない
文法によっては構文解析部分が複雑化する

などなど、まぁできない言い訳と愚痴がたまってしまい自然と挫折してしまいました。

そもそも、今回の電卓の話のように、コンパイラ開発の基礎や作法みたいなものは確立されているのですが、そういった基礎がないまま・基礎を理解しないままコンパイラを作ろうとしているので挫折してしまって当然と言えば当然かも知れません。

中田先生の「コンパイラ」はパッと見大学の教科書風のオーラが漂っているのですが、書いてある内容はかなり分かりやすく丁寧に書かれていました。

特に上記の構文解析については他の書籍ではかかれていない、

「なぜそういう手法を取るのか」

という次元で説明が書かれていたので私にとっては目からうろこでした。

挫折していた私の場合、構文解析における定石を理解しないまま、ゴリゴリと我流で処理を書こうとして、どつぼにはまっていたという事になると思います。

後置記法によって式(文字列)を解析し計算すると書きましたが、後置記法と言っても、実際のコード上での表現は「スタック」というデータ構造をうまく使って解析を行うことになります。

スタックなんてプログラマは皆日常的に利用しているのですが、私自身スタックが持つ性質を理解できていなかったことを教えられた気がします。
特に、構文解析に便利なデータ構造だという認識は有りませんでした。やはり基礎的部分、本質的な部分の知識や理解がないとだめですね・・・(涙)

感想

電卓に限らないですが、C言語でコードを書くといろいろ書かないといけないコードが出てきて、結果としてコード量が多くなってしまいますね。

上記の私のコードですと、文字列→数値変換はatoiを使って手抜きをしているのですが、2桁以上の数字を変換する際に、解析位置のポインタ(pos)を進める処理を間違えてしまいました。

atoiで変換した桁数分だけ、解析位置も進めないといけないのですが、当初のコードではポインタを進める際に単純に、



pos++

と書いており、2桁以上の数値を扱う式ではうまく動きませんでした。

あわてて桁数を調べる即席の関数(val_strlen)を書いてその場をしのぎました。

atoiやisdigitのような関数も利用しないとなると更に自作部のコードは増えることになります。

あと、コードを見て頂ければ分かる通り要所要所にデバッグ用のfprintfを入れております。
上記のatoiのようなミスを別にしても、こういう解析系の処理ってなかなか一発で思うようには書けませんね・・・

構文解析の実装

C言語では上記の通りコード量が増えるので、rubyを使ってコンパイラ(ネイティブのコードを吐くC言語風の言語)を作ろうと、電卓のような「数式」ではなく「プログラム」を解析する部分を書いてみました。
勉強のお蔭もあってか以前より構文解析のコードは綺麗にかけたので、次のフェーズに進もうと思っているのですが、試しに解析結果をいきなりマシン語におとそうとしてまた足踏みしています。