Квантификаторы

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

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

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

Допустим, необходимо искать во входном потоке слова color или colour. Эти слова почти одинаковы и отличаются только одной буквой u. Следующее регулярное выражение позволяет найти любой из указанных вариантов слова:

В данном случае метасимвол ? обозначает, что предшествующая ему буква u является необязательным символом. Она может находиться в данной позиции текста, но ее наличие не требуется для успеха совпадения входного слова с заданным регулярным выражением. Следует отметить, что эквивалентный результат позволяет обеспечить операция объединения в следующей конструкции выбора:

Более богатыми возможностями обладает квантификатор *, который обозначает, что во входном потоке может находиться любое, в том числе равное нулю, количество экземпляров предшествующего ему символа регулярного выражения. Это одна из классических базовых операций, которая известно в теории формальных языков как итерация или замыкание Клини.

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

В этом регулярном выражении квантификатор * применяется к классу символов [0-9], обеспечивая совпадение с цифровой последовательностью любой, в том числе нулевой длины. Класс символов [1-9] гарантирует наличие первой цифры натурального числа. Из диапазона символов этого класса исключена цифра 0, с которой, очевидно, не может начинаться не может начинаться натуральное число. Это регулярное выражение также возможность совпадения исключает совпадения с числом 0, которое не принадлежит натуральному ряду чисел. Следует отметить, что в данном случае весьма проблематично построить эквивалентное регулярное выражение, используя оператор объединения.

Похожими возможностями обладает квантификатор +, который также как метасимвол *, обеспечивает многократное повторение элементов входного потока, но гарантирует наличие хотя бы одного экземпляра, удовлетворяющего регулярному выражению. В теории формальных языков эту регулярную операцию часто называют позитивным замыканием Клини. Она может быть успешно использована, например, для спецификации символьных разделителей информационных структур. Обычно в разделителях допускается произвольное количество разделяющих символов, но обязательно должен быть хотя бы один. В частности, следующее регулярное выражение позволяет идентифицировать разделители из произвольного числа символов пробела и горизонтальной табуляции:

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

Кроме рассмотренных одно-символьных квантификаторов генератор LEX предоставляет специальную мета-последовательность, которая позволяет конкретно задавать наименьшее обязательное и наибольшее допустимое число экземпляров повторений. Эта конструкция называется интервальным квантификатором и имеет следующий формат:

В этой конструкции, параметры N и M, указанные в фигурных скобках, задают целые неотрицательные десятичные числа, которые устанавливают, соответственно, минимальное и максимальное количество повторений во входном потоке символа или фрагмента регулярного выражения, обозначенного литерой R перед фигурными скобками. В конструкции интервального квантификатора значение первого целочисленного параметра не должно превосходить величины второго целочисленного параметра, а литерал, допустимый диапазон повторений которого они определяют, может быть любым символом. Наиболее часто используется вариант применения интервального квантификатора, когда заданное минимальное количество повторений строго меньше максимального (N < M). Такая интервальная конструкция удобна, например, для распознавания идентификаторов переменных и констант в исходных текстах программ.

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

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

Следует отметить, что если не требуется ограничивать максимальную длину идентификатора, то в рассмотренном регулярном выражении нужно заменить интервальный квантификатор {0,31} метасимволом *:

Менее распространенным является вариант спецификации интервального квантификатора, где заданные минимальное и максимальное значения количества повторений равны (N = M). Это позволяет задавать в регулярном выражении фиксированное количество повторений.

Например, следующее регулярное выражение определяет огромное целое число, равное единице с 24-мя нулями (1024), которое согласно представлениям современной астрофизики определяет размер видимой части Вселенной, выраженный в километрах:

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

Например, для спецификации инструкции инкремента языка программирования C, которая обозначается парой знаков плюс (++) после идентификатора переменной, может быть предложено следующее регулярное выражение:

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

Следует отметить, что концепция регулярных определений, принятая в генераторе LEX, напоминает технологию использования макроопределений, которая реализуется, например, в системе программирования C директивой предпроцессорной обработки #define, в частности, для символического обозначения констант.

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

Характерные разновидности конструкций грамматических правил в спецификациях генератора YACC. Основные операции грамматического разбора, реализуемые при восходящем синтаксическом анализе.

Каждое правило описывает грамматическую конструкцию, называемую нетерминальным символом, и сопоставляет ей имя. С точки зрения грамматического разбора правила рассматриваются как правила вывода (подстановки). Грамматические правила описываются в терминах некоторых исходных конструкций, которые называются лексическими единицами, или лексемами. Имеется возможность задавать лексемы непосредственно (литерально) или употреблять в грамматических правилах имя лексемы. Как правило, имена сопоставляются лексемам, соответствующим классам объектов, конкретное значение которых не существенно для целей грамматического анализа. (Иногда в литературе с понятием лексемы совпадает понятие терминального символа; однако, ряд авторов называет терминальными символами отдельные символы стандартного набора). Примерами имен лексем могут служить идентификатор и число, а введение таких Лексем позволяет обобщить конкретные способы записи идентификаторов и чисел. В некоторых случаях имена лексем служат для придания правилам большей выразительности.

При восходящем разборе стек используют для накопления основы. Автомат при

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

Сентенциальной формой грамматики G называется цепочка, выводимая из начального нетерминала грамматики G.

Сентенцией грамматики G называется сентенциальная форма, состоящая только из терминальных символов.

Левосторонний восходящий грамматический разбор («слева- направо»)

Метод разбора «слава-направо» применим, если грамматика не содержит правил с

правосторонней рекурсией.

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

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

26. Построить ДКА для распознавания строк, генерируемых грамматикой G с порождающими правилами:….