Erstellen Sie einen Analysebaum in C++
-
Verwenden Sie die
if-else-Anweisungen, um den Analysebaum in C++ zu erstellen - Verwenden Sie bedingte Anweisungen, um den Analysebaum in C++ zu erstellen
- Verwenden Sie Polymorphismus, um den Analysebaum in C++ zu erstellen
In diesem Tutorial lernen Sie drei primäre C++-Methoden zum Erstellen eines Analysebaums in C++ kennen. Die erste Methode verwendet die Auswahlanweisungen if (condition) statement und if (condition) statement else statement.
Die zweite Methode verwendet bedingte Anweisungen mit einer einfachen rekursiven Struktur, und die dritte verwendet Polymorphismus. Das Erstellen eines Analysebaums erfordert Lexing (Erkennen von Wörtern und Entfernen von Kommentaren), Analysieren (Strukturieren des linearen Eingabestroms in einen abstrakten Syntaxbaum) und Auswertung oder Codegenerierung.
Verwenden Sie die if-else-Anweisungen, um den Analysebaum in C++ zu erstellen
Ein Parse-Baum (als C++ BNF) verfügt über eine kontextfreie Grammatik zum Parsen, und if-else- oder Auswahlanweisungen spielen eine wichtige Rolle bei seiner Erstellung. Alternativ können Sie try {if (statement) add (statement-tag);} finally {show(your_code);} verwenden, um Ihren Parser auf eine Bedingung zu verweisen, die wahr ist, um einen Codeblock auszuführen.
Die Auswertungsreihenfolge für den gesamten Ausdruck ist durch die Hierarchie des Analysebaums leicht verständlich, da sie eine wesentliche Rolle bei der Erstellung von Sätzen und mathematischen Ausdrücken spielt, um reale Konstruktionen darzustellen. Die Erstellung eines Analysebaums basiert auf den vier Hauptregeln, die in der folgenden C++-Codesequenz codiert sind.
In jeder Klausel der bedingten Anweisung if können Sie den Analysebaum verstehen und untersuchen, der durch Implementieren der Regeln mit Aufrufen der binären Baummethoden erstellt wurde. Am wichtigsten ist, dass es im Falle eines Fehlers wichtig ist, den Grund zu verstehen, und die Verwendung der Wertfehlerausnahme in der else-Klausel der bedingten Anweisung ist äußerst hilfreich.
#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;
}
Ausgang:
10
5
+
3
*
Ein Parse-Baum mit aus Baumbesuchen erstellten Symboltabellen kann sogar als Grundlage für einen einfachen Interpreter dienen und erlaubt Transformationen und Optimierungen der Quelle. Eine Grammatikregelfunktion erfordert das Hinzufügen eines neuen Kindes, um einen Analysebaum zu erzeugen, der den Quellteil darstellt, der mit der entsprechenden Grammatikregel übereinstimmt.
Ein früher Compiler, der einen solchen Baum nicht generiert hat, macht die Codegenerierung viel einfacher. Speicher ist jedoch eine wertvolle Ressource, und seine Verwendung kann einige Programmierer überfordern.
Verwenden Sie bedingte Anweisungen, um den Analysebaum in C++ zu erstellen
Bedingte Anweisungen haben wie der entsprechende rekursive Abstiegsparser eine rekursive Struktur. Außerdem werden die inneren Bedingungen als <condition> -> if <expression> then <statement> [else <statement>] geparst.
Die tokenisierte Eingabesequenz hat auch diese Form, die es dem Parse-Baum ermöglicht, syntaktische Fehler während der lexikalischen Analyse zu erkennen. Zusätzlich werden die äußeren Bedingungen als <conditional> -> if <expression> then <statement> [else <statement>] geparst.
#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
}
Ausgang:
Parse tree build successful!
The result is:
2803
Die tatsächliche Implementierung von bedingten Anweisungen zum Erstellen eines Analysebaums ist viel langwieriger und detaillierter. Jedoch erfordert die Analysebaumkonstruktion unter Verwendung von bedingten Anweisungen ein Formular aus einer tokenisierten Eingabesequenz.
Die Funktion, die die bedingte Anweisung basierend auf einer Struktur auswertet, die der Funktion ähnelt, die eine bedingte Anweisung wie folgt analysiert:
<statement> -> cond(input): <evaluate> if <statement> then <expression> [else if <statement> then <evaluation> else <expression>]
Es ist wichtig, den if-Teil der Bedingung mit einem booleschen Wert auszuwerten, um zu bestimmen, welcher Teil der bedingten Anweisung ausgewertet werden soll.
Verwenden Sie Polymorphismus, um den Analysebaum in C++ zu erstellen
Diese Methode zum Erstellen eines Analysebaums demonstriert die Verwendung von Polymorphismus in C++ als Beispiel für eine äußerst nützliche Datenstruktur. Es analysiert einen arithmetischen Ausdruck und wandelt ihn in eine Baumstruktur um, deren Knoten arithmetische Operatoren und Blattknoten Zahlen sind.
Am wichtigsten ist, dass die Parsing-Tree-Darstellung keine Klammern oder die Kenntnis der Operatorpriorität erfordert und die auszuführende Berechnung eindeutig beschreibt. Sie werden lernen, wie alle Baumknoten als Objekte geparst werden, die von der Klasse parsetree_node, die eine Zahl darstellt, und BinNode (die eine binäre Operation darstellt) erben.
#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
}
Ausgang:
Calculating the parse tree
Multiplying
Adding
The numeric node: 20
The numeric node: -10
The numeric node: 0.1
Result: 1
Die Klasse numeric_class speichert einen Double-Wert (in seinem Konstruktor initialisiert) und überlädt die virtuelle Funktion Calc(). Die Klasse binary_node weiss, wie die von der Klasse parsetree_node geerbte virtuelle Funktion zu implementieren ist.
Ein Analysebaum löst und beschreibt die syntaktischen Rollen seiner Komponenten oder führt den Vorgang des Analysierens einer Zeichenfolge oder eines Textes in einer hierarchischen Baumstruktur (mit einem Wurzelwert) durch, die als Gruppe verknüpfter Knoten dargestellt wird. In C++ stellt er Terminal- und Nicht-Terminal-Symbole dar, um die Grammatik abzuleiten, um Eingabezeichenfolgen zu erhalten, und jeder innere Knoten repräsentiert die Produktionen einer Grammatik.
Ein Analysebaum verwendet einen einzelnen physischen Baumknoten pro Nichtterminal (im Allgemeinen führt dies zu einem riesigen Baum). Es verfügt über zwei Zeigerelemente, ein Element, das zur Knotenidentifikation verwendet wird, und einen virtuellen Destruktor zur Unterstützung abgeleiteter Knoten.
Dieses Tutorial hat Ihnen beigebracht, wie einfach es ist, Parse-Bäume während des Parsens zu erstellen und hocheffiziente Parser zu verbessern und zu erstellen. Ein Parse-Baum kann alles einfacher machen, und sein einziger Nachteil sind seine hohen Laufzeit- und Speicherkosten.
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