Теория и реализация языков программирования

         

в качестве значений рациональные числа


символ N имеет атрибут "значение", принимающий в качестве значений рациональные числа и обозначаемый v(N).
Эти атрибуты можно определить следующим образом:

Таблица 1.1.
Синтаксические правила Семантические правила
B
0
v(B) = 0
B
1
v(B) = 2s(B)
L
B
v(L) = v(B), s(B) = s(L), l(L) = 1
L1
L2B
v(L1) = v(L2) + v(B), s(B) = s(L1), s(L2) = s(L1) + 1, l(L1) = l(L2) + 1
N
L
v(N) = v(L); s(L) = 0
N
L1.L2
v(N) = v(L1) + v(L2), s(L1) = 0, s(L2) = -l(L2)

Здесь при записи семантических правил принято следующее соглашение. Правая часть каждого правила представляет собой определение левой части, таким образом, s(B) = s(L) означает, что сначала должно быть вычислено s(L), а затем полученное значение следует присвоить s(B).
Важным свойством грамматики (таблица 1.1) является то, что некоторые из атрибутов, которым присваиваются значения, приписаны нетерминалам, стоящим в правой части соответствующего синтаксического правила, в то время как в 1.3 атрибуты левых частей семантических правил относились только к нетерминалам, стоящим в левой части синтаксического правила. Здесь мы используем как синтезированные атрибуты (вычисляемые через атрибуты потомков данного нетерминала), так и унаследованные атрибуты (вычисляемые через атрибуты предков). Синтезированные атрибуты вычисляются в древовидной структуре снизу вверх, а унаследованные - сверху вниз. Грамматика (таблица 1.1) включает синтезированные атрибуты v(B), v(L), l(L), v(N) и унаследованные атрибуты s(B) и s(L), так что при их вычислении необходимо проходить по дереву в обоих направлениях. Вычисление на структуре, соответствующей цепочке 1101.01, имеет вид:

Рис. 1.6. 
Можно заметить, что атрибуты "длина" символов L, стоящих справа от точки, должны быть вычислены снизу вверх до того, как будут вычислены (сверху вниз) атрибуты "масштаб" и атрибуты "значение" (снизу вверх).
Грамматика (таблица 1.1), вероятно, не является "наилучшей возможной" грамматикой для системы двоичной записи, но похоже, что она лучше согласуется с нашей интуицией, чем грамматика (пример 1.3). (Грамматика, которая более точно соответствует нашему традиционному толкованию двоичной нотации, содержит другое множество правил вывода.

Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий