Создание конечного автомата для разбора HTTP запроса

Детерминированный конечный автомат можно использовать для реализации очень быстрого способа разбора входной последовательности. Требуется всего один проход по входной последовательности, и минимальные действия на каждом шаге. К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики). Или даже если возможно построить, автомат может иметь слишком большое число состояний.

Тем не менее я решил попробовать создать парсер для HTTP запроса на основе ДКА. Основная задача не просто проверить корректность HTTP запроса, а именно выделить во входной строке элементы соответствующие определенным значениям полей HTTP запроса. Автомат должен генерироваться из BNF правил (разбросанных по) RFC2616. Реализовано все на C#, автомат на выходе тоже на C#. Хотя понятно что когда автомат готов, сгенерировать его на любом языке, в любом виде не проблема.

Для генерации ДКА реализована следующая цепочка действий:
1. Разбор BNF правил
2. Создание на их основе НКА
3. Преобразование НКА в ДКА
4. Минимизация ДКА
5. Создание файлов с исходным текстом и таблицей переходов

Для разбора BNF грамматики я воспользовался Irony, грамматика ABNF хорошо описана в RFC5234. По синтаксическому дереву программа строит НКА по правилам Томсона. Для преобразования НКА в ДКА, и минимизации использованы стандартные алгоритмы, описывать их тоже не буду.

Так как HTTP сообщение, относительно простой объект, то на выходе парсера — класс (этого достаточно), с полями соответствующими HTTP заголовкам. Для того чтобы автомат в процессе прохода мог парсить сообщение, в ДКА при генерации в нужные состояния добавляются простые действия, модифицирующие переменные класса. К примеру, нужно получить значение заголовка Host, в классе предусмотрены две переменные начало и конец заголовка. В состояниях которые срабатывают когда автомат идет по значению поля Host, добавляются действия по изменению этих переменных. В самом ДКА определить какое состояние за что отвечает, на практике невозможно. Поэтому состояния помечаются при создании НКА, и дальше эти метки сохраняются, при всех преобразованиях автомата. Для упрощения отметки состояний и назначения действий был сделан простейший язык, в котором задаются названия переменных и какие значения они получат. На основе этих данных потом уже и генерируется класс, в который парсер помещает результат работы.

Подобный подход используется в регулярных выражениях (хотя не во всех реализациях делают преобразование в ДКА). Но имея прямой доступ к автомату, возможно произвести ряд интересных оптимизаций. К примеру, поле Content-Lenght содержит длину тела сообщения, для этого поля преобразование в число происходит прямо в автомате, на выходе имеем поле класса int ContentLenght. Еще одна интересная оптимизация, к примеру для HTTP запроса определен набор методов (GET,HOST...). На выходе парсера можно сразу получить константу соответствующую методу. И все это за один проход.

Так же очень важно, что парсер принимает на вход массив байт, особенно это актуально для современных языков вроде C#, где строка это не массив байт как в C++, и простым кастингом указателя здесь не обойдешься.

В целом система выглядит следующим образом. Имеется BNF грамматика, и описание класса который хотим получить на выходе. Все это подаем на вход генератора, и получаем ДКА на C#. С готовым автоматом можно работать следующим образом:

dfa.SetDefaultValue();
dfa.Parse(message0, 0, message0.Length);
dfa.SetArray(message0);

Console.WriteLine("Method: {0}", dfa.Method);
Console.WriteLine("Request-URI: |{0}|", dfa.RequestUri.ToString());
Console.WriteLine("Host: |{0}|", dfa.Host.ToString());
Console.WriteLine("Content-Type: |{0}|", dfa.ContentType.Value.ToString());
Console.WriteLine("Content-Length: {0}", dfa.ContentLength);
Console.WriteLine("Referer: |{0}|", dfa.Referer.ToString());


На практике, ДКА для HTTP запроса содержит до минимизации 150К состояний, после 1К-2К. Понятно, во первых, что 1К-2К вполне приемлемое значение для реального использования. Во вторых 150К состояний, требует некоторой памяти и времени на вычисления (по крайней мере в моей реализации) — минут x-цать.

Скорость работы парсера очень высокая, формальная грубая оценка для такого подхода ~С*O(n), и принципиально улучшить ее наверное сложно. В реальности, парсер на C# у меня на машине, успел распарсить 1М раз за 3.3 секунды сообщение длиной 220 байт.

Исходный код проекта доступен: code.google.com/p/siprevo

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

Update: «компилятор» автомата в виде отдельной утилиты живет здесь.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 12
  • +2
    > К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики).
    Вообще-то даж теорема есть, что любой НКА можно преобразовать в эквивалентный ДКА. Но в итоге у ДКА может оказаться дохреналион состояний.
    • 0
      Да, действительно.
    • +2
      Несмотря на то, что код программы не изобилует комментариями, а все алгоритмы ясны, понятны и известны, не могли бы вы привести их хотя бы в виде «списка использованной литературы»?
      • +2
        Вот отличная релевантная статья, в ней есть ссылки на 3 pdf-ки. В них очень кратко, но мой взгляд удачно, описаны все необходимые алгоритмы: конструкции Томсона, НКА->ДКА, минимизация ДКА.
      • 0
        Пожалуйста приведите SVN репозиторий в актуальное состояние — часть файлов из проекта потеряна :(
        • 0
          Там часть файлов нужно сгенерировать, алгоритм такой: загружаем солюшен; делаем Unload project для проектов в которых не хватает файлов (HttpDfaTester, SipDfaTestet, Http.Message); под Release запускаем проект HttpDfaCompiler; после завершения делаем Reload Project для Http.Message и HttpDfaTester (у меня студию без перезагрузки не смогла собрать), собираем и эксперементируем с HttpDfaTester. В следующие разы все собирается без «танцев с бубном». Да, получилось не очень удобно, в следующей версии сделаю чтобы работало «из коробки».
        • НЛО прилетело и опубликовало эту надпись здесь
        • НЛО прилетело и опубликовало эту надпись здесь
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              1) Было желание использовать бнф как он есть в rfc, с минимальными изменениями, вообщем-то получилось вообще без изменений
              2) Меньше — да, быстрее нет. И еще одно странное ограничение, не создавать-уничтожать объекты вообще. На c++ можно было бы вообще в одну struct уложить — одним блоком памяти. На c# конечно ссылки появляются.

              Не получил уведомления с хабра, поэтому не ответил раньше.
            • 0
              Кстати, сам компилятор автомата оформил в отдельную утилиту, теперь гораздо удобнее пользоваться. И по скорости, удалось сделать существенные улучшения.
              https://github.com/vf1/bnf2dfa

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.