А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 48

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 48)

3.65 показана функция переходов для этого ДКА. Например, переход из состояния Е для входного символа б ведет в состояние А, поскольку в исходном ДКА Е при входном символе 6 переходило в состояние С, а представителем группы, в которую входит С, является состояние А. По той же причине переход из состояния А для входного символа 6 ведет вновь в состояние А, в то время как все остальные переходы— такие же, как и на рис. 3.36.

и Рнс. 3.65. Таблица переходов ДКА с минимальным количеством состояний 242 Глава 3. Лексический анализ 3.9.7 Минимизация состояний в лексических анализаторах Чтобы применить процедуру минимизации количества состояний к ДКА, сгенерированному в разделе 3.8.3, мы должны начать работу алгоритма 3.39 с разбиения, которое группирует все состояния, распознающие определенный токен, а также разместить в одной группе все состояния, которые не определяют ни один токен. Приведенный ниже пример поясняет сказанное. Пример 3.41.

Для ДКА на рис. 3.54 начальное разбиение имеет вид 10187, 7) (247? 18, 581 (08) 1О1 Здесь состояния О!37 и 7 принадлежат одной группе, поскольку они не соответствуют нн одному токену. Состояния 8 и 58 принадлежат другой группе, поскольку оба они указывают на токен а*Ь '. Обратите внимание на то, что к состояниям добавлено тупиковое состояние и, которое имеет переходы для входных символов а и Ь само в себя.

Тупиковое состояние является целевым для отсутствующих переходов для символа а из состояний 8, 58 и 68. Далее мы должны разделить состояния 0137 и 7, поскольку при входном символе а их переходы ведут в разные группы. Следует также разделить состояния 8 и 58, поскольку их переходы для входного символа Ь также ведут в разные группы. Таким образом, каждое состояние образует отдельную группу, состоящую из одного этого состояния, и на рис. 3.54 изображен ДКА с минимальным количеством состояний, распознающий три соответствующих токена. Вспомним, что ДКА, служащий в качестве лексического анализатора, обычно попадает в тупиковое состояние, и отсутствие переходов рассматривается как сигнал о том, что обнаружен конец токена. Б 3.9.8 Компромисс между скоростью и используемой памятью при моделировании ДКА Простейший и наиболее быстрый способ представления функции переходов ДКА — двумерная таблица, проиндексированная состояниями и символами. Для данного состояния и очередного входного символа мы находим в таблице следующее состояние, а также специальные действия, которые должны быть предприняты, например возврат токена синтаксическому анализатору.

Поскольку обычно лексический анализатор имеет ДКА с несколькими сотнями состояний и использует АЯС11-алфавит из 128 символов, массив требует менее мегабайта памяти. Однако компиляторы встречаются и в очень малых устройствах, для которых и мегабайт памяти — это слишком много. Для таких случаев имеется множество методов, которые могут использоваться для сжатия таблицы переходов. Например, каждое состояние может быть представлено списком переходов, т.е, парами 243 3дд Оптимизация распознавателей на основе ДКА "состояние — символ", завершающимся состоянием по умолчанию, которое выбирается в случае, если входного символа нет в списке.

Если выбрать в качестве состояния по умолчанию наиболее часто встречающееся следующее состояние, в большинстве случаев удается уменьшить количество необходимой памяти во много раз. Имеется н более подходящая структура данных, которая позволяет объединить скорость доступа к массиву с экономным расходом памяти списками с состояниями по умолчанию. Эту структуру можно рассматривать как четыре массива, как показано на рис. 3.66.в Массив Ьаве используется для определения базового расположения записей для состояния в, хранящихся в массивах нех1 и сйес7с.

Массив с1еуаи11 применяется для определения альтернативной базовой позиции, если массив сйес1с говорит нам, что данное значение Ьаве [в] некорректно. лех! свес/с сСесаид вазе Рнс. 3.66. Структура данных для представления таблиц переходов Для вычисления перехода из состояния в для входного символа а пех1осасе [в, а) мы проверяем значения записей пехс и сйес/с в позиции 1 = Ьаве [в] + а, где символ а рассматривается как целое число, вероятно, из диапазона от 0 до 127.

Если сйес1с[1] = в, то зта запись корректна, и следующим для состояния в и входного символа а является состояние пехс [1]. Если же сЬес/с[1] ф в, то мы находим другое состояние 1 = с1е1аи11 [в) и повторяем процесс так, как если бы 1 было текущим состоянием. Более формально функция пехсосасе определяется следующим образом: ш1 пехсога1е [в, а) ( И 1 сйессс [Ьаве [в] + а) == в ) гекнгп пех1«Ьаве [в] + а]; е1яе гетнгн пехсоса1е (с1е~аи11 [в], а); На нрякснке монет нсподьзояяться еще один массив, пронндекснрояянный состояниями н содержадяй связанные о состояниями действия, если таковые имеются.

