А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 37
Текст из файла (страница 37)
Работа начинается со стартового состояния О. Если первым входным символом оказывается <, то среди лексем, соответствующих шаблону для ге!ор, могут быть только «, > и <яч Мы переходим в состояние 1 и смотрим на следующий символ. Если это =, то оказывается распознанной лексема <=; мы переходим в состояние 2 и возвращаем токен ге(ор с атрибутом ЬЕ, символьной константой, представляющей конкретный оператор сравнения. Если в состоянии 1 следующим символом является >, то оказывается 181 3.4.
Распознавание токенов гегпгп ( ге1пр, ЬЕ) ге1пгп ( ге!пр, Нв) гегпгп ( ге1ер, ьт) геппп ( геЬр, св) пагег Оя геГпгп ( ге1пр, Ст) Рис. 3.13. Диаграмма переходов для ге!ор распознанной лексема <>;мы переходим в состояние 3 и возвращаем синтаксическому анализатору информацию о том, что найден оператор "не равно". В случае любых других символов найденная лексема — <, и мы переходим в состояние 4 для возврата этой информации. Обратите внимание, что состояние 4 помечено звездочкой, чтобы указать, что мы должны вернуться на одну позицию назад во входном потоке.
С другой стороны, если в состоянии О первый встреченный нами символ — =, то этот единственный символ и является лексемой. Мы немедленно возвращаем синтаксическому анализатору этот факт из состояния 5. Последняя возможность заключается в том, что первый символ представляет собой >. В таком случае мы должны войти в состояние 6 и на основании очередного символа решить, является ли лексема лексемой >= (если очередной считанный символ — =) или лексемой > (во всех остальных случаях). Заметим также, что если в состоянии О мы считываем символ, отличный от <, = или >, то прочесть лексему, соответствующую токену ге!ор, мы не в состоянии и приведенная диаграмма не может быть использована.гз 3.4.2 Распознавание зарезервированных слов и идентификаторов Распознавание ключевых слов и идентификаторов представляет собой определенную проблему.
Обычно ключевые слова наподобие тй и с)зеп зарезервированы (как в нашем примере), так что они не являются идентификаторами, даже если они выгпядялг, как идентификаторы. Таким образом, хотя для поиска лексем идентификаторов обычно используется диаграмма переходов, приведенная на Глава 3. Лексический анализ рис. 3.14, она распознает также ключевые слова зй, с)зеп и е1ае из нашего примера. (еиег или Йя(г гьгчпг(Вч То)ген( ),!пггал (Р ( )) Рис. 3.14. Диаграмма переходов для идентификаторов и ключевых слов Есть два способа обработки зарезервированных слов„вьплядящих, как идентификаторы. Изначально внести зарезервированные слова в таблицу символов.
Поле записи в таблице символов указывает, что эти строки не могут быть обычными идентификаторами, и определяет, какие именно токены они представляют. Предполагается, что именно такой метод используется на рис. 3.14. Когда мы находим идентификатор, вызов гнз(а11Ю помешает его в таблицу символов, если он еше не находится там, и возвращает указатель на запись в таблице символов для найденной лексемы. Само собой, никакой идентификатор, который в момент лексического анализа не находится в таблице символов, не может быть зарезервированным словом, так что его токен— Ы. Функция ее(Точен ищет запись для найденной лексемы в таблице символов и возвращает имя токена в соответствии с информацией из таблицы символов — Ы или один из токенов ключевых слов, изначально установленных в таблице. Создать отдельные диаграммы переходов для каждого ключевого слова.
Пример такой диаграммы приведен на рис. 3.15. Заметим, что такая диаграмма переходов построена из состояний, представляющих ситуацию после каждой очередной прочитанной буквы ключевого слова; за последней буквой выполняется проверка, что считанный символ не является ни буквой, ни цифрой, т.е. символом, который может быть продолжением идентификатора. Такая проверка завершения идентификатора необходима, иначе можно вернуть токен г1)еп в ситуациях, когда корректным токеном является токен Ы, например в случае лексемы с))епехсгга1пе, истинным префиксом которой является с))еп.
Если принять данный подход, то необходимо назначить токенам приоритеты, чтобы в случае соответствия лексемы двум шаблонам токены зарезервированных слов при распознавании имели преимущество перед токеном Ы. В нашем примере данный подход не ислользуется, поэтому состояния на рис. 3.15 не пронумерованы. Пз 3.4. Распознавание токенов п поммдпя яал Рнс. 3.15. Гипотетическая диаграмма переходов для ключевого слова реп 3.4.3 Завершение примера Диаграмма переходов для Ы, показанная на рис.
3.14, имеет простую структуру. Начиная с состояния 9, она проверяет, что лексема начинается с буквы, и в этом случае выполняется переход в состояние 1О. В состоянии 10 мы находимся до тех пор, пока нам встречаются буквы и цифры. Первый же символ, не являющийся ни буквой, ни цифрой, приводит к переходу в состояние 11, в котором лексема является распознанной. Поскольку последний символ частью лексемы не является, требуется возврат на одну позицию назад; кроме того, как говорилось в разделе 3.4.2, найденная лексема должна быть внесена в таблицу символов, и при этом мы выясняем, что же именно найдено — ключевое слово или истинный идентификатор.
Диаграмма переходов для токена пцшЬег показана на рис. 3.16, и пока что это самая сложная из виденных нами диаграмм. Начиная с состояния 12, мы переходим в состояние 13, если первый встреченный символ — цифра. В этом состоянии мы можем считать любое количество дополнительных символов. Если нам попадется символ, отличный от цифры, точки или Е, значит, мы имеем дело с целым числом наподобие 123.
Этот случай обрабатывается состоянием 20, в котором возвращаются токен пцгпЬег и указатель на таблицу констант; в которую внесена найденная лексема. Эти действия не показаны на диаграмме, но они аналогичны действиям, выполняемым при работе с идентификаторами. Й~яя 41яа Рнс. 3.16. Диаграмма переходов для беззнаковых чисел Если в состоянии 13 нам встречается точка, значит, у нас есть "необязательная дробная часть". Мы переходим в состояние 14 и ожидаем одну или несколько дополнительных цифр (для этой цели используется состояние 15). Если нам встречается символ Е (как и в состоянии 13), значит, наше число содержит "необязательный показатель степени'*, распознавание которого — обязанность, возлагаемая 184 Глава 3.
Лексический анализ на состояния 16 — 19. Если же в состоянии 15 нам встречается символ, не являющийся ни Е, ни цифрой, значит, достигнут конец дробной части числа, у которого нет показателя степени, и мы возвращаем найденную лексему в состоянии 21. Последняя диаграмма, показанная на рис. 3.17, предназначена для пробельных символов. На этой диаграмме мы ищем один или несколько "пробельных" символов, показанных как е!е!!щ, — обычно это пробелы, символы табуляции и новой строки, а возможно, и иные символы, которые не рассматриваются языком как часть какого бы то ни было токена. ае1!м Рис. 3.17. Диаграмма переходов для пробельных символов Обратите внимание, что в состояние 24 мы попадаем, обнаружив блок последовательных пробельных символов, за которыми следует символ, не являющийся пробельным.
Поэтому необходимо вернуться на один символ назад, но, как уже говорилось ранее, возврата из лексического анализатора в синтаксический анализатор при этом не происходит. Вместо это~о процесс лексического анализа после пробельных символов начинается заново. 3.4.4 Архитектура лексического анализатора на основе диаграммы переходов Существует несколько способов применения набора диаграмм переходов для построения лексического анализатора. Независимо от общей стратегии каждое состояние представляет собой фрагмент кода.
Можно представить переменную вТа~е, хранящую номер текущего состояния в диаграмме переходов. Конструкция вн1~с(з, построенная на основе значения переменной вГаГе, дает нам код для каждого из возможных состояний, где и находятся действия, выполняемые в том или ином состоянии.
Зачастую код состояния сам представляет собой конструкцию взетГ.с(з или множественное ветвление, которые путем чтения и исследования очередного символа входного потока определяют следующее состояние, в которое должен быть выполнен переход. Пример 3.10. На рис. 3.18 приведен набросок функции деГЕе1ор() на языке программирования Сч-ь, работа которой состоит в моделировании диаграммы переходов на рис. 3.13 и возврате объекта типа ТОКЕИ, т.е. пары, состоящей из имени токена (в данном случае — ге!ор) и значения атрибута (в данном случае — кода для одного из шести возможных операторов сравнения). Функция десйе1ор( ) сна- 185 3.4.
Распознавание токенов чала создает новый объект гегТо)сеп и инициализирует его первый компонент символьным кодом ДЕКОР для токена ге1ор. ТОКЕЫ дегйе1ор() ТОКЕ(4 гесТо)сеп = пеи(ВЕЕОР); иЬ11е(1) ( /* Обработка символов до тех пор, пока не будет выполнен возврат из функции или не будет обнаружена ошибка */ зи1гсЬ(згасе) ( саве О: с = пехгСЬаг()г Тй ( с == '<' ) зкасе = 1; е1зе Тй ( с == '=' ) згаге = 5; е1ве Тй ( с == '>' ) агапе = б; е1ве йа11()з /* Это не лексема ге1ор */ Ьгеа)с; сазе 1: сазе 8: геггасг(); геГТо)сеп.агггТЬпге = ОТ; гекигп(гегТо)сеп); Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
