Атрибутная грамматика: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Атрибутная грамматика''' (''Attribute grammar'') - состоит из ''КС-грамматики'' <math>G</math...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
'''Атрибутная грамматика''' (''Attribute grammar'') - состоит из ''КС-грамматики'' <math>G</math>,
'''Атрибутная грамматика''' (''[[Attribute grammar]]'') состоит из [[КС-Грамматика|''КС-грамматики'']] <math>G</math>, называемой ее ''основой'' (или [[база|''базой'']]), отображений
называемой ее ''основой'' (или ''базой''), отображений
<math>S</math> и <math>I</math>, ставящих в соответствие каждому символу <math>X</math>
<math>S</math> и <math>I</math>, ставящих в соответствие каждому символу <math>X</math>
непересекающиеся множества <math>S(X)</math> и <math>I(X)</math> его {\it
непересекающиеся множества <math>S(X)</math> и <math>I(X)</math> его синтезируемых и ''наследуемых'' атрибутов, а также из
синтезируемых} и ''наследуемых'' атрибутов, а также из
множеств <math>M(p)</math> так называемых ''семантических правил''
множеств <math>M(p)</math> так называемых ''семантических правил''
(правил вычисления значений атрибутов) для каждого правила
(правил вычисления значений атрибутов) для каждого правила
Строка 9: Строка 7:




Пусть <math>p:X_0\longrightarrow X_1X_2\ldots X_{n<p>}</math> ---
Пусть <math>p:X_0\longrightarrow X_1X_2\ldots X_{n<p>}</math>
некоторое правило грамматики <math>G</math>. Говорят, что имеется
некоторое правило [[грамматика|грамматики]] <math>G</math>. Говорят, что имеется
вхождение атрибута <math>a</math> при <math>j</math>-м символе <math>X_j</math> правила <math>p</math>
вхождение атрибута <math>a</math> при <math>j</math>-м символе <math>X_j</math> правила <math>p</math>
(обозначается <math>a<j></math>), если <math>a\in A(X_j)=I(X_j)\cup S(X_j)</math>.
(обозначается <math>a<j></math>), если <math>a\in A(X_j)=I(X_j)\cup S(X_j)</math>.
Строка 22: Строка 20:
<math>a_0<i_0>=f^{p}_{a_0<i_0>} (a_1<i_1>,\ldots , a_{k}<i_{k}>),</math>
<math>a_0<i_0>=f^{p}_{a_0<i_0>} (a_1<i_1>,\ldots , a_{k}<i_{k}>),</math>


\noindent где либо <math>i_0=0</math> и <math>a_0\in S(X_0)</math>, либо <math>1\leq
 
где либо <math>i_0=0</math> и <math>a_0\in S(X_0)</math>, либо <math>1\leq
i_0\leq n<p></math> и <math>a_0\in I(X_{i_0})</math>.
i_0\leq n<p></math> и <math>a_0\in I(X_{i_0})</math>.


Строка 39: Строка 38:
определении <math>a<i></math>.
определении <math>a<i></math>.


''Граф локальной зависимости'' в продукции <math>p</math> --- это граф
''[[Граф]] локальной зависимости'' в продукции <math>p</math> это граф
отношения <math>D(p)</math>  на множестве <math>W(p)</math>.
отношения <math>D(p)</math>  на множестве <math>W(p)</math>.


Строка 52: Строка 51:
семантических определений, если <math>D(p)</math> является ациклическим.
семантических определений, если <math>D(p)</math> является ациклическим.


См. также ''Атрибутное дерево, Атрибутное вычисление,
==См. также==
Задача трансляции.''
 
==Литература==
* ''[[Атрибутное дерево]],''
[Евстигнеев-Касьянов/98]
* ''[[Атрибутное вычисление]],''
* ''[[Задача трансляции]].''
==Литература==  
 
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

Текущая версия от 16:17, 18 ноября 2010

Атрибутная грамматика (Attribute grammar) — состоит из КС-грамматики [math]\displaystyle{ G }[/math], называемой ее основой (или базой), отображений [math]\displaystyle{ S }[/math] и [math]\displaystyle{ I }[/math], ставящих в соответствие каждому символу [math]\displaystyle{ X }[/math] непересекающиеся множества [math]\displaystyle{ S(X) }[/math] и [math]\displaystyle{ I(X) }[/math] его синтезируемых и наследуемых атрибутов, а также из множеств [math]\displaystyle{ M(p) }[/math] так называемых семантических правил (правил вычисления значений атрибутов) для каждого правила [math]\displaystyle{ p\in P }[/math].


Пусть [math]\displaystyle{ p:X_0\longrightarrow X_1X_2\ldots X_{n\lt p\gt } }[/math] — некоторое правило грамматики [math]\displaystyle{ G }[/math]. Говорят, что имеется вхождение атрибута [math]\displaystyle{ a }[/math] при [math]\displaystyle{ j }[/math]-м символе [math]\displaystyle{ X_j }[/math] правила [math]\displaystyle{ p }[/math] (обозначается [math]\displaystyle{ a\lt j\gt }[/math]), если [math]\displaystyle{ a\in A(X_j)=I(X_j)\cup S(X_j) }[/math]. Для [math]\displaystyle{ a\lt j\gt }[/math] иногда используются также обозначения [math]\displaystyle{ X_j.a }[/math] и [math]\displaystyle{ a^{X_j} }[/math]. Множество [math]\displaystyle{ M(p) }[/math] состоит из семантических правил, определяющих вычисление элементов из [math]\displaystyle{ S(X_0) }[/math] и [math]\displaystyle{ I(X_j) }[/math] для [math]\displaystyle{ j\in [1,n\lt p\gt ] }[/math] в терминах элементов [math]\displaystyle{ A(X_i), 0\leq i\leq n\lt p\gt }[/math], и имеющих вид


[math]\displaystyle{ a_0\lt i_0\gt =f^{p}_{a_0\lt i_0\gt } (a_1\lt i_1\gt ,\ldots , a_{k}\lt i_{k}\gt ), }[/math]


где либо [math]\displaystyle{ i_0=0 }[/math] и [math]\displaystyle{ a_0\in S(X_0) }[/math], либо [math]\displaystyle{ 1\leq i_0\leq n\lt p\gt }[/math] и [math]\displaystyle{ a_0\in I(X_{i_0}) }[/math].

Если [math]\displaystyle{ M(p) }[/math] содержит семантическое правило, определяющее вычисление [math]\displaystyle{ a_0\lt i_0\gt }[/math] по [math]\displaystyle{ a_1\lt i_1\gt ,\ldots , a_k\lt i_k\gt }[/math], то говорят, что [math]\displaystyle{ a_0\lt i_0\gt }[/math] локально зависит от [math]\displaystyle{ a_1\lt i_1\gt }[/math],[math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ a_k\lt i_k\gt }[/math]. В частном случае [math]\displaystyle{ k }[/math] может быть равно нулю, и тогда говорят, что атрибут [math]\displaystyle{ a_0\lt i_0\gt }[/math] получает в качестве значения константу.

Пусть [math]\displaystyle{ W(p) }[/math] обозначает множество вхождений атрибутов в правило [math]\displaystyle{ p }[/math], т.е. [math]\displaystyle{ W(p)=\{ a\lt i\gt :a\in A(X_i), 0\leq i\leq n\lt p\gt \} }[/math]. Таким образом, семантические правила из [math]\displaystyle{ M(p) }[/math] индуцируют на [math]\displaystyle{ W(p) }[/math] отношение локальной зависимости [math]\displaystyle{ D(p) }[/math] такое, что [math]\displaystyle{ b\lt j\gt D(p)a\lt i\gt }[/math] тогда и только тогда, когда [math]\displaystyle{ b\lt j\gt }[/math] появляется в определении [math]\displaystyle{ a\lt i\gt }[/math].

Граф локальной зависимости в продукции [math]\displaystyle{ p }[/math] — это граф отношения [math]\displaystyle{ D(p) }[/math] на множестве [math]\displaystyle{ W(p) }[/math].

Атрибутная грамматика является грамматикой в нормальной форме (или нормализованной), если ее семантические правила определяют вычисления атрибутов из [math]\displaystyle{ W(p) }[/math] по атрибутам из [math]\displaystyle{ I(X_0) }[/math] и [math]\displaystyle{ S(X_j) }[/math] для [math]\displaystyle{ 1\leq j\leq n\lt p\gt }[/math], т.е. они используют только атрибуты, определенные вне продукции [math]\displaystyle{ p }[/math]. Всякая атрибутная грамматика может быть преобразована в нормальную форму посредством простого преобразования семантических определений, если [math]\displaystyle{ D(p) }[/math] является ациклическим.

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.