<<
>>

Анализ исходной программы

С точки зрения транслятора исходная программа — это длинная цепочка, состоящая из многих тысяч символов. Транслятор не рассматривает такие элементы программы, как процедуры, операторы, объявления; он выполняет анализ программы, разбирая ее текст последовательно, символ за символом.

Лексический анализ, или сканирование. Первый этап компиляции называется лексическим анализом, или сканированием. Лексический анализатор читает поток символов, составляющих исходную программу, и группирует эти символы в значащие последовательности, называющиеся лексемами. Для каждой лексемы анализатор строит выходной токен (token) вида

Он передается последующему этапу, синтаксическому анализу. Первый компонент токена, имя_токена, представляет собой абстрактный символ, использующийся во время синтаксического анализа, а второй компонент, значение атрибута, указывает на запись в таблице символов, соответствующую данному токену. Информация из записи в таблице символов необходима для семантического анализа и генерации кода.

Предположим, например, что исходная программа содержит оператор присваивания

area = width + height * 17

Символы в этом присваивании могут быть сгруппированы в следующие лексемы и отображены в следующие токены, передаваемые синтаксическому анализатору:

1. area представляет собой лексему, которая может отображаться в токен , где id — абстрактный символ, обозначающий идентификатор, а 1 указывает запись в таблице символов для area. Запись таблицы символов для некоторого идентификатора хранит информацию о нем, такую как его имя и тип.

2. Символ присваивания = представляет собой лексему, которая отображается в токен . Поскольку этот токен не требует значения атрибута, второй компонент данного токена опущен. В качестве имени токена может быть использован любой абстрактный символ, например такой, как assign, но для удобства записи мы будем использовать в качестве имени абстрактного символа саму лексему.

3. width представляет собой лексему, которая отображается в токен , где 2 указывает на запись в таблице символов для width.

4. + является лексемой, отображаемой в токен .

5. height — лексема, отображаемая в токен , где 3 указывает на запись в таблице символов для height.

Этапы трансляции

55

6. * — лексема, отображаемая в токен .

7. 17 — лексема, отображаемая в токен .

Пробелы, разделяющие лексемы, лексическим анализатором отбрасываются.

На рис. 2.6 показано представление оператора присваивания после лексического анализа в виде последовательности токенов id1 id2 id3

При этом представлении имена токенов =, + и * представляют собой абстрактные символы для операций присваивания, сложения и умножения соответственно.

Синтаксический анализ, или разбор (parsing). Вторым этапом трансляции является синтаксический анализ, или разбор. На этом этапе лексемы (токены), являющиеся результатами лексического анализа, применяются для выявления более крупных программных структур: операторов, объявлений, выражений и т. п. Анализатор использует первые компоненты токенов, полученных при лексическом анализе, для создания древовидного промежуточного представления, которое описывает грамматическую структуру потока токенов. Типичным представлением считается синтаксическое дерево, в котором каждый внутренний узел представляет операцию, а дочерние узлы — аргументы этой операции. Синтаксическое дерево для потока токенов показано на выходе синтаксического анализатора на рис. 2.6.

Это дерево указывает порядок выполнения операций в операторе присваивания area = width + height * 17

Дерево имеет внутренний узел, помеченный *, левым дочерним узлом которого является , а правым — 17. Узел представляет идентификатор height. Узел, помеченный *, явно указывает, что сначала мы должны умножить значение height на 17.

Узел, помеченный +, указывает, что мы должны прибавить результат умножения к значению width. Корень дерева с меткой = говорит о том, что следует присвоить результат этого сложения ячейке памяти с идентификатором area. Порядок операций согласуется с обычными арифметическими правилами, которые говорят о том, что умножение имеет более высокий приоритет, чем сложение, и должно быть выполнено до сложения.

Последующие фазы компилятора используют грамматическую структуру, которая помогает проанализировать исходную и сгенерировать объектную программу.

Семантический анализ. Семантический анализ считается самым важным этапом трансляции. На этом этапе обрабатываются структуры, выявленные синтаксическим анализатором, начинает формироваться структура выполняемого объектного кода. По сути, семантический анализ играет роль моста, соединяющего две стадии трансляции — анализ и синтез. Семантический анализатор использует синтаксическое дерево и информацию из таблицы символов для проверки исходной программы на семантическую согласованность с определением языка. Он также собирает информацию о типах и сохраняет ее в синтаксическом дереве или в таблице символов для последующего использования в процессе генерации промежуточного кода.

