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

digit.cpp

/**
 * ## 数値 ##
 * 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);
    }
}

expr.cpp

/**
 * ## 式は項のみ or (+, -)演算子を含む式 ##
 * expr ::= term
 *        | expr (+|-) term
 *        ;
 *
 * @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 = 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;
}

factor.cpp

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

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <string>
#include <map>

using namespace std;

/**
 * バッカス記法(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 ::= '='
 */

int expr( const char* , const char** );
int term( const char* , const char** );
int factor( const char* , const char** );
int digit( const char* , const char** );
int variable( const char* , const char** );

// 変数展開用の変数定義
map<string, int> varStack;


/**
 * ## 式は項のみ or (+, -)演算子を含む式 ##
 * expr ::= term
 *        | expr (+|-) term
 *        ;
 *
 * @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 = 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;
}

/**
 * ## 項は因子 or (*, /, '%')演算子を含む項 ##
 * term ::= factor
 *        | term (*|/|%) factor
 *        ;
 *
 * @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 = 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;
}

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

/**
 * ## 数値 ##
 * 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 ::= _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);

    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);

    return 0 ;
}

/** Local Variables: **/
/** mode: c++ **/
/** End: **/

term.cpp

/**
 * ## 項は因子 or (*, /, '%')演算子を含む項 ##
 * term ::= factor
 *        | term (*|/|%) factor
 *        ;
 *
 * @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 = 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;
}

variant.cpp

/**
 * ## 変数名 ##
 * 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];
            }
        }
    }
}