迹忆客 专注技术分享

本文将教授三种主要的 C++ 方法来在 C++ 中构建解析树。 第一种方法使用选择语句 if (条件) 语句和 if (条件) 语句 else 语句。

第二种方法使用具有简单递归结构的条件语句，第三种方法使用多态性。 创建解析树需要词法分析（识别单词并删除注释）、解析（将线性输入流构建为抽象语法树）以及评估或代码生成。

使用 if-else 语句在 C++ 中构建解析树

解析树（作为 C++ BNF）具有用于解析的上下文无关语法，并且 if-else 或选择语句在其创建过程中发挥着重要作用。 或者，您可以使用 try {if (statement) add (statement-tag);} finally {show(your_code);} 将解析器指向执行代码块的条件。

通过解析树的层次结构很容易理解整个表达式的求值顺序，因为它在句子和数学表达式创建中发挥着不可或缺的作用，以表示现实世界的结构。 解析树的创建基于四个主要规则，按顺序用以下 C++ 代码进行编码。

在 if 条件语句的每个子句中，您可以理解和研究通过调用二叉树方法实现规则而创建的解析树。 最重要的是，在发生任何错误时必须了解原因，并且在条件语句的 else 子句中使用值错误异常非常有帮助。

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

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++ 中构建解析树

条件语句作为相应的递归下降解析器，具有递归结构。 此外，内部条件被解析为 <condition> -> if <expression> then <statement> [else <statement>]。

标记化的输入序列也具有这种形式，这使得解析树能够在词法分析期间检测语法错误。 此外，外部条件被解析为 <conditional> -> if <expression> then <statement> [else <statement>]。

#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++ 中，它表示终结符号和非终结符号，以推导语法以产生输入字符串，每个内部节点表示语法的产生式。

解析树对每个非终结符使用单个物理树节点（通常，这会产生一棵巨大的树）。 它具有两个指针成员，一个用于节点标识的成员，以及一个支持派生节点的虚拟析构函数。

本文介绍在解析过程中构建解析树是多么容易，并改进和构建高效的解析器。 解析树可以使任何事情变得更容易，它唯一的缺点是运行时间和内存成本较高。