А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 32
Текст из файла (страница 32)
Этот драйвер и спецификация автомата образуют ядро лексического анализатора. 3.1 Роль лексического анализатора Поскольку лексический анализатор представляет собой первую фазу компилятора, его основная задача состоит в чтении входных символов исходной программы, их группировании в лексемы и вывод последовательностей токенов для всех лексем исходной программы. Поток токенов пересылается синтаксическому анализатору для разбора.
Обычно при работе лексический анализатор взаимодействует также с таблицей символов. Когда лексический анализатор встречается 156 !лава 3. Лексический анализ с лексемой, составляющей идентификатор, эту лексему требуется внести в таблицу символов. В некоторых случаях лексический анализатор может получать из таблицы символов некоторую информацию об идентификаторах, которая может помочь ему верно определить передаваемый синтаксическому анализатору токен. Схема описанного взаимодействия представлена на рис.
3.1. Обычно взаимодействие реализуется как вызов лексического анализатора синтаксическим анализатором. Этот вызов, представленный как команда йеЯехгТо1гел, заставляет лексический анализатор читать символы из входного потока, пока он не сможет идентифицировать очередную лексему и вернуть синтаксическому анализатору корректный токен. Исходная Лексический программа ~ анализатор К семантическому анализатору Рис. 3.1. Взаимодействие лексического анализатора с синтаксическим Поскольку лексический анализатор является частью компилятора, которая читает исходный текст, он может заодно выполнять и некоторые другие действия, помимо идентификации лексем.
Одной из таких задач является отбрасывание комментариев и пробельных символов (пробел, символы табуляции и новой строки, а также, возможно, некоторые другие символы, использующиеся для отделения токенов друг от друга во входном потоке). Еще одной задачей является синхронизация сообтцений об ошибках, генерируемых компилятором, с исходной программой. Например, лексический анализатор может отслеживать количество символов новой строки, чтобы каждое сообщение об ошибке сопровождалось номером строки, в которой она обнаружена.
В некоторых компиляторах лексический анализатор создает копию исходной программы с сообщениями об ошибках, вставленными в соответствующие места исходного текста. Если исходная программа использует макропрепроцессор, то раскрытие макросов также может выполняться лексическим анализатором. Иногда лексические анализаторы разделяются на соединенные каскадом два процесса. 157 3.1. Роль лексического анализатора а) Сканирование состоит из простых процессов, не требующих токенизации входного потока, таких как удаление комментариев и уплотнение последовательностей пробельных символов в один.
б) Собственно лексический анализ — более сложная часть, которая генерирует токены из выходного потока сканера. 3.1.1 Лексический и синтаксический анализ Имеется ряд причин, по которым фаза анализа компиляции разделяется на лексический и синтаксический анализ. 1. Наиболее важной причиной является упрощение разработки. Отделение лексического анализатора от синтаксического часто позволяет упростить как минимум одну из фаз анализа. Например, включить в синтаксический анализатор работу с комментариями и пробельными символами существенно сложнее, чем удалить их лексическим анализатором. При создании нового языка разделение лексических и синтаксических правил может привести к более четкому и ясному построению языка.
2. Увеличивается эффективность компилятора. Отдельный лексический анализатор позволяет применять более специализированные методики, предназначенные исключительно для решения лексических задач. Кроме того, применение методов буферизации для чтения входного потока может существенно увеличить производительность компилятора. 3. Увеличивается переносимость компилятора. Особенности входных устройств могут ограничивать возможности лексического анализатора. 3.1.2 Токены, шаблоны и лексемы При рассмотрении лексического анализа используются три связанных, но различных термина. ° Токен представляет собой пару, состоящую из имени токена и необязательного атрибута.
Имя токена — это абстрактный символ, представляющий тип лексической единицы, например конкретное ключевое слово или последовательность входных символов, составляющую идентификатор. Имена токенов являются входными символами, обрабатываемыми синтаксическим анализатором. Далее обычно мы будем записывать имя токена полужирным шрифтом и ссылаться на токен по его имени.
° Шаблон (рацегп) — это описание вида, который может принимать лексема токена. В случае ключевого слова шаблон представляет собой просто 158 Глава 3. Лексический анализ последовательность символов, образующих это ключевое слово. Для иден- тификаторов и некоторых других токенов шаблон представляет собой более сложную структуру, которой соответствуют (шасс)зес() многие строки. ° Лексема представляет собой последовательность символов исходной программы, которая соответствует шаблону токена и идентифицируется лексическим анализатором как экземпляр токена.
Пример 3.1. На рис. 3.2 приведены некоторые типичные токены, неформальное описание их шаблонов и некоторые примеры лексем. Чтобы увидеть использова- ние этих концепций на практике, в инструкции на языке программирования С рг1псг'("Тоса1 = Ъс(кп", всоге) рг1псг и вооге представляют собой лексемы, соответствующие токену (с(, а "Тоса1 = Ъс(~п" является лексемой, соответствующей токену )!!ега!. ТОкен НЕФОРМАЛЬНОЕ ОПИСАНИЕ ПРимеРы лексем еЬе е1ве р1, вооге, 02 Рис. 3.2. Примеры токенов Во многих языках программирования описанные далее ситуации охватываю~ большинство (если не все) токенов. 1. По одному токену для каждого ключевого слова.
Шаблон для ключевого слова выглядит так же, как само ключевое слово. 2. Токены для операторов, либо отдельные, либо объединенные в классы, как это сделано в случае токена сошрагЬоп на рис. 3.2. 3. Один токен, представляющий идентификаторы. 4. Один или несколько токенов, представляющих константы, такие как числа и строковые литералы.
5. Токены для каждого символа пунктуации, такие как левые и правые скобки, запятые или точки с запятыми. сошраг!яоп (д ппшбег (!гега! Символы 1, й Символы е, 1, в, е < или > или <= или >= или == или ! = Буква, за которой следуют буквы и цифры Любая числовая константа Все, кроме ", заключенное в двойные кавычки 3. 14159, О, б.
02е23 "ооге с(пзврес!» 159 3.1. Роль лексического анализатора 3.1.3 Атрибуты токеиов Пример 3.2. Имена токенов и связанные с ними атрибуты в инструкции на языке программирования ропгап Е = М * С ** 2 приведены ниже как последовательность пар: таблице символов для Е) (Ы, Указатель на запись в (аяяйп ор) (Ы, Указатель на запись в (шп11 ор) (Ы, Указатель на запись в (ехр ор) (ппшЬег, Целое значение таблице символов для М) таблице символов для С) 2) Обратите внимание, что в ряде пар, в частности для операторов, знаков препинания и ключевых слов, атрибуты излишни.
В нашем примере токен пцшЬег имеет целочисленный атрибут. На практике типичный компилятор вместо этого хранит строку символов, представляющую константу и в качестве атрибута для пптЬег использует указатель на нее. а Если шаблону могут соответствовать несколько лексем, лексический анализатор должен обеспечить дополнительную информацию о лексемах для последуюших фаз компиляции. Например, шаблон для токена пцшЬег соответствует как строке О, так и строке 1, и при генерации кода крайне важно знать, какая именно лексема была найдена в исходной программе.
Таким образом, во многих случаях лексический анализатор возвращает синтаксическому анализатору не только имя токена, но и значение атрибута, описывающее лексему, представляющую токен; имя токена влияет на принятие решений при синтаксическом анализе, а значение атрибута — на трансляцию токена после синтаксического анализа. Мы считаем, что токены имеют не более одного связанного с ними атрибута, хотя этот атрибут может представлять собой структуру, объединяющую несколько блоков информации. Наиболее важным примером может служить токен Ы, с которым необходимо связывать большое количество информации.
Обычно информация об идентификаторе — например, его лексема, тип и место в исходной программе, где он впервые встретился (эта информация может потребоваться, например, для сообшения об ошибке) — хранится в таблице символов. Таким образом, подходяшим значением атрибута для идентификатора является указатель на запись в таблице символов для данного идентификатора. 160 Глава 3. Лексический анализ Тонкости распознавания токенов Обычно для имеющихся шаблонов, описывающих лексемы токенов, выполнить распознавание лексем во входном потоке относительно просто.
Однако в некоторых языках, встретив лексему, невозможно сразу же сказать, какому токену она соответствует. Приведенный далее пример взят из языка программирования рог(гап, фиксированный формат в котором все еще разрешен в Еопгап 90. В инструкции РО 5 1 = 1.25 до тех пор, пока мы не встретим десятичную точку после 1, мы не можем утверждать, что первая лексема — Р051, являющаяся экземпляром токена идентификатора (согласно архаичному соглашению в фиксированном формате Еопгап символы пробела игнорируются).
Если вместо точки окажется запятая, мы получим инструкцию РО Р051=125 В ней первая лексема представляет собой ключевое слово РО. 3.1.4 Лексические ошибки Без помощи других компонентов компилятора лексическому анализатору сложно обнаружить ошибки в исходном тексте программы. Например, если в программе на языке С строка йй впервые встретится в контексте йа ( а == Г(х)) лексический анализатор не сможет определить, что именно представляет собой й1 — неверно записанное слово 1й или необъявленный идентификатор функции.
Поскольку й1 является корректной лексемой для токена Ы, лексический анализатор должен вернуть этот токен синтаксическому анализатору и позволить другой фазе компилятора — в данном случае, по всей видимости, синтаксическому анализатору — обработать ошибку перестановки местами двух букв. Однако представим ситуацию, когда лексический анализатор не способен продолжать работу, поскольку ни один из шаблонов не соответствует префиксу оставшегося входного потока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
