Архитектура и семантика элементов Си-графов

Для иллюстрации семантики элементов Си-графов и архитектуры Си-графов в целом как средства графической визуализации Си-программ рассмотрим следующие примеры.

Пример 2.1. Неразветвляющийся алгоритм, Си–программа которого задана Текстом 1.1 (см. лабораторную работу №5), а соответствующий этой программе Си-граф показан на Рис. 2.1.

Для заданной Си-программы Си-граф определяется как конструкция G = G (P, S, W), представляющая собой ориентированный граф и включающая следующие элементы:

· множество Р входных вершин Р_j (j = 0, 1, 2,...) с перенумерованными выходами, не имеющих входных стрелок и отображающих декларированные в Си-программе имена исходных данных, имена данных – результатов, имена констант, а также задаваемые входным интерфейсом проектируемого устройства имена входов данных (например, а_in, b_in и т.п.);

· множество P внутренних вершин P_j с перенумерованными входами и выходами, соответствующих операциям/функциям языка Си, представленным в теле программы, при этом P = F È L, где F - множество функциональных вершин, L - множество вершин условной/безусловной передачи управления; в последующем они могут обозначаться как вершины типа f (function) и вершины типа с (control) соответственно;

· множество Р выходных вершин Р_j с перенумерованными входами (0, 1,...), не имеющих выходных стрелок и интерпретирующих интерфейсные выходы (вывода результатов выполнения программы) проектируемого устройства (они обозначаются в последующем именем данного с добавкой _out (например, s_out, z_out и т.п.));

· сопряженное S и внешнее W множества и стрелок S_j и W_j соответственно, соединяющих часть (или все) вершины и отражающих определенные в Си-программе сопряженные и внешние связи операций/функций по данным, связи по условному и безусловному управлению, а также вспомогательные (например, осведомительные связи); все связи могут отмечаться типами передаваемых данных/типами операторов условного или безусловного управления.

Примерами операций/функций языка Си, интерпретируемых f -вершинами, являются арифметические операторы (типов +, -, *, /, %), операторы отношения и логические операторы (типов >, > =, <, < = и ==,! =), инкрементные и декрементные операторы (типов ++, --), побитовые операторы (типов &, |, ^, < <, > >,...), операторы присваивания и чтения (=, *) и т.п. В качестве примеров операторов условной и безусловной передачи управления, интерпретируемых с -вершинами, назовем операторы if, switch, goto, continue, break, return.

Как видно, введенное понятие Си-графа определяет графическое представление Си-программы с детализацией до вершин, интерпретирующих данные, операции/функции Си-программы, а также входы и выходы, предписанные внешними интерфейсами. Применительно к данному уровню детализации будем говорить об операционных Си-графах.

Следующий пример поясняет рассмотренные выше понятия для случая разветвляющегося алгоритма.

Пример 2.2. Разветвляющийся алгоритм, Си–программа которого задана Текстом 1.2 (см. лабораторную работу №1), а соответствующий этой программе Си-граф показан на Рис. 2.2а и Рис. 2.2б.

При автоматическом проектировании параллельных алгоритмов целесообразно использовать, помимо операционных Си-графов, также Си-графы более высокого уровня, обеспечивающие представление Си-программ на уровне их Фрагментов (Естественных Частей, ЕЧ) Си-программ.

Пусть задан Си-граф G = G (P, S, W, В), соответствующий разветвляющемуся алгоритму, представленному Си-программой с Текстом 1.2. Определим фрагмент Си-графа как любой из его подграфов FG_i (i = 0, 1, 2,..., kf -1; kf – количество фрагментов), удовлетворяющих следующим условиям:

· входной фрагмент (ЕЧ) FG_in: этоподграф FG, в качестве входных вершин которого выступают входные вершины Си-графа G; выходной вершиной может быть одна из вершин типа bp, upl, bpv графа G, интерпретирующих безусловную передачу управления, условную передачу управления и передачу управления с возвратом (для циклов) соответственно; внутренние вершины подграфа представляют функциональные операторы P_j соответствующей неразветвляющейся части Си-программы;

· выходной фрагмент (ЕЧ) FG_out: этоподграф FG, в качестве выходной вершины которого выступает вершина типа stop, отображающая оператор Stop (закрывающую скобку функции main) Си-программы; входной вершиной подграфа может быть одна из вершин функционального типа, интерпретирующая функциональный оператор P_i, управление на который передается от одного или нескольких выходных операторов типов bp, upl, bpv, continue, return, break других фрагментов; внутренние вершины подграфа представляют функциональные операторы P_j соответствующей неразветвляющейся части Си-программы;

· внутренний фрагмент (ЕЧ) FG_loc: этоподграф FG, в качестве входной вершины которого может быть одна из вершин функционального типа, интерпретирующая функциональный оператор P_i соответствующей неразветвляющейся части Си-программы, управление на который передается от одного или нескольких выходных операторов типов bp, upl, bpv, continue, return, break других фрагментов;

выходной вершиной может быть одна из вершин типа bp, upl, bpv, cont, ret, brk графа G, интерпретирующих операции типов goto, if, continue, return, break Си-программы; внутренние вершины подграфа представляют функциональные операторы P_j соответствующей неразветвляющейся части Си-программы.

Определим Си-граф ЕЧ FG (FO, FC), соответствующий заданному Си-графу G (P, S, W, В), как ориентированный граф в котором:

а) FO = { FG_i }, (i = 0, 1,..., kf -1, где kf – количество фрагментов в операционном Си-графе) – множество вершин, интерпретирующих фрагменты (естественные части) Си-программы;

б) FC = { FC_μ }, (μ = 0, 1,..., cf -1, где cf – количество управляющих связей между фрагментами операционного Си-графа) - множество связей по управлению между вершинами-фрагментами FG -графа.

Для иллюстрации введенных понятий и представления фрагментных Си-графов в целом как средства графической визуализации схемы управления в Си-программе, в Тексте 2.1 представлена исходная разветвляющаяся Си–программа (см. Текст 1.2) с выделенными естественными частями, и соответствующий этой программе Си-граф ЕЧ FG (Рис.2.3).

#include < stdio.h>

void main(void)

{

int x, k, s;

scanf(" %d %d %d", & a, & b, & c);

x = a * b;

if(x < 0)

k = x + c;

}

Текст 2.1 - Исходная разветвляющаяся Си-программа с выделенными ЕЧ

Как видно из сказанного, аппарат Си-графов обеспечивает визуализацию Си-программ алгоритмов на двух уровнях:

· операционный уровень -операционныйСи-граф G (P, S, W), характеризующийся детализацией до данных и операций/функций языка Си и связей между ними по данным и управлению;

· уровень естественных частей – Си-граф ЕЧ FG (FO, FC), характеризующийся детализацией до вершин, соответствующих естественным частям Си-программы, и связями естественных частей программы по управлению.

Содержание отчета

а) Титульный лист.

б) Распечатка исходного текста Си-программы.

в) Распечатка спецификации Си-программы в формате СЧС(файлы БФ, ФС).

г) Выводы по результатам выполненной работы: вывод о практической возможности автоматического синтеза формата СВМ для Си-программы; вывод о логической эквивалентности/ неэквивалентности формата СВМ и исходной Си-программы.