C++ で解析ツリーを構築する

  2. プログラミングのヒント
  3. C++ ハウツー
  4. C++ で解析ツリーを構築する
Syed Hassan Sabeeh Kazmi 2023年10月12日
C++ C++ Tree
  1. if-else ステートメントを使用して C++ で解析ツリーを構築する
  2. 条件文を使用して C++ で解析ツリーを構築する
  3. ポリモーフィズムを使用して C++ で解析ツリーを構築する
C++ で解析ツリーを構築する

このチュートリアルでは、C++ で解析ツリーを構築するための 3つの主要な C++ メソッドについて説明します。 最初の方法は、選択ステートメント if (条件) ステートメント と if (条件) ステートメント else ステートメント を使用します。

2 番目の方法は単純な再帰構造を持つ条件ステートメントを使用し、3 番目の方法はポリモーフィズムを使用します。 解析ツリーを作成するには、字句解析 (単語を認識してコメントを削除する)、解析 (線形入力ストリームを抽象構文ツリーに構造化する)、および評価またはコード生成が必要です。

if-else ステートメントを使用して C++ で解析ツリーを構築する

構文解析木 (C++ BNF として) は、構文解析のための文脈自由文法を備えており、その作成において if-else または選択ステートメントが重要な役割を果たします。 または、try {if (statement) add (statement-tag);} finally {show(your_code);} を使用して、コード ブロックを実行する真の条件をパーサーに指示することもできます。

構文解析ツリーの階層は、実世界の構造を表すために文と数式の作成に不可欠な役割を果たしているため、式全体の評価の順序を理解するのは簡単です。 解析ツリーの作成は、次の C++ コードでコード化された 4つの主要な規則に基づいています。

if 条件ステートメントの各節では、バイナリ ツリー メソッドの呼び出しを使用してルールを実装することによって作成される解析ツリーを理解し、調べることができます。 最も重要なことは、エラーが発生した場合の理由を理解することが不可欠であり、条件ステートメントの else 句で値エラー例外を使用すると非常に役立ちます。

#include <algorithm>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

class parsetree_main {
 private:
  string root_key;
  parsetree_main *node_left;
  parsetree_main *node_right;

 public:
  parsetree_main(string obj_root) {
    this->root_key = obj_root;
    this->node_left = NULL;
    this->node_right = NULL;
  }

  void insertNode_left(string insert_newnode) {
    if (this->node_left == NULL) {
      this->node_left = new parsetree_main(insert_newnode);
    } else {
      parsetree_main *t = new parsetree_main(insert_newnode);
      t->node_left = this->node_left;
      this->node_left = t;
    }
  }

  void insertNode_right(string insert_newnode) {
    if (this->node_right == NULL) {
      this->node_right = new parsetree_main(insert_newnode);
    } else {
      parsetree_main *active_parsetree = new parsetree_main(insert_newnode);
      active_parsetree->node_right = this->node_right;
      this->node_right = active_parsetree;
    }
  }

  parsetree_main *getchild_rightside() { return this->node_right; }

  parsetree_main *getchield_leftside() { return this->node_left; }

  void set_rootvalue(string obj_rootvalue) { this->root_key = obj_rootvalue; }

  string get_rootvalue() { return this->root_key; }
};

