再帰下降法でC言語のパーサもどきを作る

追記（2018/11/20）

動作しなかった「ネストされたカッコのある数式」「優先順位が同じ演算子が全て右結合になってしまう」などの不具合を修正しました。一番下に修正した点とコードを載せておきますので、ご確認いただければと...。修正版はこちら

目的

今回の目的は、数式の構文解析を行うことのできる、パーサーを作ることです。最近では、構文解析を作成する際にはlex+yacc（flex+bison）などを用いることが多いですが、今回は再帰下降法を用いたパーサーを作ります。ただ、対応できていない部分などもなるので、コメントなどで対策を教えていただけるとありがたいです...。

基本的な流れとしては、BNF記法に基づいて言語の文法を表現してから、それをコードに落とし込みます。

BNF（バッカスナウア記法）

構文解析を行うにあたって、以下のようなBNF文法を作成しました。

※ 築城にもあるように、修正にてBNFが修正されています。修正版はこちら

/**
 * バッカスナウア記法(BNF)
 *
 * ## 式は項のみ or (+, -)演算子を含む式 ##
 * expr ::= term
 *        | term '+' expr
 *        | term '-' expr
 *        ;
 *
 * ## 項は因子 or (*, /)演算子を含む項 ##
 * term ::= factor
 *        | factor '*' term
 *        | factor '/' term
 *        ;
 *
 * ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
 * factor ::= DIGIT
 *          | VARIABLE
 *          | VARIABLE OPERATOR expr
 *          | '(' expr ')'
 *          ;
 *
 * ## 数値 ##
 * DIGIT ::= [0-9]+ ;
 *
 * ## 変数名 ##
 * VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
 *
 * ## 演算子 ##
 * OPERATOR ::= '='
 */

再帰下降パーサ

expr

/**
 * ## 式は項のみ or (+, -)演算子を含む式 ##
 * expr ::= term
 *        | term '+' expr
 *        | term '-' expr
 *        ;
 *
 * @param pc   解析する文字列の先頭
 * @param endp 解析が終わった場所
 * @return     計算結果
 */
int expr( const char* pc, const char** endp ) {

    // 1文字目（必ずtermに属する）を取得する
    int left = term( pc, endp );

    while( true ) {
        if ('+' == **endp)
        {
            // ＋1は '+' 分ずらす
            int right = expr( *endp + 1, endp );
            return left + right;
        }
        else if ('-' == **endp)
        {
            // ＋1は '-' 分ずらす
            int right = expr( *endp + 1, endp );
            return left - right;
        }
        else if (isspace(**endp))
        {
            *endp += 1;
        } else { break; }
    }
    return left;
}

term

/**
 * ## 項は因子 or (*, /, '%')演算子を含む項 ##
 * term ::= factor
 *        | factor '*' term
 *        | factor '/' term
 *        | factor '%' term
 *        ;
 *
 * @param pc   解析する文字列の先頭
 * @param endp 解析が終わった場所
 * @return     計算結果
 */
int term( const char* pc, const char** endp ) {

    // 1文字目（必ずfactorに属する）を取得する
    int left = factor( pc, endp );

    while( true ) {
        if ('*' == **endp)
        {
            // ＋1は '*' 分ずらす
            int right = term( *endp + 1, endp );
            return left * right;
        }
        else if ('/' == **endp)
        {
            // ＋1は '/' 分ずらす
            int right = term( *endp + 1, endp );
            return left / right;
        }
        else if ('%' == **endp)
        {
            // ＋1は '%' 分ずらす
            int right = term( *endp + 1, endp );
            return left % right;
        }
        else if (isspace(**endp))
        {
            *endp += 1;
        }
        else { break; }
    }
    return left;
}

factor

/**
 * ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
 * factor ::= DIGIT
 *          | VARIABLE
 *          | VARIABLE OPERATOR expr
 *          | '(' expr ')'
 *          ;
 *
 * @param pc   解析する文字列の先頭
 * @param endp 解析が終わった場所
 * @return     計算結果
 */
