Ишакова Е.Н. Разработка компиляторов - Методические указания к курсовой работе (1082246), страница 5

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

Текст из файла (страница 5)

IE:=,

где «:=» - двуместная операция,

I, E – операнды операции присваивания;

I – означает, что операндом операции «:=» является адрес переменной I, а не ее значение.

Пример 2.14. Оператор x:=x+9 в ПОЛИЗе имеет вид: x x 9 + :=.

Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:

p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.

Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if (not B) then goto L. Это двуместная операция с операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться:

B p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.

С использованием введенной операции условный оператор if B then S₁ else S₂ в ПОЛИЗе будет записываться:

B p₁ !F S₁ p₂ ! S₂, где p₁ – номер элемента, с которого начинается ПОЛИЗ оператора S₂, а p₁ – оператора, следующего за условным оператором.

Пример 2.15. ПОЛИЗ оператора if x>0 then x:=x+8 else x:=x-3 представлен в таблице 2.3.

Таблица 2.3 – ПОЛИЗ оператора if

Оператор цикла. С учетом введенных операций оператор цикла while B do S в ПОЛИЗе будет записываться:

B p₁ !F S p_o !, где p_o – номер элемента, с которого начинается ПОЛИЗ выражения B, а p₁ – оператора, следующего за данным оператором цикла.

Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read(I) в ПОЛИЗе запишется как I R, а оператор write(E) – E W.

Составной оператор begin S₁; S₂;...; S_n end в ПОЛИЗе записывается как S₁ S₂... S_n.

Пример 2.16. ПОЛИЗ оператора while n>3 do begin write(n*n-1); n:=n-1 end представлен в таблице 2.4.

Таблица 2.4 – ПОЛИЗ оператора while

Синтаксически управляемый перевод

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

Пример 2.17. Составим процедуры перевода в ПОЛИЗ программы на М языке.

ПОЛИЗ представляет собой массив, каждый элемент которого является парой вида (n, k), где n – номер таблицы лексем, k – номер лексемы в таблице. Расширяем набор лексем:

1) в таблицу ограничителей добавляем новые операции ! (18), !F (19), R (20), W (21);

2) для ссылок на номера элементов ПОЛИЗа введем нулевую таблицу лексем, т.е. пара (0, p) - это лексема, обозначающая p-ый элемент в ПОЛИЗе;

3) чтобы различать операнды-переменные и операнды-адреса переменных, обозначим переменные как четвертую таблицу лексем, а адреса – пятую.

Введем следующие обозначения переменных и процедур:

1) Р – переменная–массив, в который размещается генерируемая программа;

2) free – переменная, хранящая номер первого свободного элемента в массиве P;

3) LEX – переменная, хранящая очередную лексему;

4) put_lex(LEX) – запись очередной лексемы в массив P, т.е. P[free]:=LEX и free:=free+1;

5) put_l – запись текущей лексемы в массив P;

6) put_l5 – запись текущей лексемы в массив P с изменением четвертого класса лексем на пятый;

7) put_op - запись в массив P знака операции, считанного процедурой checkop;

8) make(k) - процедура, формирующая лексему-метку (0, k).

Правила, описывающие выражения языка М, с учетом действий перевода в ПОЛИЗ принимают вид.

Е  Е1 {( > | < | = ) <instl> E1 <checkop; put_op >}

E1 Т {(+ | - | ) <instl> T <checkop; put_op >}

T F {( * | / | ) <instl> F<checkop; put_op >}

F I <checkid; put_l> | N <inst(‘int’); put_l> | L <inst(‘bool’); put_l>|

F <checknot; put_lex(‘’)>| (E)

Оператор присваивания, дополненный действиями, примет вид:

S I <checkid; put_l5> := E <eqtype; put_lex(‘:=’)>

При генерации ПОЛИЗа выражений и оператора присваивания элементы массива Р записываются последовательно. Семантика условного оператора такова, что значения операндов для операций безусловного перехода и перехода «по лжи» в момент генерации еще не неизвестны. Поэтому необходимо запоминать номера элементов массива Р, соответствующих этим операндам, а затем, когда станут известны их значения, заполнять пропущенное.

Правила условного оператора и оператора цикла примут вид:

S if E <egbool; p1:=free; free:=free+1; put_lex(‘!F’)> then S <p2:=free; free:=free+1; put_lex(‘!’); P[p1]:=make(free)> else S <P[p2]:=make(free)>

S while <p0:=free> E <egbool; p1:=free; free:=free+1; put_lex(‘!F’)> do S <P[free]:=make(p0); put_lex(‘!’); P[p1]:=make(free) >

Правила операторов ввода и вывода с учетом действий записи в ПОЛИЗ будут преобразованы следующим образом:

S write (E <put_lex(‘W’)>) | read (I <checkid; put_l5; put_lex_(‘R’)> )

Чтобы в конце ПОЛИЗа была точка, правило Р переписывается в виде:

Pprogram D1 B <put_lex(‘.’)>.

Таким образом, польская инверсная запись очищена от всех служебных слов, кроме true и false; от ограничителей остаются только знаки операций и знаки «:=», «.».

2.7 Интерпретатор программы

Запись программы в форме ПОЛИЗа удобна для последующей интерпретации (выполнения программы) с помощью стека. Массив ПОЛИЗа просматривается один раз слева направо, при этом:

1) если очередной элемент ПОЛИЗа является операндом, то его значение заносят в стек;

2) если очередной элемент – операция, то на «верхушке» стека находятся ее операнды, которые извлекаются из стека, над ними выполняется соответствующая операция, результат которой заносится в стек;

3) интерпретация продолжается до тех пор, пока не будет считана из ПОЛИЗа точка, стек при этом должен быть пуст.

Пример 2.18. Интерпретировать ПОЛИЗ программы, заданный таблицей 2.5 при введенном значении а равном 7.

Таблица 2.5 – ПОЛИЗ исходной программы

Продолжение таблицы 2.5 – ПОЛИЗ исходной программы

Процесс интерпретации программы на модельном языке М, записанной в форме ПОЛИЗа, показан в таблице 2.6.

Таблица 2.6 – Ход интерпретации ПОЛИЗа программы

Продолжение таблицы 2.6 – Ход интерпретации ПОЛИЗа программы

Пример 2.19. Построим интерпретатор ПОЛИЗа для языка М.

Характеристики

Список файлов книги