4. Содержание работы

В ходе выполнения работы студенты должны выполнить следующие задания:

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

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

3. Построить сканер, который выделял бы из текста входной программы на языке С все содержащиеся в ней строковые константы и записывал их в отдельный файл. Строковые константы в языке С состоят из строк, одиночных символов и кодов символов. Строки ограничены символами “ ” (двойные кавычки), одиночные символы – символами ‘ ’ (одинарные кавычки), а коды символов начинаются со знака \ и содержат цифры.

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

1. Сравните восходящий и нисходящий распознаватели. Какими преимуществами и недостатками обладает каждый из этих методов?

2. Какой цели служит преобразование правил КС-грамматик? Всегда ли это преобразование ведет к упрощению правил?

3. На алгоритме какого распознавателя основан метод рекурсивного спуска? Можно ли реализовать распознаватель по методу расширенного рекурсивного спуска для грамматики, содержащей левую рекурсию?

4. За счет сего класс LL(1)-грамматик является более широким, чем класс КС-грамматик?

5. На каком алгоритме основана работа распознавателя для LL(k)-грамматики?

Лабораторная работа № 2

Генерация и оптимизация кода

1. Цель работы

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

2. Краткие теоретические сведения

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

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

3. Примеры

3.1. Схемы су – перевода

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

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

• оба нижележащих узла дерева – листья, помеченные операндами;

• только левый нижележащий узел является листом дерева;

• только правый нижележащий узел является листом дерева;

• оба нижележащих узла не являются листьями дерева.

Рассмотрим построение двух видов внутреннего представления по дереву вывода:

1. построение списка триад по дереву вывода;

2. построение ассемблерного кода по дереву вывода.