ACCEL ASCII парсер

[RuNTiME]

Всем привет! Пишу парсер синтаксиса accel ascii. Синтаксис представляет собой следующее:

Код:

(simpleDoc
    (foo  "simple")
    (foo1 "")
    (foo2 "Some"
        (asd 1 67 90)
        (bs)
        (testProp Test)
    )
)
(main)

Парсер строит дерево узлов и копирует в них данные. Сейчас под каждый узел дерева выделяется память отдельно, что я считаю очень не эффективно. Хотелось бы придумать что - либо получше...

И еще, сейчас чтение производится через стандартные потоки, насколько это эффективно, может быть лучше реализовать
чтение самому?

Парсер пока не дописан, выкладываю то что есть:

Код:

//accel_ascii.h

#ifndef __ACCEL_ASCII_H__
#define __ACCEL_ASCII_H__

#include <fstream>

#ifndef NULL
#define NULL 0
#endif

//максимальная вложенность узлов
#define MAX_NODE_DEPTH 512

//коды ошибок
typedef enum t_error_code {
    ec_succeful = 0, //операция завершена успешно
    ec_unknown, //неизвестная ошибка
    ec_syntax, //ошибка синтаксиса
    ec_memory, //ошибка при выделении памяти
    ec_stack_overflow, //переполнение стека
    ec_stack_clear //стек чист (возникает, когда происходит попытка чтения из пустого стека)
}error_code;

//типы значений аттрибутов
typedef enum t_accel_attrib_type {
    at_none = 0, //неопределённый тип
    at_string, //строка
    at_number, //число
    at_property //свойство
}accel_attrib_type;

//список опций узла
typedef struct t_accel_attribute {
    accel_attrib_type type; //тип
    char *field_p; //указатель на значение
    int field_len; //длинна поля данных
    struct t_accel_attribute *next; //указатель на следующий элемент
}accel_attribute, *accel_attribute_p;

//дерево узлов
typedef struct t_accel_node {
    char *name; //имя узла
    accel_attribute_p attrib_list; //список аттрибутов
    accel_attribute_p attrib_list_last; //последний узел в списке аттрибутов
    int attrib_count; //количество элементов в списке аттрибутов
    struct t_accel_node *next; //следующий узел
    struct t_accel_node *child; //дочерний узел
    struct t_accel_node *last_child; //последний дочерний
    struct t_accel_node *list_next; //указатель на следующий узел в глобальном списке узлов
}accel_node, *accel_node_p;

typedef enum t_parser_state {
    ps_idle = 0,
    ps_read_node, //чтение узла
    ps_wait_attrib, //ожидание аттрибута
    ps_read_attrib //чтение аттрибута
}parser_state;

//стек указателей на элементы дерева
class PARSER_Stack {
private:
    int _size; //размер стека
    int _ptr; //текущая позиция
    accel_node_p *_elements; //массив элементов
public:
    PARSER_Stack(int size)
        :_size(0),
         _ptr(0),
         _elements(NULL)
    {
        _size = size;
        if(_size) {
            _elements = new accel_node_p[_size];
        }
    }

    ~PARSER_Stack() {
        if(_elements != NULL) {
            delete[] _elements;
        }
    }

    //помещает элемент в стек
    bool push(accel_node_p node_p) {
        if( (_elements == NULL) ||
            (_ptr >= _size) ) {
            return false;
        }
        _elements[_ptr] = node_p;
        _ptr++;
        return true;
    }

    //извлекает элемент из стека
    accel_node_p pop() {
        if( (_elements == NULL) ||
            (_ptr <= 0) ) {
            return NULL;
        }
        return _elements[--_ptr];
    }

    //возвращает значение элемента, не извлекая его из стека
    accel_node_p peek() {
        if( (_elements == NULL) ||
            (_ptr <= 0) ) {
            return NULL;
        }
        return _elements[_ptr - 1];
    }
};

class PARSER_Three {
    accel_node_p root;
public:
    PARSER_Three()
        :root(NULL)
    {
        root = new accel_node;
        memset(root, 0, sizeof(accel_node));
    }

    ~PARSER_Three() {
        if(root != NULL) {
            accel_node_p next = root;
            while(next->list_next) {
                accel_node_p del_node = next;
                next = next->list_next;
                accel_attribute_p attr_p = next->attrib_list;
                while(attr_p) {
                    accel_attribute_p del_attr = attr_p;
                    attr_p = attr_p->next;
                    if(del_attr->field_p) {
                        delete[] del_attr->field_p;
                    }
                    delete del_attr;
                }
                if(del_node->name) {
                    delete[] del_node->name;
                }
                delete del_node;
            }
        }
    }

