И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 16

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

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

результат вычисления.Замечание1. Для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация обоперандах, хранящаяся в таблицах.2. Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак «» в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции «» возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять.Устранить неоднозначность можно, по крайней мере, двумя способами: заменить унарную операцию бинарной, т.

е. считать, что а означает 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();};Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерацииможно использовать информацию, собранную синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно воспользоваться содержимымстека, с которым работает семантический анализатор.

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

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