Материалы (7) (1115034)
Текст из файла
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: ...
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