int factor( const char* pc, const char** endp ) {

    *endp = pc;

    switch(**endp) {
        case '(': {          
            // カッコ分読み飛ばし
            *endp += 1;
            // カッコ内の式を解析
            int innerExprValue = expr( *endp, endp );

            /**
             * この部分うまく動かなかったから、以下のように修正
             *  
            // カッコの終わりまでポインタを進める
            while( true ) {
                if (')' == **endp) break;
                *endp += 1;
            }
            */

            // カッコとじまでポインタを進める
            while( true ) {
                // カッコ閉じなら
                if (')' == **endp) {
                    // カッコ分飛ばし
                    *endp += 1;
                    // pcに文字列コピー
                    pc = *endp;

                    // カッコ内の演算結果を文字列に
                    string valstr = to_string(innerExprValue);
                    char* cstr = new char[valstr.size() + 1]; // メモリ確保
                    std::strcpy(cstr, valstr.c_str());        // コピー

                    // 現在の文字列の先頭に計算結果を連結
                    char* tmps = strcat(cstr, pc);

                    // tmp文字列用のメモリ開放
                    delete[] cstr; // メモリ解放

                    // 連結後の文字列をpcに代入
                    pc = tmps;

                    // 解析済み文字列にも同様のものを代入
                    *endp = pc;

                    // 残りの数式の解析
                    int tmp = expr(pc, endp);

                    // 演算結果を返す
                    return tmp;
                } else {
                    *endp += 1;
                }
            }
        }

        default:
            return digit( pc, endp );
    }
}

DIGIT

/**
 * ## 数値 ##
 * DIGIT ::= [0-9]+
 *         ;
 *
 * @param pc
 * @param endp
 * @return
 */
int digit( const char* pc, const char** endp ) {

    // 数値文字列の変数
    string number;

    *endp = pc;

    // 数字が続くだけ続ける
    while ( true ) {
        if ( isdigit(**endp) )
        {
            // 文字列に追加
            number.push_back(**endp);
            // カウンタをインクリメント
            *endp += 1;
        }
        else if ( isspace(**endp) )
        {
            *endp += 1;
        }
        else if ( ('_' == **endp) || isalnum(**endp) ) {
            return variable( pc, endp );
        }
        else break;
    }

    // 数値文字列が空かどうか
    if (number.empty()) {
        // 空なら0を返す
        return 0;
    } else {
        // 0以外は数値を返す
        return stoi(number);
    }
}

VARIABLE, OPERATOR

/**
 * ## 変数名 ##
 * VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
 */
int variable( const char* pc, const char** endp ) {

    // 変数名の取得
    string name;

    *endp = pc;

    // 変数名を１文字ずつ取得
    while ( true ) {

        // 変数名かどうか
        if (isdigit(*pc)) {
            printf("Error. variant first letter must not number.");
            exit(0);
        }

        if ( ('_' == **endp) || isalnum(**endp) )
        {
            // 文字列に追加
            name.push_back(**endp);
            *endp += 1;
        }
        else if ( isspace(**endp) ) {
            *endp += 1;
        }
        else break;
    }

    // 変数名が空かどうか
    if (name.empty()) {
        //　空なら0を返しておく
        return 0;
    }
    else {
        if ('=' == **endp) {
            // '='の分を進める
            *endp += 1;
            pc = *endp;
            int result = expr(pc, endp);
            varStack[name] = result;
            return varStack[name];
        }
        else
        {
            // 変数スタックにキー[name]が登録されていない
            if (varStack.find(name) == varStack.end() ) {
                printf("Variant %s is undefined.\n", name.c_str());
            } else {
                // 登録されている
                return varStack[name];
            }
        }
    }
}

表示関数

/**
 *
 * @param p0 計算結果
 * @param p1 計算期待値
 */
void print(int ExpectedValue, int CalculatedValue) {
    printf("Result: %s\n"
           "    -- ExpectedValue: %d, CalculatedValue: %d\n",
            (CalculatedValue == ExpectedValue) ? "True" : "False",
            ExpectedValue,
            CalculatedValue);
}

検証

int main() {
    // 計算結果保持変数
    int res;

    // 一括代入（右結合の確認）
    const char *test = nullptr;
    expr("tx = ty = tz = 6", &test);
    printf("\n== 一括代入（右結合の確認）tx ==\n");
    test = nullptr;
    res = expr("tx", &test);
    print(6, res);
    printf("\n== 一括代入（右結合の確認）ty ==\n");
    test = nullptr;
    res = expr("ty", &test);
    print(6, res);
    printf("\n== 一括代入（右結合の確認）tz ==\n");
    test = nullptr;
    res = expr("tz", &test);
    print(6, res);

    // 20 - 単純な計算 : OK
    printf("\n== 単純な計算 ==\n");
    const char *one = nullptr;
    res = expr("1+2*5+9", &one);
    print(20, res);

    // 100 - 複数桁の単純な計算 : OK
    printf("\n== 複数桁の単純な計算 ==\n");
    const char *two = nullptr;
    res = expr("10+20+10+30*2", &two);
    print(100, res);

    // 35 - カッコを含む計算 : OK
    printf("\n== カッコを含む計算 ==\n");
    const char *three = nullptr;
    res = expr("(2*5)+5*2+15", &three);
    print(35, res);

    // 50 - 複数のカッコを含む計算 : OK
    printf("\n== 複数のカッコを含む計算 ==\n");
    const char *four = nullptr;
    res = expr("(2*5)+2*(5+15)", &four);
    print(50, res);

    // 20 - 空白を含む単純な計算 : OK
    printf("\n== 空白を含む単純な計算 ==\n");
    const char *five = nullptr;
    res = expr("1 + 2 * 5 + 9", &five);
    print(20, res);

    // TODO: ネストされてると動かない
    // 50 - カッコにカッコが含まれる計算 : NG
    printf("\n== カッコにカッコが含まれる計算 ==\n");
    const char *six = nullptr;
    res = expr("(5+(1+2*2))*5", &six);
    print(50, res);

    // 7 - 剰余演算子を含む計算 : OK
    printf("\n== 剰余演算子を含む計算 ==\n");
    const char *seven = nullptr;
    res = expr("5 + 5 % 3", &seven);
    print(7, res);

    // 5 - 複数の変数が複数個を含んだ計算 : OK
    printf("\n== 複数の変数が複数個を含んだ計算 ==\n");

    const char *eight = nullptr;
    expr("a = 3", &eight);
    eight = nullptr;
    expr("b = 2", &eight);

    eight = nullptr;
    res = expr("a+b", &eight);
    print(5, res);

    // 8 - 複数の変数が複数個を含んだ計算 : OK
    printf("\n== 複数の変数が複数個を含んだ計算 ==\n");

    const char *nine = nullptr;
    expr("c = b", &nine);
    nine = nullptr;
    expr("d = 1", &nine);

    nine = nullptr;
    res = expr("a+b+c+d", &nine);
    print(8, res);

    // 8 - 複数文字の変数を含んだ計算 : OK
    printf("\n== 複数文字の変数を含んだ計算 ==\n");

    const char *ten = nullptr;
    expr("nomunomu0504 = 1", &ten);
    ten = nullptr;
    res = expr("9+nomunomu0504", &ten);
    print(10, res);

    return 0 ;
}

== 一括代入（右結合の確認）tx ==
Result: True
-- ExpectedValue: 6, CalculatedValue: 6

== 一括代入（右結合の確認）ty ==
Result: True
-- ExpectedValue: 6, CalculatedValue: 6

