Детерминированный конечный автомат можно использовать для реализации очень быстрого способа разбора входной последовательности. Требуется всего один проход по входной последовательности, и минимальные действия на каждом шаге. К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики). Или даже если возможно построить, автомат может иметь слишком большое число состояний.
Тем не менее я решил попробовать создать парсер для 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#. С готовым автоматом можно работать следующим образом:
На практике, ДКА для HTTP запроса содержит до минимизации 150К состояний, после 1К-2К. Понятно, во первых, что 1К-2К вполне приемлемое значение для реального использования. Во вторых 150К состояний, требует некоторой памяти и времени на вычисления (по крайней мере в моей реализации) — минут x-цать.
Скорость работы парсера очень высокая, формальная грубая оценка для такого подхода ~С*O(n), и принципиально улучшить ее наверное сложно. В реальности, парсер на C# у меня на машине, успел распарсить 1М раз за 3.3 секунды сообщение длиной 220 байт.
Исходный код проекта доступен: code.google.com/p/siprevo
Код на выходе генератора старался сделать аккуратным, но сам генаратор слегка (если не сказать больше) в черновом варианте. Хорошо (только не во время отладки) что такие системы почти не могут слегка глючить, оно либо работает, либо не работает, в данном случае работает.
Update: «компилятор» автомата в виде отдельной утилиты живет здесь.
Тем не менее я решил попробовать создать парсер для 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: «компилятор» автомата в виде отдельной утилиты живет здесь.