Язык внутреннего представления программ Основные свойства языка внутреннего представления программ: он позволяет фиксировать синтаксическую структуру исходной. - презентация

1 Язык внутреннего представления программ Основные свойства языка внутреннего представления программ: он позволяет фиксировать синтаксическую структуру исходной программы; текст на нем можно автоматически генерировать во время синтаксического анализа; его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться. Некоторые общепринятые способы внутреннего представления программ: постфиксная запись, префиксная запись, многоадресный код с явно именуемыми результатами, многоадресный код с неявно именуемыми результатами, связные списочные структуры, представляющие синтаксическое дерево.

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

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

4 Неоднозначно интерпретируемые операции в ПОЛИЗе Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак "-" в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции "-" возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами: заменить унарную операцию бинарной, т.е. считать, что "-а" означает"0 - а"; ввести специальный знак для обозначения унарной операции; например, "-а" заменить Такое изменение касается только внутреннего представления программы и не требует изменения входного языка. Аналогично разрешаются неоднозначности операций ++ и --.

5 ПОЛИЗ для операторов Оператор присваивания I := E в ПОЛИЗе будет записан как &I, E, :=,... где ":=" - двухместная операция, а &I и Е - ее операнды; &I означает, что операндом операции ":=" является адрес переменной I, а не ее значение. Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации надо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они перенумерованы, начиная с 1 (допустим, занесены в последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператор перехода goto L в ПОЛИЗе можно записать как p, !,... где ! - операция выбора элемента ПОЛИЗа, номер которого равен p.

6 Введем вспомогательную операцию - условный переход "по лжи" с семантикой 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 - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L i, i = 2,3, Е - ПОЛИЗ логического выражения Е.

7 Семантика оператора цикла while Е do S : L0: if (! Е) goto L1; S; goto L0; L1:.... Тогда ПОЛИЗ оператора цикла while будет таким (порядок операндов - прежний!): Е, p1, !F, S, p0, !,... где pi - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L i, i = 0,1, Е - ПОЛИЗ логического выражения Е. Операторы ввода и вывода М-языка - одноместные операции. Оператор ввода read (I) в ПОЛИЗе будет записан как &I read ; Оператор вывода write (E) в ПОЛИЗе будет записан как E write, где Е - ПОЛИЗ выражения Е.

8 Синтаксически управляемый перевод Синтаксический, семантический анализ и генерация внутреннего представления программы часто осуществляются одновременно. Один из способов построения промежуточной программы - синтаксически управляемый перевод. В основе синтаксически управляемого перевода лежит грамматика с действиями, которые параллельно с анализом исходной цепочки лексем позволяют генерировать внутреннее представление программы. Пример: Пусть есть грамматика, описывающая простейшее арифметическое выражение. G expr :E T { T } T F { F } F a | b | (E) Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой. Gexpr_polish: E T { T } T F { F } F a | b | (E)

9 Синтаксически управляемый перевод Если необходимо переводить в ПОЛИЗ в процессе синтаксического анализа методом рекурсивного спуска выражение, содержащее правоассоциативные операции, то для таких операций соответствующие правила вывода следует писать, например, таким образом: G:А I = A | E... А грамматика с действиями по переводу выражения в ПОЛИЗ для этих правил вывода будет выглядеть так: G: A I = A | E...

10 Определение формального перевода Пусть T1 и T2 алфавиты. Формальный перевод это подмножество множества всевозможных пар цепочек в алфавитах T1 и T2: ( T1* T2* ). Входной язык перевода - язык Lвх( ) = { | : (, ) }. Целевой (или выходным) языком перевода - язык Lц( ) = { | : (, ) }. Перевод неоднозначен, если для некоторых T1*,, T2*,, (, ) и (, ). Чтобы задать перевод из L1 в L2, важно точно указать закон соответствия между цепочками L1 и L2. Пример. Пусть L1 { 0 n 1 m | n 0, m > 0} входной язык, L2 { a m b n | n 0, m > 0} выходной язык, и перевод определяется так: для любых n 0, m > 0 цепочке 0 n 1 m L1 соответствует цепочка a m b n L2. Можно записать с помощью теоретико-множественной формулы: { ( 0 n 1 m, a m b n ) | n 0, m > 0 }, Lвх ( ) = L1, Lц ( ) = L2.

11 Пример. 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 A | b A A a A | bA |

12 Генератор внутреннего представления программы на М-языке Каждый элемент в ПОЛИЗе - это лексема вида ( тип_лексемы, значение_лексемы ). При генерации ПОЛИЗа используются дополнительные типы лексем: POLIZ_GO - ! - ; POLIZ_FGO - !F ; POLIZ_LABEL - для ссылок на номера элементов ПОЛИЗа; POLIZ_ADDRESS - для обозначения операндов-адресов Генерируемая программа размещается в объекте Poliz prog (1000); класса Poliz. Генерация внутреннего представления программы проходит во время синтаксического анализа параллельно с контролем КУ. Для генерации ПОЛИЗа используется информация, "собранная" синтаксическим и семантическим анализаторами, а производится она с помощью действий, вставленных в функции семантического анализа.

13 Класс 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"; else if ( index > free) throw "POLIZ:indefinite element of array"; else return p [ index ]; } void print ( ) { for ( int i = 0; i < free; i++) cout free) throw "POLIZ:indefinite element of array"; else return p [ index ]; } void print ( ) { for ( int i = 0; i < free; i++) cout ">

14 Грамматика с действиями по контролю КУ и переводу в ПОЛИЗ выражений и операторов присваивания, ввода и вывода М-языка. E E1 | E1 [ = | ] E1 E1 T { [ + | - | or ] T } T F { [ * | / | and ] F } F I | N | [ true | false ] | not F | (E) S I := E S read (I ) S write ( E )

15 Грамматика с действиями по контролю КУ и переводу в ПОЛИЗ условного оператора и оператора цикла. if E then S1 else S2 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 while E do S l0: if (!E) goto l1; S; goto l0; l1:.... S while E < eqbool (); pl1 = prog.get_free (); prog.blank (); prog.put_lex (Lex (POLIZ_FGO)); > do S < prog.put_lex (Lex (POLIZ_LABEL, pl0); prog.put_lex (Lex (POLIZ_GO)); prog.put_lex (Lex (POLIZ_LABEL, prog.get_free()), pl1); >

16 Интерпретатор ПОЛИЗа для М-языка Польская инверсная запись выбрана в качестве языка внутреннего представления программы, в частности, потому, что записанная на нем программа может быть легко проинтерпретирована. Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо; если встречаем операнд, то записываем его в стек; если встретили знак операции, то извлекаем из стека нужное количество операндов и выполняем операцию, результат (если он есть) заносим в стек. Программа на ПОЛИЗе хранится в виде последовательности лексем в объекте класса Poliz - prog. Лексемы могут быть следующиe: - лексемы-константы (числа, true, false), - лексемы-метки ПОЛИЗа, - лексемы-операции (включая введенные в ПОЛИЗе) и - лексемы-переменные (их значения - номера строк в таблице TID). class Executer { Lex pc_el; public: void execute (Poliz & prog); };

17 void Executer::execute ( Poliz& prog ) { Stack args; int i, j, index = 0, size = prog.get_free ( ); while ( index < size ) { pc_el = prog [ index ]; switch ( pc_el.get_type () ) { case LEX_TRUE: case LEX_FALSE: case LEX_NUM: case POLIZ_ADDRESS: case POLIZ_LABEL: args.push ( pc_el.get_value () ); break; case LEX_ID: i = pc_el.get_value ( ); if ( TID [ i ].get_assign ( ) ) { args.push ( TID[i].get_value () ); break; } else throw "POLIZ: indefinite identifier";

18 case LEX_NOT: args.push( !args.pop() ); break; case LEX_OR: i = args.pop(); args.push ( args.pop() || i ); break; case LEX_AND: i = args.pop(); args.push ( args.pop() && i ); break; case POLIZ_GO: index = args.pop() - 1; break; case POLIZ_FGO: i = args.pop(); if ( !args.pop() ) index = i-1; break; case LEX_WRITE: cout

19 case LEX_READ: { int k; i = args.pop ( ); if ( TID [ i ].get_type () == LEX_INT ) { cout

20 case LEX_PLUS: args.push ( args.pop ( ) + args.pop ( ) ); break; case LEX_TIMES: args.push ( args.pop ( ) * args.pop ( ) ); break; case LEX_MINUS: i = args.pop ( ); args.push ( args.pop ( ) - i ); break; case LEX_SLASH: i = args.pop ( ); if ( ! i ) { args.push(args.pop ( ) / i); break;} else throw "POLIZ:divide by zero"; case LEX_EQ: args.push ( args.pop() == args.pop ( ) ); break; case LEX_LSS: i = args.pop ( ); args.push ( args.pop ( ) < i); break;

21 case LEX_GTR: i = args.pop(); args.push ( args.pop() > i ); break; case LEX_LEQ: i = args.pop(); args.push ( args.pop() = i ); break; case LEX_NEQ: i = args.pop(); args.push ( args.pop() != i ); break; case LEX_ASSIGN: i = args.pop(); j = args.pop(); TID[j].put_value(i); TID[j].put_assign(); break; default: throw "POLIZ: unexpected elem"; }//end of switch index++; };//end of while cout

22 class Interpretator { Parser pars; Executer E; public: Interpretator (char* program): pars ( program ) { }; void interpretation ( ); }; void Interpretator :: interpretation ( ) { pars.analyze ( ); E.execute ( pars.prog ); }

23 int main () { try { Interpretator I ("program.txt"); I.interpretation (); return 0; } catch (char c) { cout