== 一括代入（右結合の確認）tz ==
Result: True
-- ExpectedValue: 6, CalculatedValue: 6

== 単純な計算 ==
Result: True
-- ExpectedValue: 20, CalculatedValue: 20

== 複数桁の単純な計算 ==
Result: True
-- ExpectedValue: 100, CalculatedValue: 100

== カッコを含む計算 ==
Result: True
-- ExpectedValue: 35, CalculatedValue: 35

== 複数のカッコを含む計算 ==
Result: True
-- ExpectedValue: 50, CalculatedValue: 50

== 空白を含む単純な計算 ==
Result: True
-- ExpectedValue: 20, CalculatedValue: 20

== カッコにカッコが含まれる計算 ==
Result: False
-- ExpectedValue: 50, CalculatedValue: 10

== 剰余演算子を含む計算 ==
Result: True
-- ExpectedValue: 7, CalculatedValue: 7

== 複数の変数が複数個を含んだ計算 ==
Result: True
-- ExpectedValue: 5, CalculatedValue: 5

== 複数の変数が複数個を含んだ計算 ==
Result: True
-- ExpectedValue: 8, CalculatedValue: 8

== 複数文字の変数を含んだ計算 ==
Result: True
-- ExpectedValue: 10, CalculatedValue: 10

解説

プログラム一式はここに置いておきます。

再帰下降法のC言語パーサーもどき · GitHub

基本的な計算式は計算できるようです（できました）。四則演算のほかに剰余、代入演算子が使えます。その他の演算子は追加すれば使えますが、今は追加してません（気力が持ちません...笑）

唯一、カッコがネストされてる数式はうまく解析できません。対策法を教えてください....。また、OPERATORの処理がvariableの部分と同じになっていますが、分割してもいいと思います。ってか分割するべきなんです...。

変数の定義方法としてはexpr("a = 2", &test);とすれば、それ以降のコードで使用することができます。

expr("a = b + 1", &a); // error. b is undefined.

expr("b = 4", &a);
expr("a = b + 1", &a); // a = 5;

修正（2018/11/20）

上記のコードでは「カッコがネストされた数式」、「"8/4/2", "1-2-3"といった数式」がうまく解析できませんでした。なので、BNF記法から見直してみました。

修正版BNF記法

元々のBNF記法を以下のように修正してみました。

/**
 * バッカス記法(BNF) （ +, -, *, /, '(', ')' ）
 * 左辺と同じ非終端記号が右辺先頭にくると「左再帰性」になる
 *
 * ## 式は項のみ or (+, -)演算子を含む式 ##
 * expr ::= term, [(+|-) term]*
 *        ;
 *
 * ## 項は因子 or (*, /)演算子を含む項 ##
 * term ::= factor [(*|/|%) factor]*
 *        ;
 *
 * ## 因子は数値 or カッコを含む（式, 項）or 演算子を含む##
 * factor ::= DIGIT
 *          | VARIABLE
 *          | VARIABLE OPERATOR expr
 *          | '(' expr ')'
 *          ;
 *
 * ## 数値 ##
 * DIGIT ::= [0-9]+ ;
 *
 * ## 変数名 ##
 * VARIABLE ::= _a-zA-Z [_a-zA-Z0-9]+ ;
 *
 * ## 演算子 ##
 * OPERATOR ::= '='
 */

修正版演算子関数

そして、上記のBNF記法に沿って"expr", "term", "factor"を書き換えました。

int expr( const char* pc, const char** endp ) {

    // 1文字目（必ずtermに属する）を取得する
    int left = term( pc, endp );

    while( true ) {
        if ('+' == **endp)
        {
            // ＋1は '+' 分ずらす
            int right = term( *endp + 1, endp );
            left += right;
        }
        else if ('-' == **endp)
        {
            // ＋1は '-' 分ずらす
            int right = term( *endp + 1, endp );
            left -= right;
        }
        else if (isspace(**endp))
        {
            *endp += 1;
        } else { break; }
    }
    return left;
}

