Карпов - Основы построения трансляторов (2005) (943926), страница 19
Текст из файла (страница 19)
3.16. Таблица 3.16. Вычисление входной цепочки дас-'гЮКе/~~ Ие:= Стек Остаток входной Выполняемая Примечание цепочки операция символ >йОКе~ — д Ие:= 3 д, а, с - - в стек Три однотипных шага д, а, с а'ОКет — д Ие:= 3 Выполнение х~ .'=а> с; х1 — в стек сравнения; х~ я (ТМИНЕ, ГАЗАКЕ~ ~ ОКе~ — а Ие:= 3 3дх, Ы вЂ” в стек Здх~д ОК х. тх~ОК4 х~ — В стек е/ — а Ие:= 3 Выполнение операции; х. е ~ТК~ЮЕ ГА$8Е е,~ — в стек Два однотипных шага --а Ие:= 3 а Йе:=3 х- те —,~ ) ,У Ф х, — в стек 3дх..л; а — в стек 3 дх2 хз ч Ие Х4 .'= ПЕ(Х2, Х, Д); х4 — в стек По адресу д записы- вается значение х4 Д +-Л4 Стек пуст; результат записан по адресу д 10 Вычисления закончены Итак, по арифметическому выражению ~и даже фрагменту программного ко- да), приведенному в форму ПОЛИЗ, выполнение вычислений с помощью стека очень просто. Однако, как перевести арифметическое выражение в ПОЛ ИЗ? Существуют различные алгоритмы такого преобразования.
Мы рассмотрим алгоритм, основанный на синтаксически-ориентированной трансляции. Действительно, исходное множество объектов для такого алгоритма — множество цепочек, результаты — тоже цепочки символов. Поэтому можно считать Очередной входной Выполнение операции Запись в стек й1е~х„хз, су) = если х..
истинно, то х;, в противном случае искомый алгоритм транслятором„который осуществляет преобразование выражения в ПОЛИЗ на основе структуры входных цепочек. Для построения транслятора, переводящего арифметические выражения в ПОЛИЗ. построим атрибутную грамматику арифметических выражений. Синтаксические правила грамматики построены — это грамматика Ь'|,. Для просторны будем рассматривать выражения только с операциями двух типов — операцией типа сложения оп~с и более приоритетной операцией типа умножения оп~у. С~"~,-.
'Š— ~Ео~псТ~ Т Т вЂ” ~ТотуР ~ РР— и'~ (Е) Как построить семантические правила? Нашей целью является формирование постфиксной формы выражения. Обозначим р постфиксную форь~у выражения, т. е. пусть р — семантический атрибут, приписанный нетерминалам Е, Ти Р. Если структура некоторого фрагмента выражения Ео есть Е~оисТ, например, то его постфиксная форма Ео р может быть построена как конкатенация пары постфиксных форм, составляющих этот фрагмен~ подвыражений, за которым следует знак операции. т.
е. Ео.р=Е1.р Т.р о~ос. Эти простые соображения приводят к следующей атрибутной грамматике арифметических выражений, целью которой является трансляция выражений в ПОЛИЗ (табл. 3. 1 7). Рассмотрим преобразование в 1 ОЛИЗ выражения а+Ьх(с — д)+~е — ф Будем считать, что дерево вывода этой цепочки построено синтаксическим анализатором, и стоит задача вычисления ПОЛИЗ этого выражения по дереву его вывода в атрибутной грамматике табл. 3.17. Такое аннотированное дерево представлено на рис.
3.20. Таблица 3.17. Атрибутная грамматика для трансляции арифметических выражений в ПОЛИЗ Структура и значение Рис. 3.20. Построение ПОЛИЗ арифметического выражения по дереву вывода Заметим, что определение и вычисление семантических атрибутов никак не связано с предположениями о том, в каком порядке строится дерево вывода: предполагается, что дерево вывода уже построено, и уже имея полное построенное синтаксическое дерево, мы можем начать вычисление семантических атрибутов.
В реальной трансляции, однако, возникают проблемы с хранением и многократными обходами огромной структуры дерева вывода для больших программ при таком вычислении семантических атрибутов. Во многих случаях можно так определить семантические атрибуты и дополнительные операторы, что их можно подсчитывать одновременно с построением дерева, и хранения всего дерева не нужно. Например, если дерево вывода строится снизу вверх и в качестве семантических атрибутов определены только синтезированные атрибуты, то каждый раз, как происходит свертка правой части продукции к нетерминалу — ее левой части, вычисляются атрибуты левой части продукции по значениям атрибутов символов правой части, и дерева вывода хранить не нужно.
При этом„конечно, определение семантики должно учи гывать способ построения дерева вывода. Рассмотрим на примере, как упрощается трансляция при учете способа построения дерева вывода. Пусть известно. что дерево вывода арифметического выражения строится снизу вверх, выполняя свертку подстроки к соответствующему нетерминалу при просмотре строки слева направо. В этом случае для задачи перевода арифметического выражения в ПОЛИЗ достаточна следующая семантика (табл.
3.18). Глава 3 Таблица 3.18. Перевод арифметического выражения в ПОЛИЗ Рассмотрим преобразование в ПОЛИЗ выражения а+Ах(с — д). На дереве вывода этой цепочки впишем определенные в таблице семантические действия — вывод операндов и операций для 1, 3 и 6 правил грамматики, соответственно. Выполнение этих действий в порядке, определенном порядком построения дерева вывода снизу вверх (т. е.
при обходе дерева в следующем порядке: потомки слева направо, затем узел дерева), даст на выходе программы трансляции искомую цепочку абсид-х+ (рис. 3.21). Рис. 3.21. Генерация ПОЛИЗ арифметического выражения по дереву вывода 3.5.3. Интерпретация арифметических выражений Построение транслятора, интерпретирующего арифметические выражения, также удобно осуществить на основе атрибутной грамматики. Целью интерпретатора является формирование по любому арифметическому выражению Глава 3 Рис. 3.22.
Интерпретация арифметического выражения по его дереву вывода ление может иметь различные формы; часто для этого используют постфиксную нотацию, трехадресный код либо так называемый р-код ~читается "пикод"). Два последних представления можно понимать как коды ассемблера для нскоторых виртуальных машин, предоставленных в распоряжение программиста. С этих кодов может легко быть проведена трансляция в ассемблер любой машины. Мы рассмотрим здесь компиляцию арифметических выражений в р-код для стековой машины.
Выполнение программы, представленной в р-коде, обычно основано на интерпретации этого кода. Будем считать, что соответствующая виртуальная стековая машина имеет обычную память данных, память для программы и стек. Для наших целей достаточны следующие команды стековой машины ~табл.
3.20). Таблица 3.20. Команды стековой машины Структура и значение 127 Таблица 3.20 (окончание) М0Ь То же для деления Атрибутная грамматика арифметических выражений, транслирующая выра- жения в р-код, чрезвычайно проста (табл. 3.21). В этой таблице отсо обозна- чает+, а оис1 обозначает —, ои~уо обозначает х, а оиу1 обозначаеет /. Арифметическое выражение а+ох(с — И)+е будет оттранслировано так, как показано на рис. 3.23. При построении дерева вывода снизу вверх последовательное выполнение семантических правил, связанных с каждым синтаксическим правилом в дереве вывода, изменяет глобальный атрибут — генерируемую программу— так, что в результате трансляции на выходе будет сгенерирована искомая программа. Для цепочки а+Ох(с — с/)+е последовательность выполнения семантических правил, определяемая построением дерева снизу вверх, даст следующую программу: ЬВ а 1.0 Ь 10 с 1.В И ЯЗВ МШ АВВ Безадресная операция: два операнда выбираются из стека, их произведение записывается в стек Т а бл и ц а 3.
21. Атрибутная грамматика для трансляции арифметических выражений в р-код Глава 3 128 1.0 е АИЭ Здесь предполагается, что адреса операндов в памяти мнемонически совпа- дают с их именами. Рис. 3.23. Генерация р-кода по дереву вывода 3.5.5. Символьное дифференцирование Символьное дифференцирование, или задача построения производной заданной функции, является классической проблемой математического анализа.
Подчеркнем еще раз, что определенные так семантические правила будут корректны только при условии определенного порядка их выполнения, который автоматически порождается при построении синтаксического дерева снизу вверх. Более точно, определенная выше семантика будет корректной, если для трансляции арифметических выражений использовать (любой) восходящий метод синтаксического анализа, и при каждой свертке найденной подстроки к левой части соответствующего синтаксического правила выполнять связанное с этим правилом семантическое действие. Заметим, что при таком подходе построенную часть синтаксического дерева хранить не нужно — она уже была использована в момент ее построения для цели трансляции — выполнения семантических действий.
Поэтому обычно трансляция происходит без фактического построения дерева вывода. Структура и значение Поскольку построение производной есть задача преобразования цепочек, то можно попробовать решить ее на основе синтаксически-ориентированной трансляции. Этот подход, при котором в обрабатываемой цепочке восстанавливается ее структура, и правила преобразования цепочки определяются для структурных единиц в соответствии с их строением, оказывается естественным и удобным при решении этой трудной проблемы математического анализа. Записи функций, для которых строится производная — это обычные цепочки арифметических выражений, дополненные правилами порождения функциональных записей и разделяющие явно переменные и константы.
Пусть грамматика арифметических выражений имеет вид: 6~,. Š— ~Е+Т~ Т Т вЂ” +ТхР ~ РР— +Ял(Е) ~ Соя(Е) ~ х ~ С ~ (Е) Построение производной функции производится на основе правил„которые определены в математическом анализе: лроизводпая суя.цы есин сулжа протводных, производная коиспнти~ы есть ноль, и т. д.