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

intTop(void); – вернуть значение с верхушки, не удаляя его из стека.

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

Operator : while

{Push(++WhileCount); PutToPFR(“Label1” # Top() # “:”);}

( Expression )

{ PutToPFR(“Label2” # Top()); PutToPFR(“JmpF”);}

Block

{ PutToPFR(“Label1” # Top()); PutToPFR(“Jmp”);

PutToPFR(“Label2” # Pop() # “:”); }

Кроме операторов цикла while язык программирования, как правило, содержит другие формы операторов цикла (for, do, …), условные операторы, переключатели и т. д.

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

– требуется ли поддерживать отдельные счетчики для разных типов управляющих конструкций или для всех таких операторов использовать один счетчик;

– поддерживать ли несколько вспомогательных стеков или можно обойтись одним.

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

1. 
   Реализовать полную грамматику языка, заданного на курсовую работу.
   
2. 
   Используя пакет ВебТрансБилдер, изучить и освоить:
   

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

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

---

5. 
   Требования к содержанию отчета.
   

Отчет должен содержать:

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

6. 
   Контрольные вопросы
   

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

---

Лабораторная/практическая работа № 7

1. 
   Название работы: «Семантика языков программирования. Семантический анализ и генерация псевдокода».
   
2. 
   Цели работы: изучение семантических свойств объектов транслируемой программы, методов их выявления и использования, типов данных и методов контроля типов, областей видимости переменных, локальных и нелокальных сред ссылок, способов передачи параметров, приобретение навыков преобразования ПФЗ в псевдокод.
   
3. 
   Основные теоретические сведения:
   

1. 
   Задачи семантического анализа
   

Совокупность исходных данных для семантического анализа формируется предыдущими этапами процесса трансляции.

1. 
   Постфиксная форма записи (ПФЗ) или ее эквивалент – синтаксическое дерево транслируемой программы – промежуточное представление, которое образуется в процессе синтаксического анализа.
   
2. 
   Набор информационных таблиц, в которых накоплены сведения об используемых программой данных.
   

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

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

1. 
   Компиляция – продолжение преобразований представления программы на стадии трансляции, завершающееся формированием и сохранением так называемого объектного (целевого) кода, который впоследствии может многократно исполняться процессором компьютера (реальной машиной) уже без какого бы то ни было участия транслятора.
   
2. 
   Интерпретация – исполнение последовательности операций непосредственно транслятором (прямая интерпретация) или специально разработанной для этого программой (так называемой виртуальной машиной – отложенная интерпретация), возможно, с предварительным преобразованием постфиксной записи в более удобную промежуточную или сохраняемую форму.
   

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

---

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

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

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

Таким образом, в логической последовательности этапов процесса трансляции семантический анализ занимает позицию непосредственно после синтаксического и перед генерацией объектного кода в случае компиляции либо перед исполнением вычислений в случае интерпретации. Реальная последовательность выполнения этапов при трансляции совсем не обязательно совпадает с логической последовательностью.

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

Однако применительно к каждому конкретному синтаксически целостному фрагменту текста (модулю/файлу, подпрограмме/функции, блоку, оператору, …) логическая последовательность этапов трансляции всегда строго соблюдается.

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

---

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

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

Трансляторы с таких языков вынужденно реализуют более чем один проход по тексту программы (или по одному из ее промежуточных представлений – последовательности токенов (лексем), постфиксной записи, …).

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

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




Рис. 7.1. Структура семантического анализатора

Например, пусть транслятор с языка С/С++ обрабатывает функцию вычисления наибольшего общего делителя двух аргументов:

int nod( int first, int second ){

while ( first != second )

if ( first < second )

second –= first;

else

first –= second;

return first;

}

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

nod int functionActivate 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

Здесь:

nod int functionActivate

---