Регулярки - применение. Итог темы об автоматных языках⁠⁠

Предыдущая статья: Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка в vk.com

Чем выгодно отличаются регулярные выражения от рисунка порядка и записи грамматики, так это то, что они представляют из себя строки. Что даёт нам возможность легко обрабатывать их программно и автоматизированно создавать распознаватели автоматных языков. Реализация которых может быть представлена в виде таких схем:

В предыдущей статье, показана таблица соответствий регулярных выражение с участками рисунка порядка, а в предпредстатье создание распознавателя не прибегая к таблицам переходов.

Регулярные выражения (далее РВ) по своей сути являются языком из алфавита { |, (, ), *, a}, где а - множество различных символов алфавита задаваемого языка. Можно ли с помощью РВ задать язык РВ? Ответ: нет, так как язык РВ не является автоматным, из-за самовложения он является КС-языком. Ниже представлена его грамматика с учётом приоритетов операций:

R → T | R ′′|′′ T
T → M | RM
M → a | M* | ( R ) | ε

Запись ′′|′′ представляет знак | используемый в регулярных выражениях.

При реализации РВ, человеческая лень с одной стороны упростила запись РВ , с другой усложнило понимание и чтение их, но это спорное утверждение. Была расширена нотация языка с помощью сокращений, для кол-ва повторений:

a? = (a|)
a+ = (aa*)
a{2,4} = (aa|aaa|aaaa)

Сокращение для «или»:
[abcd] = (a|b|c|d) - нужно отметить ещё, что символы между [ и ] не нужно экранировать.

Сокращения часто встречающихся множеств, один пример:
\d = (0|1|2|3|4|5|6|7|8|9)

А то и вовсе добавлены управляющие символы движка распознавателя, для указания где в строке нужно искать совпадение в ^ начале или в $ конце? В любом случае вам придётся открывать руководство конкретно-используемого инструмента, так как на долго в голове всё это удержать не возможно.

С помощью всего этого запись: (+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* превратилась в [+-]?\d+ , но вам никто не запрещает писать по «старинке».

В этой же статье я хотел вам показать взаимосвязь регулярных выражений с автоматными языками и распознавателями.

Итог: С помощью автоматных грамматик и регулярных выражений определяется синтаксис простейших конструкций языков программирования, таких как идентификаторы, различные литералы цифр, знаки операций.

Путеводитель по пройденным статьям:
1. Что такое язык программирования? Не спешим отвечать, знакомимся с определением формальных языков
2. Грамматика языка и порождающие грамматики. Сказ о «правильных» скобочках
3. Хомски и его иерархия грамматик
4. Дерево вывода предложения (сентенции) грамматики. Синтаксическое дерево
5. Задача разбора, для чего она нужна? Или что такое parsing?
6. Эквивалентность и однозначность грамматики или почему иногда 2+2*2=8?
7. Графы автоматных грамматик. Что же, начинаем знакомится с конечными автоматами?
8. Конечные автоматы, что там внутри?
9. Обещанная реализация КА и попытка создать таблицу переходов не детерминированному автомату
10. Преобразование НКА в ДКА, один из алгоритмов
11. Синтаксические диаграммы автоматных языков - рисунок порядка автоматных языков
12. Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка

Ну как-то так, друзья. Дальше в лес КС-грамматик, присоединяйтесь.