2日で作る電卓インタプリタ[0日目]の続きです．
2日目はこちらから

今回は前回言った通り，字句解析器と構文解析器を実装して抽象構文木を生成するところまで行こうと思います．この電卓の名前はvmcalcとでもしておきましょう．
実際のソースコードが出てきますが，C++とclassらへんが若干分かるなら苦なく読めるはずです．コンパイラはg++ 7.3.0を使っています．
このvmcalc,リポジトリに全部コードが上がってるんでそこも参照しつつ見ていってください．

字句解析器

　lexというツールを使えば簡単に出来ますが，時代は手書きです．

トークンを種類別に分ける

　810や514などの数字ならNumber，+や-などの符号ならSymbol，fooやvarなどの識別子ならIdentiferなど，トークンに種類があります．なのでその種類を定義してやります．
今回はNumberとSymbolしか出てこないのでその２つと，終わりを示すEndも追加します．

vmcalc.h

enum class TOKEN {
    NUMBER,
    SYMBOL,
    END,
};

トークンの型を作る

　字句が持つ情報は種類だけではなく，その数値や演算子も含みます．なのでtoken_t構造体を用意してトークン型を作ります．

vmcalc.h

struct token_t {
    TOKEN type;
    std::string value; //値
};

トークンクラスを作る

　一つのソースコードにあるトークンは大抵1個だけじゃなく，複数個あるはずです．なので，token_t型の可変長配列と，それに要素を追加していくpushﾎﾆｬﾗﾗ関数を追加します．あとトークン列を実際目で見たいのでshow関数も．

vmcalc.h

class Token {
    public:
        void push_number(std::string);
        void push_symbol(std::string);
        void push_end();
        void show();
    private:
        std::vector<token_t> tokens;
};

pushﾎﾆｬﾗﾗはここでもう実装しちゃいましょう．簡単です．

token.cpp

void Token::push_number(std::string value) {
    tokens.push_back((token_t){TOKEN::NUMBER, value});
}

void Token::push_symbol(std::string value) {
    tokens.push_back((token_t){TOKEN::SYMBOL, value});
}

void Token::push_end() {
    tokens.push_back((token_t){TOKEN::END, ""});
}

tokensにpush_back()でどしどし追加してるだけです．

字句解析器クラスを作る

　字句解析器はLexerと言ったりします．Tokenが返ってくるようにしたいので，

vmcalc.h

class Lexer {
    public:
        Token run(std::string);
};

これだけですね．引数には与えられたソースコードが入ります．

いよいよ本題

　字句解析器の中心部を実装します．少しだけ長くなります！

lexer.cpp

Token Lexer::run(std::string src) {
    Token token;

    for(unsigned int i = 0; i < src.size(); i++) {
        if(isdigit(src[i])) {
            std::string value_num;

            for(; isdigit(src[i]);i++) {
                value_num += src[i];
            }
            --i;  //1マスもどる
            token.push_number(value_num);
        }
        else if(src[i] == '+' || src[i] == '-' || src[i] == '*' || src[i] == '/' ||
                src[i] == '(' || src[i] == ')') {
            std::string value{src[i]};

            token.push_symbol(value);
        }
        else if(isblank(src[i])) continue;
        //ここで空白文字のスキップを行っている．
        //isblank()は引数が空白文字のときにtrueを返す.
        else {
            //どの条件にも当てはまらない場合はエラー
            fprintf(stderr, "invalid syntax: \" %c \"", src[i]);
        }
    }
    token.push_end();    //トークンの終わり

    return token;
}

重要な(？)とこ意外はコードにコメントで説明を書いちゃいました．

for(; isdigit(src[i]);i++) {
    value_num += src[i];
}

isdigit()関数は引数が数値のときにtrueを返します．ここは「読んでいる文字が数値である間は，そこは数字だから文字列に追加し続けろ」という意味です(説明しにくい)．これで65536などの複数桁の数値も字句解析することができます．はい次！

else if(src[i] == '+' || src[i] == '-' || src[i] == '*' || src[i] == '/' ||
        src[i] == '(' || src[i] == ')') {
     std::string value{src[i]};

     token.push_symbol(value);
}

ここは単純に，読んでる文字が+とかの場合はsymbolとしてトークン列に追加しているだけです．3行目でchar -> std::stringの変換を行ってます．はい字句解析以上！次！

実際に見てみる

　実際目で見て確認しないとできてるか不安なのでトークン列を出力するshow()を実装します．

token.cpp

