Статистические управляемые схемы перевода и атрибутные грамматики.

Формально процесс синтаксического анализа и синтеза объектной программы реализует преобразование синтаксического дерева текста программы на входном языке в текст эквивалентной формы объектной программы. Это преобразование и сложность его программной реализации существенно зависят от выбора объектного языка. Выбор последнего в синтаксически управляемых методах перевода тесно связан не только с синтаксической структурой входного языка, но и ориентирован на неё.

Хорошей теоретической моделью преобразований синтаксического дерева являются простые синтаксически управляемые схемы перевода. Они не учитывают контекстные соотношения в исходной программе, однако позволяют строить синтаксически правильные формы объектных программ. Объектная программа включает в себя понятие программ на объектом языке, семантически эквивалентной исходной программе. Степень адекватности первой программы по отношению ко второй будет зависеть от семантики исходной программы, которая в априори должна быть заложена в семантические процедуры анализа и определять суть семантического анализа и контроля. Обычно при семантическом анализе и контроле ограничиваются проверкой контекстных условий.

В трансляторах интерпретирующего типа проверка некоторых контекстных условий, например, соответствий видов значений, участвующих в операциях часто выполняется при интерпретации объектной программы.

Атрибутные грамматики (А – грамматики) в сочетании с методом синтаксически управляемого перевода позволяют учитывать контекстные условия при отображении синтаксического дерева в объектную программу. Понятие атрибутной трансляционной грамматики (АТ – грамматики), включающие два указанных понятия, будем использовать для построения отображения синтаксического дерева исходной программы в объектную программу.

Понятие атрибутивной трансляционной грамматики (АТ – грамматики), включающие два указанных понятия, будем использовать для построения отображения синтаксического дерева исходной программы в объектную программу.

Определение: КС-грамматика G(V_T,V_N,P,S) называется атрибутной, если выполняются следующие условия:

1) Каждому символу хV_TV_N сопоставлено два непересекающихся множества: множество синтезированных атрибутов А₀ (х) и множество унаследованных атрибутов А₁(х),А₁(S)=к А(х)=хV_T; пусть А(х)=А₀(х)А₁(х)

2) Каждый атрибут αимеет множество значений(возможно, бесконечное)

3) С каждым правилом X₀→ X₁X₂…X_nР,n≥0, связывается множество семантических правил, которые определяются функциями вида:

:xx…x->при ≤i≤n и некоторых αА(x_i), если i=0 или αА₁(x_i), i>0, где t=t(i,α)≥0 и α_j=α_j(i,α)А(X_kj), 0≤k_j=k_j(i,α)≤n,i≤j≤t.

Другими словами функция задаёт правило вычисления значения атрибута α символа х_i по значениям некоторых атрибутов символов X₀,X₁,…,X_n. Атрибутная грамматика связывает атрибуты с вершинами синтаксического дерева вывода. Семантические правила вычисления значений атрибутов, соответствующие правилу КС- грамматики, применяются для всех вхождений этого правила в дерево вывода. Синтезированные атрибуты некоторой вершины хранят информацию, которая синтезируется из поддерева этой вершины и передаётся вверх к корню дерева. Унаследованные атрибуты служат для хранения информации, которая передаётся сверху вниз от корня дерева к его листьям. Фактически унаследованные атрибуты определяют контекст, в котором погружена вершина вместе со своим поддеревом.

Контекстно-зависимые условия входного языка должны выражаться через ряд условий, входящих в семантические правила атрибутной грамматики. Эти условия должны выражать соотношения между значениями атрибутов, которые выполняются в дереве вывода правильной программы.

Описание семантики языка с помощью атрибутных грамматик позволяет определить «смысл» исходной программы, как значение одного или нескольких специальных атрибутов корня синтаксического дерева этой программы, т.к. главной задачей в процессе трансляции является получение объектной, то можно считать, что один из специальных атрибутов корня синтаксического дерева получает значение – последовательности операций абстрактной машины, т.е. объектную программу. Удобным формализмом для построения контекстно-свободной структуры объектной программы по синтаксическому дереву исходной программы является аппаратом простых синтаксически управляемых схем (СУ-схем) перевода.

