 |
Создание внутреннего представления программы
|
|
|
|
Для программ, назначение которых заключается в анализе и обработке других программ, основным параметром является текст исходной программы. В отличие от параметров простых типов, такой сложно организованный параметр требует предварительного анализа с целью обеспечить возможность получения из него необходимой для решаемой задачи информации. И поскольку для большинства приложений такого рода доступа к входной программе на уровне символов в текстовом файле недостаточно, возникает задача перевода текста программы в некоторую структуру, отражающую его в виде законченных языковых конструкций - идентификаторов, типов, структур данных, операторов, управляющих конструкций и др. Иными словами, необходимо произвести разбор исходного текста - parsing. Однако в некоторых случаях этого недостаточно и для решения поставленных задач требуется подняться на более высокий уровень абстракции. Следовательно, встает вопрос о создании некоего высокоуровнего представления программы, отражающего специфику конкретной задачи.
2.1 Разбор исходного текста. Система Sage++
Первоочередной задачей на этапе создания внутреннего представления программы, написанной на некотором языке, является разбор исходного текста. В результате такого анализа должна быть доступна информация о порядке выполнения операторов программы с учетом использованных в ней языковых конструкций, нарушающих последовательный характер их выполнения - ветвления, безусловные переходы, циклы, обращения к подпрограммам, операторы прекращения выполнения программы и т.п. Несмотря на то, что для строго типизированных языков программирования анализ операторов объявления может дать полную информацию о константах, переменных и их типах, представляется существенным дополнением наличие таблиц типов и имен. Все перечисленные возможности предоставляет свободно распространяемая библиотека Sage++, разработанная в Иллинойском университете..
|
|
|
“Sage++ является попыткой предложить объектно-ориентированный инструментарий для построения систем обработки программ на языках Fortran77, Fortran90, C и C++. Sage++ предназначен для разработчиков, проводящих исследования в следующих областях: построение распараллеливающих компиляторов, средств анализа производительности и оптимизаторов исходного кода” [2].
Библиотека Sage++ реализована в виде иерархии классов C++, которые позволяют получить доступ к дереву разбора, таблице имен и таблице символов для каждого файла, входящего в исходное приложение. Классы объединены в пять семейств: “Проекты и файлы” - хранят информацию обо всех файлах приложения, “Операторы” - ссылаются на базовые операторы языков, “Выражения” - указывают на выражения, содержащиеся внутри операторов, “Символы” - определенные в программе идентификаторы, “Типы” - сопоставленные с каждым идентификатором и выражением типы. Библиотека обеспечивает средства как всестороннего изучения исходной программы, так и различной ее модификации - добавление к ней новых файлов, создание и изменение операторов, входящих в файлы, вставка и модификация содержащихся в операторах выражений и др. Рассмотрим основные возможности Sage++, представляющие для нас интерес в рамках первого аспекта.
Перед началом анализа программы необходимо создать и сохранить на диске Sage++-представления каждого входящего в ее состав файла специальной утилитой из пакета Sage++. После этого надо создать текстовый файл проекта со списком имен полученных файлов.
Для получения доступа к данным проекта существует класс SgProject:
|
|
|
SgProject(char *proj_file_name) - конструктор, proj_file_name - имя файла проекта;
int numberOfFiles() - количество файлов в проекте;
SgFile &file(int i) - i-й файл проекта.
Класс SgFile представляет файл, входящий в исходное приложение:
SgStatement *firstStatement() - указатель на первый оператор файла;
SgSymbol *firstSymbol() - указатель на первый элемент таблицы имен файла;
SgType *firstType() - указатель на первый элемент таблицы типов файла.
Каждый определенный в файле идентификатор содержится в таблице имен и представляется объектом одного из наследников класса SgSymbol:
int variant() - тэг, определяющий класс символа;
int id() - уникальный номер символа в таблице;
char *identifier() - текстовое представление символа
SgType *type() - тип символа;
SgStatement *declaredInStmt() - оператор объявления;
SgSymbol *next() - указатель на следующий элемент таблицы.
После выяснения тэга подлежащего анализу идентификатора можно при помощи соответствующей ему глобальной функции получить указатель на объект класса-наследника SgSymbol, содержащего специфические для этого идентификатора данные. Примерами таких производных классов могут служить:
SgVariableSymb - переменная программы;
SgConstantSymb - константа;
SgFunctionSymb - процедура, функция или главная программа.
С каждым идентификатором и выражением соотнесен его тип - скалярный или сложный, представленный объектом класса SgType или одного из его наследников:
int variant() - тэг типа, соответствующий либо скалярному типу, либо классу-наследнику;
int id() - уникальный номер типа в таблице типов;
SgType *baseType() - указатель на базовый тип для сложных типов;
SgType *next() - указатель на следующий элемент таблицы типов.
Пример производного от SgType класса - SgArrayType, объект которого создается для каждого определенного в программе массива. Основные члены этого класса:
int dimension() - размерность массива;
SgExpression *sizeInDim(int i) - выражение, характеризующее длину по i-му измерению.
Каждый файл программы разбит на операторы, для представления которых используется класс SgStatement и его производные:
int variant() - тэг оператора;
|
|
|
int id() - уникальный номер оператора;
int lineNumber() - номер строки в исходном тексте;
SgExpression *expr(int i) - i-е выражение, входящее в оператор (i = 0,1,2);
SgStatement *lexNext() - следующий в лексическом порядке оператор;
SgStatement *lexPrev() - предыдущий в лексическом порядке оператор;
SgStatement *controlParent() - охватывающий управляющий оператор;
SgStatement *lastNodeOfStmt() - для операторов, не являющихся листом дерева разбора, возвращает указатель на последний оператор поддерева.
Аналогично другим классам Sage++ тэг объекта SgStatement позволяет определить класс-потомок SgStatement, соответствующий рассматриваемому оператору. В каждом из них существуют данные и методы, специфические для представляемого этим классом оператора. Эти классы объединены в несколько семейств:
· заголовочные операторы;
· операторы объявления;
· управляющие операторы;
· исполняемые и другие операторы.
Примеры классов, относящихся к этим семействам.
Заголовочные:
· SgProgHedrStmt - заголовок программы (Fortran);
· SgProcHedrStmt - заголовок подпрограммы (Fortran);
· SgBlockDataStmt - оператор блока данных (Fortran).
Операторы объявления:
· SgVarDeclStmt - оператор объявления переменной;
· SgParameterStmt - оператор объявления констант (Fortran);
· SgImplicitStmt - оператор Implicit (Fortran).
Управляющие:
· SgForStmt - цикл FOR;
· SgIfStmt - оператор ветвления If-Then-Else (Fortran), if (C);
· SgLogIfStmt - оператор логического If (Fortran);
· SgArithIfStmt - оператор арифметического If (Fortran).
Исполняемые и другие:
· SgAssignStmt - оператор присваивания (Fortran);
· SgCallStmt - оператор Call (Fortran);
· SgContinueStmt - оператор Continue;
· SgControlEndStmt - обозначает конец одного из основных блоков (напр. ENDIF);
· SgReturnStmt - оператор Return;
· SgGotoStmt - оператор Goto.
Большинство операторов программы содержат некоторые выражения. Класс SgExpression является базовым для выражений всех видов:
int variant() - тэг вида выражения;
SgExpression *lhs() - левое поддерево выражения;
SgExpression *rhs() - правое поддерево выражения;
В отличие от иерархии классов, порождаемой SgStatement, не вводится подкласс для каждой операции, находящейся в корне дерева разбора выражения. Основные бинарные операции, такие, как стандартные арифметические, идентифицируются только тэгом. Листья дерева могут иметь собственные классы, например:
|
|
|
· SgValueExp - представляет значение одного из базовых типов;
· SgVarRefExp - ссылка на переменную или на массив;
· SgArrayRefExp - ссылка на элемент массива;
· SgFunctionCallExp - вызов функции.
Разработчиками Sage++ предлагается следующий алгоритм разбора исходной программы. Производится последовательный перебор файлов, входящих в проект. Начиная с указателя SgStatement* SgFile:: firstStatement() осуществляется обход операторов текущего файла. При этом анализируется оператор, входящие в него выражения, тело(а) - для операторов, содержащих таковое (например, управляющей группы). Переход на следующий оператор реализуется кодом cur_stmt=cur_stmt->lastNodeOfStmt()->lexNext() для операторов, не являющихся листом дерева разбора, и cur_stmt=cur_stmt->lexNext() для остальных (где cur_stmt - указатель на текущий оператор). Использование рекурсивного подхода к просмотру дерева представляется достаточно естественным.
|
|
|
