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

Тема в разделе "C/C++/C#", создана пользователем mashakasha, 6 ноя 2012.

  1. mashakasha

    mashakasha Гость

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

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

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

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    а в чем проблема?
    ищите в дереве фрагмент
    <var> := <list>
    сохраняете значение <list> удаляете узлы <var> и <list>, а узел ":=" Заменяете сохраненным значением <list>
     
  3. mashakasha

    mashakasha Гость

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

    [​IMG]
    [​IMG]

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

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    оплата....напиши в аську: 395-546-218
     
Загрузка...

Поделиться этой страницей