Ответ 1
Russ Cox содержит прекрасную коллекцию статей о Реализация регулярных выражений, особенно его статья Сравнение регулярных выражений может быть простым и быстрым стоит прочитать.
Создание механизма регулярных выражений - онлайн-ресурсов?
Мне интересно создать механизм регулярных выражений, как побочный проект, только для учебных целей.
Я знаю теорию оценки регулярных выражений и достаточно разбираюсь в конечных автоматах и т.д.
Что меня интересует, так это то, как в программном обеспечении реализован механизм регулярных выражений. Поэтому мне было интересно, существует ли какой-либо учебник или онлайн-ресурс, объясняющий реализацию механизма регулярных выражений, перевод из регулярного выражения в FSM и т.д. Я не хочу, чтобы какие-либо сайты просто объясняли теорию, лежащую в ее основе.
Спасибо.
Ответы
Ответ 2
Я думаю, что статья Как работают регулярные выражения от Mark-Jason Dominus. Он ориентирован на не-программистов, но он написан очень алгоритмически, и поэтому его можно использовать для реализации такого движка, особенно если у вас есть опыт компиляции. Я сделал это сам.
В статье также упоминаются более продвинутые советы и рекомендации, а также информация об ограничениях на двигатели.
Ответ 3
В первой главе "Красивый код" (Amazon, онлайн-проект) Брайан Керниган рассказывает о элегантном, очень маленьком регулярном выражении Роба Пайка. Это очень просто, но Керниган дает семь упражнений, чтобы расширить его, что может быть хорошим вступлением для вас.
Ответ 4
У меня есть две интересные ссылки для механизмов регулярных выражений,
Ответ 5
Если вам удобно с C, вам, вероятно, удастся найти исходный код для Perl-совместимые регулярные выражения.
Ответ 6
Я опаздываю на вечеринку, но я нашел это назначение курса WSU, наиболее полезным при представлении реализаций двигателя regex на высоком уровне, Я не знаю C, поэтому было приятно, что материал был представлен в языке-агностическом формате. Важно отметить, что он отлично справляется:
- Зачем использовать постфиксную нотацию
- Что представляет собой стек фрагментов NFA
- Алгоритм postfix-to-NFA в псевдокоде
- Структура данных NFA
Кроме того, я нашел статью профессора Pace, полезную при реализации метода re2post, упомянутого WSU и Cox.
Я бы рекомендовал сначала прочитать статью WSU, а затем статью Russ Cox для большей глубины.
Ответ 7
Пятая глава из Алгоритмы Роберта Седжуика - очень хорошее введение в эту тему. Он объясняет, что такое NFA, и как NFA можно создать из регулярного выражения. Примеры имеют визуальные эффекты и очень ясны. У него даже есть код для простого регулярного выражения. И есть несколько упражнений для реализации дополнительных функций регулярных выражений.
Ответ 8
другое простое и ясное воплощение (C, менее 500 строк) RecursiveRegexpRaptor
Ответ 9
Для немецких читателей третья глава "Pattern-Matching-Algorithmen für einfache Strings" из " Algorithmen auf Sequenzen" может быть интересной. Автор - профессор Свен Рахманн, Лерхштул XI, Fakultät für Informatik, TU Dortmund. Все алгоритмы имеют примеры Python.