Определение: Пусть G(V_T,V_N,P,S) – КС грамматика. ∆-множество операционных символов. Каждому правилу A₀→x₁A₁x₂A₂…x_nA_nX_n+1Р, где A_iV_N, x_i+1V_T*,0≤i≤n, будет соответствовать правило A₀→y₁A₁y₂A₂…y_nA_ny_n+1, y_i+1∆*. Простой СУ – схемой называется пятёрка T=(V_T,∆,V_N,R,S), где R – множество пар правил (A₀→x1A1x2A2…A_nx_nx_n+1,A₀→y₁A₁y₂…y_nA_ny_n+1). Обозначим пару таких правил через (A₀→α,A₀→α').

Множество пар терминальных цепочек (х,у)синхронно выводимых из пары цепочек (S,S) с помощью СУ –правил (A₀→α,A₀→α') называется простым синтаксически управляемым переводом.

Простая СУ-схема, является частным случаем атрибутикой грамматики. Если считать, что вторая компонента в каждом СУ-правиле определяет синтаксическое правило для вычисления значения специального синтезируемого атрибута, связанного с нетерминалом, стоящим в левой части этой компоненты.

Каждой синтаксически правильной исходной программе х простой СУ- перевод ставит в соответствие цепочку у из операционных символом, которая определяет некоторую контекстно-свободную форму объектной программы. Например, с помощью просто СУ-схемы легко получить польскую обратную запись различных конструкций входного языка.

Определение: КС-грамматика, у которой множество терминальных символов разбито на множество входных символов V_T и множество операционных символов ∆ называется трансляционной. Предложения языка порождённые трансляционной грамматикой называется активными цепочками.

Реальный транслятор строит не только синтаксическую структуру объектной программы. Вхождениям операционных символов будут соответствовать вызовы семантических процедур.

Определение: Атрибутной трансляционной грамматикой называется трансляционная грамматика с атрибутами и семантическими правилами вычисления значений атрибутов.

Определение:АТ- грамматика называется L-атрибутной, если выполняются следующие условия:

1) Пусть x₀→x₁x₂…x_nP – правило АТ- грамматики, – семантическая функция для вычисления унаследованного атрибута αА_i(x_i) 1≤i≤n. Тогда каждый аргумент - либо атрибут βА₁(x₀), либо произвольный атрибут А(x_j) 1≤j≤n.

2) Пусть - функция для вычисления синтезированного атрибута αА₀(x₀). Тогда каждый аргумент либо атрибут А₁(x₀), либо произвольный атрибут А(x_j), 1≤j≤n.

3) Если X_i – операционный символ и αА₀(x_i), в функции все аргументы представляют собой унаследованный атрибуты этого символа.

Для правила A→BC,например, значения атрибутов можно вычислить в таком порядке:

a. Унаследованные атрибуты символа А;

b. Унаследованные атрибуты В;

c. Синтезированные атрибуты символа В;

d. Унаследованные атрибуты символа С;

e. Синтезированные атрибуты символы С;

f. Синтезированные атрибуты символа А.

Этот порядок соответствует обходу дерева сверху вниз и слева направо. Спускаясь вниз от вершины, вычисляем унаследованные атрибуты, поднимаясь вверх к вершине, вычисляем синтезированные атрибуты.

Операционные символы АТ – грамматики можно интерпретировать как вызовы семантических процедур, которые реализуют соответствующие семантические правила для вычисления (с учётом контекстных условий) специального атрибута <объектная программа>. Очевидно, контекстные условия должны определяться унаследованными атрибутами операционных символов. При передаче значений атрибутов операционные символы употребляются, когда требуется обозначить сложную операцию, связанную с проверкой контекстно-зависимых соотношений для атрибутов и с вычислением их значений.

В случае простой передачи достаточного с нетерминалом в левой части правила грамматики и соответствующим символом в правой части связать одно тоже имя атрибута. Каждое правило L-атрибутной грамматики можно интерпретировать, как описание рекурсивной процедуры, причём нетерминал в левой части правила принимают за имя процедуры, а его атрибуты – за параметры этой процедуры.

Вхождение нетерминалов в правую часть правила вместе с их атрибутами интерпретирующая как вызовы соответствующих процедур с параметрами. Последние замечания имеют значения в связи с возможностью реализации однопроходного транслятора для входного языка.