Construir un árbol de análisis en C++
-
Use las declaraciones
if-elsepara construir el árbol de análisis en C++ - Use declaraciones condicionales para construir el árbol de análisis en C++
- Usar polimorfismo para construir el árbol de análisis en C++
Este tutorial enseñará tres métodos principales de C++ para construir un árbol de análisis en C++. El primer método utiliza sentencias de selección sentencia if (condición) y sentencia if (condición) else.
El segundo método usa declaraciones condicionales con una estructura recursiva simple y el tercero usa polimorfismo. La creación de un árbol de análisis requiere lexing (reconocer palabras y eliminar comentarios), analizar (estructurar el flujo de entrada lineal en un árbol de sintaxis abstracta) y evaluación o generación de código.
Use las declaraciones if-else para construir el árbol de análisis en C++
Un árbol de análisis (como un BNF de C++) presenta una gramática libre de contexto para el análisis, y las instrucciones de selección o if-else juegan un papel importante en su creación. Alternativamente, puede usar try {if (statement) add (statement-tag);} finalmente {show (your_code);} para apuntar su analizador a una condición que es verdadera para ejecutar un bloque de código.
Es fácil comprender el orden de evaluación de toda la expresión a través de la jerarquía del árbol de análisis, ya que juega un papel integral en la creación de oraciones y expresiones matemáticas para representar construcciones del mundo real. La creación de un árbol de análisis se basa en las cuatro reglas principales, codificadas secuencialmente en el siguiente código C++.
En cada cláusula de la declaración condicional if, puede comprender y estudiar el árbol de análisis creado al implementar las reglas con llamadas a los métodos del árbol binario. Lo que es más importante, es esencial comprender el motivo en caso de cualquier error, y usar la excepción de error de valor en la cláusula else de la declaración condicional es extremadamente útil.
#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;
}
Producción :
10
5
+
3
*
Un árbol de análisis sintáctico con tablas de símbolos compiladas a partir de visitas a árboles puede incluso servir como base para un intérprete simple y permite transformaciones y optimizaciones de la fuente. Una función de regla gramatical requiere agregar un nuevo elemento secundario para generar un árbol de análisis que represente la parte de origen que coincide con la regla gramatical correspondiente.
Un compilador anterior que no generaba dicho árbol facilitaba mucho la generación de código. Sin embargo, la memoria es un recurso precioso y su uso puede abrumar a algunos programadores.
Use declaraciones condicionales para construir el árbol de análisis en C++
Las declaraciones condicionales, como el analizador descendente recursivo correspondiente, tienen una estructura recursiva. Además, las condiciones interiores se analizan como <condición> -> si <expresión> entonces <sentencia> [else <sentencia>].
La secuencia de entrada tokenizada también tiene esta forma, lo que permite que el árbol de análisis detecte errores sintácticos durante el análisis léxico. Además, las condiciones externas se analizan como <condicional> -> if <expresión> then <sentencia> [else <sentencia>].
#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
}
Producción :
Parse tree build successful!
The result is:
2803
La implementación real de declaraciones condicionales para construir un árbol de análisis es mucho más tediosa y detallada. Sin embargo, la construcción del árbol de análisis sintáctico mediante declaraciones condicionales requiere un formulario de una secuencia de entrada tokenizada.
La función que evalúa la declaración condicional basada en una estructura similar a la función que analiza una declaración condicional como:
<statement> -> cond(input): <evaluate> if <statement> then <expression> [else if <statement> then <evaluation> else <expression>]
Es importante evaluar la parte if de la condición a un valor booleano para determinar qué parte de la declaración condicional evaluar.
Usar polimorfismo para construir el árbol de análisis en C++
Este método de construcción de un árbol de análisis demuestra el uso del polimorfismo en C++ como ejemplo de una estructura de datos extremadamente útil. Analizará una expresión aritmética y la convertirá en una estructura de árbol cuyos nodos son operadores aritméticos y los nodos hoja son números.
Lo que es más importante, la representación del árbol de análisis sintáctico no requiere paréntesis ni el conocimiento de la precedencia del operador y describe de manera única el cálculo que se realizará. Aprenderá cómo todos los nodos de árbol de análisis como objetos heredados de la clase parsetree_node, que representa un número, y BinNode (que representa una operación binaria).
#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
}
Producción :
Calculating the parse tree
Multiplying
Adding
The numeric node: 20
The numeric node: -10
The numeric node: 0.1
Result: 1
La clase numeric_class almacena un valor doble (inicializado en su constructor) y sobrecarga la función virtual Calc(). La clase binary_node sabe cómo implementar la función virtual heredada de la clase parsetree_node.
Un árbol de análisis resuelve y describe los roles sintácticos de sus componentes o realiza el acto de analizar una cadena o un texto en una estructura de árbol jerárquico (con un valor raíz) representado como un grupo de nodos vinculados. En C++, representa símbolos terminales y no terminales para derivar la gramática y generar cadenas de entrada, y cada nodo interior representa las producciones de una gramática.
Un árbol de análisis utiliza un solo nodo de árbol físico por no terminal (generalmente, esto da como resultado un árbol enorme). Cuenta con dos miembros punteros, un miembro utilizado para la identificación de nodos y un destructor virtual para admitir nodos derivados.
Este tutorial le ha enseñado lo fácil que es construir árboles de análisis durante el análisis y mejorar y construir analizadores altamente eficientes. Un árbol de análisis puede hacer cualquier cosa más fácil, y su única desventaja es su alto costo de memoria y tiempo de ejecución.
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