Графовая форма стандартной схемы
Представим стандартную схему программ как размеченный граф, вершинам которого приписаны операторы из некоторого базиса В.
Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:
1. Начальная вершина (ровно одна) помечена начальным оператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.
2. Заключительная вершина (может быть несколько). Помечена заключительным оператором. Из нее не выходит ни одной дуги.
3. Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.
4. Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).
5. Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.
Конечное множество переменных схемы S составляют ее память ХS.
Из определения следует, что один и тот же оператор может помечать несколько вершин схемы.
Вершины именуются (метки вершины) целым неотрицательным числом(0, 1, 2,...). Начальная вершина всегда помечается меткой 0.
Схема S называется правильной, если на каждой дуге заданы все переменные.
Пример правильной ССП S 1 в графовой форме приведен на рисунке 1.3, а.
Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины.
Дата добавления: 2015-12-20; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!