中置記法から S 式への変換

中置記法からS式への変換 - みずぴー日記 にインスパイヤされて、再帰降下型パーサを使って中置記法から S 式へ変換してみます。

Amazon.co.jp: プログラミング言語AWK: Alfred V.Aho, Brian W.Kernighan, Peter J.Weinberger: 本 には既に再帰降下型パーサを使った中置記法のパース方法が書かれていますので、これにしたがって記述します。

# /usr/local/bin/nawk -f
# i2s.awk
# 中置記法を S 式に変換する
# usage: nawk -f i2s.awk

BEGIN {
    print i2s("1 + 2 * 3 - 4 / 5");
    print i2s("( 1 + 2 ) / 3");             # 括弧にも対応
}

function i2s(eqn) {
    split(eqn, term);
    i = 1;

    return expr();
}

# expr():   足し算と引き算
function expr(    e) {
    e = terms();                            # 掛け算と割り算を先に処理
    while (term[i] == "+" || term[i] == "-") {
        e = term[i++] == "+" ? "(+ " e " " terms() ")" : \
                               "(- " e " " terms() ")";
    }

    return e;
}

# terms():  掛け算と割り算
function terms(    e) {
    e = factor();                           # 括弧と数値を先に処理
    while (term[i] == "*" || term[i] == "/") {
        e = term[i++] == "*" ? "(* " e " " factor() ")" : \
                               "(/ " e " " factor() ")";
    }

    return e;
}

# factor():     数値と括弧
function factor(    e) {
    if (term[i] ~ /^[+-]?([0-9]+[.]?[0-9]*|[.][0-9]+$)/) {
        return term[i++];
    } else if (term[i] == "(") {
        i++;
        e = expr();

        if (term[i++] != ")") {
            printf("error: missing ) at %s\n", $f);
        }

        return e;

    } else {
        return 0;
    }
}

処理する順序に注意して、expr -> terms -> factor と分解していきます。 では、実行してみます。

$ nawk -f i2s.awk
(- (+ 1 (* 2 3)) (/ 4 5))
(/ (+ 1 2) 3)

S 式を扱う言語でも四則演算は構文糖衣 (シンタックスシュガー) で中置記法が使えるものもあるようですが、こうして S 式で記述すると人間には分かりにくいです。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png