244 Глава 3. Лексический анализ Использование структуры, показанной на рис. 3.66, призвано сократить массивы пехг и свес?г путем использования подобия состояний. Например, состояние 1, являющееся состоянием по умолчанию для а, может быть состоянием, которое говорит "мы работаем с идентификатором", как, например, состояние 1О на рис.

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

Таким образом, мы устанавливаем сйес?г (Ьазе (а) + е] равным а (чтобы подтвердить, что это корректная запись для я), а пехг (Ьиье (з) + е) равным состоянию, запоминающему строку ~1те. Кроме того, Не7аий (з) устанавливается равным 1. Хотя мы можем оказаться не способными выбрать значения базе так, чтобы не оставалось неиспользованных записей лехг!свес?г, опыт показывает, что простейшая стратегия поочередного присваивания значений Ьазе состояниям и присваивания каждому Ьахе (з) минимального целого значения, такого, что специальные записи могут заполняться без конфликтов с существующими, достаточно хороша.

Более того, она использует объем памяти, лишь ненамного превышающий минимально возможный. 3.9.9 Упражнения к разделу 3.9 Упражнение 3.9.1. Расширьте таблицу на рис. 3.58 так, чтобы она включала опе- раторы? и Упражнение 3.9.2. Воспользуйтесь алгоритмом 3.36 для преобразования регулярных выражений из упражнения 3.7.3 непосредственно в детерминированные конечные ав гоматы. ! Упражнение 3.9.3. Можно доказать, что два регулярных выражения эквивалентны, показав, что их ДКА с минимальным количеством состояний одинаковы с точностью до имен состояний.

Покажите таким способом, что регулярные выражения (а ~ Ь)*, (а* ~ Ь")' и ((е ~ а) Ь*)* эквивалентны. Примечание: ДКА для этих выражений вы должны были получить при решении упражнения 3.7.3. ! Упражнение 3.9.4. Постройте ДКА с минимальным количеством состояний для следующих регулярных выражений: а) (а ~ Ь) а (а ( Ь); б) (а ! Ь)*а(а ( Ь) (а ! Ь); в) (а ! Ь)* а(а / Ь)(а ! Ь)(а ! Ь), 3.10. Резюме к главе 3 245 Вы не видите в построенных деревьях некоторого шаблона? 1! Упражнение 3.9.5. Чтобы формально обосновать неформальное утверждение из упражнения 3.25, покажите, что любой детерминированный конечный автомат для регулярного выражения (а / Ь)" а (а ! Ь) (а ! Ь) (а ! Ь), где (а ~ Ь) встречается в конце п.

— 1 раз, должен иметь как минимум 2 состояний. Указание: рассмотрите шаблон из упражнения 3.9.4. Какое условие, связанное с историей поступления входных символов, представляет каждое состояние? 3.10 Резюме к главе 3 + Токелы. Лексический анализатор сканирует исходную программу и выдает последовательность токенов, которая обычно передается синтаксическому анализатору по одному токену. Некоторые токены состоят из одного имени токена, в то время как другие могут иметь связанное с ними лексическое значение, несущее информацию о конкретном экземпляре токена, найденном во входном потоке.

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

Две методики, ускоряющие процесс сканирования входного потока — циклическое использование пары буферов с применением ограничителей, которые предупреждают о достижении конца буфера. + Шаблоны. Каждый токен имеет шаблон, который описывает, какая последовательность символов может формировать лексему, соответствующую этому токену. Множество слов, или строк символов, которые соответствуют данному шаблону, называется языком. + Регулярные выражения.

Эти выражения обычно используются для описания шаблонов. Регулярные выражения строятся из отдельных символов с использованием операторов объединения, конкатенации и замыкания Клини. 246 Глава 3. Лексический анализ + Регулярные определения. Для определения сложных наборов языков, таких как шаблоны, описывающие токены языка программирования, часто используются регулярные определения, которые представляют собой последовательности инструкций, в которых регулярным выражениям сопоставляются обозначающие их переменные. Регулярное выражение для некоторой переменной может использовать ранее определенные переменные для других регулярных выражений.

Характеристики

Список файлов книги