    //вставляет узел, если не указан родитель, то узел будет вставлен в root
    accel_node_p insert(accel_node_p parent_p = NULL) {
        if(root == NULL) {
            return NULL;
        }
        if(parent_p == NULL) {
            parent_p = root;
        }
        accel_node_p node_p = new accel_node;
        if(node_p) {
            memset(node_p, 0, sizeof(accel_node));
            if(parent_p->child == NULL) {
                parent_p->child = node_p;
            }
            else if(parent_p->last_child) {
                parent_p->last_child->next = node_p;
            }
            parent_p->last_child = node_p;
            if(parent_p->list_next) {
                node_p->list_next = parent_p->list_next;
            }
            parent_p->list_next = node_p;
        }
        return node_p;
    }

    //возвращает указатель на корневой узел
    inline accel_node_p get_root() { return root; }

    //добавляет аттрибут в список аттрибутов узла
    bool add_attribute(accel_node_p node_p, char *value_p, int size, 
                       accel_attrib_type type) {
        if(root == NULL) {
            return false;
        }
        if(!node_p) {
            node_p = root;
        }
        accel_attribute_p attr_p = new accel_attribute;
        if(!attr_p) {
            return false;
        }
        attr_p->next      = NULL;
        attr_p->field_len = size;
        attr_p->field_p   = value_p;
        attr_p->type      = type;
        if(!node_p->attrib_list) {
            node_p->attrib_list = attr_p;
        }
        else if(node_p->attrib_list_last){
            node_p->attrib_list_last->next = attr_p;
        }
        node_p->attrib_list_last = attr_p;
        node_p->attrib_count++;
        return true;
    }
};

class ACCEL_Parser {
    PARSER_Stack stack;
    PARSER_Three three;
private:
    //возвращает true, если переданный символ является пробелом
    inline bool _is_space(int c) { return (c == ' ') || (c == '\t'); }
    //возвращает true, если переданный символ является переводом на новую строку
    inline bool _is_new_line(int c) { return (c == '\r') || (c == '\n'); }
    //возвращает true, если переданный символ является допустимым в числах
    inline bool _is_number(int c) { return isdigit(c) || (c == '.') || (c == ',') || (c == '-'); }
    //выделяет буфер и читает слово из потока
    char *_read_word(std::istream &_in, int start, int end) {
        int cur_pos = _in.tellg();
        int length  = end - start;
        char *value = new char[length + 1];
        if(!value) {
            return NULL;
        }
        _in.seekg(start, std::ios::beg);
        _in.read(value, length);
        value[length] = 0;
        _in.seekg(cur_pos, std::ios::beg);
        return value;
    }
public:
    ACCEL_Parser()
        :stack(MAX_NODE_DEPTH)
    {
    }

    ACCEL_Parser(std::istream &_in)
        :stack(MAX_NODE_DEPTH)
    {
        load(_in);
    }

