А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 36
Текст из файла (страница 36)
3.8. Регулярные выражения Еех г1 гз г1 ~ гз (г) г1(гз Один неоператорный символ с Символ с буквально Строка я буквально Любой символ, кроме символа новой строки Начало строки Конец строки Любой символ из я Нуль или более строк, соответствующих г Одна или более строк, соответствующих т Нуль или одно г От т до и повторений г гм за которым следует гз г1 или гз То же, что и г гь если за ним следует гз 176 Глава 3. Лексический анализ Упражнение 3.3.7.
Обратите внимание на то, что в регулярных выражениях сле- дующие символы (олераеорные) имеют особый смысл: Этот особый смысл можно отключить, если требуется, чтобы такой символ представлял в строке самого себя. Этого можно добиться, заключив строку длиной не менее 1 в двойные кавычки; например, регулярному выражению "**" соответствует строка **.
Можно также назначить буквальное значение операторному символу, поместив перед ним обратную косую черту. Так, регулярному выражению ~*~* также соответствует строка **. Напишите регулярное выражение, которому соответствует строка " ~. Упражнение 3.3.8. В ].ех дополняющий класс символов представляет любой символ, кроме перечисленных в классе символов. Обозначением дополняющего класса является знак дополнения в качестве первого символа. Сам по себе этот символ не является частью дополняющего класса, если только он не указан в этом классе в другом месте.
Таким образом, 1 "А-Еа-х] соответствует любому символу, не являющемуся прописной или строчной буквой английского алфавита, а [ "~ ] представляет любой символ, кроме знака дополнения (или символа новой строки, поскольку он не может входить ни в какой класс символов). Покажите, что для каждого регулярного выражения с дополняющими классами существует эквивалентное регулярное выражение без дополнений. ! Упражнение 3.3.9. Регулярное выражение г ]гп, и) представляет от т до п повторений шаблона г.
Например, а(1, 5) соответствует строкам, состоящим из символов а от одного до пяти. Покажите, что для каждого регулярного выражения с таким оператором повторения существует эквивалентное регулярное выражение без этого оператора. ! Упражнение 3.3.10. Оператор соответствует левому концу строки, а 8 — правому концу. Это тот же оператор, который используется в классе-дополнении, и его конкретный смысл определяется контекстом его применения.
Например, 1 "аезоц]*$ соответствует любой полной строке, не содержащей ни одной строчной гласной. а) Как определить, какое именно значение имеет то или иное вхождение символа " в регулярное выражение? б) Всегда ли можно заменить регулярное выражение с операторами " и 8 эквивалентным регулярным выражением без этих операторов? ! Упражнение 3.3.11. В операционной системе 1Лч]Х оболочка а]т использует операторы, приведенные на рис. 3.9, при указании имен файлов лля описания множества файлов. Например, выражение *.
о соответствует всем файлам, имена которых заканчиваются на . о; аогГ1.? соответствует всем именам вида вохГ1. с, 177 3.4, Распознавание токенов где с — произвольный символ. Покажите, как выражения для имен файлов в вЬ могут быть заменены регулярными выражениями с применением только базовых операторов объединения, конкатенации и замыкания. Рис, 3.9.
Выражения для имен файлов, используемые зл Упражнение 3.3.12. В Я( !! присутствует рудиментарное использование шаблонов с двумя символами со специальным смыслом: символ подчеркивания ( ) означает любой один символ, а символ процента (Ъ) — любую строку из нуля или большего количества символов. Кроме того, программист может определить любой символ, скажем, е, как служебный, так что его предшествование символам , Ъ или самому е возвращает им буквальное значение. Покажите, как записать любой шаблон ЯЯ!. в виде регулярного выражения, если известно, какой именно символ выступает в роли служебного. 3.4 Распознавание токенов Из предыдущего раздела вы узнали, как записывать шаблоны с использованием регулярных выражений.
Теперь нужно изучить, как из шаблонов для всех необходимых токенов построить часть кода, которая исследует входной поток и находит в нем префикс, который является лексемой для одного из шаблонов. Мы воспользуемся для этого следующим примером. Пример 3.8. Фрагмент грамматики на рис. 3.10 описывает простые инструкцию ветвления и условные выражения.
Приведенный синтаксис похож на синтаксис языка программирования Раиса! тем, что после условия явно указывается ключевое слово 1Ьеп. Для ге!ор используются операторы сравнения, подобные операторам в Рааса! и $1,11., где = означает "равно'*, а <> — "не равно", поскольку они представляют интересную структуру лексем. Терминалы грамматики !1; 1Ьеп, е!яе, ге!ор,!д и ппшЬег представляют собой при рассмотрении лексического анализатора имена токенов.
Шаблоны для этих токенов описаны с применением регулярных выражений на рис. 3.11. Шаблоны для Ы и литЬег аналогичны шаблонам из примера 3.7. 178 Глава 3. Лексический анализ згтг — 1Г ехр» 1Ьеп згт1 11 ехр«1Ьеп згт1 е!яе в1тг е ехрг — 1егт ге1ор 1егт 1егт гегт — Ы пшпЬег Рис. 3.10. Грамматика лля инструкций ветвления Йф1 Йя11з питЬег (0-9] Йфг+ Йд11в (. Йф!в)? ( Е (+-]? Йя11з )? (А-Еа-х] 1еиег ( 1еиег ~ Йе11 )* хй ?е11е« и? (у' глен сЬеп ейе — е1ве ге1ор — < ) > ) <= ! >= ! = ( <> Рнс. 3.11. Шаблоны токенов из примера 3.8 В этом языке лексический анализатор должен распознавать ключевые слова хЕ, спеп и е1ве, а также лексемы, которые соответствуют шаблонам ге1ор, Ы и нитбег.
Для упрощения считаем, что ключевые слова являются зарезервированными, т.е. несмотря на то, что они соответствуют шаблону идентификаторов, они не являются идентификаторами. Кроме того, лексическому анализатору будет поручено удалить пробельные символы путем распознавания "токена*' нз, определенного как из — ( Ыапй ~ таЬ | петт11пе )+ Здесь Ыапй, 1аЬ и пепйпе являются абстрактными символами, которые использованы для того, чтобы выразить соответствующие символы АБСН вЂ” пробелы, символы табуляции и новой строки. Токен из отличается от других токенов тем, что после распознавания он не возвращается синтаксическому анализатору, и лексический анализ выполняется заново, с символа, следующего за пробельным, в поисках токена, который будет возвращен синтаксическому анализатору.
Действия нашего лексического анализатора подытожены на рис. 3.12. В приведенной здесь таблице для каждой лексемы или семейства лексем указано, ка- 179 3УК Распознавание токенов кое имя токена должно быть возвращено синтаксическому анализатору и каким должно быть значение атрибута (см. раздел 3.1.3). Обратите внимание на то, что для шести операторов сравнения в качестве атрибутов используются символьные константы ЬТ, ЬЕ и другие, которые указывают, какие именно экземпляры токена ге1ор обнаружены. Конкретный обнаруженный оператор определяет, какой именно код будет сгенерирован компилятором.
и Рис. 3.12. Токены, их шаблоны и значения атрибутов 3.4.1 Диаграммы переходов В качестве промежуточного шага при построении лексического анализатора вначале преобразуем шаблоны в стилизованные блок-схемы, именуемые диаграммами переходов (1гапгббоп йайгат). В данном разделе мы выполняем преобразование шаблонов в виде регулярных выражений в диаграммы переходов вручную, но в разделе 3.6 будет показано наличие механического способа построения таких диаграмм из коллекций регулярных выражений. Диаграмма переходов содержит ряд узлов, или кружков, именуемых состояниями (а1а1е). Каждое состояние представляет ситуацию, которая может возникнуть в процессе сканирования входного потока в поисках лексемы, соответствующей одному из нескольких шаблонов. Состояния можно рассматривать как подытоженную информацию обо всех просмотренных символах между указателями 1ехетеВех(п и /оги аЫ (как в ситуации на рис.
3.3). 180 Глава 3. Лексический анализ Дуги (ебйе) представляют собой направленные линии из одного состояния в другое. Каждая дуга помечена символом или множеством символов. Если мы находимся в некотором состоянии а и следующий входной символ — а, мы ищем дугу, исходящую из з и помеченную а (а возможно, и какими-то другими символами). Если мы находим такую дугу, то перемещаем указатель|огиаЫ и входим в новое состояние диаграммы переходов, в которое нас приводит упомянутая дуга. Мы полагаем, что все наши диаграммы переходов детерминированные (бегепп!и1зг(с), т.е.
что имеется не более одной дуги, выходящей из данного состояния с данным символом среди ее меток. В разделе 3.5 требование детерминированности будет ослаблено, что облегчит жизнь разработчикам лексических анализаторов и усложнит — реализующим их программистам.
Вот некоторые важные соглашения о диаграммах переходов. 1. Некоторые состояния являются долускаклцими (лринимгпои!ими, ассербпй), или конечными (бпа1). Эти состояния указывают, что искомая лексема найдена, хотя фактически лексема может и не состоять из всех позиций между указателями )ехеглеВе8!л и гогланд Конечные состояния на диаграмме изображены как двойные кружкй, и если должно выполняться какое-то действие — обычно возврат токена и значения его атрибута синтаксическому анализатору, — то оно указывается у конечного состояния. 2.
Кроме того, если необходимо вернуть указатель 1огиаго на одну позицию назад (т.е. лексема не включает символ, который привел нас в конечное состояние), то возле такого узла дополнительно ставится символ *. В нашем примере никогда не потребуется возвращать указатель Гогвап! более чем на одну позицию, но если это необходимо, то у конечного состояния можно указать соответствующее количество звездочек.
3. Одно состояние является стартовым (з!аг!), или начальным (!и!!!а1); оно указывается при помощи дуги, помеченной словом "з!аг!" и входящей в состоянис ниоткуда. Диаграмма переходов всегда начинается в стартовом состоянии (перед тем как будет считан хотя бы один символ из входного потока). Пример 3.9. На рис. 3.13 приведена диаграмма переходов, которая распознает лексемы, соответствующие токену ге!ор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
