構文解析をして抽象構文木を作ってみる

プログラミング

こんにちは。

前回、BNFとレールロード・ダイヤグラムで数式の構文がどのように構成されているか確認しました。

それでは、今回は構文解析するプログラムを作っていきます。

構文解析木のノードを作る

はじめに構文解析木のノードになるクラスを作ります。

ノードには、トークンを表す _token とそのトークンがどのような役割を果たしているかを表す _tokenType をメンバ変数とします。

メソッドとしては、getToken，getTokenType，to_stiringを作っておきます。

ファイル名は MyASTNode.h です。

#pragma once
#include<string>
using namespace std;

class MyASTNode
{
public:
    MyASTNode(string token,string tokenType){
        _token = token;
        _tokenType = tokenType;
    }

    string getTokenType(){
        return _tokenType;
    }

    string getToken(){
        return _token;
    }

    string to_string(){
        return "(" + _token + "," + _tokenType + ")";
    }

private:
    string _token;
    string _tokenType;
};

字句解析器を修正する

次に、前々回に作った字句解析器は、token と tokenType を別々の変数で記憶させていました。

上のプログラムでこれらをMyASTNode クラスにまとめたので、字句解析器を変更しておきます。

ファイル名は MyLexer.h としておきます。

#pragma once
#include"MyASTNode.h"
#include"MyQueue.h"
#include<string>
using namespace std;

class MyLexer
{
public:
    MyLexer(string s){
        _tokens = new MyQueue<MyASTNode*>();

        for (int i = 0; i < s.length();i++){
            while (s[i] == ' ' || s[i]=='\t' || s[i]=='\n'){
                i++;
            }

            string res = "";
            
            if('0'<=s[i] && s[i]<='9'){
                res += s[i++];
                while('0'<=s[i] && s[i]<='9'){
                    res += s[i++];
                }

                if(s[i]=='.'){
                    res += s[i++];
                }

                while('0'<=s[i] && s[i]<='9'){
                    res += s[i++];
                }

                i--;
                _addToken(res, "numeral");
                continue;
            }

            if(s[i]=='*' || s[i]=='/' || s[i]=='%'){
                res = s[i];
                _addToken(res, "operator1");
                continue;
            }

            if(s[i]=='+' || s[i]=='-'){
                res = s[i];
                _addToken(res, "operator2");
                continue;
            }

            if(s[i]=='(' ){
                res = s[i];
                _addToken(res, "leftPar");
                continue;
            }

            if(s[i]==')' ){
                res = s[i];
                _addToken(res, "rightPar");
                continue;
            }

            throw runtime_error("Lexer error");
        }
    }

    MyQueue<MyASTNode*> *getTokens(){
        return _tokens;
    }

private:
    MyQueue<MyASTNode*> *_tokens;

    void _addToken(string letter,string tokenType){
        MyASTNode *token = new MyASTNode(letter,tokenType);
        _tokens->offer(token);
    }
};

構文解析器を作る

数式の構文を解析する解析器を作ります。

前回の BNF やレールロード・ダイヤグラムでは、数式は expression でした。

そこで、メソッド expression を呼び出します。

expression は、はじめに term が現れ続いていくつかの（0個も認めて） operatior2 term …とoperatior2 と term のつながりが現れます。

term はまだまだ分解できます。メソッド term を呼び出して分解します。

expression と同様に、はじめに factor が現れて続いていくつかの operater1 factor …とつながっていきます。

factor は、数値 numeric または (expression) のいずれかです。

括弧が現れたらさらに expression を呼び出します。

ぐるっと一回りして、再帰呼び出しになっています。

このように数式のトップからより下位にある部分に解析して、再帰的に構文解析する方法を再帰下降構文解析といいます。

これを実装したのが次のプログラムです。ファイル名は MyParser.h としておきます。

#pragma once
#include"MyTreeNode.h"
#include"MyASTNode.h"
using namespace std;


class MyParser{
public:
    MyParser(){
        _ast = nullptr;
    }

    void parse(MyQueue<MyASTNode*> *tokens){
        _tokens = tokens;
        _ast = expression();
    }

    MyQueue<MyASTNode*>* getTokens(){
        return _tokens;
    }

    MyTreeNode<MyASTNode*>* getAst(){
        return _ast;
    }

private:
    MyTreeNode<MyASTNode*> *_ast;
    MyQueue<MyASTNode*> *_tokens;

    MyTreeNode<MyASTNode*> *expression()
    {
        MyTreeNode<MyASTNode *> *res1 = term();
        while( !_tokens->isEmpty() && _tokens->peek()->getTokenType()=="operator2"){
            MyASTNode *element = _tokens->poll();
            MyTreeNode<MyASTNode *> *ter = term();
            res1 = new MyTreeNode<MyASTNode *>(element, res1, ter);
        }
        return res1;
    }

    MyTreeNode<MyASTNode *> *term()
    {
        MyTreeNode<MyASTNode *> *res1 = factor();
        while( !_tokens->isEmpty() && _tokens->peek()->getTokenType()=="operator1"){
            MyASTNode *element = _tokens->poll();
            MyTreeNode<MyASTNode *> *fac = factor();
            res1 = new MyTreeNode<MyASTNode *>(element, res1, fac);
        }
        return res1;
    }

    MyTreeNode<MyASTNode*> *factor()
    {
        if(_tokens->peek()->getTokenType()=="leftPar"){
            _tokens->poll();
            MyTreeNode<MyASTNode *> *res = expression();
            if( !_tokens->isEmpty() && _tokens->peek()->getTokenType()=="rightPar"){
                _tokens->poll();
                return res;
            }
        }

        if(_tokens->peek()->getTokenType()=="numeral"){
            MyTreeNode<MyASTNode*> *res = new MyTreeNode<MyASTNode*>( _tokens->poll(),nullptr,nullptr);
            return res;
        }
    }
};

構文解析した結果できた構文解析木がうまく表示できなかったので、これまでに作ったクラスも修正しているのですが、長くなってしまうので割愛します。

数式を字句解析・構文解析してみる

それでは、うまく動くか確かめてみます。

#include"MyLexer.h"
#include"MyParser.h"
#include<string>
#include<iostream>
using namespace std;

int main(){
    MyLexer* l = new MyLexer("(12.3+45)*(6.-78.9)");
    MyQueue<MyASTNode *> *res1 = l->getTokens();
    cout << res1->to_string() << endl;

    MyParser *p = new MyParser();
    p->parse(res1);
    MyTreeNode<MyASTNode *> *res2 = p->getAst();
    cout << MyTreeNode<MyASTNode *>::order_string("post", res2) << endl;
}

実行結果です。

[(),rightPar)] → [(78.9,numeral)] → [(-,operator2)] →
 [(6.,numeral)] → [((,leftPar)] → [(*,operator1)] →
 [(),rightPar)] → [(45,numeral)] → [(+,operator2)] →
 [(12.3,numeral)] → [((,leftPar)]
(12.3,numeral) (45,numeral) (+,operator2) (6.,numeral) (78.9,numeral) (-,operator2) (*,operator1)

かなり横長の表示になるので、見やすくなるように改行していますが、このように逆ポーランド記法に変換されます。

ちなみに、15行目を

    cout << MyTreeNode<MyASTNode *>::order_string("in", res2) << endl;

に変える（"post"を"in"に変える）と、括弧がない中置記法になります。

無理やりトークンとトークンの型がわかるように出力するようにしてしまった結果、以前作った逆ポーランド記法の数式を計算するプログラムがそのままでは使えなくなってしまいました・・・

どうしよう？

今回はこれでおしまいにします。それではまた。

Posted by 春日井 優