Тема 12. Синтаксически управляемый перевод при генерации промежуточного представления

[ содержание | предыдущая тема | используемые источники ]

Содержание темы

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

Организация промежуточного представления программы

Промежуточное представление (ПП) - это программа в кодах виртуальной машины (ВМ) на языке, эквивалентном или близком к исходному. Однако, это уже машинная программа, и из нее убран текстовый (языковый) контекст. Cтруктура ПП может определяться в зависимости от числа проходов.

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

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

Формирование команд виртуальной машины

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

1. Семантика команд ВМ полностью имитирует структуру операторов языка высокого уровня (ЯВУ), для которого разрабатывается транслятор. В этом случае мы, за счет синтаксического анализа, освобождаемся от цепочки символов, представляющей программу, заменяя ее структурированным двоичным представлением в памяти вычислительной машины. Данный вид промежуточного представления является объектной моделью рассматриваемого языка программирования. Она полностью зависит от особенностей организации и состава языка.

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

Основные отношения на уровне команд

Команда - это элементарная единица работы, поддерживающая следующие отношения между другими командами и данными.

1. Отношения между операндами. Команда может иметь операнды-аргументы, которые она обрабатывает и формировать результаты этой обработки – тоже операнды. Результаты одних команд являются аргументами других.

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

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

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

M: X = A+B*(C-D);
if(X > 0) {C--;goto M;}
else put(X);

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

Структура команд языка промежуточного представления

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

Oтношения между операндами задаюются двумя списками: аргументов и результатов. То есть в общем случае команда может иметь несколько элементов исходных данных и формировать на выходе несколько результатов.

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

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

struct Instruction {
// Код операции.
    opcType     opc;
// Список аргументов.
    opdList     arg;
// Список результатов.
    opdList     rez;
// Список отношений управления.
    controlList control
// Отношение расположения.
    struct Instruction  *next
};

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

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

Организация промежуточных команд демонстрационного языка

Изучение операторов и операций языка DPL позволяет выделить в нем отдельные группы команд промежуточного представления.

1. Команды, используемые в выражениях. Это операции различного вида, применяемые в арифметических выражениях и отношениях. Они делятся на:

1.1. унарные. (это только унарный минус);

1.2. бинарные (плюс, бинарный минус, умножить и т.д.).

2. Команды для работы с переменной. Данная категория команд определяет доступ к внутренней структуре переменных. Выделяется только одна команда данной группы:

2.1. выделить (взять) элемент из вектора (квадратные скобки "[…]").

3. Команды в операторах. Эти команды обеспечивают организацию вычислений на уровне различных операторов исходного языка. К ним относятся:

3.1. команда присваивания, обеспечивающая присваивание значение некоторой переменной, что эквивалентно пересылке данных из одной ячейки в другую;

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

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

3.4. команда ввода значения переменной (в отличие от оператора, позволяет вводить только одно значение, несколько значений вводятся последовательностью команд);

3.5. команда вывода значения переменной (выводит только одно значение);

3.6. команды вывода форматирующих символов (каждая команда выводит только один заданный символ);

3.7. команда прерывания;

3.8. пустая команда, которая ничего не выполняет;

3.9. команда завершения программы, передающая управление системе или останавливающая выполняемую программу;

3.10. команда- метка предназначенная для установке позиции метки в поток команд.

Форматы описанных команд приведены на рис 12.3.

Формат команды промежуточного представления и его реализация

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

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

Формат полученной обобщенной команды промежуточного представлен на рис. 12.4.

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

struct INSTRUCTION {
	opcType	opc;
	// отношение расположения/управления
struct INSTRUCTION	*next; 
// Операндная часть инструкции
	struct OPERAND	*arg1;
	struct OPERAND	*arg2;
	struct OPERAND	*rez;
// Место встречи в тексте программы
	int		line;
	int		column;
};

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

Поле opc хранит код операции, который может быть задан в виде перечислимого тип, например, следующим образом:

// Разновидности команд промежуточного представления.
typedef enum {
addOpc, 	assOpc,		divOpc,		eqOpc,		
emptyOpc,	exitOpc,	geOpc,		gotoOpc,	
gtOpc,		ifOpc,		inOpc,		indexOpc,
labelOpc,	leOpc,		ltOpc,		minOpc,
modOpc,		multOpc,	neOpc,		outOpc,	
skipOutOpc,	spaceOutOpc,	subOpc,		tabOutOpc 
} opcType; 

Структура операнда демонстрационного языка

Для окончатльного определения списка команд необходимо сформировать структуру операнда. Операндами команд в промежуточном языке являются:

- переменные заданные в описания и хранящиеся в памяти по выделенным адресам;

- константы, обрабатываемые размещаемые в памяти транслятором;

- временные переменны, формируемые транслятором как промежуточные элементы для связи команд по общим данным;

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

Обобщенное представление структуры операнда промежуточного представления демонстрационного языка программирования приведено на рис. 12.5.

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

// Структуры данных, обеспечивающие 
// хранение и обработку операндов
// Организация константы
struct CONST {
scalType typ; // тип константы
union {
int	unum;	// целая константа
float	fnum;	// действительная константа
} val;	// значение константы
};

// Разновидности операнда
typedef enum {
nameVarOpd, // именованная переменная из таблицы имен
tmpVarOpd,  // промежуточная переменная в выражениях
constOpd,	  // константный операнд
labelOpd	  // операнд - метка
} opdType;

