Материалы (7) (Материалы к лекциям)

148Внутреннее представление программыОсновныепрограмм:свойстваязыкавнутреннегопредставления1) внутреннее представление фиксирует синтаксическую структуруисходной программы;2) генерация внутреннего представления происходит в процессесинтаксического анализа;3) конструкции языка внутреннего представления должныотносительно просто транслироваться в объектный код либо достаточноэффективно интерпретироваться.149Некоторыепрограмм:способывнутреннегопредставления(а)постфиксная запись(б)префиксная запись(в)многоадресный код с явно именуемыми результатами(г)многоадресный код с неявно именуемыми результатами(д)связные списочные структуры, представляющиесинтаксическое дерево.В основе каждого из этих способов лежит некоторый методпредставления синтаксического дерева.150ПОЛИЗ – польская инверсная запись (постфикснаязапись)Пример. Обычной (инфиксной) записи выраженияa*(b+c)-(d-e)/fсоответствует такая постфиксная запись:abc+*de-f/- порядок операндов остался таким же, как и в инфиксной записи,- учтено старшинство операций,- нет скобок.151Простым будем называть выражение, состоящее из однойконстанты или имени переменной.Приоритет и ассоциативность операций в инфиксныхвыражениях позволяют четко установить границы операндов:a — простое выражение ;a + b ∗ c ∼ a + (b ∗ c) ;a – b + c – d ∼ (( a – b ) + c) – d .ПОЛИЗ выражений(1) если Е является простым выражением, то ПОЛИЗвыражения Е — это само выражение Е;(2) ПОЛИЗом выражения Е1 θ Е2,где θ — знак бинарной операции, Е1 и Е2 операнды для θ,является запись E1′ E2′ θ ,где E1′ и E2′ — ПОЛИЗ выражений Е1 и Е2 соответственно;(3) ПОЛИЗом выражения θ E, где θ — знак унарнойоперации, а Е — операнд θ,является запись E′ θ,где E′ — ПОЛИЗ выражения Е;(4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.152153Алгоритм интерпретации с помощью стекаПОЛИЗ просматривается поэлементно слева направо.

В стекехранятся значения промежуточных вычислений и результат.(1) если очередной элемент — операнд, то его значениезаносится в стек;(2) если очередной элемент — операция, то на "вершине"стека сейчас находятся ее операнды (это следует изопределенияПОЛИЗаипредшествующихдействийалгоритма); они извлекаются из стека, над ними выполняетсяоперация, результат снова заносится в стек;(3) когда выражение, записанное в ПОЛИЗе, прочитано, встеке останется один элемент — это значение всеговыражения.Замечание: для интерпретации, кроме ПОЛИЗа выражения, необходимадополнительная информация об операндах, хранящаяся в таблицах.154Алгоритм Дейкстры перевода в ПОЛИЗ выраженийБудем считать, что ПОЛИЗ выражения будет формироваться вмассиве, содержащем лексемы — элементы ПОЛИЗа, и при переводе вПОЛИЗ будет использоваться вспомогательный стек, также содержащийэлементы ПОЛИЗа — операции, имена функций и круглые скобки.1.

Выражение просматривается один раз слева направо.2. Пока есть непрочитанные лексемы входного выражения,выполняем действия:а) Читаем очередную лексему.б) Если лексема является числом или переменной, добавляем ее вПОЛИЗ-массив.в) Если лексема является символом функции, помещаем ее в стек.155г) Если лексема является разделителем аргументов функции(например, запятая):до тех пор, пока верхним элементом стека не станетоткрывающаяся скобка, выталкиваем элементы из стека вПОЛИЗ-массив.

Если открывающаяся скобка не встретилась,это означает, что в выражении либо неверно поставленразделитель, либо несогласованы скобки.д) Если лексема является операцией θ, тогда:1) пока приоритет θ меньше либо равен приоритету операции,находящейся на вершине стека (для лево-ассоциативныхопераций), или приоритет θ строго меньше приоритетаоперации, находящейся на вершине стека (для правоассоциативных операций) выталкиваем верхние элементыстека в ПОЛИЗ-массив;2) помещаем операцию θ в стек.е) Если лексема является открывающей скобкой, помещаем ее встек.156ж) Если лексема является закрывающей скобкой, выталкиваемэлементы из стека в ПОЛИЗ-массив до тех пор, пока на вершинестека не окажется открывающая скобка.

При этом открывающаяскобка удаляется из стека, но в ПОЛИЗ-массив не добавляется.Если после этого шага на вершине стека оказывается символфункции, выталкиваем его в ПОЛИЗ-массив. Если в процессевыталкивания открывающей скобки не нашлось и стек пуст, этоозначает, что в выражении не согласованы скобки.3.

