В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 24
Текст из файла (страница 24)
. Xn . Атрибутная грамматика AG сопоставляет каждому правилу p из P конечное множество R(p)семантических правил видаa(Xi ) = f (b(Xj ), c(Xk ), . . . , d(Xm )),где 0 6 j , k , . . . , m 6 n, причем 1 6 i 6 n, если a(Xi ) ∈ AI (Xi ) (т. е. a(Xi ) —наследуемый атрибут), и i = 0, если a(Xi ) ∈ AS (Xi ) (т. е. a(Xi ) — синтезируемый атрибут).Таким образом, семантическое правило определяет значение атрибута aсимвола Xi на основе значений атрибутов b, c, .
. ., d символов Xj , Xk , . . .,Xm соответственно.В частном случае длина n правой части правила может быть равна нулю;тогда будем говорить, что атрибут a символа Xi получает в качестве значенияконстанту.В дальнейшем будем считать, что атрибутная грамматика не содержитсемантических правил для вычисления атрибутов терминальных символов.Предполагается, что атрибуты терминальных символов — либо предопределенные константы, либо доступны как результат работы лексического анализатора.Пример 5.5. Рассмотрим атрибутную грамматику, позволяющую вычислить значение вещественного числа, представленного в десятичной записи. Здесь N == {N um, Int, F rac}, T = {digit, .}, S = N um, а правила вывода и семантическиеправила определяются следующим образом (верхние индексы используются дляссылки на разные вхождения одного и того же нетерминала):N um → Int .
F rac v(N um) = v(Int) + v(F rac);p(F rac) = 1;Int → eInt1 → digit Int2F rac → ev(Int) = 0;p(Int) = 0;2v(Int1 ) = v(digit) ∗ 10p(Int ) + v(Int2 );12p(Int ) = p(Int ) + 1;v(F rac) = 0;1F rac1 → digitF rac2 v(F rac1 )= v(digit) ∗ 10−p(F rac ) + v(F rac2 );p(F rac2 )= p(F rac1 ) + 1;Для этой грамматикиAS (N um) = {v},AS (Int) = {v , p},AS (F rac) = {v},AI (N um) = ∅;AI (Int) = ∅;AI (F rac) = {p}.5.3. Атрибутные грамматики119Пусть даны атрибутная грамматика AG и цепочка, принадлежащая языку,определяемому соответствующей G = (N , T , P , S). Сопоставим этой цепочке«значение» следующим образом.
Построим дерево разбора T этой цепочкив грамматике G. Каждый внутренний узел этого дерева помечается нетерминалом X0 , соответствующим применению p-го правила грамматики; такимобразом, у этого узла будет n непосредственных потомков (рис. 5.2).Рис. 5.2Пусть теперь X — метка некоторого узла дерева и пусть a — атрибутсимвола X . Если a — синтезируемый атрибут, то X = X0 для некоторогоp ∈ P ; если же a — наследуемый атрибут, то X = Xj для некоторых p ∈ Pи 1 6 j 6 n. В обоих случаях дерево вблизи этого узла имеет вид, приведенный на рис. 5.2. По определению, атрибут a имеет в этом узле значение v ,если в соответствующем семантическом правилеa(Xi ) = f (b(Xj ), c(Xk ), .
. . , d(Xm ))все атрибуты b, c, . . ., d уже определены и имеют в узлах с метками Xj ,Xk , . . ., Xm значения vj , vk , . . ., vm соответственно, а v = f (v1 , v2 , . . . , vm ).Процесс вычисления атрибутов на дереве продолжается до тех пор, покаможно вычислить хотя бы один атрибут. Вычисленные в результате атрибутыкорня дерева представляют собой «значение», соответствующее данному дереву вывода.Заметим, что значение синтезируемого атрибута символа в узле синтаксического дерева вычисляется по атрибутам символов в потомках этогоузла; значение наследуемого атрибута вычисляется по атрибутам «родителя»и «соседей».Атрибуты, сопоставленные вхождениям символов в дерево разбора, будемназывать вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами — атрибутированным деревом разбора.Пример 5.6. Атрибутированное дерево для грамматики из предыдущего примераи цепочки w = 12,34 показано на рис.
5.3.Будем говорить, что семантические правила заданы корректно, еслиони позволяют вычислить все атрибуты произвольного узла в любом деревевывода.Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующими120Глава 5. Элементы теории переводаРис. 5.3примененным синтаксическим правилам. Эти зависимости могут бытьпредставлены в виде ориентированного графа следующим образом.Пусть T — дерево разбора. Сопоставим этому дереву ориентированныйграф D(T ), узлами которого являются пары (n, a), где n — узел дерева T , a— атрибут символа, служащего меткой узла n. Граф содержит дугу из (n1 , a1 )в (n2 , a2 ) тогда и только тогда, когда семантическое правило, вычисляющееатрибут a2 , непосредственно использует значение атрибута a1 . Таким образом,узлами графа D(T ) являются атрибуты, которые нужно вычислить, а дугиопределяют зависимости, подразумевающие, какие атрибуты вычисляютсяраньше, а какие позже.Пример 5.7.
Граф зависимостей атрибутов для дерева разбора из предыдущегопримера показан на рис. 5.4.Можно показать, что семантические правила корректны тогда и толькотогда, когда для любого дерева вывода T соответствующий граф D(T ) не содержит циклов (т. е. является ориентированным ациклическим графом).Рис. 5.45.3. Атрибутные грамматики1215.3.2. Классы атрибутных грамматик и их реализация.
В общем видереализация вычислителей для атрибутных грамматик вызывает значительныетрудности. Это связано с тем, что множество значений атрибутов, связанныхс данным деревом, приходится вычислять в соответствии с зависимостямиатрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая егок тому или иному способу обхода дерева. Рассматривают многовизитные,многопроходные и другие атрибутные вычислители. Это, как правило, ведетк ограничению допустимых зависимостей между атрибутами, поддерживаемых вычислителем.Простейшими подклассами атрибутных грамматик, для которых вычисление всех атрибутов может быть осуществлено одновременно с синтаксическиманализом, являются S-атрибутные и L-атрибутные грамматики.Определение 5.4.
Атрибутная грамматика называется S-атрибутной, если она содержит только синтезируемые атрибуты.Нетрудно видеть, что для S-атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дерева снизу-вверх.Таким образом, можно вычислять атрибуты параллельно с восходящим синтаксическим анализом, например, LR(1)-анализом.Пример 5.8. Рассмотрим S-атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ.
Здесь атрибут v имеет строковый тип, k обозначаетоперацию конкатенации. Правила вывода и семантические правила определяютсяследующим образом:E 1 → E 2 + T , v(E 1 ) = v(E 2 ) k v(T ) k ′ + ′ ;E → T,v(E) = v(T );T → T ∗ F,v(T 1 ) = v(T 2 ) k v(F ) k ′ ∗;T → F,v(T ) = v(F );F → id,v(F ) = v(id);F → (E),v(F ) = v(E).Определение 5.5.
Атрибутная грамматика называется L-атрибутной, если любой наследуемый атрибут любого символа Xj из правой части каждогоправила X0 → X1 X2 . . . Xn грамматики зависит только от:1) атрибутов символов X1 , X2 , . . ., Xj−1 , находящихся в правиле слеваот Xj ;2) наследуемых атрибутов символа X0 .122Глава 5. Элементы теории переводаЗаметим, что каждая S-атрибутная грамматика является L-атрибутной.Все атрибуты на любом дереве для L-атрибутной грамматики могут бытьвычислены за один обход дерева сверху-вниз слева-направо.
Таким образом,вычисление атрибутов можно осуществлять параллельно с нисходящим синтаксическим анализом, например, LL(1)-анализом или рекурсивным спуском.В случае рекурсивного спуска в каждой функции, соответствующейнетерминалу, надо определить формальные параметры, передаваемые по значению, для наследуемых атрибутов, и формальные параметры, передаваемыепо ссылке, для синтезируемых атрибутов.
В качестве примера рассмотримреализацию атрибутной грамматики из примера 5.5 (нетрудно видеть, чтограмматика является L-атрибутной). Классы FloatRef и IntRef введены дляреализации передачи параметра по ссылке. Предполагается, что в переменнойInSym хранится десятичное значение выбранной цифры.class FloatRef {float val;}class IntRef {int ref;}void int_part(FloatRef V0, IntRef P0){if (Map[InSym]==Digit){ int I=InSym;FloatRef V2;IntRef P2;InSym=getInSym();int_part(V2,P2);V0.val=I*exp(P2.val*ln(10))+V2.val;P0.val=P2.val+1;}else {V0.val=0;P0.val=0;}}void fract_part(FloatRef V0, IntRef P0){if (Map[InSym]==Digit){ int I=InSym;FloatRef V2;int P2=P0+1;InSym=getInSym();fract_part(V2,P2);V0.val=I*exp(-P0.val*ln(10))+V2.val;}else {V0.val=0;}}void number(){ FloatRef V1,V3;5.3. Атрибутные грамматики123float V0;IntRef P;int_part(V1,P);if (InSym!=’.’) error();fract_part(V3,1);V0=V1.val+V3.val;}5.3.3.
Язык описания атрибутных грамматик. Формализм атрибутных грамматик оказался очень удобным средством для описания семантикиязыков программирования. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большимитрудностями. В связи с этим было сделано множество попыток рассматриватьте или иные классы атрибутных грамматик, обладающих «хорошими» свойствами. К числу таких свойств относятся прежде всего простота алгоритмапроверки атрибутной грамматики на зацикленность и простота алгоритмавычисления атрибутов для атрибутных грамматик данного класса.Атрибутные грамматики использовались для описания семантики языковпрограммирования, и было создано несколько систем автоматизации разработки трансляторов, основанных на формализме атрибутных грамматик.
Опытих использования показал, что «чистый» атрибутный формализм может бытьуспешно применен для описания семантики языка, но его использованиевызывает трудности при создании транслятора. Эти трудности связаны какс самим формализмом, так и с некоторыми технологическими проблемами.К трудностям первого рода можно отнести несоответствие между чистофункциональной природой атрибутного вычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степениявляется преимуществом этого формализма), с одной стороны, и упорядоченностью элементов программы — с другой. Это несоответствие ведет к тому,что приходится идти на искусственные приемы для их сочетания.
Технологические трудности связаны с эффективностью трансляторов, полученныхс помощью атрибутных систем. Как правило, качество таких трансляторовдовольно низко из-за больших расходов памяти и неэффективности вышеупомянутых искусственных приемов.Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка программирования, в котором предполагается наличие операторов, а значит, и возможностьуправления порядком их исполнения. Этот порядок может быть привязанк обходу атрибутированного дерева разбора сверху-вниз слева-направо. Чтокасается грамматики входного языка, то мы не будем предполагать принадлежность ее определенному классу (например, LL(1) или LR(1)).
Будемсчитать, что дерево разбора входной программы уже построено как результат124Глава 5. Элементы теории переводасинтаксического анализа и что атрибутные вычисления осуществляются в результате обхода этого дерева. Таким образом, входная грамматика атрибутного вычислителя может быть даже неоднозначной, что не влияет на процессатрибутных вычислений.При записи синтаксиса мы будем использовать расширенную БНФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
