А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 35
Текст из файла (страница 35)
все строки из а и 6: 1с,п,6,аа,п6.6а,66.пап,,.,), Другое регулярное выражение для того же языка — (а*Ь*) ". 5. Регулярное выражение а ) а*Ь описывает язык 1а,6, а6, сса6, ааа6,...), те. строку а и все строки, состоящие из нуля или нескольких а и завершающиеся 6. о Язык, который может быть определен регулярным выражением, называется регулярным множеством (гейи1аг зе~). Если два регулярных выражения г и в описывают один и тот же язык, то г и в называются эквивалемишыми, что записывается как г = ж Например,(а ~ Ь) = (Ь | а). Имеется ряд алгебраических законов для регулярных выражений; каждый такой закон заключается в утверждении об эквивалентности двух разных видов регулярных выражений.
На рис. 3.7 приведены некоторые из этих алгебраических законов для произвольных регулярных выражений т, я и 1. 3.3.4 Регулярные определения Для удобства записи определенным регулярным выражениям можно присваивать имена и использовать их в последующих выражениях так, как если бы это были символы. Если Е является алфавитом базовых символов, то регулярное 171 3.3. Спецификация токенов ОПИСАНИЕ ЗАКОН Оператор ~ коммутативен Оператор ~ ассоциативен Конкатенация ассоциативна Конкатенация дистрибутивна над ~ ег= ге =г г* = (т ~ г)* г*' = г* е гарантированно входит в замыкание Оператор * идемпотентен Рис. 3.7. Алгебраические законы для регулярных выражений определение представляет собой последовательность определений вида д„- г„ Здесь 1) каждое д; — новый символ, не входящий в Е и не совпадающий ни с каким другим 4 2) каждое г; — регулярное выражение над алфавитом Е 0 ~г1ы И2,..., г1, Ограничивая каждое г; символами из Е и ранее определенными именами, можно избежать рекурсивных определений и построить регулярное выражение для любого г, только над Е.
Для этого сначала в г2 выполняется замена всех вхождений 4 (в г2 не могут использоваться никакие иные д), затем в гз выполняется замена 4 и Й2 на г1 и (уже модифицированное) г2 и т.д, наконец, в г„ заменяются все д„г = 1, 2,..., и — 1 модифицированными версиями г„каждая из которых содержит только символы из алфавита Е. Пример 3.5. Идентификаторы С представляют собой строки из букв, цифр и сим- волов подчеркиваний. Далее приведено регулярное определение идентификаторов языка программирования С (для символов, определенных в регулярных опреде- лениях, использован курсив): г(в = в!г г ) (в ( 1) = 1г ) в) ( 1 г (в8) = (гв) 1 г (в / 1) = гв / гй; (в(8)г=вг(1г г является единичным элементом по отношению к кон- катенации 172 Глава 3.
Лексический анализ 1еаег — А ) В ! .. 1 Е ) а 1 Ь | ... ) х ! а!1л1! — 0)1! ..)9 и! — 1е!се! (1еиег / Йп!!)* Пример 3.6. Беззнаковые числа (целые или с плавающей точкой) представляют собой строки типа 5280, О. 01234, 6. 336Е4 или 1. 89Е-4.
Точная специфика- ция этого множества строк представляет собой регулярное определение — 011). )9 д!р! йр1* — . а!!81!з ) с — > (Е (+/ — /с) Йк1гя)/с — с1!и!!з ор!1опа1сгасг1оп орг!опа1Ехропеп! йф! Йу'гз орс!опа1г гас!!оп орс1опа1Ехропеп! пип!Ьег Данное определение гласит; что орс!опа1сгасг1оп либо представляет собой десятичную точку, за которой следует одна или несколько цифр, либо отсутствует (является пустой строкой). В случае присутствия орг1опа1Ехропеп! представляет собой Е, за которым следует необязательный знак + или — и одна или несколько цифр. Заметьте, что за точкой должна следовать как минимум одна цифра, т.е.
запись 1. некорректна, в отличие от записи 1. О. сэ 3.3.5 Расширения регулярных выражений 2. Нуль или один экзелоьтяр. Унарный постфиксный оператор? означает "нуль или один экземпляр", т.е. запись г? представляет собой сокращенную запись г ~ с или, говоря иначе, Б(г?) = Х (г) О (с).
Оператор? имеет те же приоритет и ассоциативность, что и операторы * и +. С тех пор как в 1950-х годах Клини (К!еепе) ввел регулярные выражения с базовыми операторами для объединения, конкатенации и замыкания Клини, к ним было добавлено много расширений, повышающих их способность определять строковые шаблоны. Здесь будут упомянуты несколько расширений в записи регулярных выражений, которые первоначально появились в утилитах 11шх, таких как Еех, и которые в особенности полезны при определении лексических анализаторов. В списке литературы к данной главе содержатся описания некоторых вариантов регулярных выражений, использующихся в настоящее время.
1. Один или несколько экзеиплярое. Унарный постфиксный оператор + представляет положительное замыкание регулярного выражения и его языка. Иными словами, если г — регулярное выражение, то (г) описывает язык + (Ц! ))+. Оператор ~ имеет те же приоритет и ассоциативность, что и оператор '. Два полезных алгебраических закона, г* = г+ ~ с и т+ = гг' = т'г, связывают замыкание Клини и положительное замыкание.
173 3.3. Спецификация токеиов 3. Классы символов. Регулярное выражение а1 ] аз ] ] и„, где все о, являются символами алфавита, может быть представлено сокращением [а1аз .а„], Важно заметить, что, если аыаз,...,а„образуют логическую последовательность, т.е. последовательные прописные буквы, строчиые буквы или цифры, их можно заменить выражением а1 — а„, т.е. первым и последним символами, разделенными дефисом. Например, (аЬс] представляет собой сокращение для а ] Ь ] с, а ]а — к] — сокращение для а]Ь] .
]г. Пример 3.7. Используя указанные сокращения, можно переписать регулярное определение из примера 3.5 в виде ?епег — ]А-еа-а ] ай — ~ ]О- 9] Ы вЂ” 1епег (1епег ] Йр1) Регулярное определение из примера З.б также можно упростить; йф1 — ~ (0-9] Й!фь — ~ Ищй питЬег — йя1м (. йфй)? (Е ]+-]? йрзя)? 3.3.6 Упражнения к разделу 3.3 Упражнение 3.3.1. Обратитесь к руководствам по языкам программирования а) С, б) С++, в) С)5, г) Рог!гап, д) 5ача, е) 1ляр, ж) Я.Н.
и определите ! ) множество символов, образующих входной алфавит (исключая символы, которые могут встречаться только в строках символов или комментариях), 2) лексический вид числовых констант и 3) лексический вид идситификаторов. ! Упражнение 3.3.2. Опишите языки, соответствующие следующим регулярным выражениям: а) а(а]Ь)*а; б) ((е]а)Ь*)*; в) (а]Ь)*а(а]Ь)(а]Ь); г) а*Ьа*Ьа'Ьа*; 11д) (аа]ЬЬ)*((аЬ]Ьа)(аа]ЬЬ)*(аЬ]Ьа)(аа]ЬЬ)*)*.
174 Глава 3. Лексический анализ Упражнение 3.3.3. Сколько в строке длиной п может содержаться а) префиксов; б) суффиксов; в) истинных префиксов; ! г) подстрок; ! д) подпоследовательиостей. Упражнение 3.3.4. Большинство языков чувствительны к регистру (саве зепв)пне), так что их ключевые слова могут записываться единственным образом, и регулярные выражения, описываюпзие соответствующие лексемы, очень просты.
Однако некоторые языки наподобие Я( П. нечувствительны к регистру (саве !пзепя6че), так что ключевые слова могут быть записаны как строчными, так н прописными буквами, а также комбинацией букв в разных регистрах. Так, ключевое слово БОБ БЕЗВЕСТ может быть записано, например, как ве1есс, Яе1есс или вЕ1ЕсТ. Покажите, как написать регулярное выражение для ключевого слова в нечувствительном к регистру языке.
Проиллюстрируйте ваше решение, написав регулярное выражение для "ве1есс" из Я П!.. Упражнение 3.3.5. Напишите регулярные определения для следующих языков. а) Все строки из строчных букв, содержащие пять гласных, а, е, 1, о, и, в указанном порядке.
б) Все строки из строчных букв, в которых буквы находятся в возрастающем лексикографическом порядке. в) Комментарии, представляющие собой строки, заключенные в /* и */, без промежуточных символов */ (кроме случаев, когда они заключены в двойные кавычки). !! г) Все строки из неповторяющихся цифр. Указиьие: попробуйте сначала решить задачу для нескольких цифр, например для (О, 1, 2).
!! д) Все строки из цифр, причем в строке может повторяться не более одной цифры. !! е) Все строки из а и б, в которых четное количество а и нечетное — 6. ж) Множество шахматных ходов в неформальной записи, таких как р-!с4 н !сЬр хе!и. !! з) Все строки нз а и б, не содержащие подстроку або. 175 3.3. Спецификация токеиов и) Все строки из а и б, не содержащие подпоследовательность абб. Упражнение 3.3.6. Запишите классы символов для следующих множеств. а) Первые десять букв (по "3" включительно) как в верхнем, так и в нижнем регистрах. б) Строчные согласные. в) "Цифры" шестнадцатеричного числа (для "цифр", больших 9, могут использоваться либо строчные, либо прописные буквы). г) Символы, могущие находиться в конце корректного предложения на английском языке (например, восклицательный знак).
В следующих упражнениях, по 3.3.10 включительно, используется расширенная запись регулярных выражений из Еех (генератор лексических анализаторов, который будет рассматриваться в разделе 3.5). Выражения расширенной записи приведены на рис. 3.8. Соответствие ВЫРАЖЕНИЕ ПРИМЕР п**п а.*Ь "аЬс аЬсб И Гя] (аЬс) ("аЬс) Любой символ, не входящий в а г+ г! г(т,и) а? а(1,5) аЬ а)Ь (а)Ь) аЬс/123 Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
