Теория компиляторов-1. Л.51 Классическая теория компиляторов Лекция 5. - презентация

1 Теория компиляторов-1. Л.51 Классическая теория компиляторов Лекция 5

2 Теория компиляторов-1. Л.52 ВНУТРЕННИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ ПОЛЬСКАЯ ФОРМА 1.Если R является операндом (идентификатором или константой), то его значение заносится в стек аргументов S и осуществляется считывание следующего символа (правило " ::=идентификатор"). 2.Если R – оператор, то из стека аргументов S извлекается необходимое количество аргументов; выполняется операция и результат заносится обратно в стек S. R := getchar while R != # do case тип(R) of 'операнд':push(R) 'бин.оператор':pop(B), pop(A), Tmp := R(A,B), push(Tmp) 'унарн.оператор':pop(A), Tmp := R(A), push(Tmp) endcase R := getchar endwhile Замечание. Существуют операторы, которые не заносят в стек результаты своей работы.

3 Теория компиляторов-1. Л.53 Операторы в ПФ Безусловные переходы Безусловный переход на метку (аналог GOTO L) L $BRL (Branch to label) L – имя в таблице символов. Значение его – адрес перехода. Основная проблема при реализации этого оператора – определение адреса перехода. Возможным решением является введение фиктивного оператора, соответствующего метке, на которую будет осуществлен переход с последующим поиском его в массиве польской формы. Безусловный переход на символ C $BR Условные переходы $BRxZ|$BRM|$BRP|$BRMZ|$BRPZ| – значение арифметического выражения, – номер или место символа в польской цепочке (адрес). $BRx – код оператора. При этом можно ввести самые разнообразные условия перехода. Например: $BRZ – переход по значению 0, $BRM – переход по значению 0, $BRMZ – переход по значению =0, и т.п. При выполнении условия перехода в качестве следующего символа берется тот символ, адрес которого определяется вторым операндом. В противном случае работа продолжается как обычно.

4 Теория компиляторов-1. Л.54 Условные конструкции IF THEN ELSE $BRZ $BR Предполагается, что для любого выражения 0 означает "ложь", а неравенство нулю – "истина". Здесь – номер символа, с которого начинается, – номер символа, следующего за, $BR – оператор безусловного перехода на символ, $BRZ – оператор перехода на символ c1, если значение равно нулю).

5 Теория компиляторов-1. Л.55 Массивы и функции Описание массивов ARRAY A[L1..U1,...,Lk..Uk] L1 U1... Lk Uk A $ADEC, где $ADEC – оператор объявления массива. Оператор $ADEC имеет переменное количество аргументов, зависящее от числа индексов. Операнд A – адрес в таблице символов. При вычислении $ADEC из этого элемента таблицы извлекается информация о размерности массива A и, следовательно, о количестве операндов $ADEC. Отсюда понятно, почему операнд A должен располагаться непосредственно перед оператором $ADEC. Обращение к элементу массива A[,.., ].. A $SUBS Оператор $SUBS, используя элемент A таблицы символов и индексные выражения, вычисляет адрес элемента массива. Затем операнды исключаются из стека и на их место заносится новый операнд, специфицирующий тип элемента массива и его адрес. Вызов подпрограмы Вызов функции вида f(x1,x2): x1 x2 f $CALL, где x1 и x1 – аргументы, f – имя функции, $CALL – команда передачи управления по адресу, определяемому именем функции. При этом предполагается, что мы заранее занесли в таблицу имен информацию о том, сколько и каких аргументов у функции f, а также ее адрес – индекс начала кода подпрограммы в массиве польской формы.

6 Теория компиляторов-1. Л.56 Циклы FOR I=N1 TO N2 DO Operator I := N1; L1:IF I>N2 THEN GOTO L2; Operator; I:=I+1; GOTO L1; L2:

7 Теория компиляторов-1. Л.57 Пример BEGIN INTEGER K; ARRAY A[1..I-J]; K := 0; L:IF I>J THEN K := K+A[I-J]*6 ELSE BEGIN I := I+1; GOTO L; END END.

