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

         

что нам нужно дать точное


Допустим, что нам нужно дать точное определение двоичной системы записи чисел. Это можно сделать многими способами. В данном разделе мы рассмотрим метод, который может быть использован и для других систем счисления. В случае двоичной системы этот метод сводится к определению, основанному на следующей констекстно-свободной (КС) грамматике.
B
0 B
1 L
B L
LB N
L N
L.L
Пример 1.1.
(html, txt)
Здесь терминальными символами являются ".", "0" и "1", нетерминальными - B, L и N, обозначающие соответственно бит, список битов и число. Двоичным числом будем считать любую цепочку терминальных символов, выводимую из N при помощи правил (пример 1.1). Эта грамматика в действительности выражает тот факт, что двоичное число представляет собой последовательность из одного или более нулей и единиц, за которой может следовать точка и еще одна последовательность нулей и единиц. Кроме того, грамматика приписывает каждому двоичному числу определенную древовидную структуру. Например, цепочка 1101.01 получает следующую структуру:

Рис. 1.2. 
Естественно определять значение двоичной записи (пример 1.1) с помощью некоторого пошагового процесса, сопоставленного ее структуре (рис. 1.2); значение всей двоичной записи строится из значений отдельных частей. Это можно сделать, приписав каждому нетерминалу атрибуты следующим образом:
бит B имеет целочисленный атрибут "значение", обозначаемый v(B).
список битов L имеет целочисленный атрибут "длина", обозначаемый l(L).
список битов L имеет целочисленный атрибут "значение", обозначаемый v(L).
число N имеет атрибут "значение", являющийся рациональным числом и обозначаемый v(N).
(Заметим, что у всех нетерминалов L по два атрибута; вообще говоря, каждому нетерминалу можно приписывать любое желаемое число атрибутов).
Грамматику (пример 1.1) можно теперь расширить так, чтобы каждому синтаксическому правилу отвечали семантические правила.
B
0 v(B) = 0 B
1 v(B) = 1 L
B v(L) = v(B); l(L) = 1 L1
L2B v(L1) = 2v(L2) + v(B); l(L1) = l(L2) + 1 N
L v(N) = v(L) N
L1:L2 v(N) = v(L1) + v(L2)=2l(L2)

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







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