• Регулярные выражения изнутри

    Регулярные выражения (РВ) — это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим примеры таких систем:

    • Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
    • Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
    • РВ в языках программирования.


    В данной статье мы сначала ознакомимся с конечными автоматами и их видами (ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.
    Читать дальше →