1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 50
Текст из файла (страница 50)
Можно убедиться, что структурированная схема Яр,.т аквивалевтна стандартной схеме 8ье ив и. 2.2 гл. 4. Все теоремы о свободных интерпретациях (п. 3.2 гл. 4) сохраняют силу и длн структурированных схем. 1.2. Трансляция струнтурврованшех схем в стандартные. '1' е о р е и а $ОЛ. Власе структурирееанимл сеем трелелируем е велес етеидар~пних сеем. Д о к а а а т е л ъ с т в о. Алгоритм трансляции структурированных схем в стандартные достаточно прост.
Все схемные операторы помечаются иеткамн-числамн в соответствии с порядком ях вхождения в структурированную схему. Условный оператор й: селин те й + $: а, иначе й а, конец, ц~е й + 1 и 1 — метки первых операторов в последовательностях ам ае, ааменяется на последовательность инструкций йт еслв я те й + $ иначе 1, й + Ф: аг па т, 1: аю где т — метка оператора, следующего аа условеым оператором. Кслн а или ае — пустав последовательность, то Й+ $ или, соответственно, 1 должны равнатъся т, а соответствующие последовательности помеченных операторов отсутствуют в стандартной схеме.
Осюратор цикла Й пока к цикл я+ 1: а конец заменяется последователъностъю операторов й еелв я то й + 1 иначе т, й + 1: а па й, где ж — метка оператора, следующего эа оператором цикла. Оператор цикла й: до п цикл й + 1: о конец заменяется последовательностью операторов й если и то т иначе й + 1, й + 1: о ва й, где т — метка оператора, следующего за оператором цикла. Если о — пустая последовательность, то первый оператор цикла заменяется на распознаватель й: если п то й иначе т, а второй на й: ес.зн я то т иначе й. Последовательной заменой всех условных операторов и операторов цикла последовательностями инструкций строится стандартная схема. Содержательный анализ правил замен убеждает, что построенная схема эквивалентна исходной.
Д Стандартная схема Яю,з, эквивалентная структурированной схеме Ям.з. имеет вид (старт (х), 1: у:= 7(х), 2: если р (у) то 7 иначе 3, В: у:= ~(у), 4: есля р (у) то 5 иначе 7, 5: если р (х) те 6 иначе 7, 6: х:= й (х) иа 5, 7: стоп (х, у)). 1.3. Трапслацпк стзадартиых схем в сгруктурвроваивъж. Структурированные программы универсальны в том смысле, что набора предоставленных им программных средств достаточно длв описания любой вычнслимой фувкцпи. Задача автоматического преобразования стандартных схем в структурированные по- разному Формулировалась в резвых работах с привлечением раз- личных определений классов схем и отношений транслируемоств (62, И5, Иб).
В рамках данного нами определения травслируе- мостн ($2 гл. В) и для введенного класса структурированных схем ответ на вопрос о возможности трансляции стандартных схем в структурированные носит отрицательный характер. Т е о р е м а 10.2. Класс стаидаржнпх стем не транслируем о класс ппрукжурированнпх схем. Д о к а э а тел ъ с т в о.
На рис. 10.1 приведен пример стан- дартной схемы Яюл, для которой не существует эквивалентной 23$ структурированной схемы. Предположим противное, в нусть 8— структурированная схема, эквивалентная схеме 8гьв. На основавин содержательного анализа схемы Я е.в можно установить, что эта схема является свободной и в схеме Я должен быть хотя бы один оператор цикла, лоп1ческое выражение которого содержит креднкатвый символ р или д (пусть, для определенности, символ р).
Кроме того, существуют свободные интерпретации, при которых этот оператор выполняется. Зафиксируем такую интерпретацию 1 следующим образом. Полагаем предикат Р = 1 (р) тождественно равным $, а предвкат 9 = 1 (д) выбираем так, чтобы Ч (а) = 1 для всех термов-знастлет<ху чений а, появляющихся при выполнении программы (о, 1) до того момента, когда начнет выполняться оператор цикла с предикатным символом р, н ч (а) =- 0 для всех остальных тернов-значений. Ясно, что программа (о, 1) зацикливается (на ФЩ операторе цвкла с предикатвым о символом р).
В то же время «:-г~«> етое~. > программа (81е-ы 1) останавли- вается после некоторого выпол- Р . $0 т. ста и схема 8 кения распознавателя с пРеЛи~екаертек схем' гмв кат м с лом д, т к как число тернов а, при которых ф (а) = $, конечно, а переменная х получает зсе новые значения, отличные от а. Из того факта, что (8, 1) зацикливается, а (8 е ы 1) останавливается, следует, что предположение о существовании схемы 8, эквивалентной схеме Яюл, было неверным. П Т е о р е м а $0.3.
Класс стандартных схслв строго моивнсв класса структурированных схем. Доказательство. Следствиензтеорем$0Л и 10.2. П Таким образом, структурные ограничения, нрисущне структурированным схемам, уменывают их выразительные возможности, если сохраняется базис класса стандартных схем. В следующем параграфе этот бааис будет расширен, и это изменит свтуацшо. б 2. Структурированные схемы с логвческнмв операциями Второй класс структурированных схем, который рассматривается здесь, обладает ббльшимк возможноствми за счет усложнения логических выраженвй в условных операторах в операторах цикла. Если до сих пор логичвские выражения имели вид' р~т (тм..., ъ„), где рл"> — предикатный символ, т,..., т„— термы, то в определяемом классе структурированных схем логиче- 232 скин выражением будем считать любую бескванторную логическую формулу, составленную иэ символов логических операцвй 1 (отрицание), /~ (конъюнкция), ~/ (двэъюнкция) в атомарных формул, которымн являются логические выражении в старом смысле.
Примеры расширенных логвческих выражений: 1р( ) Лб(у х) р (б (г, Ю)) ~/ д (Ь (х), х). Класс структурированных схем с логяческими операциями получается иэ класса структурированных схем, определенных в предыдущем параграфе, добавлением в базис расширенных логвческвх выражений. Проблема трансляции стандартных схем в струнтурированные схемы с логическими операциями была исследована Ашкрофтом н Манной 1821, предлои«нввшмв два алгоритма трансляции, каждый иэ которых требовал расширения памяти.
Мы рассмотрим первый алгоритм, в вем расширение памяти осуществляется только эа счет добавления новых переменных — символов, в то время как во втором алгоритме (хотя он проще и дает более «экономвыеэ схемы) требуется введение интерпретированных логических переменных. Алгоритм Ашкрофта и Манны применим к стандартным схемам, заданным э нормальной форме 11001, которая покаэана на ! ! ! ! ! ! ! ! ! ! ! Л ! ! ! ! ! ! ! ! ! $ ! ! ! ! ! Рве. т0.2. Нормгльмао форма стовдертоой схемы в вормеасвыс фроимевты рис.
$0.2, а..1«оргмь«ьиый 33рагмгиги определяется рекурсивно череэ багогыг иоргмь«ьиыг !3!гагмгиты: (а) басовый нормальный фрагмент — это или преобразователь, или распоэваватель; (б) фрагмент. получаемый вог!иогицигй (рис. $0.2, б) илв го!ривгигаиигг«(рис. 10.2, о) нормальных фра!"ментов, является нормальным. Оставляем читателю в качестве самостоятельного ваданкявоэможность убедизъсн, что любую стандартную схему можно представить в нормальной форме.
233 Т е о р е м а т0.4 (Ашкрофт — Манка). Класс стакдарк»имх схем к»ралсяируем в квасе структурироеаккмх схем с яогическики опера»риьви. До к а з а те л ь с т в о. Будет описан алгорнтм преобразования, для которого исходная схема задана в нормалъной форме. Алгоритм сопоставляет каждому нормальному фрагменту У' фрагмент структурированной схемы Ж, а каждому выходу нз нормального фрагмента — вспомогательную информацию, состоящую из выходкой косяедввак»ельке»тли (операторов присваивания) и выходного условия. Иэ фрагмента Ж, построенного по максимальному нормалъному фрагменту, и связанной с ним вспомогателъной информации конструируется результирующая схема.
Пусть К вЂ” базовый нормалъный фрагмент. В атом случае Ж вЂ” пустой фрагмент. Если Я' — оператор присваивания, то выходная последовательность состоит нэ этого единственного оператора, а выходное условие отсутствует. Если Я вЂ” распоанаватель с логическим выражением к, то выходная последовательность пуста, а два выходных условия — это к (для т-дугв) н 3я (для О-дугн). Пусть Я вЂ” композиция двух нормальных фрагментов т и Я , причем выход » фрагмента К ведет на начало фрагмента х .
Выходы фрагмента Я вЂ” это выходы у и Я „ кроме выхода ». Рассмотрим разные случаи. а) У'г — бааовый фрагмент, преобразователь х:= т, Выходные условия всех выходов фрагмента Я остаются теми же, какими онн были у выходов фрагментов К и Я,. Выходные последовательности для тех выходов, которые являются одновременно выходами У», также не изменяются, а последовательности для тех выходов, которые являются выходами фрагмента Кг, имеют ввд (щ, х:= т), где а; — выходная последовательность для выхода $ фрагмента Я». Фрагмент Ж, соответствующий фрагменту у, совпадает с Ж», соответствующим У».
б) Я г — базовый фрагмент, распознаватель с логическим выражением и. Выходные последовательности для всех выходов Я остаются такими же, как и у соответствующих выходов фрагментов Я» и Ям Выходные условия тех выходов, которые являются выходамн Я», не меняются. Выходные условия тех выходов, которые были выходами фрагмента Я г, меняются на «р» /~ я' и «р» /~ 1 и', где «р» — выходное условие выхода» фрагмента Я'», а и' — формула, получаемая иэ к и выходной последовательности а» того же выхода $ следующим образом. Для последовательности операторов по которая рассматривается как свободно ннтернретнрованиая цепочка преобразователей, находятся термальные значения тех переменных памяти, которые входят в логическое выражение я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
