Как текстовый движок регулярных выражений работает внутри?

Question

Я хочу реализовать простой движок регулярных выражений с текстовым управлением, используя MFC в c ++. Так можете ли вы сказать мне, как текстовый движок регулярных выражений работает внутри?

Например, <. +> Это найдет тег в html. Как это работает внутри?

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

Answer 1

Это слишком сложно объяснить в SO-ответе. Вам нужен либо расширенный учебник по компиляторам, либо доступ к исходному коду существующего движка Regex. К счастью, исходный код OpenJDK является открытым исходным кодом ... как и исходный код для версии Apache Harmony, версии Perl, версии Python и т. Д.

Некоторые возможные учебники:

• "Компиляторы: принципы, методы и инструменты (2-е изд.)" от Aho Sethi & Ullman (он же книга Дракона) Глава о лексическом анализе охватывает регулярные выражения и их реализацию.

• «Введение в теорию автоматов, языков и вычислений (3-е издание)» , автор Hopcroft, Motwani &. Ульман. (Предоставлено @Noufal Ibrahim.)

(Более ранние издания обеих книг также доступны ... за меньшие деньги.)

---

Например, <.+> это найдет тег в html, как он работает внутри.

Глупый ответ заключается в том, что это зависит от используемого вами движка Regex.

Answer 2

Вообще говоря, регулярные выражения переводятся внутренне в конечный автомат, который затем «выполняется» на основе текстового ввода. Это довольно сложная тема, но вы можете реализовать подмножество современных регулярных выражений в выходные дни, если хотите изучить внутреннее устройство. Книги, которые Стивен С. связал (особенно книга дракона), и любой стандартный учебник по дискретной математике должны содержать подробности