parsetree_main *build_newparsetree(string obj_parse) {
  string var_buffer;
  stringstream ss(obj_parse);
  vector<string> vector_list;
  while (ss >> var_buffer) {
    vector_list.push_back(var_buffer);
  }
  stack<parsetree_main *> parsetree_stack;
  parsetree_main *pri_parsetree = new parsetree_main("");
  parsetree_stack.push(pri_parsetree);
  parsetree_main *active_parsetree = pri_parsetree;

  string parsetreearray_1[] = {"+", "-", "*", "/"};
  vector<string> parse_vector_1(
      parsetreearray_1, parsetreearray_1 + (sizeof(parsetreearray_1) /
                                            sizeof(parsetreearray_1[0])));

  string parsetreearray_2[] = {"+", "-", "*", "/", ")"};
  vector<string> parse_vector_2(
      parsetreearray_2, parsetreearray_2 + (sizeof(parsetreearray_2) /
                                            sizeof(parsetreearray_2[0])));

  for (unsigned int i = 0; i < vector_list.size(); i++) {
    if (vector_list[i] == "(") {
      active_parsetree->insertNode_left("");
      parsetree_stack.push(active_parsetree);
      active_parsetree = active_parsetree->getchield_leftside();
    }

    else if (find(parse_vector_1.begin(), parse_vector_1.end(),
                  vector_list[i]) != parse_vector_1.end()) {
      active_parsetree->set_rootvalue(vector_list[i]);
      active_parsetree->insertNode_right("");
      parsetree_stack.push(active_parsetree);
      active_parsetree = active_parsetree->getchild_rightside();
    }

    else if (vector_list[i] == ")") {
      active_parsetree = parsetree_stack.top();
      parsetree_stack.pop();
    }

    else if (find(parse_vector_2.begin(), parse_vector_2.end(),
                  vector_list[i]) == parse_vector_2.end()) {
      try {
        active_parsetree->set_rootvalue(vector_list[i]);
        parsetree_main *node_parent = parsetree_stack.top();
        parsetree_stack.pop();
        active_parsetree = node_parent;
      }

      catch (string error_value) {
        cerr << "Token:  " << vector_list[i]
             << " Error: It's not a valid integer!" << endl;
      }
    }
  }
  return pri_parsetree;
}

void postorder(parsetree_main *createInst_parseTree) {
  if (createInst_parseTree != NULL) {
    postorder(createInst_parseTree->getchield_leftside());
    postorder(createInst_parseTree->getchild_rightside());
    cout << createInst_parseTree->get_rootvalue() << endl;
  }
}

int main() {
  parsetree_main *main_parsetree = build_newparsetree("( ( 10 + 5 ) * 3 )");
  postorder(main_parsetree);

  return 0;
}

出力：

10
5
+
3
*

ツリーの訪問からコンパイルされたシンボル テーブルを含む解析ツリーは、単純なインタープリターの基礎としても機能し、ソースの変換と最適化を可能にします。 文法規則関数では、対応する文法規則に一致するソース部分を表す解析ツリーを生成するために、新しい子を追加する必要があります。

このようなツリーを生成しなかった初期のコンパイラは、コード生成をはるかに容易にします。 ただし、メモリは貴重なリソースであり、その使用量に圧倒されるプログラマもいます。

条件文を使用して C++ で解析ツリーを構築する

条件付きステートメントは、対応する再帰降下パーサーとして、再帰構造を持っています。 さらに、内部条件は <条件> -> if <式> then <ステートメント> [else <ステートメント>] として解析されます。

トークン化された入力シーケンスにもこの形式があり、構文解析ツリーが 字句解析 中に構文エラーを検出できるようにします。 さらに、外側の条件は <条件> -> if <式> then <ステートメント> [else <ステートメント>] として解析されます。

#include <iostream>
#include <vector>

using namespace std;

class priTree_binary {
 private:
  char node_root;
  priTree_binary *node_left = NULL;
  priTree_binary *node_right = NULL;

 public:
  priTree_binary(char value_rootnode) {
    // constructor
    node_root = value_rootnode;
  }
  void insert_rightnode(char rightnode_value) {
    priTree_binary *create_newnode = new priTree_binary(rightnode_value);
    if (node_right == NULL)
      node_right = create_newnode;
    else {
      create_newnode->node_right = node_right;
      node_right = create_newnode;
    }
  }
  void insert_leftnode(char leftnode_value) {
    priTree_binary *create_newnode = new priTree_binary(leftnode_value);
    if (node_left == NULL)
      node_left = create_newnode;
    else {
      create_newnode->node_left = node_left;
      node_left = create_newnode;
    }
  }
  priTree_binary *get_rightnode() { return node_right; }
  priTree_binary *get_leftnode() { return node_left; }
  char get_rootnode() { return node_root; }
  void set_rootnode(char rootnode_value) { node_root = rootnode_value; }
};

