Введение в архитектуру компьютеров


Язык диспозиций - часть 2


· имеется, по крайней мере, одна вершина, из которой не исходит ни одна дуга и которой сопоставлен знак #. Эти вершины называются выходами диспозиции и обозначаются aвых1, aвых2, ..., aвыхn;

· вершинам, которые не являются выходами, сопоставлены операторы диспозиции. При этом, если из вершин исходит n дуг, то ей может быть сопоставлен только тот оператор Ai, число выходов которого Pi ³ n. Каждый выход оператора Ai сопоставляется одной из дуг, исходящих из соответствующей вершины a. Каждой дуге, исходящей из a, должен быть сопоставлен, по крайней мере, один из выходов оператора Ai.

Граф Г(D) и соответствующую ему диспозицию D назовем правильными, если выполняются следующие дополнительные требования:

· из любой вершины графа Г существует путь, по крайней мере, в

один выход;

· для каждой вершины графа Г существует путь, ведущий из входа в

эту вершину.

Так определенная диспозиция задает систему допустимых последовательностей преобразований текста, а именно: если задан начальный текст T0, то оператор, сопоставленный входу диспозиции aвх, проверяет условие w0 i; если оно не выполнено (w0 i = 0), то текст T0 не меняется; если же w0 i = 1, то к тексту T0 применяется преобразование, соответствующее данному оператору, причем до выполнения этого преобразования вычисляются значения w1i, w2i, ... wki. После преобразования текста вычисляются значения функций

j1i, j2i, ..., jрii.

Те функции jj, которые принимают значение 1, определяют дуги, исходящие из входной вершины графа диспозиции, по которым возможен переход в следующую вершину. Один из этих переходов должен быть осуществлен. Тем самым на следующем шаге процесса реализации диспозиции выбирается одна из смежных с предыдущей вершина графа Г(D).

Если все функции jj = 0, то процесс останавливается. Эта ситуация называется безрезультатной остановкой.

Оператор диспозиции, сопоставленный этой вершине, применяется к полученному тексту таким же образом, как входной оператор применяется к исходному тексту T0.


Начало  Назад  Вперед



Книжный магазин