    //загружает документ из потока
    error_code load(std::istream &_in) {
        error_code result  = ec_succeful; //код ошибки
        register parser_state state = ps_idle; //текущее состояние
        register int c = 0;
        int read_start = 0; //позиция, с которой начинается чтение слова
        int read_end   = 0; //позиция, в которой заканчивается чтение слова
        accel_attrib_type attr_type = at_none; //тип читаемого аттрибута
        accel_node_p node_p = NULL; //текущий узел дерева
        if( !stack.push(three.get_root()) ) {
            return ec_stack_overflow;
        }
        while( (result == ec_succeful) && !_in.eof() ) {
            switch(state) {
                case ps_idle:
                    if(c == '(') {
                        c = _in.get();
                        if( !isalpha(c) ) {
                            /* После открывающей скобки должны быть
                             * только символы английского алфавита,
                             * пробелы, переносы строк и другие символы
                             * не допускаются */
                            result = ec_syntax;
                            continue;
                        }
                        read_start = _in.tellg();
                        read_start--;
                        state      = ps_read_node;
                        continue;
                    }
                    if(c == ')') {
                        if( !stack.pop() ) {
                            result = ec_stack_clear;
                            continue;
                        }
                        node_p = stack.peek();
                        if(!node_p) {
                            result = ec_stack_clear;
                            continue;
                        }
                    }
                    break;
                case ps_read_node:
                    if( _is_space(c) || _is_new_line(c) ||
                        (c == '(') || (c == ')') ) {
                            //прочитали имя узла...
                            node_p = three.insert(node_p); //создаем узел дерева
                            if(!node_p) { //ошибка выделения памяти
                                result = ec_memory;
                                continue;
                            }
                            if( !stack.push(node_p) ) { //помещаем указатель на узел в стек
                                result = ec_stack_overflow;
                                continue;
                            }
                            read_end = _in.tellg();
                            read_end--;
                            node_p->name = _read_word(_in, read_start, read_end);
                            if(!node_p->name) {
                                result = ec_memory;
                                continue;
                            }
                            if(!node_p->name) {
                                result = ec_memory;
                                continue;
                            }
                            if( (c == '(') || (c == ')') ) {
                                state = ps_idle;
                                continue;
                            }
                            state = ps_wait_attrib;
                            break;
                    }
                    if( !isalnum(c) ) {
                        //недопустимый символ в имени узла
                        result = ec_syntax;
                        continue;
                    }
                    break;
                case ps_wait_attrib:
                    if( _is_space(c) || _is_new_line(c) ) {
                        break; //пропускаем пробелы и переводы строк
                    }
                    if( (c == '(') || (c == ')') ) {
                        state = ps_idle;
                        continue;
                    }
                    read_start = _in.tellg();
                    if(c == '"') {
                        attr_type = at_string; //тип значения аттрибута - строка
                    }
                    else if( _is_number(c) ) {
                        attr_type = at_number; //тип значения аттрибута - число
                        read_start--; //аттрибут без разделителей
                    }
                    else if( isalnum(c) ) {
                        attr_type = at_property; //тип значения аттрибута - опция
                        read_start--; //аттрибут без разделителей
                    }
                    else { //недопустимый символ...
                        result = ec_syntax;
                        continue;
                    }
                    state = ps_read_attrib;
                    break;
                case ps_read_attrib:
                    if(attr_type == at_string) {
                        if(c == '"') {
                            //нашли конец строки...
                            read_end = _in.tellg();
                            read_end--;
                            char *value = _read_word(_in, read_start, read_end);
                            if(!value) {
                                result = ec_memory;
                                continue;
                            }
                            if( !three.add_attribute(node_p, value, read_end - read_start,
                                at_string) ) {
                                    result = ec_memory;
                                    continue;
                            }
                            state = ps_wait_attrib;
                        }
                    }
                    else {
                        if( (attr_type == at_number) ||
                            (attr_type == at_property) ) {
                            if( _is_space(c) || _is_new_line(c) ||
                                (c == ')') || (c == '(') ) {
                                //чтение аттрибута завершено
                                read_end = _in.tellg();
                                read_end--;
                                char *value = _read_word(_in, read_start, read_end);
                                if(!value) {
                                    result = ec_memory;
                                    continue;
                                }
                                if( !three.add_attribute(node_p, value, read_end - read_start,
                                    attr_type) ) {
                                        result = ec_memory;
                                        continue;
                                }
                                if( (c == ')') || (c == '(') ) {
                                    state = ps_idle;
                                    continue;
                                }
                                state = ps_wait_attrib;
                            }
                            else if( (attr_type == at_number) && !_is_number(c)) {
                                //недопустимый символ в числе...
                                result = ec_syntax;
                                continue;
                            }
                        }
                    }
                    break;
            }
            c = _in.get();
        }
        return result;
    }
};

class ACCEL_Document {
private:
    ACCEL_Parser parser;
public:
    ACCEL_Document()
    {
    }

    ACCEL_Document(std::istream &input)
        :parser(input)
    {
    }

    ACCEL_Document(char *file_name)
    {
        std::ifstream f(file_name, std::ios::binary);
        if( f.is_open() ) {
            parser.load(f);
            f.close();
        }
    }
};

#endif //__ACCEL_ASCII_H__

[Антон (LogRus)]

Лично я бы читал через потоки, если библиотека внутренняя можно элементы дерева выделять из пула памяти
код тяжеловат и является смесью C и C++ особенно удручают длинные case/if/else я бы заменил на вызов функций
далее определение типа атрибута я бы выкинул вообще (строка и всё) или перенёс бы на момент, когда атрибут зачитан целиком или поместить в вариант.
конструкции  read_end-- или read_start-- или _in.seekg(start, std::ios::beg) а также _ptr++
вопервых такой простой формат можно распарсить за один проход, вовторых  есть STL и стандартные контейнеры

