Всем привет! Пишу парсер синтаксиса 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__
