formal_languages_translation_theory (852748), страница 16

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

Текст из файла (страница 16)

В этом случае во время интерпретации операции «» возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять.Устранить неоднозначность можно, по крайней мере, двумя способами: заменить унарную операцию бинарной, т. е. считать, что а означает 0  а; либо ввести специальный знак для обозначения унарной операции; например, а заменить наa. Важно отметить, что это изменение касается только внутреннего представления программы и не требует изменения входного языка.83Элементы теории трансляции / Генерация внутреннего представления программОператор присваиванияI : Eв ПОЛИЗе будет записан какI E :где «:» — это двухместная операция, а I и Е — ее операнды; подчеркнутое I означает,что операндом операции «:» является адрес переменной I, а не ее значение.Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации надопродолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода.Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они перенумерованы, начиная с 1 (допустим, занесены в последовательные элементы одномерногомассива).Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператор перехода goto L в ПОЛИЗе можно записать какp!где «!» — операция выбора элемента ПОЛИЗа, номер которого равен p.Немного сложнее окажется запись в ПОЛИЗе условных операторов и операторовцикла.Например, если рассматривать оператор if B then S1 else S2 как обычную трехместнуюоперацию с операндами B, S1, S2, то ПОЛИЗ такого оператора должен выглядеть примернотак: B′ S1′ S2′ if, где B′ — ПОЛИЗ условия, S1′ S2′ — ПОЛИЗ операторов S1, S2, if — обозначение условной операции.

Но тогда при интерпретации ПОЛИЗа обе ветви S1, S2 заранее вычисляются, независимо от условия B, что не соответствует семантике условного оператора.Для корректной реализации в ПОЛИЗе управляющих конструкций if, while и т. п., их сначалазаменяют эквивалентными фрагментами при помощи операторов перехода. Введем вспомогательную операцию — условный переход «по лжи» с семантикойif (!B) goto LЭто двухместная операция с операндами B и L.

Обозначим ее !F, тогда в ПОЛИЗе онабудет записана какB′ p !F,где p — номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L,B′ — ПОЛИЗ логического выражения В.Семантика условного оператораif Е then S1 else S2с использованием введенной операции может быть описана так:if (! Е) goto L2; S1; goto L3; L2: S2; L3: ...Тогда ПОЛИЗ условного оператора будет таким (порядок операндов — прежний!):Е′ p2 !F S1′ p3 ! S2′ ...,где pi — номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой Li,i  2,3, Е′ — ПОЛИЗ логического выражения Е.

Заметим, что расположение внутренних84Элементы теории трансляции / Генерация внутреннего представления программконструкций — условия Е и операторов S1 , S2 — относительно друг друга не изменилось.Это обязательное требование к ПОЛИЗу управляющих конструкций.Семантика оператора цикла 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) в ПОЛИЗе будет записан как Е′ write, где Е′ — ПОЛИЗвыражения Е.Постфиксная польская запись операторов обладает всеми свойствами, характернымидля постфиксной польской записи выражений, поэтому алгоритм интерпретации выраженийпригоден для интерпретации всей программы, записанной в ПОЛИЗе (нужно только расширить набор операций; кроме того, выполнение некоторых из них не будет давать результата,записываемого в стек).Постфиксная польская запись может использоваться не только для интерпретациипромежуточной программы, но и для генерации по ней объектной программы.

Для этого валгоритме интерпретации вместо выполнения операции нужно генерировать соответствующие команды объектной программы.Синтаксически управляемый переводНа практике синтаксический, семантический анализ и генерация внутреннего представления программы часто осуществляются одновременно.Существует несколько способов построения промежуточной программы. Один из них,называемый синтаксически управляемым переводом, особенно прост и эффективен.В основе синтаксически управляемого перевода лежит уже известная нам грамматикас действиями (см. раздел о контроле контекстных условий).

Теперь, параллельно с анализомисходной цепочки лексем, будем выполнять действия по генерации внутреннего представления программы. Для этого дополним грамматику вызовами соответствующих процедур генерации.Содержательный пример — генерация внутреннего представления программы для Мязыка — приведен ниже, а здесь в качестве иллюстрации рассмотрим более простой пример.Пусть есть грамматика, описывающая простейшее арифметическое выражение.Gexpr:E → T {T }T → F {F }F →a | b | (E)Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой.85Элементы теории трансляции / Генерация внутреннего представления программGexpr_polish:E → T {T  cout  ''; }T → F {F  cout  '';  }F → a  cout  'a';  | b  cout  'b';  | (E)В процессе анализа методом рекурсивного спуска входной цепочки a  b  с по грамматике Gexpr_polish в выходной поток будет выведена цепочка a b с  , являющаяся польскойзаписью исходной цепочки.

Таким образом, данная грамматика с действиями каждой цепочке языка арифметических выражений ставит в соответствие подходящую цепочку языкапольских записей арифметических выражений. Иными словами, такая грамматика задаетперевод из одного формального языка в другой.Определение: Пусть T1 и T2 — алфавиты. Формальный перевод  — это подмноже**ство множества всевозможных пар цепочек в алфавитах T1 и T2:   (T1  T2 ).Назовем входным языком перевода  язык Lвх()  { |  : (,  )  }.Назовем целевым (или выходным) языком перевода  язык Lц()  { |  : (, )  }.**Перевод  неоднозначен, если для некоторых   T1 , ,   T2 ,   , (, )   и(, )  .Рассмотренная выше грамматика Gexpr_polish задает однозначный перевод: каждому выражению ставится в соответствие единственная польская запись.

