XML парсер своими руками...?

[ip]

Здравствуйте.
Хотелось бы узнать, что будет эффективнее, если стоит такая задача:
Есть xml файл, нужно написать свой парсер (не используя библиотеки др. разработчиков, типа libxml, expat и др.)
Т.е. к примеру xml такой:

Код: Выделить всё

<a>
  [b][/b]
</a>

Я напишу приблизительный алгоритм (как я себе представляю), а вы меня поправте пожалуйста.

1) Определяем начало и конец каждого тега (т.е. позицию "<" и ">")
Вопрос: если нам за ранее не известно число тегов, то тут явно нужен динамический массив, но как лучше сделать?
а) первый раз пропарсить текст, подсчитать кол-во "<" и кол-во ">", затем на основании этого создать динамический массив. И дальше уже по второму разу парсить текст и заносить в этот массив позиции начала/конца тега ("<" и ">").
б) сразу создать динамический массив, учитывая то, что в минимальном случае число "<" будет равно

Код: Выделить всё

angel_brackets = sizeof(xml_string)/sizeof(char) / 4 + 1;
или
angel_brackets = ((sizeof(xml_string)/sizeof(char)) >> 2) + 1;

т.е. четверть от всего кол-ва символов плюс 1 - это число открывающихся угловых скобок, и по идеи число открывающихся угловых скобок должно быть равно закрывающимся.
Значит можно создавать динамический массив из left_angel_brackets элементов. Если в данном примере все нормально (см. выше) и число скобок можно вычислить с небольшой погрешностью (в сторону увеличения), то если пример будет содержать не пустые теги, а текст и имена тегов будут длинные, то избыток будет ОЧЕНЬ заметным... в n раз. Получается расход памяти увеличивается....Что плохо.

Как тут лучше поступить?

2) Парсим от первой "<" до первой ">" получаем имя открывающегося тега + параметры (если например <a id="123">) и т.д. от второй "<" до второй ">" - второй тег. С проверкой того, чтобы за "<" не следовал символ "/" иаче это закрывающийся тег.

3) сохраняем все это в какую-то структуру.
Вопрос: как хранят структуру XML? Нужно смотреть в сторону деревьев? Может кто подскажет, куда копать?

Это общая такая концепция, является ли она здравой? Или совсем не годится?

Спасибо.

[evgeny_d]

вообще есть 2 подхода к обработке XML.
1) SAX (Simple API for XMLб если я усе правильно помню)
Тут все просто. Документ считывает кусками.

Если попалось открытие тега вызывается что-то типа метода
openTag(String parameters[])
ну и соотв.
closeTag()

Т.е. в памяти ничего обособливо хранить не надо.
Очевидный минус - плохо работать со сложными двевовидными структурами.

Подробнее: http://sax.sourceforge.net/ (там же в исзодниках можно покопаться)

2) DOM (Document Object Model) - более сложная и громоздкая модель.
Отличается тем, что работает с документом в целом. Со всеми вытекающими - деревья, ветки и т.п.
Подробнее: http://www.w3.org/DOM/

[evgeny_d]

Ну а если хочется самому парзер писать - ИМХО, лучше использовать технологию SAX

[Kolinus]

На общую концепцию ИМХО тянет,
но ИМХО зачем писать свои дополнительные глюки, когда есть уже написанные.

Там где ты спрашивал про массив - есть (как правило) или можно реализовать самому списки, который разростаются по мере необходимости.

[chur]

Парсим от первой "<" до первой ">"

Надо учесть, что в значениях атрибутов могут быть символы "<" или ">". Например: <A attr="<opa>">

[ip]

Парсим от первой "<" до первой ">"

Надо учесть, что в значениях атрибутов могут быть символы "<" или ">". Например: <A attr="<opa>">

Ну вообщето знаки "<" и ">" не могут быть использованы в качестве значения атрибутов и имен элементов.

[Absurd]

Грамотные люди обычно юзают какой-нибудь parser generator типа YACC.
Ему на вход дают специальный файл с описанием синтаксиса на спец. языке, а он в ответ порождает парсер с этого языка (в виде программы на ANSI C).

[ip]

Грамотные люди обычно юзают какой-нибудь parser generator типа YACC.
Ему на вход дают специальный файл с описанием синтаксиса на спец. языке, а он в ответ порождает парсер с этого языка (в виде программы на ANSI C).

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

Код: Выделить всё

<stream>
  <msg id="10">
    Some message
  </msg>
</stream>

Что-то типа этого. Т.е. тут как мне кажется задействовать что-то очень серьезное - не стоит .

[DeeJayC]

Ты часом не TIQS API реализуешь?

[ip]

Да нет