Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 9

В состояниях, у которых действия не определены, действует правило умолчания. Согласно формальной модели , действие по умолчанию в конечных автоматах является чтение очередного символа из последовательности. Это действие действует во всех состояниях.

2.3.2  Задача: преобразовать в обратную польскую запись заданное простое выражение. Простое выражение задается следующей грамматикой в форме Бэкуса – Наура. (см.  1.7.1)

При разработке проекта данной задачи в терминах конечных автоматов использовалась смешанная методика, то есть действия в этом проекте выполняются, как  в состояниях, так  и на переходах рис.7.

Таблица приоритетов

символы

      *

       +

  (

на входе

(

 в стеке

       )

    #

приоритет

      2

        1

   3

 0

       0

    0


  3.    СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

3.1 Выполнение программ

                3.1.1  Схемы программ

Одним из методов изучения  программ является метод формализации программ.

Если выделить в программе  два оператора О1 и О2 ,  а отношения между ними обозначить R, то в формуле О12  можно выделить два типа отношений:

1) отношения  по передачи управления;

2) отношения по передачи информации.

  Расчленение программы  на операторы, действующие над памятью, и рассмотрение системы управляющих и информационных связей  между операторами - это наиболее общие  черты существующих  формализмов в теории программировании.

Если исключим из программы отношения по передачи информации и абстрагируемся от конкретных действий выполняемых в программе, то мы перейдём к понятию, которое в  теоретическом программирование, называется  схемой программы. Для этого все действия в программе  мы будем обозначать буквами латинского алфавита (f, h, p, r), множество входных данных обозначим через - X, а множество результатов - через Y.

Графическое представление схемы программы называется блок - схемой.

        3.1.2   Блок - схемы программ

 Блок - схема - это направленный граф, который указывает порядок выполнения программы. Каждый оператор программы представляют  как узел графа, размеченный буквами латинского алфавита, а каждое  возможное направление передачи управления - как направленная дуга.

 Если узел блок - схемы имеет один вход и один выход, его называют функциональным узлом. Такой узел обозначается прямоугольником, при этом функция, указываемая  в прямоугольнике, можеть быть оператором присваивания:

 

   Если узел блок - схемы имеет один вход и два  выхода и является чистым  оператором управления(не меняет состояния памыти),  его называют предикатным узлом. Ромб, обозначающий такой узел, содержит имя предиката p:

Предикатный узел определяет порядок выполнения программы в соответствии с  тем, какое значение принимает предикат - истина или ложь, и никаких действий над данными не оказывает. Условимся, что если в  дальнейшем метки И ( истина) и Л (ложь) около предикатного узла будут отсутствовать, линия, размеченная символом И, будет находится всегда выше, чем линия, размеченная символом Л.

 Узел с двумя входами и одним выходом будем называть узлом  слияния. На схеме такой узел  будем обозначать кружком и если это необходимо размечать целыми числами. Узел слияния никаких действий над данными не оказывает:

  

Узел с произвольным количеством входов рис.1 можно изобразить в виде последовательности узлов слияния рис.2.

 Блок – схема, построенная по таким правилам приведена  на рис.3:

рис  3.

3.1.3 Простые программы.

    Простая программа - это программа с управляющей структурой, обладающей следующими особенностями:  1) имеется только один вход  и один выход и 2) через каждый узел проходит путь от входа  к выходу структуры.

Второе свойство определяет недопустимость управляющих структур, которые содержат либо недостижимые узлы, либо бесконечные циклы.