Лекции (3) (Презентации лекций (PDF))

Язык внутреннего представления программОсновные свойства языка внутреннего представления программ: он позволяет фиксировать синтаксическую структуру исходнойпрограммы; текст на нем можно автоматически генерировать во времясинтаксического анализа; его конструкции должны относительно просто транслироваться вобъектный код либо достаточно эффективно интерпретироваться.Некоторые общепринятые способы внутреннего представленияпрограмм: постфиксная запись, префиксная запись, многоадресный код с явно именуемыми результатами, многоадресный код с неявно именуемыми результатами, связные списочные структуры, представляющие синтаксическоедерево.ПОЛИЗПОЛИЗ идеален для внутреннего представления интерпретируемых ЯП,которые, как правило, удобно переводятся в ПОЛИЗ и легко интерпретируются.В ПОЛИЗе операнды выписаны слева направо в порядке их следования висходном тексте.Знаки операций стоят таким образом, что знаку операции непосредственнопредшествуют ее операнды.Более формально постфиксную запись выражений можно определить такимобразом:1) если Е является единственным операндом, то ПОЛИЗ выражения Е- это сам этот операнд;2) ПОЛИЗом выражения Е1  Е2, где  - знак бинарной операции,Е1 и Е2 операнды для , является запись E1’ E2’  , где E1’ и E2’ –ПОЛИЗ выражений Е1 и Е2 соответственно;3) ПОЛИЗом выражения  E, где - знак унарной операции, а Е - операнд ,является запись E’ , где E’ - ПОЛИЗ выражения Е;4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.Алгоритм вычисления выражений, записанных вПОЛИЗеВыражение просматривается один раз слева направо, при этомЕсли очередной элемент ПОЛИЗа - это операнд, то его значениезаносится в стек;Если очередной элемент ПОЛИЗа - это операция, то на"верхушке" стека находятся ее операнды, они извлекаются изстека, и над ними выполняется операция, результат выполненияснова заносится в стек;Когда выражение, записанное в ПОЛИЗе, прочитано, в стекеостанется один элемент - это значение всего выражения.Для интерпретации, кроме ПОЛИЗа выражения, необходимадополнительная информация об операндах, хранящаяся втаблицах.Неоднозначно интерпретируемые операции вПОЛИЗеМожет оказаться так, что знак бинарной операции по написаниюсовпадает со знаком унарной; например, знак "-" в большинствеязыков программирования означает и бинарную операцию вычитания,и унарную операцию изменения знака.В этом случае во время интерпретации операции "-" возникнетнеоднозначность: сколько операндов надо извлекать из стека и какуюоперацию выполнять.

Устранить неоднозначность можно, по крайнеймере, двумя способами: заменить унарную операцию бинарной, т.е. считать, что "-а"означает"0 - а"; ввести специальный знак для обозначения унарной операции;например, "-а" заменить на “@a". Такое изменение касается тольковнутреннего представления программы и не требует изменениявходного языка.Аналогично разрешаются неоднозначности операций ++ и --.ПОЛИЗ для операторовОператор присваиванияI := Eв ПОЛИЗе будет записан как&I , E, := , ...где ":=" - двухместная операция, а &I и Е - ее операнды;&I означает, что операндом операции ":=" является адрес переменной I, ане ее значение.Оператор перехода в терминах ПОЛИЗа означает, что процессинтерпретации надо продолжить с того элемента ПОЛИЗа, который указан какоперанд операции перехода.Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что всеони перенумерованы, начиная с 1 (допустим, занесены в последовательныеэлементы одномерного массива).Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p,тогда оператор перехода goto L в ПОЛИЗе можно записать какp , !, ...где ! - операция выбора элемента ПОЛИЗа, номер которого равен p.Введем вспомогательную операцию - условный переход "по лжи" ссемантикойif (!B) goto LЭто двухместная операция в операндами B и L.

Обозначим ее !F, тогда вПОЛИЗе она будет записана какB, p, !F, ...где p - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой L, В - ПОЛИЗ логического выражения В.Семантика условного оператораif Е then S1 else S2с использованием введенной операции может быть описана так:if (! Е) goto L2; S1; goto L3; L2: S2; L3: ...Тогда ПОЛИЗ условного оператора будет таким (порядок операндов прежний!):Е, p2, !F, S1, p3, !, S2, ...где pi - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой Li, i = 2,3, Е - ПОЛИЗ логического выражения Е.Семантика оператора цикла while Е do S :L0: if (! Е) goto L1; S; goto L0; L1: ... .Тогда ПОЛИЗ оператора цикла while будет таким (порядок операндов- прежний!):Е, p1, !F, S, p0, !, ...где pi - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой Li, i = 0,1, Е - ПОЛИЗ логического выражения Е.Операторы ввода и вывода М-языка - одноместные операции.Оператор ввода read (I) в ПОЛИЗе будет записан как&I read ;Оператор вывода write (E) в ПОЛИЗе будет записан какE write ,где Е - ПОЛИЗ выражения Е.Синтаксически управляемый переводСинтаксический, семантический анализ и генерация внутреннегопредставления программы часто осуществляются одновременно.Один из способов построения промежуточной программы синтаксически управляемый перевод.В основе синтаксически управляемого перевода лежит грамматика сдействиями, которые параллельно с анализом исходной цепочки лексемпозволяют генерировать внутреннее представление программы.Пример:Пусть есть грамматика, описывающая простейшее арифметическоевыражение.Gexpr:E→T{T }T→F{F }F → a | b | (E)Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗбудет такой.Gexpr_polish:E → T {  T < cout << ''; > }T → F {  F < cout << ''; > }F → a < cout << 'a'; > | b < cout << 'b'; > | (E)Синтаксически управляемый переводЕсли необходимо переводить в ПОЛИЗ в процессесинтаксического анализа методом рекурсивного спускавыражение, содержащее правоассоциативные операции,то для таких операций соответствующие правила выводаследует писать, например, таким образом:А→I=A|E...А грамматика с действиями по переводувыражения в ПОЛИЗ для этих правил вывода будеттакой:G:G:A → I < cout << “&I” ; > = A < cout << ‘=‘ ; > | E...Определение формального переводаПусть T1 и T2 — алфавиты.Формальный перевод  — это подмножество множества всевозможныхпар цепочек в алфавитах T1 и T2:   ( T1*  T2* ).Входной язык перевода  - язык Lвх() = {  |  : (,  )   }.Целевой (или выходным) языком перевода  - язык Lц() = { |  : (, )  }.Перевод  неоднозначен, если для некоторых   T1*, ,   T2*,   ,(, )   и (, )  .Чтобы задать перевод из L1 в L2, важно точно указать закон соответствиямежду цепочками L1 и L2.L1  { 0n 1m | n  0, m > 0} — входной язык,L2  { am bn | n  0, m > 0} — выходной язык, иперевод  определяется так:для любых n  0, m > 0 цепочке 0n1m  L1 соответствует цепочка ambn L2.Пример.