общее впечатление - слишком сложно, что бы это работало

[RuNTiME]

LogRus,  да согласен, код тяжеловат, но факт что работает:) и парсер работает в один проход. Длинная конструкция switch это реализация конечного автомата на 4 состояния и перебросить от туда код в функции довольно сложно, т.к. в проверках if/else происходит управление работой всего цикла спомощью continue и break и переключение состояний автомата. Даже если вынести код в функции, то результат их выполнения придется проверять и появятся дополнительные if/else которые не тольго загрузят код, но еще дадут дополнительную задержку... Вопрос несколько в другом, каким образом организовать выделение памяти, чтобы не использовать такое количество new/delete. Ведь они вносят основную задержку в выполнение кода.

[Алексей++]

утяжеляет код не наличие свичей и if , а кривое форматирование

[Антон (LogRus)]

эх молодёж

LogRus,  да согласен, код тяжеловат, но факт что работает:) и парсер работает в один проход.

во-первых, пока ты используешь read_end-- или read_start-- или _in.seekg(start, std::ios::beg) можешь мне про один проход не рассказывать
полагаю твой парсер не сможет работать, если вместо файла ему подсунуть stdin

Длинная конструкция switch это реализация конечного автомата на 4 состояния и перебросить от туда код в функции довольно сложно

Жалкие отмазки, не достойные программиста Если честно, то я бы своим коллегам высказал всё, что думаю о коде и попросил бы переписать, если понадобится с нуля.

Даже если вынести код в функции, то результат их выполнения придется проверять и появятся дополнительные if/else которые не тольго загрузят код, но еще дадут дополнительную задержку...

Бу-га-га буквально думаю враг твоей производительности new и delete, а не какие-то примитивные if/else/switch
ранняя оптимизация это одна из самых худших вещей которые может сделать программист

Вопрос несколько в другом, каким образом организовать выделение памяти, чтобы не использовать такое количество new/delete. Ведь они вносят основную задержку в выполнение кода.

во-во
тут тебе нужно искать компромис между скоростю и расходом памяти может еще какие компромиссы найдутся

[RuNTiME]

LogRus,

во-первых, пока ты используешь read_end-- или read_start-- или _in.seekg(start, std::ios::beg) можешь мне про один проход не рассказывать
полагаю твой парсер не сможет работать, если вместо файла ему подсунуть stdin

Парсер сможет работать и с stdin. Т.к. функция seekg определена в istream, а в файловом потоке
ifstream она просто переопределена для работы с файлами.
Переменные read_end и read_start существуют только за тем, чтобы измерить длинну слова и динамически выделить под него память. Я хотел ибзавить код от ограничения на длинну строки. Как ты себе представишь выделение памяти, если не знаешь заранее длинну строки? только не надо говорить про std::string s+= str; ...  Да действительно после измерения длинны строки парсер перемещается на её начало и копирует строку в память, но заметь, синтаксис не разбирается по новой, по этому я говорю, что парсер работает в один проход. И если допустить ограничение на длинну слова и выделить постоянный буфер, в который будет сразу копироваться слово (копирование будет перенесено на этап измерения длинны слова), то все равно, после окончания копирования во временный буфер, придется снова копировать в динамически создаваемые структуры, что ничем не лучше чем перемещение по istream и ОДНОКРАТНОЕ копирование слова в память.

Жалкие отмазки, не достойные программиста  Если честно, то я бы своим коллегам высказал всё, что думаю о коде и попросил бы переписать, если понадобится с нуля.

С этим могу согласиться... if/else вносят ничтожно малую нагрузку... Но я не уверен в том, что проверок возвращаемых значений функций будет намного меньше и код будет выглядеть намного лучше, хотя с этим надо поэкспериментировать...

во-во
тут тебе нужно искать компромис  между скоростю и расходом памяти может еще какие компромиссы найдутся

Это собственно и был начальный вопрос топика, если ты не заметил...

[Антон (LogRus)]

Переменные read_end и read_start существуют только за тем, чтобы измерить длинну слова и динамически выделить под него память. Я хотел ибзавить код от ограничения на длинну строки.

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

[RuNTiME]

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

LogRus,  да в таком варианте работать не будет. Если делать однонаправленное чтение, то необходим буфер фиксированной длинны, это наложит ограничение на длину строки. Что ты можешь предложить в этом случае?