Здравствуйте!
Дали задание - сделать оптимизацию синтаксического дерева и дерева разбора. Мне досталась оптимизация "распространением копий" (позволяет избавится от лишних (промежуточных) присваиваний переменных, подменяя в выражениях промежуточные переменные)
Синтаксическое дерево я одолела, но с деревом разбора никак не могу справиться. Прилагаю документацию по моему примеру и написанную оптимизацию по синтаксическому дереву. Буду очень рада любой помощи! Спасибо большое всем откликнувшимся)
Посмотреть вложение m_kalinichenko.doc
Дали задание - сделать оптимизацию синтаксического дерева и дерева разбора. Мне досталась оптимизация "распространением копий" (позволяет избавится от лишних (промежуточных) присваиваний переменных, подменяя в выражениях промежуточные переменные)
Синтаксическое дерево я одолела, но с деревом разбора никак не могу справиться. Прилагаю документацию по моему примеру и написанную оптимизацию по синтаксическому дереву. Буду очень рада любой помощи! Спасибо большое всем откликнувшимся)
Посмотреть вложение m_kalinichenko.doc
C++:
#include <iostream>
#include <cassert>
#include <stdlib.h>
#include <sstream>
using namespace std;
typedef struct tree {
char data[25];
char node_type[25];
struct tree* left, *right;
} TREE;
TREE* root = NULL;
typedef enum tag_type {RIGHT, LEFT} TYPE;
TREE* add_node(TREE* node,char* data,char* node_type, TYPE type = LEFT)
{
TREE* new_node = (TREE *)malloc(sizeof(TREE));
if(type == LEFT && node != NULL) node->left = new_node;
else if(node != NULL) node->right = new_node;
strcpy(new_node->data,data);
strcpy(new_node->node_type,node_type);
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
void print (TREE* node, int level = 0 )
{
TREE *tn = node;
if(tn) print(tn->right, level+1);
for (int n=0; n<level;++n)
cout << " ";
if(tn)
cout << tn->data << endl;
else
cout << "" << endl;
if(tn) print(tn->left, level+1);
}
void del_next(TREE* node)
{
if(node != NULL)
{
del_next(node->left);
del_next(node->right);
printf("node %s - deleted\n",node->data);
free(node);
}
}
void del_tree()
{
if(root != NULL)
{
del_next(root->left);
del_next(root->right);
printf("node %s - deleted\n",root->data);
free(root);
}
}
TREE* find(TREE* node)
{
TREE* new_node = (TREE *)malloc(sizeof(TREE));
new_node = NULL;
if ((node != NULL )&&(node->left!=NULL)&&(node->right != NULL))
{
if ((!strcmp(node->left->node_type,node->right->node_type))&&(!strcmp(node->data, ":=")))
{
new_node = node;
return new_node;
} else {
new_node = find(node->left);
if (new_node == NULL) new_node = find(node->right);
}
}
return new_node;
}
void opt(TREE* node){
strcpy(node->node_type,node->right->node_type);
strcpy(node->data,node->right->data);
del_next(node->right);
del_next(node->left);
node->left=NULL;
node->right=NULL;
}
void optimisation()
{
TREE* tmp = find(root);
while(tmp != NULL) {
opt(tmp);
tmp = find(root);}
}
int main()
{
root = add_node(NULL,":=","operation");
add_node(root,"+","operation",RIGHT);
add_node(root,"c","type",LEFT);
add_node(root->right,":=","operation",RIGHT);
add_node(root->right,":=","operation",LEFT);
add_node(root->right->left,"a","type",LEFT);
add_node(root->right->left,"x","type",RIGHT);
add_node(root->right->right,"b","type",LEFT);
add_node(root->right->right,"y","type",RIGHT);
print(root,0);
optimisation();
print(root,0);
root = NULL;
return 0;
}
