Next:5.14 Автоматная диаграмма
Up:5 Выбор представления данных
Previous:5.12 Система дорог

5.13 Грамматика

грамматика ::=  нетерминал пробел {нетерминал пробел}* правила
нетерминал ::= буква
правила ::= правило пробел {правило пробел}*
правило ::= буква: цепочка{| цепочка}*
цепочка ::= {элемент-текста}*
элемент-текста ::= {любое множество литер, не содержащее пробел и символы ';' и '|'}
 

В этом представлении можно условиться, что начальный нетерминал записывается первым.
Абстрактный тип ГРАММАТИКА со следующим набором операций:

НачНетерминал(ГРАММАТИКА):Нетерминал;
ПервЦепочка(Нетерминал):Цепочка;
СледЦепочка(Цепочка):Цепочка;
ПервСимвол(Цепочка):Символ;
СледСимвол(Символ):Символ;
Терминал(Символ):Boolean;

Кроме того, для решения некоторых задач понадобятся еще процедуры удаления и добавления новых правил, процедуры создания и изменения слов. В качестве в н у т р е н н е г о представления слов на языке Zonnon рекомендуется использовать либо массивы:

const N=100;  (* Максимальная длина цепочки *)
type Цепочка=array N of Char;

либо списки символов:

object { public, ref } Цепочка;
var { public }  Голова:Char;
        Хвост: Цепочка
end Цепочка;

Если известно, что суммарная длина всех цепочек в правых частях правил ограничена некоторой константой M, то можно хранить все цепочки в одном массиве

type ЦЕПОЧКИ=array M of Char; Цепочка=object Начало, Длина : integer end;
object { public, value } Цепочка;
var { public }  Начало, Длина : integer
end Цепочка;

При таком представлении цепочка является пустой, если значение поля X. Начало равно 0, и состоит из символов, находящихся в элементах массива с номерами

X .Начало, X .Начало+1,..., X .Начало+X.Длина-1,

если цепочка не пуста. Таким образом, на языке Zonnon можно взять следующую реализацию грамматики:

object { public, ref } Узел;
var { public }
    Элемент:Цепочка;
    След: Узел
end Узел;
object { public, ref } Грамматика;
var { public }
    НачНетерминал: Char;
    Правила: array 33 of Цепочка
end Грамматика; 

При таком представлении, все правила грамматики с одинаковой левой частью представляются в виде списка цепочек, ссылка на первый элемент которого храниться в элементе массива Правила с индексом integer(X)-integer('A'), где X - нетерминал, стоящий в левой части. Если же некоторая буква X не является нетерминалом грамматики, то в элементе массива Правила c индексом integer(X)-integer('A') хранится Nil.

Next:5.14 Автоматная диаграмма
Up:5 Выбор представления данных
Previous:5.12 Система дорог