Синтаксический анализ текста всегда начинается с лексического анализа или tokenizing-а. Существует простой способ решить эту задачу практически для любого языка с помощью регулярных выражений. Еще одно применение старым добрым regexp-ам.
Рубрика «DFA»
Профессиональный лексический анализ на регулярных выражениях
2019-08-07 в 6:11, admin, рубрики: algorithms, DFA, java, lexer, nfa, regex, regexp, syntax analysis, syntax highlight, tokenizer, tokenizing, Алгоритмы, Компиляторы, Программирование, Регулярные выраженияРазбор решения занявшего второе (пока что) место в конкурсе Hola по программированию почтовых фильтров на JavaScript
2016-01-12 в 11:58, admin, рубрики: deterministic finite automata, DFA, hola, javascript, nfa, node.js, nodejs, non-deterministic finite automata, Алгоритмы, конечный автомат, конкурс, конкурсы, конкурсы разработчиков, оптимизация, соревнование, соревнования, соревнования по программированию, Спортивное программирование, фильтрация писем, фильтрация почтыВ ноябре прошлого (уже) года, Hola объявила конкурс по программированию почтовых фильтров на js, и недавно опубликовала его результаты.
Я разделил второе место с Ильей Макаровым, и сейчас я расскажу…
Как это было
Что-то посложнее факториала
2013-05-08 в 11:28, admin, рубрики: c++, DFA, nfa, templates, КодоБред, ненормальное программирование, ностальгия, метки: c++, DFA, nfa, templates, ностальгия Давным-давно, когда трава была зеленее, а деревья выше, жил-был тролль, по имени Xenocephal. Жил он, в принципе, во многих местах, но мне повезло встретить его на одном форуме, где я, в то время, набирался ума-разума. Я уже не вспомню топика, в котором протекала беседа, но суть ее сводилась к тому, что Xenocephal пытался убедить всех окружающих, что Lisp (с его макросами) — всему голова, а C++, с его шаблонами, жалкое подобие левой руки. Также утверждалось, что наметапрограммировать в нем что-то сложнее набившего оскомину факториала не представляется возможным.
Читать полностью »
Ошибка в HTTP протоколе
2012-10-01 в 14:05, admin, рубрики: .net, DFA, http, nfa, Алгоритмы, ДКА, Программирование, метки: DFA, http, nfa, ДКА В статье я хочу рассказать не столько об ошибке в RFC 2616, сколько о своем подходе к созданию парсера HTTP сообщений, показать его преимущества и недостатки. В основу моего подхода положено два принципа «лучше час потерять, потом за пять минут долететь» и «пусть компьютер работает, а я отдохну».
Читать полностью »
Создание конечного автомата для разбора HTTP запроса
2012-04-09 в 12:49, admin, рубрики: .net, DFA, http, parser, ДКА, Компиляторы, метки: DFA, http, parser, ДКАДетерминированный конечный автомат можно использовать для реализации очень быстрого способа разбора входной последовательности. Требуется всего один проход по входной последовательности, и минимальные действия на каждом шаге. К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики). Или даже если возможно построить, автомат может иметь слишком большое число состояний.
Тем не менее я решил попробовать создать парсер для HTTP запроса на основе ДКА. Основная задача не просто проверить корректность HTTP запроса, а именно выделить во входной строке элементы соответствующие определенным значениям полей HTTP запроса. Автомат должен генерироваться из BNF правил (разбросанных по) RFC2616. Реализовано все на C#, автомат на выходе тоже на C#. Хотя понятно что когда автомат готов, сгенерировать его на любом языке, в любом виде не проблема.
Читать полностью »