В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 14
Текст из файла (страница 14)
Нетрудно видеть, что существуетпоследовательность шагов вывода(E, E) ⇒ (T, T ) ⇒ (T ∗ F, T F ∗) ⇒ (F ∗ F, F F ∗) ⇒ (id ∗ F, id F ∗) ⇒ (id ∗(E), id E∗) ⇒ (id ∗ (E + T ), id E T + ∗) ⇒ (id ∗ (T + T ), id T T + ∗) ⇒ (id ∗ (F +T ), id F T + ∗) ⇒ (id ∗ (id + T ), id id T + ∗) ⇒ (id ∗ (id + F ), id id F + ∗ ) ⇒ (id ∗(id + id), id id id + ∗),переводящая эту цепочку в цепочку id id id + ∗.Рассмотрим связь между переводами, определяемыми СУ-схемами иосуществляемыми МП-преобразователями [2].Теорема 5.1.
Пусть P – МП-преобразователь. Существует такая простая СУ-схема T r, что τ (T r) = τ (P ).Теорема 5.2. Пусть T r – простая СУ-схема. Существует такой МПпреобразователь P, что τ (P ) = τ (T r).Таким образом, класс переводов, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов.Рассмотрим теперь связь между СУ-переводами и детерминированными МП-преобразователями, выполняющими нисходящий или восходящий разбор [2].Теорема 5.3. Пусть T r = (N, T, Π, R, S) – простая СУ-схема, входнойграмматикой которой служит LL(1)-грамматика. Тогда перевод{x$, y)|(x, y) ∈ τ (T r)} можно осуществить детерминированным МПпреобразователем.Существуют простые СУ-схемы, имеющие в качестве входных грамматик LR(1)-грамматики и не реализуемые ни на каком ДМП-преобразователе.Пример 5.3. Рассмотрим простую СУ-схему с правиламиS → Sa,S → Sb,S → e,aSabSbeВходная грамматика является LR(1)-грамматикой, но не существует ДМПпреобразователя, определяющего перевод {(x$, y)|(x, y) ∈ τ (T r)}.5.2.
СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД85Назовем СУ-схему T r = (N, T, Π, R, S) постфиксной, если каждоеправило из R имеет вид A → u, v, где v ∈ N ∗ Π∗ . Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, закоторыми следует цепочка выходных символов.Теорема 5.4. Пусть T r – простая постфиксная СУ-схема, входная грамматика для которой является LR(1). Тогда перевод{(x$, y)|(x, y) ∈ τ (T r)}можно осуществить детерминированным МП-преобразователем.5.2.2Обобщенные схемы синтаксически управляемого переводаРасширим определение СУ-схемы, с тем чтобы выполнять более широкий класс переводов.
Во-первых, позволим иметь в каждой вершине дерева разбора несколько переводов. Как и в обычной СУ-схеме, каждыйперевод зависит от прямых потомков соответствующей вершины дерева. Во-вторых, позволим элементам перевода быть произвольными цепочками выходных символов и символов, представляющих переводы впотомках. Таким образом, символы перевода могут повторяться или вообще отсутствовать.Определение.
Обобщенной схемой синтаксически управляемого перевода (или трансляции, сокращенно: OСУ-схемой) называется шестерка T r = (N, T, Π, Γ, R, S), где все символы имеют тот же смысл, что идля СУ-схемы, за исключением того, что(1) Γ – конечное множество символов перевода вида Ai , где A ∈ N и i –целое число;(2) R – конечное множество правил перевода видаA → u, A1 = v1 , ... , Am = vm ,удовлетворяющих следующим условиям:(а) Aj ∈ Γ для 1 6 j 6 m,(б) каждый символ, входящий в v1 , . . .
, vm , либо принадлежит Π,либо является Bk ∈ Γ, где B входит в u,(в) если u имеет более одного вхождения символа B, то каждыйсимвол Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B.A → u называют входным правилом вывода, Ai – переводом нетерминала A, Ai = vi – элементом перевода, связанным с этим правилом перевода. Если в ОСУ-схеме нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной.86ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАВыход ОСУ-схемы определим снизу вверх.
С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai . Эта цепочка называется значением(или переводом) символа Ai в вершине n. Каждое значение вычисляетсяподстановкой значений символов перевода данного элемента переводаAi = vi , определенных в прямых потомках вершины n.Переводом τ (T r), определяемым ОСУ-схемой T r, назовем множество{(x, y) | x имеет дерево разбора во входной грамматике для T r и y – значение выделенного символа перевода Sk в корне этого дерева}.Пример 5.4. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x, функции sin и cos , а также операции ∗и +. Такие выражения порождает грамматикаE →E+T |TT →T ∗F |FF → (E) | sin (E) | cos (E) | x | 0 | 1Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2.
Индекс 1 указывает на то, что выражение не дифференцировано, 2 – что выражение продифференцировано. Формальная производная – это E2 . Законы дифференцирования таковы:d(f (x) + g(x)) = df (x) + dg(x)d(f (x) ∗ g(x)) = f (x) ∗ dg(x) + g(x) ∗ df (x)d sin (f (x)) = cos (f (x)) ∗ df (x)d cos (f (x)) = − sin (f (x))df (x)dx = 1d0 = 0d1 = 0Эти законы можно реализовать следующей ОСУ-схемой:5.3. АТРИБУТНЫЕ ГРАММАТИКИE → E +TE1 = E1 + T1E2 = E2 + T2E→TE1 = T1E2 = T2T →T ∗FT1 = T1 ∗ F1T2 = T1 ∗ F2 + T2 ∗ F1T →FT1 = F1T2 = F2F → (E)F1 = (E1 )F2 = (E2 )F → sin (E)F1 = sin (E1 )F2 = cos (E1 ) ∗ (E2 )F → cos (E)F1 = cos (E1 )F2 = − sin (E1 ) ∗ (E2 )F →xF1 = xF2 = 1F →0F1 = 0F2 = 0F →1F1 = 1F2 = 087Дерево вывода для sin (cos (x)) + x приведено на рис. 5.1.5.3Атрибутные грамматикиСреди всех формальных методов описания языков программированияатрибутные грамматики (введенные Кнутом [6]) получили, по-видимому,наибольшую известность и распространение.
Причиной этого являетсято, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов.5.3.1Определение атрибутных грамматикАтрибутной грамматикой называется четверка AG = (G, AS , AI , R),где(1) G = (N, T, P, S) – приведенная КС-грамматика;ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА88( VLQFRV[[( FRVFRV[VLQ[(( VLQFRV[( FRVFRV[VLQ[ (77 [7 7 VLQFRV[7 FRVFRV[VLQ[ 7)) VLQFRV[) FRVFRV[VLQ[ )) [) [VLQFRV (( FRV[( VLQ[77 FRV[7 VLQ[)) FRV[) VLQ[(77 [7 )) [) [Рис.
5.1:( [( 5.3. АТРИБУТНЫЕ ГРАММАТИКИ89(2) AS – конечное множество синтезируемых атрибутов;(3) AI – конечное множество наследуемых атрибутов, AS ∩ AI = ∅;(4) R – конечное множество семантических правил.Атрибутная грамматика AG сопоставляет каждому символу X из N ∪ Tмножество AS (X) синтезируемых атрибутов и множество AI (X) наследуемых атрибутов. Множество всех синтезируемых атрибутов всех символов из N ∪ T обозначается AS , наследуемых – AI . Атрибуты разныхсимволов являются различными атрибутами.
Будем обозначать атрибут a символа X как a(X). Значения атрибутов могут быть произвольных типов, например, представлять собой числа, строки, адреса памятии т.д.Пусть правило p из P имеет вид X0 → X1 X2 ... 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, а правила вывода и семантическиеправила определяются следующим образом (верхние индексы используются дляссылки на разные вхождения одного и того же нетерминала):ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА90N um → Int . F racv(N um) = v(Int) + v(F rac)p(F rac) = 1Int → ev(Int) = 0p(Int) = 0Int1 → digit Int2v(Int1 ) = v(digit) ∗ 10p(Intp(Int1 ) = p(Int2 ) + 1F rac → ev(F rac) = 0F rac1 → digit F rac2v(F rac1 ) = v(digit) ∗ 10−p(F racp(F rac2 ) = p(F rac1 ) + 12)+ v(Int2 )1)+ v(F rac2 )Для этой грамматикиAS (N um) = {v},AS (Int) = {v, p},AS (F rac) = {v},AI (N um) = ∅,AI (Int) = ∅,AI (F rac) = {p}.Пусть дана атрибутная грамматика AG и цепочка, принадлежащаяязыку, определяемому соответствующей G = (N, T, P, S). Сопоставимэтой цепочке “значение” следующим образом.
Построим дерево разбораT этой цепочки в грамматике G. Каждый внутренний узел этого деревапомечается нетерминалом X0 , соответствующим применению p-го правила грамматики; таким образом, у этого узла будет n непосредственных потомков (рис. 5.2).;;; ;QРис. 5.2:Пусть теперь X – метка некоторого узла дерева и пусть a – атрибутсимвола X. Если a – синтезируемый атрибут, то X = X0 для некоторогоp ∈ P ; если же a – наследуемый атрибут, то X = Xj для некоторых p ∈ Pи 1 6 j 6 n. В обоих случаях дерево “в районе” этого узла имеет вид,приведенный на рис. 5.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