void Token::show() {
    std::string literal;

    for(token_t token: tokens) {
        switch(token.type) {
            case TOKEN::NUMBER: literal = "Number"; break;
            case TOKEN::SYMBOL: literal = "Symbol"; break;
            case TOKEN::END:    literal = "End";    break;
            default: puts("error"); break;
        }

        std::cout << literal << "( " << token.value << " )" << std::endl;
    }
}

実際に動かしてみましょう．実際に動かすにはmain関数が必要です．

main.cpp

#include "vmcalc.h"

int main(int argc, char **argv) {
    if(argc != 2) {
        puts("error"); exit(1);
    }
    std::string src = std::string(argv[1]);
    Token token;
    Lexer lexer;
    token = lexer.run(src);
    token.show();
}

用意したら，下のようにコンパイルしてみて下さい．

g++ -o vmcalc main.cpp lexer.cpp token.cpp

するとvmcalcという実行ファイルが出来るはずです．実行しましょう．

$ ./vmcalc '10 * 20 + 30 * 40 * 50'
Number( 10 )
Symbol( * )
Number( 20 )
Symbol( + )
Number( 30 )
Symbol( * )
Number( 40 )
Symbol( * )
Number( 50 )
End(  )

はい勝ち．

構文解析器を作る

　これもyaccというツールを使えば簡単に済みますが，俺の宇宙では手書きがアツいので．

ノードの種類を定義する

　前回抽象構文木(AST)の説明をしたときに，こんな図を出しました．

       +
     /   \
    *     *
   / \   / \
  1   2 3   *
           / \
          4   5

この木構造の節々のことをノードと言います(+とか1とか)．ASTはノードの集まりです．そして，このノードにも種類があります．それは数字のノードだったり，変数のノードだったり，二項演算子のノードだったりします．今回は数字と二項演算子しか出てこないので，その2種類を定義してあげましょう．

vmcalc.h

enum class NODE {
    NUMBER,    //数字
    BINARY,    //二項演算子
};

抽象構文木を表現する

　ここが一番複雑です．まず，一番大元である基底クラスのASTクラスを用意します．

vmcalc.h

class AST {
    public:
        virtual NODE get_ndtype() = 0;
};

なんだこのvirtual!?ってなった方は，「仮想関数 C++」あたりでググればいろいろ出てきます(テキトーですいません)．
get_ndtype()はその名の通り，さっき定義した種類を返してくれます．
こっからクラスの継承を使って各ノードを表現していきます．

数値のノード

こいつは数字しか持ってませんね．

vmcalc.h

class Node_number: public AST {
    public:
        int value;
        virtual NODE get_ndtype() { return NODE::NUMBER; }

        Node_number(int v): value(v) {}
};

コンストラクタでメンバ変数の初期化を行っています．

二項演算子のノード

こいつがちょっと複雑です．
二項演算子は単体であるものではありません．

<left> + <right>

のように

演算子
左辺のノード
右辺のノード

と3つの情報を持っています．なので，二項演算子のノードは

vmcalc.h

class Node_binary: public AST {
    public:
        std::string op;    //演算子
        AST *left;         //左辺のノード
        AST *right;        //右辺のノード
        virtual NODE get_ndtype() { return NODE::BINARY; }

        Node_binary(std::string o, AST *l, AST *r):
            op(o), left(l), right(r) {}
};

のようになります．この2つの定義したノードで

       +
     /   \
    *     *
   / \   / \
  1   2 3   *
           / \
          4   5

この抽象構文木が表現できていることを実際に確かめてみて下さい．(一番上の+は左辺に*があるから*を表すノードを持っていて...みたいな)

文法の定義

　構文解析器を作る前に，構文の定義をしてあげなければいけません．プログラミング言語の文法のルールを定義します．例えば，

434 + * 32

などの意味不明なコードは「ルール違反」としてエラーを出してあげたいわけです．
また，

2 * 3 + 4 * 5

など，演算子の優先順位も考えないといけない式が出てきます．その優先順位も構文定義で決定しちゃいます．

BNF(バッカスナウア記法)

　プログラミングの構文を定義する言語として有名なものにBNFがあります．BNFの文法は以下の通りです．

記号	意味
`::=`	文法の定義
`()`	括弧内のグループ化
`< >`	非終端記号(抽象的な式や文など)
`" "`	終端記号(具体的な数字，演算子など)
`*`	直前のものを0回以上繰り返す
`+`	直前のものを1回以上繰り返す
`(or)`	「または」

※ (or)は|です．(Qiitaの仕様上表の一部として認識されちゃう)
こいつで四則演算の構文を定義してみましょう．

まずは足し算，引き算から