Важной частью семантического анализа является проверка типов, когда компилятор проверяет, имеет ли каждый оператор операнды соответствующего типа. Например, многие определения языков программирования требуют, чтобы индекс массива был целым числом; компилятор должен сообщить об ошибке, если в качестве индекса массива используется число с плавающей точкой.

56

Глава 2. Виртуальные машины и трансляция языков

Рис. 2.6. Трансляция оператора присваивания

Спецификация языка может разрешать неявные преобразования типов, именуемые неявными приведениями (coercion).
Например, бинарная арифметическая операция может быть применена либо к паре целых чисел, либо к паре чисел с плавающей точкой. Если такая операция применена к числу с плавающей точкой и целому числу, то компилятор может выполнить преобразование целого числа в число с плавающей точкой.

Такое неявное приведение показано на рис. 2.6. Предположим, что area, width и height были объявлены как числа с плавающей точкой и что лексема 17 образует целое число. Проверка типов в семантическом анализаторе на рис. 2.6 определяет, что операция * применяется к числу с плавающей точкой height и целому числу 17. В этом случае целое число может быть преобразовано в число с плавающей точкой. Обратите внимание, что на рис. 2.6 в синтаксическом дереве, полученном на выходе семантического анализатора, имеется дополнительный узел для оператора

Этапы трансляции

57

1п11оИоа1, который явным образом преобразует свой целый аргумент в число с плавающей точкой.

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

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

Обработчик арифметических выражений использует описанные типы для генерации объектного кода операций. Опишем наиболее общие функции специализированных анализаторов.

Поддержка таблицы символов. Таблица символов имеет сложную структуру. В таблице символов содержатся не только имена, но и другие, самые разнообразные атрибуты идентификаторов:

? вид (простая переменная, имя массива, имя подпрограммы, формальный параметр и т. д.);

? тип значения (целочисленный, вещественный и т. д.);

? адресные ссылки;

? любые сведения, извлекаемые из объявления.

Все эти данные надо сохранять и использовать. Обычно таблица символов уничтожается после окончания трансляции, но в отдельных случаях она может сохраняться и в период выполнения программы.

Включение неявной информации. Достаточно часто неявную информацию из исходной программы нужно отразить в объектной программе самым явным образом. Как правило, это относится к соглашениям по умолчанию. Например, если в языке Fortran тип переменной в программе не задан объявлением, то по умолчанию этой переменной приписывается тип, зависящий от начального символа в ее имени.

Обнаружение ошибок. На различных этапах трансляции возможно появление самых разнообразных ошибок, например:

? разделитель операторов в середине выражения;

? объявление среди последовательности операторов;

? символ операции вместо ожидаемого идентификатора;

? вещественная переменная вместо ожидаемой целой переменной;

? индексированная переменная с двумя индексами вместо элемента одномерного массива.

Анализатор должен не только распознавать ошибки и выдавать сообщения о них, но и принимать разумное решение о продолжении трансляции.

Макрообработка и служебные операции. Макросом называют такую часть текста программы, которая определена отдельно и должна быть вставлена в программу во

58

Глава 2. Виртуальные машины и трансляция языков

время трансляции, если в программе она вызывается. Служебные операции обеспечивают контроль над трансляцией исходной программы и выполняются в ходе компиляции. Например, в языке C имеется несколько таких операций:

? Операция #Се^пе позволяет вычислять значение констант и выражений до начала компиляции программы.

? Операция #ifCef (if-defined) позволяет транслировать какой-то один из нескольких альтернативных фрагментов кода (в зависимости от наличия или отсутствия определенных переменных).

<< | >>

Еще по теме Анализ исходной программы:

  1. Программа Да и программа Нет
  2. Свободное воспроизведение программ для ЭВМ и баз данных. Декомпилирование программ для ЭВМ
  3. Исходные положения.
  4. Исходные данные
  5. Подготовка исходных данных
  6. Исходные положения.
  7. Предмет социологии: исходные позиции
  8. 2.2.2. Область создания и распространения исходной и производной информации
  9. Статья 888. Исходные данные для проведения проектных и поисковых работ
  10. 2.6. Диагностика исходного уровня знаний о профессии педагога
  11. Правило критического возвратак исходной точке.
  12. Правило критического возврата к исходной точке.