Практика создания грамматики по регулярным выражениям и построение дерева вывода

Состав и синтаксис регулярных выражений

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

• (пустое множество) ?.
• (пустая строка) е обозначает строку, не содержащую ни одного символа. Эквивалентно ««.
• (символьный литерал) «a», где a — символ алфавита У.

и следующие операции:

• (сцепление, конкатенация) RS обозначает множество {бв | б? R & в? S}. Например, {" boy", «girl» }{" friend", «cott» } = {" boyfriend", «girlfriend», «boycott», «girlcott» }.
• (дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {" ab", «c» }|{" ab", «d», «ef» } = {" ab", «c», «d», «ef» }.
• (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит е и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {" Go", «Russia» }* = {е, «Go», «Russia», «GoGo», «GoRussia», «RussiaGo», «RussiaRussia», «GoGoGo», «GoGoRussia», «GoRussiaGo», …}.

Синтаксис Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] / ^ $. |? * + () { }, которые могут быть предварены символом (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Можно экранировать целую последовательность символов, заключив её между Q и E.

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

Метасимвол. (точка) означает один любой символ, но в некоторых реализациях исключая символ новой строки.

Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. В частности, [абв]задаёт возможность появления в тексте одного из трёх указанных символов, а [1 234 567 890] задаёт соответствие одной из цифр. Возможно указание диапазонов символов: например, [А-Яа-я] соответствует всем буквам русского алфавита, за исключением букв «Ё» и «ё».

Если требуется указать символы, которые не входят в указанный набор, то используют символ ^ внутри квадратных скобок, например [^0−9] означает любой символ, кроме цифр.

Некоторые символьные классы можно заменить специальными метасимволами:

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