足し算，引き算では
5, 5 + 10, 5 + 10 - 4, 1 + 2 + 3 + 4 - 5などが表現できるはずです．
ここで，1 + 2 + 3 + 4 - 5をこんな感じに分解してみます．

1 | + 2 | + 3 | + 4 | - 5

こう見ると，足し算引き算の式は，数値1つと(+ or -) 数値の0回以上の繰り返しであると言えます(「0回以上」なのは数値1つだけでも式と定義してあげるためです)．
足し算，引き算の式を<expr_add>，数値を<expr_num>とて，BNFに落としてあげると，こうなります．

足し算引き算

<expr_add> ::= <expr_num> ( ("+"|"-") <expr_num>)*

掛け算割り算

足し算と引き算を定義することができたので，次は1段階レベルアップして掛け算割り算です．
足し算引き算掛け算割り算の式は，
5, 5 + 10, 6 * 2, 1 * 3 / 4, 1 * 2 + 3 * 4 * 5などが表現できるはずです．
まず掛け算割り算だけの式(1 * 3 / 4とか)を考えます．こいつは，足し算引き算のときと同じです．掛け算割り算の式を<expr_mul>として，BNFに落とします．

掛け算割り算のみ

<expr_mul> ::= <expr_num> ( ("*"|"/") <expr_num>)*

ここからです．足し算引き算掛け算割り算を含めた式(1 * 2 + 3 * 4 * 5 + 6 * 7とか)について考えていきます．
まず，1 * 2 + 3 * 4 * 5 + 6 * 7の一般的な演算子の優先順位を()でくくって表現してあげると，(1 * 2) + (3 * 4 * 5) + (6 * 7)のようになります．*が先，+が後ですね．
先程のように分解してみます．

1 * 2  |  + 3 * 4 * 5  |  + 6 * 7

こう見ると，足し算引き算は**掛け算割り算1つと(+ or -) 掛け算割り算の0回以上の繰り返し**　と考えることはできませんか？？
そして掛け算割り算は**数値1つと(* or /) 数値の0回以上の繰り返し**です．つまり，数値1つでも掛け算割り算と言えるので，5も， 5 + 10も， 6 * 2も， 1 * 3 / 4も， 1 * 2 + 3 * 4 * 5も全てこれで表現できてしまいます．
以上のことをBNFに落としたのがこちらです．

<expr_add> ::= <expr_mul> ( ("+"|"-") <expr_mul>)*
<expr_mul> ::= <expr_num> ( ("*"|"/") <expr_num>)*

同じ要領で()についてもやってみて下さい．()の中は足し算でも掛け算でも数値でもなんでもいいので<expr_add>になっています．
これで四則演算の構文定義をすることができました．以下がそのBNFです．

四則演算のBNF

<expr_add> ::= <expr_mul> [ ("+"|"-") <expr_mul> ]*
<expr_mul> ::= <expr_primary> [ ("*"|"/") <expr_primary> ]*
<expr_primary> ::= <expr_num> | "(" <expr_add> ")"

今回構文解析の手法として再帰下降構文解析を用います．再帰下降構文を用いた場合，生成した構文規則に演算子の優先順位が考慮されています．
このBNFを見ると，根が<expr_add>で根から木が下に向かっていることが分かります(下降)．また，<expr_primary>では()の中で<expr_add>が呼び出されているため，循環していることになります(再帰)．

本題

　では，実際に字句からASTにするコードを実装していきます．

Parserクラス

　構文解析のことをParser(パーサ？パーザ？)と言ったりします．字句を受け取ってASTを返したいので，こんな感じになります．

vmcalc.h

class Parser {
    public:
        AST *run(Token);    //ここがメイン
        void show(AST *);
    private:
        Token token;
        AST *expr_add();
        AST *expr_mul();
        AST *expr_primary();

        AST *expr_num(token_t);
};

show()は名前の通りASTを標準出力します(どうやるかは後で)．
tokenは受け取ったトークンが入るとこです．exprﾎﾆｬﾗﾗ()は式の構文解析をする奴らです．

トークンの位置管理

　構文解析する際に，トークンの位置をちまちま進めたり，トークンの値を確認したり取得したりとトークンの操作がしたいので，Tokenクラスをいじります．

vmcalc.h

class Token {
    public:
        void push_number(std::string);
        void push_symbol(std::string);
        void push_end();
        void show();

        bool is(std::string);
        bool istype(TOKEN);
        bool expect(std::string);
        void step();
        token_t get_step();
    private:
        std::vector<token_t> tokens;
        int pos = 0;    //位置
};

メンバ関数の実装は以下のようになっています．

token.cpp