ПустьМожно записать  с помощью теоретико-множественной формулы:  { ( 0n1m, ambn ) | n  0, m > 0 }, Lвх () = L1 , Lц () = L2 .Пример.L1 = {  |   { a, b }+,  a = n,  b = m }L2 = { a[n/2] b[m/2] | n >= 0, m >= 0}G(L1):S → aA | bAA → aA | bA | Грамматика с действиями по переводу L1 в L2:S → a < n = 1; m = 0; > A | b < n = 0; m = 1; > A A → a < if (n) { cout << 'a'; n = o; } else n = 1; > A |bA < if (m) { cout << 'b'; m = o; } else m = 1; } > | Генератор внутреннего представленияпрограммы на М-языкеКаждый элемент в ПОЛИЗе - это лексема вида( тип_лексемы, значение_лексемы ).При генерации ПОЛИЗа используются дополнительные типы лексем:POLIZ_GO - “!” - ;POLIZ_FGO - “!F” ;POLIZ_LABEL для ссылок на номера элементов ПОЛИЗа;POLIZ_ADDRESS - для обозначения операндов-адресовГенерируемая программа размещается в объектеPoliz prog (1000);класса Poliz.Генерация внутреннего представления программы проходит во времясинтаксического анализа параллельно с контролем КУ.Для генерации ПОЛИЗа используется информация, "собранная"синтаксическим и семантическим анализаторами, а производится она спомощью действий, вставленных в функции семантического анализа.Класс Poliz.class Poliz{Lex *p;int size;int free;public:Poliz ( int max_size ) { p = new Lex [ size = max_size ]; free = 0;}~Poliz ( ) { delete [ ] p; }void put_lex ( Lex l ) { p [ free ] = l; free++; }void put_lex ( Lex l, int place ) { p [ place ] = l; }void blank ( ) { free++; }int get_free ( ) { return free; }lex& operator [ ] ( int index ) {if ( index > size ) throw "POLIZ:out of array";elseif ( index > free) throw "POLIZ:indefinite element of array";else return p [ index ];}void print ( ) {for ( int i = 0; i < free; i++) cout << p [ i ];}};Грамматика с действиями по контролю КУ и переводу вПОЛИЗ выражений и операторов присваивания, ввода ивывода М-языка.E → E1 | E1 [ = | < | > ] < st_lex.push (TD [c_val] ) > E1 < check_op () >E1 → T { [ + | - | or ] < st_lex.push (TD [c_val] ) > T < check_op () > }T → F { [ * | / | and ] < st_lex.push (TD [c_val] ) > F < check_op () > }F → I < check_id (); prog.put_lex ( curr_lex ); > |N < st_lex.push (LEX_INT); prog.put_lex ( curr_lex ); > |[ true | false ] < st_lex.push (LEX_BOOL); prog.put_lex ( curr_lex ); > |not F < check_not(); > | (E)S → I < check_id (); prog.put_lex (Lex (POLIZ_ADDRESS, c_val)); > :=E < eqtype (); prog.put_lex (Lex (LEX_ASSIGN)); >S→read (I <check_id_in_read(); prog.put_lex (Lex (POLIZ_ADDRESS, c_val));>)< prog.put_lex (Lex (LEX_READ)); >S → write ( E ) < prog.put_lex (Lex (LEX_WRITE)); >Грамматика с действиями по контролю КУ и переводу вПОЛИЗ условного оператора и оператора цикла.if E then S1 else S2if (!E) goto l2; S1; goto l3; l2: S2; l3:…S → if E < eqbool(); pl2 = prog.get_free(); prog.blank();prog.put_lex (Lex (POLIZ_FGO)); >then S1 < pl3 = prog.get_free(); prog.blank();prog.put_lex (Lex (POLIZ_GO));prog.put_lex (Lex (POLIZ_LABEL, prog.get_free()), pl2); >else S2 < prog.put_lex (Lex (POLIZ_LABEL, prog.get_free()), pl3); >while E do Sl0: if (!E) goto l1; S; goto l0; l1: ...