Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

first int getArgument second int getArgument – ПФЗ заголовка функции;

label#0#0: first second != label#0#1 jmpOnFalse – ПФЗ заголовка оператора цикла;

first second < label#1#0 jmpOnFalse second first –= label#1#1 jmp label#1#0: first second –= label#1#1: – ПФЗ условного оператора, составляющего тело цикла;

label#0#0 jmp – ПФЗ завершения оператора цикла;

label#0#1: first return – ПФЗ оператора возврата значения функции.

В этой форме записи для наглядности подчеркнуты все знаки операций. Большинство знаков операций (functionActivate, getArgument, !=, jmpOnFalse, <, –=) являются бинарными, но есть и унарные знаки (jmp и return).

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

label#0#0: firstsecond!=label#0#1 jmpOnFalse

У бинарного знака операции jmpOnFalse в этом фрагменте первым операндом является другой бинарный знак операции !=. В действительности это означает, что первым операндом операции jmpOnFalse является булево значение, вырабатываемое операцией сравнения. Это значение должно быть сохранено либо в стеке времени выполнения, либо в переменной, формируемой транслятором.

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

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

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

---

push и извлекаются из стека в последующих тетрадах с использованием другого имени верхушки стека pop.

Недостатком тетрад является то, что для объявления имени (метки) какой-либо операции приходится добавлять специальную тетраду с кодом операции «Создать метку». Этого недостатка лишены виртуальные машины, у которых каждая операция имеет дополнительной поле метки. Команды такой виртуальной машины называют пентадами (по количеству полей).

Таблица 7.1.

Нет в УП Код операции	Первый операнд	Второй операнд	Результат
defineLabel	label#0#0
!=	second	first	push
jmpOnFalse	label#0#1	pop
<	second	first	push
jmpOnFalse	label#1#0	pop
–=	first	second	second
jmp	label#1#1
defineLabel	label#1#0
–=	second	first	first
defineLabel	label#1#1
jmp	label#0#0
defineLabel	label#0#1
return	first

В табл. 7.2. показан псевдокод той же функции в виде последовательности пентад. Количество операций уменьшилось за счет удаления операций «Создать метку». В этом варианте виртуальной машины для хранения промежуточных результатов вычислений вместо стека используются временные переменные, создаваемые семантическим анализатором транслятора.

---

Таблица 7.2

Метка	Нет в УП Код операции	Первый операнд	Второй операнд	Результат
label#0#0	!=	second	first	tmpVar1
	jmpOnFalse	label#0#1	tmpVar1
	<	second	first	tmpVar2
	jmpOnFalse	label#1#0	tmpVar2
	–=	first	Second	second
	jmp	label#1#1
label#1#0	–=	second	First	first
label#1#1	jmp	label#0#0
label#0#1	return	first

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


Таблица 7.3.

Нет в УП Код операции	Первый операнд	Второй операнд
!=	second	first
jmpOnFalse	+8	–1
<	second	first
jmpOnFalse	+4	–1
–=	first	second
=	–1	second
jmp	+3
–=	second	first
=	–1	first
jmp	–9
return	first

---

В этом примере вместо имен операций и промежуточных результатов используется относительная адресация. Числа вида +8 или –1 в полях наименований операндов означают указание триады, находящейся на расстоянии 8 вперед или 1 назад по отношению к текущей триаде. Если относительный номер триады используется в операции преобразования данных, то под ним понимается результат, вырабатываемый адресуемой триадой.

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

2. 
   Преобразование постфиксной записи в последовательность тетрад
   

Шаг 1. Подготовка. Очистка стека, установка первого слова постфиксной записи в качестве текущего.

Шаг 2. Выявление назначения текущего слова ПФЗ. Если это наименование операнда, то переход к шагу 3, иначе (знак операции) – к шагу 4.

Шаг 3. Текущее слово заносится в стек и удаляется с входа (текущим становится следующее слово ПФЗ). Возврат к шагу 2.

Шаг 4. Знак операции удаляется с входа и заносится в тетраду. Определяется арность этого знака операции, далее формируются наименования операндов тетрады согласно выявленному случаю.

Случай 0 – оба наименования операндов устанавливаются равными null.

Случай 1 – с верхушки стека снимается одно наименование и заносится в тетраду в качестве первого операнда, в качестве второго операнда устанавливается null.

Случай 2 – с верхушки стека снимаются два наименования и заносятся (в порядке извлечения из стека) в тетраду в качестве операндов.

Случай k>2 – с верхушки стека снимаются k слов, для каждого строится вспомогательная тетрада со знаком операции присваивания, снятым со стека наименованием в качестве первого операнда, значением null в качестве второго операнда и наименованием формального аргумента процедуры/функции в качестве результата. Каждая вспомогательная тетрада выдается на выход. После этого формируется тетрада с наименованием процедуры/функции в качестве знака операции и пустыми (null) наименованиями операндов.

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

---

Шаг 5. Если был достигнут конец входной ПФЗ, то выполняется останов процесса преобразования, иначе – переход к шагу 2. Конец алгоритма.

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

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

Кроме того, заметим, что для случая k-арного знака операции при
k> 2 возможна модификация соответствующего случая шага 4 алгоритма, согласно которой строится k – 2 вспомогательных тетрады, а 2 последних извлекаемых из стека слова используются в качестве наименований операндов последней формируемой тетрады. В рассматриваемом ниже примере это привело бы к исчезновению тетрад 3 и 4 и замене обозначений null на x в поле операнд1 и на y в поле операнд2 тетрады.

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

1. 
   определить тип данных первого операнда;
   
2. 
   определить тип данных второго операнда;
   
3. 
   проверить, применим ли код операции к данным этих типов;
   
4. 
   сформировать и запомнить тип данных результата операции.
   

Все эти задачи можно решать и прямо в процессе формирования операций псевдокода.

Аналогичным образом можно преобразовывать ПФЗ в пентады и различные виды триад.

4. 
   Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Sample7):
   

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

---