Оптимизация Дерева Разбора

  • Автор темы mashakasha
  • Дата начала
M

mashakasha

#1
Здравствуйте!
Дали задание - сделать оптимизацию синтаксического дерева и дерева разбора. Мне досталась оптимизация "распространением копий" (позволяет избавится от лишних (промежуточных) присваиваний переменных, подменяя в выражениях промежуточные переменные)

Синтаксическое дерево я одолела, но с деревом разбора никак не могу справиться. Прилагаю документацию по моему примеру и написанную оптимизацию по синтаксическому дереву. Буду очень рада любой помощи! Спасибо большое всем откликнувшимся)

Посмотреть вложение 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;
}
 

Вложения

R

rrrFer

#2
а в чем проблема?
ищите в дереве фрагмент
<var> := <list>
сохраняете значение <list> удаляете узлы <var> и <list>, а узел ":=" Заменяете сохраненным значением <list>
 
M

mashakasha

#3
r04
это в синтаксическом так. а в дереве разбора прежде всего несколько потомков и другой синтаксис.
вот прилагаю фрагмент из Ульмана, чтобы было понятно, о том, что за дерево разбора.




и вообще - вызвавшемуся помочь возможна оплата!