Карпов - Основы построения трансляторов (2005) (943926), страница 18
Текст из файла (страница 18)
3.18). Рис. 3.18. "Желаемая" структура дерева вывода цепочки с+~+!хгхг+Ы: Более приоритетная операция 'х' должна выполняться до того, как ее результат будет использоваться в вычислениях. Можно догадаться, что для того. чтобы дерево вывода имело желаемую структуру, в искомой грамматике группы операндов, связанные операцией 'х', должны порождаться из нетерминала Т так же, как в грамматике б~; порождается сам операнд ~. Иными 1 словами, нетерминал Тдолжен играть роль начального символа грамматики, порождающей цепочки операндов, связанных операцией 'х'.
Точно так же, как в б~, из начального символа Е порождались цепочки операндов, связан- 1 ных операцией '*', с выполнением операций слева направо, в искомой грамматике из Т должны порождаться цепочки операндов, связанных операцией 'х'. Значит, необходимо ввести дополнительный нетерминал (назовем его Г). Искомая грамматика будет иметь вид: О~~,. à — +Е+Т ~ Т Т-+ТхГ ~ Г Р' — и' В этой грамматике дерево вывода цепочки г+г+юхЫ+~хг будет иметь следующий вид (рис. 3.19). Очевидно, что простая семантика с использованием только синтезированных атрибутов дает правильные вычисления значения любого арифметического выражения в этой грамматике. Если мы добавим еще один уровень приоритета операций, а именно возведение в степень, то, конечно, нетерминал Е должен быть начальным символом грамматики, порождающей фрагменты арифметического выражения, состоящие из операндов и знаков возведения в степень.
Пусть этот знак '1'. Глава 3 Рис. ЗЛ9. Дерево вывода цепочки в искомой грамматике Грамматика: Š— +Р ~Р ~ РР— и из начального символа Г порождает цепочки вида РР~1г, причем вычисление значения выра>кения при естественном определении семантики будет левоассоциативным — выполняться слева направо, т. е. 21314 будет пониматься как (2 ) или же 2 " . Но в некоторых языках программирования операция возведения в степень считается правоассоциативной, т. е. вычисление цепочки 213Т4 желательно понимать как (2 ) .
Чтобы достичь этого при естествен- з~ ном определении семантики, нужно просто немного изменить грамматику в этой части: à — эРТГ~ РР— эк Возможность использования скобок в арифметическом выражении можно учесть следующим образом. Любое арифметическое выра>кение, взятое в скобки, должно рассматриваться как операнд на следующих этапах вычислений вверх по дереву вывода. Поэтому полную грамматику арифметических вычислений можно представить следующим образом: б~,.
Š— эЕ+Т~ Š— Т~ Т ТэТХУГ ~ У7У ~ à à — +РТЕ~ Р Р-и ~(Е) Определим атрибутную грамматику для вычисления значения выражения (табл. 3.12). Структура и значение Таблица 3.12. Атрибутная грамматика арифметических выражений Введенные дополнительные нетерминалы имеют 'традиционные названия: Т вЂ” <терм>, à — <фактор>, Р— <первичное> или <рпп1агу>. Именно так традиционно представляется грамматика арифметических выражений и семантика ее продукций в современных языках программирования.
Отметим, что грамматика б'~, имеет следующие свойства: Г3 она задает язык арифметических выражений, т. е. порождает все правиль- ные выражения и ни одного неправильного; О она является недвусмысленной, т. е. каждой цепочке языка сопоставляет только одно дерево вывода; З она позволяет определить естественную простую атрибутную семантику с использованием только синтезированных атрибутов, определяющую стандартный порядок вычисления значения выражения с учетом приоритетов операций и вычисления операций с одинаковым приоритетом слева направо, а операций возведения в степень — справа палево; П при необходимости порядок вычисления в выражении можно регулиро- вать, используя скобки.
Следует отметить, однако, что этот "стандартный" порядок вычислений используется не всегда. В языке АПЛ-ЗбО, который в ~ХС82~ авторы называют "мощным средством, способствующим более четкой организации мышления", принят другой порядок вычислений арифметических выражений— а именно все операции выполняются в АПЛ-360 справа налево без учета при- Глава 3 оритетов. Такое отступление от общепринятой схемы авторы языка объясняют тем, что этот язык имеет много операторов, которые используются в выражениях, и введение приоритетов могло бы внести путаницу в понимание порядка вычисления значений.
Кроме того, по мнению авторов языка АПЛ-360, такой порядок удобен для "размышления одновременно с записью". Например, если вы хотите вычислить годовой доход при заработке, составляющем в месяц 2000 рублей за вычетом подоходного налога (13%) и спецналога (1%), то можно написать: 3+ — 12х2000х1 — %13+1.
Это можно прочитать как: зарплата будепг начисляться 12 месяцев, каждый месяц по 2000 рублей, за вычетом ~в процени~ах) 13 как подоходного налога и 1 — как спецналога". Вычисление этого выражения должно проводиться справа налево без учета приоритетов. В языке АПЛ-360 это выражение записывается без скобок. Очевидно, что в языке Паскаль, например, для правильного вычисления значения это выражение должно содержать, по меньшей мере, три пары скобок: 12х(2000х(1 — 0.01х(13+1))). Конечно, в языке АПЛ-360 для явного определения порядка вычислений можно использовать и скобки.
Определим атрибутную грамматику арифметических выражений в языке АПЛ-360 (табл. 3.13). Таблица 3.13. Атрибутная грамматика арифметических выражений в языке АПЛ-360 Здесь простейшая грамматика и естественная семантика продукций определяют порядок выполнения операций справа налево без учета приоритетов для арифметических выражений, однако с помощью скобок можно определить любой желаемый порядок вычислений.
Структура и значение 3.5.2. Перевод арифметических выражений в ПОЛИЗ Построенная в предыдущем разделе грамматика арифметических выражений может быть использована для решения различных проблем обработки цепочек этого языка. В данном и в последующих разделах этой главы мы покажем, как на основе одной и той же построенной нами порождающей грамматики арифметических выражений могут быть определены атрибутные семантики. позволяющие решить различные проблемы обработки арифметических. выражений. ПОЛИЗ, или Польская инверсная запись, — это специальная бесскобочная форма записи арифметических выражений, удобная для автоматического вычисления.
Другое название этой формы — постфиксная запись, отражающая структуру выражения, при которой знак операции непосредственно следует за своими операндами. В действительности, можно различить три формы записи выражения: инфиксную, при которой знак бинарной операции стоит между операндами (это наша обычная форма, 'а+О'), префиксную — знак операции перед своими операндами '+аЬ', и постфиксную — знак операции после операндов 'аЬ+'. Г1рефиксную форму можно понимать как обычную функциональную запись Яа, о), в которой опущены скобки и знак функции (например.
'+') стоит непосредственно перед операндами, разделенными каким-то разделителем. Аналогично: постфиксная форма — это стилизованная функциональная запись (а, Ь)1. Удобство как префиксной, так и постфиксной форм записи арифметических выражений состоит в том, что они, в отличие от привычной нам инфиксной формы записи, не требуют скобок для определения любого порядка выполнения операций. Очевидно, что операции (функции), используемые здесь, не обязательно бинарные (просто по их виду должна быть ясна арность операции) и, более того, нс обязательно арифметические. Примеры этих форм записи приведены в табл. 3.14 (в этой таблице трехместная функция фйеи-йс(а, о, с), выдающая в качестве результата Ь, если а истинно, а в противном случае выдающая с, обозначена как 'Йе').
Таблица 3.14, Три формы записи выражения 120 Глава 3 Т а б л и ц а 3. 1 4 ~окончание) Префиксная форма была введена в 1925 г. польским логиком Яном Лукасевичем, поэтому ее вариант — постфиксная запись — традиционно называется Польской инверсной записью, или ПОЛИЗ. ПОЛИЗ значительно более удобная форма, чем префиксная запись: простой алгоритм с использованием стека позволяет вычислить значение выражения. А именно, в стек записываются операнды по мере поступления, слева направо, а как только встретится знак операции, из стека выбираются операнды этой операции, операция выполняется, и ее результат снова записывается в стек. В частности, рассмотрим примеры 4 и 5 табл. 3.15.
Значение выражения в этой записи можно вычислить так, как в табл. 3.15. Таблица 3.15. Вычисление значения выражения в записи абсид — х+~е — + Очередной входной Остаток входной Стек Выполняемая операция Примечание символ цепочки ~ Стек пуст. Первый ' символ входной Ьсд — ~+ф — -'3 а -- в стек цепочки — операнд Ь, с, И вЂ” в стек 6, с, И Три однотипных шага — х+/е — + 3 л,:=с — И; х, — в стек Выполнение операции ' — ' х -'~е — +3 Выполнение операции 'х' 3 аЬх~ х~ .'= Ьхх~', х. — в стек ~ Выполнение операции '+' ~е — +3 хз .'= а+х.; хз-- в стек ~ е — в стек Два однотипных шага х4 .'=~ — е; х4 — в стек Выполнение операции '-' Выполнение операции '+' х5 хз х4~ х~ — в стек Результат— в верхушке стека Вычисления закончены Структура и значение Другой пример: входная цепочка вычисляется так, как показано в табл.