Hi, all!

Кто-нибудь из вас занимался написанием парзеров, например, для разбора HTML
тагов в документе? Я занимался. По-хорошему необходимо написать конечный
автомат, который в общем случае получается громоздким и нелинейным. Когда я
делал такой автомат, я потратил 3 дня головной боли, чтобы только построить
таблицу. А вы видели документы RFC, а именно спецификации протоколов? Там
везде используется для описания формата Бэкуса-Наура формулы. И это
правильно. Они интуитивно понятны и могут описывать любой строго заданный
синтаксис. Я тут подумал... И написал некоторую фишку, которая, возможно,
будет интересна обществености... Итак, представляю вам на суд универсальный
парзер (звучит почти как Вечный Двигатель :) ).

Описание: синтаксический анализатор
Назначение: разбор текстовых данных по набору правил, заданных в BNF
Область применения: обработчики протоколов, разбор текстовых данных,
проверка синтаксиса данных, языковые интерпретаторы. И другие.
Принцип работы: обход бинарного дерева правил BNF
Средства разработки: голый GNU C++ v 2.96.
Использованные технологии:
перегрузка операторов, сборка мусора, бинарное дерево, конечный автомат.
Оттестирован на платформах: Intel(Linux), SPARC(Solaris). Не содержит ничего
специфичного для конкретной реализации CPP, операционки или процессора,
поэтому должен компилироваться и под Виндами. Я не пробовал, но уверен. :)

Пример:
#include <stdio.h>
#include <unistd.h>
#include <sys/resource.h>
#include "Formula.h"

#ifdef CCXX_NAMESPACES
using namespace DVLIB;
#endif

void cr( void) {
DVLIB_TOKEN tok = { NULL, 0};
String strtr;
bool ret = false;
try {
------------------------- определяем синтаксис записи URL -------------
Formula OCTET;  OCTET.R( 1, 255);   --------- область с первого по 255
символ
Formula UPALPHA;  UPALPHA.R( 'A', 'Z');  -------- большие буквы
Formula LOALPHA;  LOALPHA.R( 'a', 'z');  --------- маленькие
Formula ALPHA = 1*( LOALPHA | UPALPHA);   -------- просто буквы
Formula DIGIT;  DIGIT.R( "0123456789");   --------- цифры
Formula spec;  spec.R( "~._-");   -------------- спецзнаки
Formula spec1;  spec1.R( "=+-_)(*&%$#@!~'<>?,./:\";[]{}|\\");  ------------
спецзнаки
Formula sheme = ( 1*ALPHA).B(1,10);  ------------ от одной до 10 букв
sheme.setName( "sheme");  ------------- присвоили имя - чтобы сохранялся
контент
Formula fseg = 1*( ALPHA | DIGIT);  ----------- одна буква или цифра
Formula seg = ++( ALPHA | DIGIT);  ------------- от нуля до много букв или
цифр
Formula fsegc = 1*( ALPHA | DIGIT | spec);
Formula segc = ++( ALPHA | DIGIT | spec);
Formula port = (1*DIGIT).B(1,5);  --------- от одного до 5 цифровых
символов
port.setName( "port");
Formula pp = ":" + port;  ------------ после двоеточия следует правило port
Formula rel_path = fsegc + ( ++( "/" + segc));
Formula path = "/" + ( !rel_path);  ------------ после слеша необязательное
правило rel_path
Formula host = fseg + ( 1*( "." + fseg));
host.setName( "host");
Formula abs_URI = !( sheme + "://") + host + ( !pp) + ( !path);
Formula rel_URI = path;
Formula fragment = 1*( ALPHA | DIGIT);
fragment.setName( "fragments");
Formula params = 1*( ALPHA | DIGIT | spec1);
params.setName( "parameters");
Formula url = ( abs_URI | rel_URI) + ( !( "#" + fragment)) + ( !( "?" +
params));
url.setName( "URL");
------------------------- синтаксис записи УРЛа определен, можно
оперировать... :)
ret = url.Parse( "xxx.9090023./ru");
---------- ret = false ==> не подчиняется правилам
ret = url.Parse( "http://xxx.ru:80/index.html");
--------- ret = true - можно работать. :)
String port = url.getElement( "port");
----------- port = "80", заменим его на 8080:
ret = url.setElement( "port", "8080");
----------- ret = true ==> поле изменилось ==> можно собрать новый URL
ret = url.Construct();
----------- ret = true == > формат правилен, новый УРЛ собран
String tmp = url.getElement( "URL");
---------- tmp = "http://xxx.ru:8080/index.html"

---------- и так далее.....

} catch ( Exception &_e) {  _e.print( stdout);  }
}

int main( int argc, char *argv[]) {

printf( "Compiled %s %s to %s\n", __DATE__, __TIME__, argv[ 0]);
cr();
return( 0);
}

Этот код сейчас (без серьезной оптимизации) выполняется на моем 266
Celeron'е под Линуксом 10.000 раз в секунду. Используемая память - 1.2 Kb,
что эквивалентно конечному автомату с матрицей размером 10x10.

Есть, конечно, и недостатки, над которыми я сейчас работаю...
1) если в процессе парзинга обнаружилось, что входной текст не соответствует
формату, парзер тихо завершается со словами "не по правилам!" и нельзя
узнать, что именно "не по правилам". Этот недостаток устраним. :)
2) он на порядок медленнее конечного автомата, что, конечно, не есть хорошо.
КА - самый быстрый способ парзинга и я занимаюсь оптимизацией кода Формулы.
А вот здесь... Сложно приблизить к скорости КА, но можно. Если извернуться
маленько.

Если кого-то заинтересовала эта штучка - пишите.
Я думаю ее приковырять к какому-нибуть стоящему проекту. Есть идеи?
А можно ли найти ей коммерческое применение?
Какие мнения?
---------------------------------------------------------------------
WBR, Dvorkin

Можно, конечно, использовать lexx или bison... Но там все не так просто и
могут быть неоднозначности. :)

• RE: Парзеры, pth, 01:25 , 23-Май-02, (1)