bool check_operator(char opr_token) {
  string valid_operators = "+-/*";
  for (unsigned long long int ing = 0; ing < valid_operators.length(); ing++)
    if (valid_operators[ing] == opr_token) return true;
  return false;
}

priTree_binary *build_parse_tree(string valid_expression) {
  vector<priTree_binary *> vector_stack;
  priTree_binary *binarytree_primary = new priTree_binary(' ');
  vector_stack.push_back(binarytree_primary);
  for (long long unsigned int i = 0; i < valid_expression.length(); i++) {
    if (valid_expression[i] == '(') {
      binarytree_primary->insert_leftnode(' ');
      vector_stack.push_back(binarytree_primary);
      binarytree_primary = binarytree_primary->get_leftnode();
    } else if (isdigit(valid_expression[i])) {
      binarytree_primary->set_rootnode(valid_expression[i]);
      binarytree_primary = vector_stack.back();
      vector_stack.pop_back();
    } else if (check_operator(valid_expression[i])) {
      binarytree_primary->set_rootnode(valid_expression[i]);
      binarytree_primary->insert_rightnode(' ');
      vector_stack.push_back(binarytree_primary);
      binarytree_primary = binarytree_primary->get_rightnode();
    } else {
      binarytree_primary = vector_stack.back();
      vector_stack.pop_back();
    }
  }
  return binarytree_primary;
}

int eval_parse_tree(priTree_binary *parsetree_main) {
  // cout << "Root: " << tree -> get_root() << endl;
  char _operation;
  int node_left, node_right;
  priTree_binary *leftnode_child = parsetree_main->get_leftnode();
  priTree_binary *rightnode_child = parsetree_main->get_rightnode();
  if (leftnode_child && rightnode_child) {
    _operation = parsetree_main->get_rootnode();
    node_left = eval_parse_tree(leftnode_child);
    node_right = eval_parse_tree(rightnode_child);
    switch (_operation) {
      case '+':
        return (int)node_left + (int)node_right;
      case '-':
        return (int)node_left - (int)node_right;
      case '*':
        return (int)node_left * (int)node_right;
      case '/':
        return (int)node_left / (int)node_right;
    }
  } else
    return parsetree_main->get_rootnode();
}

int main(void) {
  cout << "Parse tree build successful! \nThe result is: " << endl;
  cout << eval_parse_tree(build_parse_tree("(5+(2*7))"))
       << endl;  // returns 2803, instead of 19
}

出力：

Parse tree build successful!
The result is:
2803

解析ツリーを構築するための条件ステートメントの実際の実装は、はるかに退屈で詳細です。 ただし、条件ステートメントを使用した解析ツリーの構築には、トークン化された入力シーケンスからのフォームが必要です。

条件文を次のように解析する関数と同様の構造に基づいて条件文を評価する関数:

<statement> -> cond(input): <evaluate> if <statement> then <expression> [else if <statement> then <evaluation> else <expression>]

条件ステートメントのどの部分を評価するかを決定するには、条件の if 部分をブール値に評価することが重要です。

ポリモーフィズムを使用して C++ で解析ツリーを構築する

解析ツリーを構築するこの方法は、非常に有用なデータ構造の例として、C++ でのポリモーフィズムの使用を示しています。 算術式を解析し、ノードが算術演算子でリーフ ノードが数値であるツリー構造に変換します。

最も重要なことは、構文木表現は、括弧や演算子の優先順位の知識を必要とせず、実行される計算を一意に記述します。 数値を表すクラス parsetree_node と BinNode (二項演算を表す) から継承するオブジェクトとして、すべての解析ツリー ノードをどのように学習するかを学習します。

#include <iostream>

class parsetree_node {
 public:
  virtual ~parsetree_node() {}
  virtual double binaryOpr_calculation() const = 0;
};

