В состояниях, у которых действия не определены, действует правило умолчания. Согласно формальной модели , действие по умолчанию в конечных автоматах является чтение очередного символа из последовательности. Это действие действует во всех состояниях.
2.3.2 Задача: преобразовать в обратную польскую запись заданное простое выражение. Простое выражение задается следующей грамматикой в форме Бэкуса – Наура. (см. 1.7.1)
При разработке проекта данной задачи в терминах конечных автоматов использовалась смешанная методика, то есть действия в этом проекте выполняются, как в состояниях, так и на переходах рис.7.
Таблица приоритетов
|
символы |
* |
+ |
( на входе |
( в стеке |
) |
# |
|
приоритет |
2 |
1 |
3 |
0 |
0 |
0 |
 |
|||
 |
|||
3. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
3.1 Выполнение программ
3.1.1 Схемы программ
Одним из методов изучения программ является метод формализации программ.
Если выделить в программе два оператора О1 и О2 , а отношения между ними обозначить R, то в формуле О1RО2 можно выделить два типа отношений:
1) отношения по передачи управления;
2) отношения по передачи информации.
Расчленение программы на операторы, действующие над памятью, и рассмотрение системы управляющих и информационных связей между операторами - это наиболее общие черты существующих формализмов в теории программировании.
Если исключим из программы отношения по передачи информации и абстрагируемся от конкретных действий выполняемых в программе, то мы перейдём к понятию, которое в теоретическом программирование, называется схемой программы. Для этого все действия в программе мы будем обозначать буквами латинского алфавита (f, h, p, r), множество входных данных обозначим через - X, а множество результатов - через Y.
Графическое представление схемы программы называется блок - схемой.
3.1.2 Блок - схемы программ
Блок - схема - это направленный граф, который указывает порядок выполнения программы. Каждый оператор программы представляют как узел графа, размеченный буквами латинского алфавита, а каждое возможное направление передачи управления - как направленная дуга.
Если узел блок - схемы имеет один вход и один выход, его называют функциональным узлом. Такой узел обозначается прямоугольником, при этом функция, указываемая в прямоугольнике, можеть быть оператором присваивания:
Если узел блок - схемы имеет один вход и два выхода и является чистым оператором управления(не меняет состояния памыти), его называют предикатным узлом. Ромб, обозначающий такой узел, содержит имя предиката p:
Предикатный узел определяет порядок выполнения программы в соответствии с тем, какое значение принимает предикат - истина или ложь, и никаких действий над данными не оказывает. Условимся, что если в дальнейшем метки И ( истина) и Л (ложь) около предикатного узла будут отсутствовать, линия, размеченная символом И, будет находится всегда выше, чем линия, размеченная символом Л.
Узел с двумя входами и одним выходом будем называть узлом слияния. На схеме такой узел будем обозначать кружком и если это необходимо размечать целыми числами. Узел слияния никаких действий над данными не оказывает:
Узел с произвольным количеством входов рис.1 можно изобразить в виде последовательности узлов слияния рис.2.
Блок – схема, построенная по таким правилам приведена на рис.3:
рис
3.
3.1.3 Простые программы.
Простая программа - это программа с управляющей структурой, обладающей следующими особенностями: 1) имеется только один вход и один выход и 2) через каждый узел проходит путь от входа к выходу структуры.
Второе свойство определяет недопустимость управляющих структур, которые содержат либо недостижимые узлы, либо бесконечные циклы.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.