Задание на лабораторную работу
Разработать синтаксический анализатор подмножества заданного языка программирования на основе метода LR(1). Варианты заданий приведены в таблице 5.5. Код задания на лабораторную работу состоит из трех компонент.
Первая цифра варианта определяет язык программирования (1- PL0, 2- ASPLE). Описание синтаксиса языков программирования PL0 и ASPLE приведены соответственно в приложениях 1 и 2.
Вторая цифра варианта определяет подмножество языка программирования. Описание подмножеств языков программирования PL0 и ASPLE приведены соответственно в приложениях 3 и 4.
Таблица 5.5
| Номер варианта | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Код задания | 11П | 12С | 13П | 14С | 21П | 22С | 23П | 24С |
| Номер варианта | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Код задания | 11С | 12П | 13С | 14П | 21С | 22П | 23С | 24П |
Третья цифра-язык программирования: П- Паскаль, С -Си.
Содержание отчета
5.3.1.Постановка задачи.
5.3.2.Управляющая таблица разбора.
5.3.3.Текст программы.
5.3.4.Описание тестовых примеров.
5.3.5.Распечатка результатов.
Библиографический список
1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. - М.: Мир, 1978. - 612с.
2. Р.Хантер. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232с.
3. Д.Грис. Конструирование компиляторов для ЦВМ. - М.: Мир, 1975.- 544 с.
ЛАБОРАТОРНАЯ РАБОТА № 6 ОПТИМИЗАЦИЯ ОБЪЕКТНОГО КОДА
|
|
|
Цель работы: изучение методов оптимизации объектного кода, получение навыков в программировании алгоритмов оптимизации.
Теоретическое введение
Под оптимизацией будем понимать ряд преобразований, которые можно выполнять над программой с целью повышения эффективности объектного кода. Такие преобразования можно выполнять в различных блоках компилятора, но наиболее сложные из них обычно выполняются отдельным блоком оптимизации, включаемым в работу после синтаксического анализа до генерации кода(1,2,3).
Рассмотрим подмножество оптимизирующих преобразований, которые предлагается реализовать в рамках данной лабораторной работы. Объектный код, над которым выполняются оптимизирующие преобразования, будем считать заданным в виде последовательности триад, состоящих из полей:
<метка><код операции><операнд 1><операнд 2>.
Поле <метка> предназначено для идентификации составных частей циклов и может содержать один из следующих четырёх идентификаторов:INIT(инициализация цикла), INCR(изменение параметра цикла), TEST(проверка условия выхода из цикла) , LOOP(тело цикла).
Удаление общих подвыражений.
Некоторая i-ая триада линейного списка считается лишней, если существует более ранняя идентичная ей j-ая триада, и никакая переменная, от которой зависит результат этой триады, не изменяется третей триадой, лежащей между i-ой и j-ой (1-3).
|
|
|
Для того чтобы следить за внутренней зависимостью переменных и триад, поставим им в соответствие поставим им числа зависимости по следующим правилам.
1.Вначале для всех переменных объектного кода числа зависимости dep(<переменная>) равны 0.
2.После обработки i-ой триады, в которой переменной A присваивается некоторое значение, dep(A) меняется на i.
3.При обработке i-ой триады ее число зависимости dep(Ti) равно 1+<максимальное из чисел зависимости ее операндов>.
Полученные числа зависимости используются следующим образом:
если i-ая триада идентична j-ой триаде (j<i), тогда i-ая триада считается лишней в том и только том случае, когда dep(i)=dep(j).
Пример.
Об'ектный код dep A B C D Ti
* С В 0 0 0 0 1
+ D T1 0 0 0 0 2
:= D T2 0 0 0 0 3
* C B 0 0 0 3 1
+ D T4 0 0 0 3 4
:= A T5 0 0 0 3 5
6 0 0 3
|
|
|
Триада Т4 идентична триаде Т1 и dep(T4)=dep(T1)=1. После преобразования получим объектный код:
dep(Ti)
* С В 1
+ D T1 2
:= D T2 3
+ D T1 4
:= A T4 5
Удаление мертвых переменных
Переменная называется мертвой в программе, если ее значение после определения нигде в программе не используется. Из объектного кода следует удалить триаду, присваивающую значение мертвой переменной, и все триады, вычисляющие это значение. Во избежание удаления триад, на которые есть ссылки в других участках объектного кода, такое преобразование рекомендуется выполнять после удаления общих подвыражений /1-3/.
Распространение констант
Процедура распространения констант заключается в выполнении тех операций, значения операндов которых известны во время компиляции /1/.
Для выполнения такой процедуры организуется вспомогательная таблица Т, содержащая пары (A,K) для всех переменных A, для которых известно текущее значение К. Каждая свертываемая (вычисляемая) триада заменяется на С К, где С- новая "операция", для которой не нужно генерировать команды, а К- результат вычисления триады.
|
|
|
Алгоритм распространения констант последовательно просматривает триады линейного участка и для каждой триады делает следующее.
1.Если операнд-переменная, которая содержится в Т, то он заменяется на константу К.
2.Если операнд-ссылка на триаду типа С К _ , то он заменяется на константу К.
3.Если все операнды являются константами, то выполняется указанная в данной триаде операция, и триада заменяется на С К _ , где К-результат выполнения операции.
4.Если триада реализует присвоение вида А:=В, то:
- если В-константа, то А со значением В заносится в таблицу Т (старое значение А, если оно было, исключается);
-если В- не константа, то А своим значением исключается из Т, если она там была.
Пример:
| Обьектный код | Результат операции | ||||||
| Обьектный код | Таблица Т | ||||||
| + | 1 | 1 | С | 2 | А | 2 | |
| := | А | Т1 | := | А | 2 | I | 3 |
| := | I | 3 | := | I | 3 | B | 9.2 |
| + | 6.2 | I | C | 9.2 | |||
| := | B | T4 | := | B | 9.2 | ||
Удаление лишних переменных
Переменная называется лишней, если после своего определения она используется в программе один раз(1-3).
Для выявления лишних переменных каждой переменной объектного кода ставится в соответствие троичный признак использования, который устанавливается в 0 при обнаружении триады, присваивающей значение переменной, в 1 и 2 при первом и втором появлении этой переменной в качестве операнда в триадах линейного участка программы соответственно. Выявление лишней переменной происходит в момент установки признака использования в 0: если его предыдущее значение было равно 1, то переменная является лишней, и ссылку на неё следует заменить присвоенным ей значением или ссылкой на триаду, вычисляющую её значение.
Пример.
|
Обьектный код | Признаки использования переменных | ||
| А | В | С | |
| := А В | 0 | х | Х |
| + А 1 | 1 | х | Х |
| := С 0 | 1 | х | 0 |
| +Т2 С | 1 | х | 1 |
| + С Т4 | 1 | х | 2 |
| := А Т5 | 0 | х | 2 |
Переменная А в приведённом линейном участке объектного кода является лишней. В триаде Т2 её следует заменить присвоенным ей значением, а в триаду Т1-удалить:
+ B 1
:= C 0
+ T1 C
+ C T3
:= A T4
Удаление индуктивных переменных
Переменная Х называется индуктивной, если принимаемые ею последовательно значения х1,х2,… на участках цикла INIT и LOOP образует арифметическую прогрессию(1-3).
Индуктивные переменные i1 и i2 одного участка цикла связываются друг с другом линейными преобразованиями вида i1=i2+const. Поэтому внутри области цикла можно использовать только одну из индуктивных переменных, а все остальные, если их значения требуются за пределами цикла, вычислять один раз при выходе из этого цикла.
Пример 1.
INIT := I 1
:= L J
:= K 0
LOOP + L I
:= S T4
+ K S
:= K T6
INCR + I 1
:= I T8
TEST = I 1000
JFALSE T4
В приведённом объектном коде индуктивными переменными являются I (принимает значения 1,2,…..1000) и S(принимает значения J+1,J+2,….,J+1000).
Задача нахождения всех индуктивных переменных в области является нетривиальной, и алгоритма её решения не существует.В рамках лабораторной работы предлагается составить программу преобразования заданного участка объектного кода при заданном списке индуктивных переменных, вычисляемых этим участком.
Одна из переменных этого списка может быть выбрана в качестве базовой. Тогда для всех остальных переменных списка следует определить значения констант, связывающих эти переменные с базовой, собрав эти значения в таблицу. При построении такой таблицы формирование записи для одной переменной потребует выполнения, возможно, нескольких шагов, поскольку переменная может быть связана с базовой не явно, а через другие индуктивные переменные.
Выберем, например, в качестве базовой такую переменную из списка индуктивных, которой присваивается значение на участке INIT раньше других. Таблицу индуктивных переменных построим за несколько шагов. На каждом шаге для любой индуктивной переменной будем определять имя текущей переменной (или триады), относительно которой определено значение данной индуктивной переменной, и вычислять константу, связывающую индуктивную переменную с текущей.Изменение записи таблицы, относящейся к некоторой индуктивной переменной, будем выполнять до тех пор, пока имя переменной, относительно которой определена данная индуктивная переменная, не совпадет с именем базовой переменной.
Пример 2.
Об'ектный код
INIT := I 1
LOOP + I 1 Список индуктивных переменных:
+ T2 2 I,K,S.
:= K T3
- K 3
+ T5 4
:= S T6
Выберем I в качестве базовой переменной. Построим таблицу связей индуктивных переменных.
Шаг 1 Шаг 2 Шаг 3 Шаг 4
I 1,0 1,0 1,0 1,0
K T3,0 T2,2 I,3 I,3
S T6,0 T5,4 K,1 I,4
Для объектного кода из примера 1,если выбрать базовой переменную I, значение S=I+L определяется за два шага.
Теперь цикл может быть преобразован вынесением за его пределы вычислений всех индуктивных переменных, кроме базовой:
INIT := I 1
:= L J
:= K 0
LOOP + L I
+ K T4
:= K T5
INCR + I 1
:= I T7
TEST = I 1000
JFALSE T4
+ L I
:= S T11
Отметим, что в рассмотренном примере было бы выгоднее в качестве базовой выбрать переменную S, поскольку она используется для вычислений внутри участка LOOP, и, следовательно, триаду + L I из этого участка удалить нельзя, в то время как переменная I используется только для управления циклом. Если управление циклом возложить на переменную S, то от I можно совсем избавиться:
INIT := L J
:= K 0
+ L 1
:= S T3
+ S 1000
:= R T5
LOOP + K S
:= K T7
INCR + S 1
:= S T9
TEST = S R
JFALSE T7
Дата добавления: 2019-02-12; просмотров: 242; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!