Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

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

Для иллюстрации работы созданного компилятора взяты два примера входной программы:

1. Программа, вычисляющая факториал числа.

2. Программа, на примере которой можно иллюстрировать работу оптимизирующих алгоритмов.

Оба примера приведены в приложении 4.

Первый пример вычисляет факториал входной величины, причем если величина отрицательная или превышает 31, то программа возвращает 0. Умножение реализовано через цикл операций сложения. Входной файл приведен в листинге П4.1, а полученный результирующий файл – в листинге П4.2, приложение 4.

Второй пример содержит почти бессмысленную программу, которая всегда возвращает значение, равное 0, но на примере этой программы можно хорошо проиллюстрировать работу оптимизирующих алгоритмов. Входной файл приведен в листинге П4.3, в листинге П4.4 приведен результирующий файл, полученный без применения оптимизации, а в листинге П4.5 – файл, полученный с применением оптимизации. Желающие могут сравнить ассемблерный код этих двух файлов и проверить эффективность используемых алгоритмов оптимизации. [12]

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

Построенный компилятор обнаруживает все синтаксические ошибки языка, а также семантические ошибки:

• присваивание значений константам (когда первый операнд в операторе присваивания – константа);

• присваивание значений предопределенной входной переменной InpVar;

• использование предопределенной переменной Result.

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

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

• свертка объектного кода;

• исключение лишних операций;

• исключение бесполезных арифметических и логических операций;

• модификация операций загрузки значения в регистр с учетом особенностей процессоров типа Intel 80x86.

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

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

1. Лексический анализ исходного текста и построение таблицы лексем.

2. Синтаксический анализ по таблице лексем и построение дерева синтаксического разбора.

3. Построение списка триад по дереву синтаксического разбора.

4. Оптимизация списка триад методом свертки объектного кода.

5. Оптимизация списка триад методом исключения лишних операций.

6. Построение результирующего ассемблерного кода по списку триад.

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

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

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

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

Условные обозначения:

• А– любой алфавитно-цифровой символ;

• А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;

• П – любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);

• Б – любая буква английского алфавита (прописная или строчная) или символ подчеркивания («_»);

• Б(*) – любая буква английского алфавита (прописная или строчная) или символ подчеркивания («_»), кроме перечисленных в скобках;

• Ц – любая цифра от 0 до 9;

• F – функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое; обозначения ее аргументов:

v – переменная, запомненная при работе КА;

d – константа, запомненная при работе КА;

a – текущий входной символ КА.

В остальных случаях аргументом функции F является соответствующая лексема. Конечный автомат:

M(Q,Σ,δ,q 0,F):

Q = {H, C, G, V, D, I1, I2, T1, T2, T3, T4, E1, E2, E3, E4, O1, O2, X1, X2, X3, A1, A2, A3, F}

Σ = А (все допустимые алфавитно-цифровые символы); q 0= H; F = {F}.

В таблице П1.1. указаны значения функции переходов δ.

При описании функции переходов через разделитель «|» указаны вызовы функции F, необходимые при выполнении того или иного перехода (если они есть).