int term( const char* pc, const char** endp ) {

    // 1文字目（必ずfactorに属する）を取得する
    int left = factor( pc, endp );

    while( true ) {
        if ('*' == **endp)
        {
            // ＋1は '*' 分ずらす
            int right = factor( *endp + 1, endp );
            left *= right;
        }
        else if ('/' == **endp)
        {
            // ＋1は '/' 分ずらす
            int right = factor( *endp + 1, endp );
            left /= right;
        }
        else if ('%' == **endp)
        {
            // ＋1は '%' 分ずらす
            int right = factor( *endp + 1, endp );
            left %= right;
        }
        else if (isspace(**endp))
        {
            *endp += 1;
        }
        else { break; }
    }
    return left;
}

int factor( const char* pc, const char** endp ) {

    *endp = pc;

    while (true) {
        if ('(' == **endp) {
            // カッコ分読み飛ばし
            *endp += 1;

            // カッコ内の式を解析
            int innerExprValue = expr(*endp, endp);

            // カッコとじまでポインタを進める
            while (true) {
                // カッコ閉じなら
                if (')' == **endp) {
                    // カッコ分飛ばし
                    (*endp)++;
                    // pcに文字列コピー
                    pc = *endp;

                    // カッコ内の演算結果を文字列に
                    string valstr = to_string(innerExprValue);
                    char *cstr = new char[valstr.size() + 1]; // メモリ確保
                    strcpy(cstr, valstr.c_str());        // コピー

                    // 現在の文字列の先頭に計算結果を連結
                    char *tmps = strcat(cstr, pc);

                    // tmp文字列用のメモリ開放
                    delete[] cstr; // メモリ解放

                    // 連結後の文字列をpcに代入
                    pc = tmps;

                    // 解析済み文字列にも同様のものを代入
                    *endp = pc;

                    // 残りの数式の解析
                    int tmp = expr(pc, endp);

                    // 演算結果を返す
                    return tmp;
                } else {
                    *endp += 1;
                }
            }
        } else if (isspace(**endp)) {
            (*endp)++;
        } else if (isdigit(**endp)) {
            return digit(pc, endp);
        } else if (isalpha(**endp)) {
            return variable(pc, endp);
        } else {
            return expr(pc, endp);
        }
    }
}

コード検証

書き換えたら、前回の検証コードに加えて、以下のようなコードもテストしました。

const char *_one = nullptr;
res = expr("8/4/2", &_one);
print(1, res);

const char *_three = nullptr;
res = expr("8/4*2", &_three);
print(4, res);

const char *_four = nullptr;
res = expr("2*4/8", &_four);
print(1, res);

const char *_two = nullptr;
res = expr("1-2-3", &_two);
print(-4, res);

// -----------------------------------------

Result: True
-- ExpectedValue: 1, CalculatedValue: 1
Result: True
-- ExpectedValue: 4, CalculatedValue: 4
Result: True
-- ExpectedValue: 1, CalculatedValue: 1
Result: True
-- ExpectedValue: -4, CalculatedValue: -4

これで、一応は計算を真面目にすることはできるようになったのではないでしょうか...。（たぶん）

不明点

「カッコがネストされた数式」では、以下のような処理を行っています。

// カッコ内の演算結果を文字列に
string valstr = to_string(innerExprValue);
char *cstr = new char[valstr.size() + 1]; // メモリ確保
strcpy(cstr, valstr.c_str());        // コピー

// 現在の文字列の先頭に計算結果を連結
char *tmps = strcat(cstr, pc);

// tmp文字列用のメモリ開放
delete[] cstr; // メモリ解放

ただ、デバッグのようにライン実行だと、うまくいくのですが、コンパイル実行だと文字列連結がうまく行われません。プログラムの組み方が悪いんだと思いますが、要検討点です...。