bool Token::is(std::string val) {        //トークンの値を比較
    return tokens[pos].value == val;
}

bool Token::istype(TOKEN ty) {           //トークンの種類を比較
    return tokens[pos].type == ty;
}

bool Token::expect(std::string val) {    //そのトークンを期待する．そうでなかったらエラーを出す
    if(tokens[pos].value == val) {
        step();
        return true;
    }
    else
        fprintf(stderr, "error: %s expected", val.c_str());
    return false;
}

token_t Token::get_step() {               //現在位置のトークンを返して一つ進める
    return tokens[pos++];
}

void Token::step() {                      //トークンを1つ進める
    pos++;
}

さて，前準備が済んだのでいよいよ中核に迫っていきます．

中核を作る

　ここから一番の中核となるコードを書いていきます．

入り口

　この構文解析器の入り口を書かなくてはダメなので書きます．

parser.cpp

AST *Parser::run(Token _t) {
    token = _t;

    AST *program = expr_add();
    return program;
}

トークンを受け取ってASTを返してますね．

構文解析器

先程BNFで定義した文法を見てみましょう．

<expr_add> ::= <expr_mul> [ ("+"|"-") <expr_mul> ]*
<expr_mul> ::= <expr_primary> [ ("*"|"/") <expr_primary> ]*
<expr_primary> ::= <expr_num> | "(" <expr_add> ")"

これをそのままコードに落とし込むだけです．

parser.cpp

//<expr_add> ::= <expr_mul> [ ("+"|"-") <expr_mul> ]*
AST *Parser::expr_add() {
    AST *left = expr_mul();

    while(1) {
        if(token.is("+")) {
            token.step();
            left = new Node_binary("+", left, expr_mul());
        }
        else if(token.is("-")) {
            token.step();
            left = new Node_binary("-", left, expr_mul());
        }
        else
            return left;
    }
}

//<expr_mul> ::= <expr_primary> [ ("*"|"/") <expr_primary> ]*
AST *Parser::expr_mul() {
    AST *left = expr_primary();

    while(1) {
        if(token.is("*")) {
            token.step();
            left = new Node_binary("*", left, expr_mul());
        }
        else if(token.is("/")) {
            token.step();
            left = new Node_binary("/", left, expr_mul());
        }
        else
            return left;
    }
}

//<expr_primary> ::= <expr_num> | "(" <expr_add> ")"
AST *Parser::expr_primary() {
    while(1) {
        if(token.istype(TOKEN::NUMBER)) return expr_num(token.get_step());
        else if(token.is("(")) {
            token.step();
            AST *left = expr_add();
            token.expect(")");
            return left;
        }

        fprintf(stderr, "??? : %s", token.get_step().value.c_str());
        return nullptr;
    }
}

AST *Parser::expr_num(token_t tk) {
    return new Node_number(atoi(tk.value.c_str()));
}

ソースコードとBNFを読み比べてみて下さい．かなり似てると思います．
これで構文解析器ができました．わーいやったーっ！

出力

最後に，できたASTをS式にして出力するshow()関数をのっけて1日目は終わりです！

parser.cpp

void Parser::show(AST *ast) {
    switch(ast->get_ndtype()) {
        case NODE::NUMBER: {
            auto n = (Node_number *)ast;
            printf("%d ", n->value);
        } break;
        case NODE::BINARY: {
            auto b = (Node_binary *)ast;
            printf("(");
            printf("%s ", b->op.c_str());
            show(b->left);
            show(b->right);
            printf(")");
        } break;
        default: puts("error");
    }
}

それに応じてメインファイルも書き換えます．

main.cpp

#include "vmcalc.h"

int main(int argc, char **argv) {
    if(argc != 2) {
        puts("error"); exit(1);
    }
    std::string src = std::string(argv[1]);
    Token token;
    Lexer lexer;
    token = lexer.run(src);
    token.show();
    Parser parser;
    AST *ast;
    ast = parser.run(token);
    parser.show(ast); puts("");
}

ここに完全なコードが載っていますので，参照して自分でmakeファイルを書いたり，git cloneしたりしてみて実行して下さい．

$ ./vmcalc '1 * 2 + 3 * 4 * 5'
Number( 1 )
Symbol( * )
Number( 2 )
Symbol( + )
Number( 3 )
Symbol( * )
Number( 4 )
Symbol( * )
Number( 5 )
End(  )
(+ (* 1 2 )(* 3 (* 4 5 )))

完璧です！ではまた来週(？)！

おわりに

一番キツイとこもガッと書きました．色々ググって他のページの情報も見て，理解を深めて下さい．
お疲れ様でした．

参考リンク集