8 Теория компиляторов-1. Л.58 ТЕТРАДЫ (1) $BLOCK (10) + K, T4, T5 (2) - I, J, T1(11) := T5,, K (3) $BOUNDS 1, T1(12) $BR 18 (4) $ADEC A(13) + I, 1, T6 (5) := 0,, K(14) := T6,, I (6) - I, J, T2(15) + I, 1, T7 (7) $BMZ 13, T2(16) := T7,, I (8) - I, J, T3(17) $BRL L (9) * A[T3], 6, T4(???)(18) $BLOCKEND BEGIN INTEGER K; ARRAY A[1..I-J]; K := 0; L:IF I>J THEN K := K+A[I-J]*6 ELSE BEGIN I := I+1; GOTO L; END END.

9 Теория компиляторов-1. Л.59 Тетрады $AINDX I $AGET A, R "A[1,2]+B[J]" $AINDX 1 $AINDX 2 $AGET A, T1 $AINDX J $AGET B, T2 + T1, T2, T3

10 Теория компиляторов-1. Л.510 Префиксная форма записи Определение префиксной формы записи (ПрФ): Если инфиксное выражение Е представляет собой один операнд а, то ПрФ выражения Е - это а. Если инфиксное выражение - знак операции, а Е1 и Е2 - инфиксные выражения для операндов, то ПрФ этого выражения - где E1', E2' - ПрФ выражений Е1 и Е2. Если (Е) есть инфиксное выражение, то ПрФ этого выражения есть Е.

11 Теория компиляторов-1. Л.511 Примеры Пример 1. E инф = a + b По определению ПрФ выражения - где Е1',Е2' - ПрФ выражений Е1 и Е2. ПрФ для E1 и E2 – это E1' = a, E2' = b Окончательно: +ab Пример 2. E инф = a + b*c По определению ПрФ выражения - где Е1',Е2' - ПрФ выражений Е1 и Е2. ПрФ для E1 и E2 – это E1' = a, E2' = *bc Окончательно: +a*bc

12 Теория компиляторов-1. Л.512 Примеры Пример 3. E инф = (a + b) * (c - d) Представляем E в виде E1*E2, где E1 = (a + b), E2 = (c - d). По определению ПрФ выражения - где Е1',Е2' - ПрФ выражений Е1 и Е2. ПрФ для E1 и E2 – это E1' = +ab, E2' = -cd Окончательно: *+ab-cd Пример 4. E преф =log + y - y 2 / b sin x

13 Теория компиляторов-1. Л.513 Примеры E инф = x 2 +(x+ 3) 2 E инф = y+ 3

14 Теория компиляторов-1. Л.514 Примеры

15 Теория компиляторов-1. Л.515 Примеры Пример 6. E инф = cos 2 (a+1)+sin 2 (a+1)

16 Теория компиляторов-1. Л.516 Основная теорема префиксной формы записи Последовательность символов S является правильно построенной префиксной формой, если и только если: 1.ранг(S)=-1 2.ранг(последовательности слева от S) 0 Причем считается, что: ранг(оператора) = вес(оператора)-1, ранг(пустой последовательности) = 0, ранг(n-го символа) = n-1, ранг(переменной) = ранг(константы) = -1, ранг(S1 соединенной с S2) = ранг(S1)+ранг(S2).

17 Теория компиляторов-1. Л.517 Пример Пример 7. E инф = cos 2 (a+1)-sin 5 (b+2) Суммарный ранг равен -1. Для нахождения границы терма, образованного, например, оператором cos, начнем суммировать ранги, начиная с этого оператора. Мы остановимся в позиции 6. Таким образом, граница терма - с 3 по 6 позиции (cos + a 1).

18 Теория компиляторов-1. Л.518 Вычисление префиксной формы записи 1. Прочитать очередной символ входной цепочки R. 2. Если входной символ - оператор, то занести его в стек 3. Если входной символ - операнд, то: 3.1. Отыскать в стеке последний оператор OP Если этому оператору хватает операндов (тех, что находятся в стеке после OP плюс текущий операнд R), то извлечь из стека оператор OP, соответствующие операнды вместе с R и выполнить операцию. Результат поместить в стек. Вернуться к п.3.1. иначе поместить символ R в стек. 4. Вернуться к П1. Необходим стек, умеющий хранить как вычисляемые значения, так и операторы.