Лекции (3) (1119474)

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

Текст из файла

Язык внутреннего представления программОсновные свойства языка внутреннего представления программ: он позволяет фиксировать синтаксическую структуру исходнойпрограммы; текст на нем можно автоматически генерировать во времясинтаксического анализа; его конструкции должны относительно просто транслироваться вобъектный код либо достаточно эффективно интерпретироваться.Некоторые общепринятые способы внутреннего представленияпрограмм: постфиксная запись, префиксная запись, многоадресный код с явно именуемыми результатами, многоадресный код с неявно именуемыми результатами, связные списочные структуры, представляющие синтаксическоедерево.ПОЛИЗПОЛИЗ идеален для внутреннего представления интерпретируемых ЯП,которые, как правило, удобно переводятся в ПОЛИЗ и легко интерпретируются.В ПОЛИЗе операнды выписаны слева направо в порядке их следования висходном тексте.Знаки операций стоят таким образом, что знаку операции непосредственнопредшествуют ее операнды.Более формально постфиксную запись выражений можно определить такимобразом: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: ...

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций