Pull to refresh

Comments 12

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

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

Articles