Когда просмотр входного выражения завершен, выталкиваем всеоставшиеся в стеке символы в ПОЛИЗ-массив. (В стеке должны былиоставаться только символы операций; если это не так, значит ввыражении не согласованы скобки.)157Представление операторовОператор присваиванияI := Eв ПОЛИЗе будет записан какI E :=где ":=" - это двухместная операция, а I и Е - ее операнды; Iозначает, что операндом операции ":=" является адреспеременной I, а не ее значение.Расширение набора операций ПОЛИЗАОперация перехода (обозначается «!») в терминах ПОЛИЗаозначает, что процесс интерпретации надо продолжить с того элементаПОЛИЗа, который указан как операнд этой операции.Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать,что все они перенумерованы, начиная с 1 (например, занесены впоследовательные элементы одномерного массива).Пусть ПОЛИЗ оператора, помеченного меткой L, начинается сномера p, тогда оператор переходаgoto L в ПОЛИЗе записывается так:p!где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.158159Операция условный переход "по лжи" с семантикой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, Е’ – ПОЛИЗ логического выражения Е.160Семантика оператора цикла 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,где Е’ – ПОЛИЗ выражения Е.161Синтаксически управляемый переводВ основе синтаксически управляемого перевода лежит уже известная намграмматика с действиями.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)В процессе анализа методом рекурсивного спуска входной цепочки a + b ∗ спо грамматике Gexpr_polish в выходной поток будет выведена цепочкаa b с∗+162Определение: Пусть T1 и T2 — алфавиты.

Формальныйперевод τ — это подмножество множества всевозможных парцепочек в алфавитах T1 и T2 :τ ⊆ ( T1*× T2* ).Назовем входным языком перевода τ язык Lвх (τ)= {α | ∃ β :(α, β ) ∈ τ }.Назовем целевым (или выходным) языком перевода τ языкLц(τ)= {β | ∃ α : (α, β ) ∈τ }.Перевод τ неоднозначен, если для некоторых α ∈ T1*, β,γ ∈ T2*, β ≠ γ справедливы соотношения: (α, β ) ∈ τ и (α, γ ) ∈ τ.Рассмотренная выше грамматика Gexpr_polish задает однозначныйперевод: каждому выражению ставится в соответствие единственнаяпольская запись. Неоднозначные переводы могут быть интересны приизучении моделей естественных языков; длятрансляции языковпрограммирования используются однозначные переводы.Генератор внутреннего представления программы на МязыкеКаждый элемент в ПОЛИЗе - это лексема, т.е.

пара вида(тип_лексемы, значение_лексемы). При генерации ПОЛИЗабудем использовать дополнительные типы лексем:POLIZ_GO - “!” ;POLIZ_FGO - “!F” ;POLIZ_LABEL - для ссылок на номера элементов ПОЛИЗа;POLIZ_ADDRESS - для обозначения операндов-адресов(например, в ПОЛИЗе оператора присваивания).Будем считать, что генерируемая программа размещается вобъектеPoliz prog (1000);класса Poliz:163class 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 ofarray";elseif(index > free) throw "POLIZ:indefinite elementof array";else return p[index];};void print(){for (int i=0; i < free; i++) cout << p[i]; };};164Добавим действия по генерации в некоторые функциисемантического анализа: check_not( ) и c heck_op( ).void Parser::check_not () {if (st_lex.pop() != LEX_BOOL)throw "wrong type is in not";else {st_lex.push (LEX_BOOL);prog.put_lex (Lex (LEX_NOT));}}165void Parser::check_op () {type_of_lex t1, t2, op, t = LEX_INT, r =LEX_BOOL;t2 = st_lex.pop();op = st_lex.pop();t1 = st_lex.pop();if(op==LEX_PLUS ||op==LEX_MINUS||op==LEX_TIMES ||op==LEX_SLASH)r = LEX_INT;if (op == LEX_OR || op == LEX_AND)t = LEX_BOOL;if (t1 == t2&&t1 == t) st_lex.push(r);else throw "wrong types are in operation";prog.put_lex (Lex (op) );}166167Грамматика, содержащая действия по контролю контекстныхусловий и переводу выражений модельного языка в ПОЛИЗE→ E1 | E1 [ = | < | > ] 〈 st_lex.push (c_type) 〉 E1 〈 check_op ( ) 〉E1→ T { [ + | - | or ] 〈 st_lex.push (c_type ) 〉 T 〈 check_op ( ) 〉 }T→ F { [ * | / | and ] 〈 st_lex.push (c_type ) 〉 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)Пример реализации процедуры анализа инетерминала F :void Parser::F (){if ( c_type == LEX_ID ){check_id();prog.put_lex (Lex (LEX_ID, c_val));gl();}else if ( c_type == LEX_NUM ){st_lex.push ( LEX_INT );prog.put_lex ( curr_lex );gl();}else if ( c_type == LEX_TRUE ){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_TRUE, 1) );gl();}перевода для168else if ( c_type == LEX_FALSE){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_FALSE, 0) );gl();}else if (c_type == LEX_NOT){gl();F();check_not();}else if ( c_type == LEX_LPAREN ){gl();E();if ( c_type == LEX_RPAREN)gl();elsethrow curr_lex;}elsethrow curr_lex;}169170Действия для оператора присваиванияS → I 〈 check_id ( ); prog.put_lex (Lex (POLIZ_ADDRESS, c_val )); 〉 :=E 〈eqtype ( ); prog.put_lex (Lex (LEX_ASSIGN )); 〉Для условногоif (!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); 〉171Оператор цикла while E do S описывается так:L0: if (!E) goto l1; S; goto l0; l1: ...