И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 15
Текст из файла (страница 15)
Проблем не возникает, если сложные подвыражения явно ограничены скобками. Например, в выражении (a + b) ∗ с левым операндомоперации ∗ является подвыражение a + b, а правым — простое выражение с. Когда скобкиявно не расставлены, как в случаях a + b ∗ с и a − b + c, важно учитывать приоритет операций, а также ассоциативность операций одинакового приоритета. Умножение имеет больший приоритет, чем сложение, поэтому в выражении a + b ∗ c операнд b относится к опера-81Элементы теории трансляции / Генерация внутреннего представления программции умножения и эквивалентное выражение со скобками будет таким: a + (b ∗ c).
В выражении a − b + c операнд b относится к левой операции, т. е. к «минусу», а не к «плюсу» (в силулевой ассоциативности операций + и −, имеющих одинаковый приоритет), и это выражениеэквивалентно выражению (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) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.Пример.
ПОЛИЗом выражения a + b + c является a b + c +, но не a b c + +. Последняязапись является ПОЛИЗом для выражения a + (b + c).Алгоритм Дейкстры перевода в ПОЛИЗ выраженийБудем считать, что ПОЛИЗ выражения будет формироваться в массиве, содержащемлексемы — элементы ПОЛИЗа, и при переводе в ПОЛИЗ будет использоваться вспомогательный стек, также содержащий элементы ПОЛИЗа (операции, имена функций) и круглыескобки.1. Выражение просматривается один раз слева направо.2. Пока есть непрочитанные лексемы входного выражения, выполняем действия:Читаем очередную лексему.Если лексема является числом или переменной, добавляем ее в ПОЛИЗ-массив.Если лексема является символом функции, помещаем ее в стек.Если лексема является разделителем аргументов функции (например, запятая),то до тех пор, пока верхним элементом стека не станет открывающаяся скобка,выталкиваем элементы из стека в ПОЛИЗ-массив.
Если открывающаяся скобкане встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.д) Если лексема является операцией θ, тогда: пока приоритет θ меньше либо равен приоритету операции, находящейся навершине стека (для лево-ассоциативных операций), или приоритет θ строгоменьше приоритета операции, находящейся на вершине стека (для правоассоциативных операций), выталкиваем верхние элементы стека в ПОЛИЗмассив; помещаем операцию θ в стек.е) Если лексема является открывающей скобкой, помещаем ее в стек.а)б)в)г)82Элементы теории трансляции / Генерация внутреннего представления программж) Если лексема является закрывающей скобкой, выталкиваем элементы из стекав ПОЛИЗ-массив до тех пор, пока на вершине стека не окажется открывающаяскобка.
При этом открывающая скобка удаляется из стека, но в ПОЛИЗ-массивне добавляется. Если после этого шага на вершине стека оказывается символфункции, выталкиваем его в ПОЛИЗ-массив. Если в процессе выталкиванияоткрывающей скобки не нашлось и стек пуст, это означает, что в выражении несогласованы скобки.3.
Когда просмотр входного выражения завершен, выталкиваем все оставшиеся в стеке символы в ПОЛИЗ-массив. (В стеке должны были оставаться только символы операций;если это не так, значит в выражении не согласованы скобки.)Например, обычной (инфиксной) записи выраженияa ∗ ( b + c) − (d − e) / fсоответствует такая постфиксная запись:abc+∗de−f/−ЗамечаниеОбратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфиксной записи, учтено старшинство операций, а скобки исчезли.Запись выражения в такой форме очень удобна для последующей интерпретации (т.
е.вычисления значения этого выражения) с помощью стека.Алгоритм вычисления выражений, записанных в ПОЛИЗе1) Выражение просматривается один раз слева направо и для каждого элемента выполняются шаги (2) или (3);2) Если очередной элемент ПОЛИЗа — операнд, то его значение заносится в стек;3) Если очередной элемент ПОЛИЗа — операция, то на верхушке стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;4) Когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент — это значение всего выражения, т.
е. результат вычисления.Замечание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 mm nВставим действия по переводу цепочек вида 0 1 в соответствующие цепочки видаa b :SA25)→ 0S 〈cout << 'b';〉 | 1 〈cout << 'a';〉 A→ 1 〈cout << 'a';〉 A | εnПри условии, что хотя бы один из языков L1, L2 бесконечен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