Неоднозначные переводымогут быть интересны при изучении моделей естественных языков; для трансляции языковпрограммирования используются однозначные переводы.Заметим, что для двух заданных языков L1 и L2 существует бесконечно много формальных переводов25). Чтобы задать перевод из L1 в L2, важно точно указать закон соответствия между цепочками L1 и L2.n mm nПример. Пусть L1  {0 1 | n  0, m  0} — входной язык, L2  {a b | n  0, m  0} —выходной язык и перевод  определяется так: для любых n  0, m  0 цепочкеn mm n0 1  L1 соответствует цепочка a b  L2.

Можно записать  с помощью теоретикоn m m nмножественной формулы:  { (0 1 , a b ) | n  0, m  0 }, Lвх ()  L1, Lц ()  L2 .Задача.n mm nРеализовать перевод  { (0 1 , a b ) | n  0, m  0} грамматикой с действиями.РешениеЯзык L1 можно описать грамматикой:S → 0S | 1AA → 1A | n mВставим действия по переводу цепочек вида 0 1 в соответствующие цепочки видаm na b :SA25)→ 0S cout  'b'; | 1 cout  'a'; A→ 1 cout  'a'; A | При условии, что хотя бы один из языков L1, L2 бесконечен. Действительно, пусть L1  {a | n  0},L2  {b, c}. Существует бесконечно много переводов i  {(ai, b)}  {(an, c) | n  i, i  0}, гдеnLвх(i)  L1, Lц(i)  L2.86Элементы теории трансляции / Генерация внутреннего представления программТеперь при анализе методом рекурсивного спуска цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.Генератор внутреннего представления программы на М-языкеКаждый элемент в ПОЛИЗе — это лексема, т.

е. пара вида  тип_лексемы, значение_лексемы . При генерации ПОЛИЗа будем использовать дополнительные типы лексем(для внутреннего представления операторов): POLIZ_GO — «!»; POLIZ_FGO — «!F»; POLIZ_LABEL — для ссылок на номера элементов ПОЛИЗа; POLIZ_ADDRESS — для обозначения операндов-адресов (например, в ПОЛИЗеоператора присваивания).Будем считать, что генерируемая программа размещается в объекте progPoliz, заданном описанием:классаPoliz prog (1000);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";elsereturn p[index];};void print(){for ( int I = 0; i < free; ++i )cout << p[i];};};87Элементы теории трансляции / Генерация внутреннего представления программОбъект prog для хранения внутреннего представления программы разместим в открытой части класса Parser:class Parser{Lex curr_lex;...public:Polizprog;Parser (const char *program ) : scan (program),prog (1000) {}voidanalyze();};Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерацииможно использовать информацию, собранную синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно воспользоваться содержимымстека, с которым работает семантический анализатор.

Кроме того, можно дополнить функции семантического анализа действиями по генерации.Добавим в конец тела функции check_op( ) оператор prog.put_lex (Lex (op) ); записывающий в ПОЛИЗ знак операции op, а в конец функции check_not( ) добавим операторprog.put_lex (Lex (LEX_NOT) ); записывающий лексему not (во внутреннем представлении) вПОЛИЗ.Тогда грамматика, содержащая действия по контролю контекстных условий и переводу выражений модельного языка в ПОЛИЗ, будет такой:EE1TF→ E1 | E1 [  |  |  ]  st_lex.push (c_type )  E1  check_op ( ) → T { [  |  | or ]  st_lex.push (c_type )  T  check_op ( )  }→ F { [  | / | and ]  st_lex.push (c_type )  F  check_op ( )  }→ 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 ) ); При генерации ПОЛИЗа выражений и оператора присваивания элементы объекта progзаполнялисьпоследовательно.Семантикаусловногооператораif E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода «по лжи» в момент генерации операций еще неизвестны:if (!E) goto l2; S1; goto l3; l2: S2; l3 :…88Элементы теории трансляции / Генерация внутреннего представления программПоэтому придется оставлять соответствующие этим операндам элементы объектаprog незаполненными и запоминать их номера, а затем, когда станут известны их значения,заполнять пропущенное.Тогда грамматика, содержащая действия по контролю контекстных условий и переводу условного оператора модельного языка в ПОЛИЗ, будет такой: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 S описывается так:L0: if (!E) goto l1; S; goto l0; l1: ...,а грамматика с действиями по контролю контекстных условий и переводу оператора цикла вПОЛИЗ будет такой:S → while  pl0  prog.get_free ( ); 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); ЗамечаниеПеременные pli (i  0, 1, 2, 3) должны быть локализованы в процедуре S, иначе возникнет ошибкапри обработке вложенных операторов.Наконец, запишем соответствующие действия для операторов ввода и вывода: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) ); Интерпретатор ПОЛИЗа для модельного языкаПольская инверсная запись была выбрана нами в качестве языка внутреннего представления программы, в частности, потому, что записанная таким образом программа можетбыть легко проинтерпретирована.Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо; если встречаемоперанд, то записываем его в стек; если встретили знак операции, то извлекаем из стеканужное количество операндов и выполняем операцию, результат (если он есть) заносим встек и т.

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

Список файлов книги