// Организация операнда
struct OPERAND {
opdType typ;	// тип операнда
union {
// ссылка на именованную или промежуточную переменную:
struct application *var;
struct CONST *cons;		  // ссылка на константу
struct INSTRUCTION *label; // ссылка на метку
} val;	// значение операнда
// Дополнительные параметры, обеспечивающие тестирование
int		ident; 	  // уникальный идентификатор операнда
struct OPERAND	*next; // для организации списка операндов
}; 

Генерация промежуточного представления

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

1) добавление команды к уже существующему списку команд;

2) слияние двух отдельных списков команд в один в заданной последовательности;

3) добавление отельной команды в голову списка.

Генерация структур, представляющих константные операнды

Генерация структур данных, представляющих операнды, осуществляется в тех функциях распознавателя, которые реализуют работу с операндами. В частности порождение констант осуществляется в правиле, задающем число. В соответствии с синтаксически управляемым переводом оно модифицируется за счет добавления семантических вставок (рис. 12.6).

Введенные в правило семантические вставки выполняют следующие действия:

Вставка 1. Генерируется константа целочисленного типа путем заполнения полей структуры CONST соответствующим признаком целочисленной константы INTTYP и значением этой константы.

Вставка 2. Генерируется константа действительного типа путем заполнения полей структуры CONST соответствующим признаком целочисленной константы FLOATTYP и значением этой константы.

Этот нетерминал число входит в правило, описывающее терм. В этом правиле полученная константа включается в операнд и подсоединяется к дополнительной оболчке, содержащей список команд. Формирование списка команд протекает и по другим альтернативам терма: переменной и выражению. Однако для числа характерно то, что список команд является пустым, так как формируется только операнд при отсутствии константы. Семантическая вставка (рис. 12.7) описывающая построение списка команд, реализует следующее действие:

Вставка 1. При распознавании числа формируется константный операнд. Создается также пустой список команд, указатель на операнд которого ссылается на сформированный константный операнд. Полученный список команд и является возвращаемым параметром.

Следует отметить, что список команд имеет следующую структуру:

// Список команд
struct INSTR_LIST {
    INSTRUCTION	*firstInstr; 	// Первая команда в списке.
    INSTRUCTION	*lastInstr;	// Последняя команда в списке.
    OPERAND	*lastOpd;	// Последний полученный операнд.
};

Сохранение операнда, полученного в ходе генерации списка команд позволяет передавать последний полученных результат для вновь генерируемой команды. Таким образом может проходить формирование отношений между командой и операндами, полученными в различных подвыражениях. Более подробно этот процесс рассматривается при генерации кода для выражений.

Генерация промежуточного представления для переменной

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

Они выполняют следующие действия:

Вставка1. Расширяет ранее выполняемые операции по поиску значения идентификатора в таблице имен дополнительными действиями, связанными с формированием структуры операнда-переменной. Создается также пустой список команд, в котором операнд-переменная фиксируется в качестве последнего операнда.

Вставка 2. При наличии индексного выражения генерируется команда выделения значения из вектора по индексу переменной. Первым операндом этой команды является операнд, сформированный в семантической вставке 1, а второй операнд - это последний операнд, зафиксированный в списке команд, возвращенном из выражения. После этого осуществляется конкатенация списков команд содержащих идентификатор и выражение. К нему добавляется команда вычисления индекса. Последним операндом вновь сформированного списка команд становится результат команды взятия индекса.

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

Генерация промежуточного представления для выражений

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

Семантические вставки правила выполняют следующие действия:

Вставка 1. Формируется команда, вычисляющая унарный минус. Ее результатом является промежуточная переменная, а аргумент пока не определен.

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

Генерация промежуточного представления для правил описывающих вычисления посредством бинарных операций, происхоит по одинаковой схеме. Ниже этот процесс рассматривается на примере правила, определяющего слагаемого и содержащего операции умножения, деления и вычисления остатка (рис. 12.10).

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

Вставка 1. Запоминается список команд и его последний операнд, возвращенные из множителя.

Вставка 2. Генерируется команда умножения. Возвращенный из первого множителя последний операнд становится ее первым операндом.

Вставка 3. Генерируется команда деления. Возвращенный из первого множителя последний операнд становится ее первым операндом.

Вставка 4. Генерируется команда вычисления остатка. Возвращенный из первого множителя последний операнд становится ее первым операндом.

Вставка 5. Последний операнд, возвращенный из второго множителя, становится вторым операндом команды, сформированной в пунктах 2, 3, 4. Осуществляется конкатенация списков команд, определяющих первый и второй множители. К полученному списку добавляется команда, сформированная в пунктах 2, 3, 4. Ее результат, являющийся промежуточной переменной, становится последним операндом сформированного списка.

Аналогичным образом осущствляется генерация промежуточного представления и для операторов демонстрационного языка программирования. Более подробно с этим можно ознакомиться по исходным текстам программы реализующей транслятор с DPL, которые прилагаются к учебному пособию.

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

1. Назовите способы задания семантического представления.
2. В чем заключается особенность промежуточного представления программы?
3. Как формируются команды виртуальной машины?
4. Какие отношения существуют между командами?
5. Что задает операнд промежуточного представления?
6. Опишите семантические вставки для различных синтаксических правил.
7. Добавте в программный модуль, реализующий функции распознавателя вставки, обеспечивающие генерацию промежуточного представления.

[ содержание | предыдущая тема | используемые источники ]