Cで作る再帰下降構文解析電卓：コンパイラ入門の第一歩

目的

筆者はコンパイルの仕組みに興味があるのですが、いきなり理解することは難しいのでまずは再帰下降構文解析という手法を用いて電卓を作ります。
コンパイラにも使われている手法なので電卓を理解してからコンパイラに挑みます。

実装

gcc test.c -o test

test.c

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

const char *p;  // 入力文字列を指すポインタ

// 前方宣言
int expr();  // 式
int term();  // 項
int factor(); // 因子

// 1文字先読み
int peek() {
    while (*p == ' ') p++;  // 空白跳ばす
    return *p;
}

// 1文字消費
int get() {
    while (*p == ' ') p++;
    return *p++;
}

// 因子: 数字または (式)
int factor() {
    int result;
    if (peek() == '(') {
        get(); // '(' を消費
        result = expr();
        if (get() != ')') {
            printf("エラー: ) がありません\n");
            return 0;
        }
    } else if (isdigit(peek())) {
        result = 0;
        while (isdigit(peek())) {
            result = result * 10 + (get() - '0');
        }
    } else {
        printf("エラー: 数字か(式)が必要です\n");
        get(); // エラーでも次に進める
        result = 0;
    }
    return result;
}

// 項: 因子 (* 因子 | / 因子)*
int term() {
    int result = factor();
    for (;;) {
        if (peek() == '*') {
            get();
            result *= factor();
        } else if (peek() == '/') {
            get();
            int divisor = factor();
            if (divisor == 0) {
                printf("エラー: 0除算\n");
                return 0;
            }
            result /= divisor;
        } else {
            break;
        }
    }
    return result;
}

// 式: 項 (+ 項 | - 項)*
int expr() {
    int result = term();
    for (;;) {
        if (peek() == '+') {
            get();
            result += term();
        } else if (peek() == '-') {
            get();
            result -= term();
        } else {
            break;
        }
    }
    return result;
}

int main() {
    char buf[256];

    printf("C 電卓 (終了: Ctrl+D)\n");
    while (fgets(buf, sizeof(buf), stdin)) {
        p = buf;
        int result = expr();
        printf("= %d\n", result);
    }

    return 0;
}

手で追う

再帰は理解がかなり難しいため、幾つかの計算式を用意して、ソースを追いながら計算をするとよく分かります。
１０回くらいやっていると何となく分かり始めます。

例1: 1+2*3

expr()
 ├─ term()
 │   └─ factor() → 1
 └─ '+' term()
     ├─ factor() → 2
     └─ '*' factor() → 3

例2: (4+6)/2

expr()
 └─ term()
     ├─ factor()
     │   └─ '(' expr()
     │       ├─ term()
     │       │   └─ factor() → 4
     │       └─ '+' term()
     │           └─ factor() → 6
     │       （ここで expr() が 10 を返す）
     └─ '/' factor() → 2

例3: (1+2*(3+4))

expr()
 └─ term()
     └─ factor()
         └─ '(' expr()
             ├─ term()
             │   └─ factor() → 1
             └─ '+' term()
                 ├─ factor() → 2
                 └─ '*' factor()
                     └─ '(' expr()
                         ├─ term()
                         │   └─ factor() → 3
                         └─ '+' term()
                             └─ factor() → 4
                         （ここで expr() が 7 を返す）
                 （ここで term() が 2*7=14 を返す）
             （ここで expr() が 1+14=15 を返す）

動作確認

動作環境（Linux / ARM 版）

• OS: Armbian 23.08.0-trunk (Debian 12 Bookworm)
• Kernel: Linux 6.1.38-meson (armv7l)
• CPU: ARM Cortex-A5, 4 cores, Little Endian
• GCC: 12.2.0
• Architecture: armv7l
• 備考: Windows10からSSH接続して使用

動作環境確認コマンドは以下の通り

uname -a
cat /etc/os-release
gcc --version
lscpu