class numeric_node : public parsetree_node {
 public:
  numeric_node(double node_number) : parsetree_nodeRep(node_number) {}
  double binaryOpr_calculation() const;

 private:
  const double parsetree_nodeRep;
};

double numeric_node::binaryOpr_calculation() const {
  std::cout << "The numeric node: " << parsetree_nodeRep << std::endl;
  return parsetree_nodeRep;
}

class binary_node : public parsetree_node {
 public:
  binary_node(parsetree_node* parse_leftnode, parsetree_node* parse_rightnode)
      : imp_leftnode(parse_leftnode), imp_rightnode(parse_rightnode) {}
  ~binary_node();

 protected:
  parsetree_node* const imp_leftnode;
  parsetree_node* const imp_rightnode;
};

binary_node::~binary_node() {
  delete imp_leftnode;
  delete imp_rightnode;
}

class multiplication_node : public binary_node {
 public:
  multiplication_node(parsetree_node* parse_leftnode,
                      parsetree_node* parse_rightnode)
      : binary_node(parse_leftnode, parse_rightnode) {}
  double binaryOpr_calculation() const;
};

double multiplication_node::binaryOpr_calculation() const {
  std::cout << "Multiplying\n";
  return imp_leftnode->binaryOpr_calculation() *
         imp_rightnode->binaryOpr_calculation();
}

class add_node : public binary_node {
 public:
  add_node(parsetree_node* parse_leftnode, parsetree_node* parse_rightnode)
      : binary_node(parse_leftnode, parse_rightnode) {}
  double binaryOpr_calculation() const;
};

double add_node::binaryOpr_calculation() const {
  std::cout << "Adding\n";
  return imp_leftnode->binaryOpr_calculation() +
         imp_rightnode->binaryOpr_calculation();
}

int main() {
  // ( 20.0 + (-10.0) ) * 0.1
  parsetree_node* parsetree_node_1 = new numeric_node(20.0);
  parsetree_node* parsetree_node_2 = new numeric_node(-10.0);
  parsetree_node* parsetree_node_3 =
      new add_node(parsetree_node_1, parsetree_node_2);
  parsetree_node* parsetree_node_4 = new numeric_node(0.1);
  parsetree_node* parsetree_node_5 =
      new multiplication_node(parsetree_node_3, parsetree_node_4);
  std::cout << "Calculating the parse tree\n";

  // tell the root to calculate itself
  double x = parsetree_node_5->binaryOpr_calculation();
  std::cout << "Result: " << x << std::endl;

  delete parsetree_node_5;  // and all children
}

出力：

Calculating the parse tree
Multiplying
Adding
The numeric node: 20
The numeric node: -10
The numeric node: 0.1
Result: 1

numeric_class クラスは、(コンストラクターで初期化された) double 値を格納し、Calc() 仮想関数をオーバーロードします。 binary_node クラスは、parsetree_node クラスから継承された仮想関数を実装する方法を知っています。

解析ツリーは、そのコンポーネントの構文上の役割を解決して説明するか、リンクされたノードのグループとして表される階層ツリー構造 (ルート値を持つ) 内の文字列またはテキストを解析する動作を実行します。 C++ では、文法を派生させて入力文字列を生成する終端記号と非終端記号を表し、各内部ノードは文法の生成を表します。

解析ツリーは、非ターミナルごとに 1つの物理ツリー ノードを使用します (一般に、これは巨大なツリーになります)。 ノード識別に使用されるメンバーと、派生ノードをサポートするための仮想デストラクタの 2つのポインター メンバーを備えています。

このチュートリアルでは、解析中に解析ツリーを構築し、非常に効率的なパーサーを改善および構築することがいかに簡単かを説明しました。 解析ツリーはあらゆることを容易にしますが、その唯一の欠点は実行時間とメモリのコストが高いことです。

著者： Syed Hassan Sabeeh Kazmi
Syed Hassan Sabeeh Kazmi avatar Syed Hassan Sabeeh Kazmi avatar

Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.

GitHub

関連記事 - C++ Tree