C++에서 구문 분석 트리 구축
이 자습서에서는 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 <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++에서 파스 트리 구축
조건문은 해당 재귀 하강 파서로서 재귀 구조를 갖습니다. 또한 내부 조건은 <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 클래스는 이중 값(생성자에서 초기화됨)을 저장하고 Calc() 가상 함수를 오버로드합니다. binary_node 클래스는 parsetree_node 클래스에서 상속된 가상 함수를 구현하는 방법을 알고 있습니다.
구문 분석 트리는 해당 구성 요소의 구문 역할을 해결 및 설명하거나 연결된 노드 그룹으로 표시되는 계층적 트리 구조(루트 값 포함)에서 문자열 또는 텍스트를 구문 분석하는 작업을 수행합니다. C++에서 이것은 입력 문자열을 생성하기 위해 문법을 유도하는 터미널 및 비터미널 기호를 나타내며 각 내부 노드는 문법의 생성을 나타냅니다.
구문 분석 트리는 비단말당 하나의 물리적 트리 노드를 사용합니다(일반적으로 거대한 트리가 됩니다). 두 개의 포인터 멤버, 노드 식별에 사용되는 멤버 및 파생 노드를 지원하는 가상 소멸자가 특징입니다.
이 자습서에서는 구문 분석 중에 구문 분석 트리를 구축하고 매우 효율적인 구문 분석기를 개선 및 구축하는 것이 얼마나 쉬운지 알려 주었습니다. 구문 분석 트리는 모든 것을 더 쉽게 만들 수 있으며 유일한 단점은 높은 런타임 및 메모리 비용입니다.
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