- •Глава 13 Основные
- •Определение компилятора. Отличие компилятора от транслятора
- •Определение интерпретатора. Разница между интерпретаторами и трансляторами
- •Назначение трансляторов, компиляторов и интерпретаторов. Примеры реализации
- •Этапы трансляции. Общая схема работы транслятора
- •Понятие прохода. Многопроходные и однопроходные компиляторы
- •Интерпретаторы. Особенности построения интерпретаторов
- •Трансляторы с языка ассемблера («ассемблеры»)
- •Реализация компиляторов с языка ассемблера
- •Макроопределения и макрокоманды
- •Простейшие методы построения таблиц идентификаторов
- •Построение таблиц идентификаторов по методу бинарного дерева
- •Построение таблиц идентификаторов на основе хэш-функций
- •Построение таблиц идентификаторов по методу цепочек
- •Комбинированные способы построения таблиц идентификаторов
- •Принципы построения лексических анализаторов
- •Определение границ лексем
- •Выполнение действий, связанных с лексемами
- •Построение лексических анализаторов
- •Автоматизация построения лексических анализаторов (программа lex)
- •Дерево разбора. Преобразование дерева разбора в дерево операций
- •1 Повтор того, что сказано до начала Шагов. — Примеч. Ред.
- •Автоматизация построения синтаксических анализаторов (программа yacc)
Выполнение действий, связанных с лексемами
Выполнение действий в процессе распознавания лексем представляет для сканера гораздо меньшую проблему. Фактически KA, который лежит в основе распознавателя лексем, должен иметь не только входной язык, но и выходной. Он должен не только уметь распознать правильную лексему на входе, но и породить связанную с ней последовательность символов на выходе. B такой конфигурации KA преобразуется в конечный преобразователь [5, 6, т. 1, 42].
Для сканера действия по обнаружению лексемы могут трактоваться несколько шире, чем только порождение цепочки символов выходного языка. Сканер должен уметь выполнять такие действия, как запись найденной лексемы в таблицу лексем, поиск ее в таблице символов и запись новой лексемы в таблицу символов. Набор действий определяется реализацией компилятора. Обычно эти действия выполняются сразу же по обнаружению конца распознаваемой лексемы.
B KA сканера эти действия можно отобразить сравнительно просто — достаточно иметь возможность с каждым переходом на графе автомата (или в функции переходов автомата) связать выполнение некоторой произвольной функции f(q,a), где q — текущее состояние автомата, а — текущий входной символ. Функция может выполнять произвольные действия, доступные сканеру, в том числе работать с хранилищами данных, имеющимися в компиляторе (функция может быть и пустой — не выполнять никаких действий). Такую функцию, если она есть, обычно записывают на графе переходов KA под дугами, соединяющими состояния KA.
Построение лексических анализаторов
Теперь можно рассмотреть практическую реализацию сканеров. B принципе компилятор может иметь в своем составе не один, а несколько лексических анализаторов, каждый из которых предназначен для выборки и проверки определенного типа лексем.
Таким образом, обобщенный алгоритм работы простейшего лексического анализатора в компиляторе можно описать следующим образом:
Q из входного потока выбирается очередной символ, в зависимости от которого запускается тот или иной сканер (символ может быть также проигнорирован либо признан ошибочным);
Q запущенный сканер просматривает входной поток символов программы на исходном языке, выделяя символы, входящие в требуемую лексему, до обнаружения очередного символа, который может ограничивать лексему, либо до обнаружения ошибочного символа;
Q при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем и таблицу идентификаторов, алгоритм возвращается к перво-
му этапу и продолжает рассматривать входной поток символов с того места, на котором остановился сканер;
О при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера — либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
Рассмотрим пример анализа лексем, представляющих собой целочисленные константы в формате языка C. B соответствии с требованиями языка, такие константы могут быть десятичными, восьмеричными или шестнадцатеричны-ми. Восьмеричной константой считается число, начинающееся с O и содержащее цифры от O до 7; шестнадцатеричная константа должна начинаться с последовательности символов Ox и может содержать цифры и буквы от а до f. Остальные числа считаются десятичными (правила их записи напоминать, наверное, не стоит). Константа может начинаться также с одного из знаков + или -, а в конце цифры, обозначающей значение константы, в языке C может следовать буква или две буквы, явно обозначающие ее тип (u, U — unsigned; h, H — short; 1, L — long). При построении сканера будем учитывать, что константы входят в общий текст программы на языке C. Для избежания путаницы и сокращения объема информации в примере будем считать, что все допустимые буквы являются строчными (читатели легко могут самостоятельно расширить пример для прописных букв, которые язык C в константах не отличает от строчных).
Рассмотренные выше правила могут быть записаны в форме Бэкуса—Наура в грамматике целочисленных констант для языка C.
Эта грамматика является леволинейной автоматной регулярной грамматикой. По ней можно построить KA, который будет распознавать цепочки входного языка (см. раздел «Конечные автоматы», глава 10). Граф переходов этого автомата приведен на рис. 13.8. Видно, что построенный автомат является детерминированным KA, поэтому в дальнейших преобразованиях он не нуждается. Начальным состоянием автомата является состояние H.
Приведем автомат к полностью определенному виду — дополним его новым состоянием E, на которое замкнем все дуги неопределенных переходов. Ha графе автомата дуги, идущие в это состояние, не нагружены символами — они обозначают функцию перехода по любому символу, кроме тех символов, которыми уже помечены другие дуги, выходящие из той же вершины графа (такое соглашение принято, чтобы не загромождать обозначениями граф автомата). Ha рис. 13.8 это состояние и связанные с ним дуги переходов изображены пунктирными линиями.
При построении KA знаком «1» были обозначены любые символы, которыми может завершаться целочисленная константа языка C. Однако в реальной программе этот символ не встречается. При моделировании KA следует принять во внимание, какими реальными символами входного языка может завершаться целочисленная константа языка C.
B языке C в качестве границы константы могут выступать:
Теперь можно написать программу, моделирующую работу указанного автомата. Ниже приводится текст функции на языке Pascal, реализующей данный распо-
знаватель. Результатом функции является текущее положение считывающей головки анализатора в потоке входной информации после завершения разбора лексемы при успешном распознавании либо O при неуспешном распознавании (если лексема содержит ошибку).
B программе переменная iState отображает текущее состояние автомата, переменная i является счетчиком символов входной строки. B текст программы вписаны комментарии в те места функции, где возможно выполнить запись найденной лексемы в таблицу лексем и таблицу символов, а также выдать сообщение об обнаруженной ошибке.
function RunAuto Cconst sInput: string: iPos: integer): integer:
Конечно, рассмотренная программа — это всего лишь пример для моделирования такого рода автомата. Она построена так, чтобы можно было четко отследить соответствие между этой программой и построенным на рис. 13.8 автоматом. Конкретный распознаватель будет существенно зависеть от того, как организовано его взаимодействие с остальными частями компилятора. Это влияет на возвращаемое функцией значение, а также на то, как она должна действовать при обнаружении ошибки и при завершении распознавания лексемы.
B данном примере предусмотрено, что основная часть лексического анализатора сначала считывает в память весь текст исходной программы, а потом начинает его последовательный просмотр. B зависимости от текущего символа вызывается тот или иной сканер. По результатам работы каждого сканера разбор либо продолжается с позиции, которую вернула функция сканера, либо прерывается, если функция возвращает O.
Приведенный в примере сканер можно дополнить сканерами для констант с плавающей точкой языка C, а также идентификаторов и ключевых слов языка. B последнем случае распознающий KA будет явно недетерминированным, поскольку в языке C возможны, например, идентификатор i ffl и ключевое слово i f, имеющие принципиально разное значение. Такой KA потребует дополнительных преобразований.
B целом техника построения сканеров основывается на моделировании работы детерминированных и недетерминированных KA с дополнением функций распознавателя вызовами функций обработки ошибок, а также заполнения таблиц символов и таблиц идентификаторов. Такая техника не требует сложной математической обработки и принципиально важных преобразований входных грамматик. Для разработчиков сканера важно только решить, где кончаются функции сканера и начинаются функции синтаксического разбора. После этого процесс построения сканера легко поддается автоматизации.
