Файл: Богданов В.С. Системы математического обеспечения цифровых вычислительных машин учеб. пособие.pdf

- 25 -

для КС-грамматин. КС-грамматики обладаііт двумя весьма цен­ ными с точки зрения составителя программ транслирования ка­ чествами. Во-первых, требование, чтобы в левой части правила был только один символ, делает структуру КС-грамматик более простой, что облегчает составление программ трансляции. КС- гоамматики,“во-вторых, дают возможность описывать языки про­ граммирования в принципе^без учета контекстов, что тоже, уп­ рощает их изучение и описание.

Трансляция алгоритмических языков в машине осуществляет­

§ 7. Понятие магазинного автомата

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

•Реализация трансляторов на основе таких автоматов пред­ ставляется достаточно простои и гибкой.

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

Магазин (магазинный автомат) - это память, используемая

- 27 -

Фактически М-автсмат^или автомат с магазинной памятью, представляет собой недетерминированную машину Тьюринга,удов­ летворяющую следующим условиям (недетерминированная машина Тьюринга отличается от обычной машины Тьюринга только тем, что в ее программе могут быть различные команды с тсадественными левый частями).

1. Пашина имеет три ленты: входную, рабочую и выходную

итри головки по одной для ленты. Все ленты ограничены слеза

ине ограничены справа^

2. Машина имеет три внешних алфавита: входной - для входной ленты (основной словарь), рабочий - для рабочей лен­

ты (набор возможных направлений синтаксического анализа исход­

б) на рабочей ленте - либо писать в обозреваемой ячейке не­ пустой символ и сдвигать головку на одну ячейку вправо, либо сдвигать ее влево и стирать записанный в ячейке сим­ вол. Таким образом, рабочая лента есть не что иное, как магазин;

в) на выходной ленте только записывать символ и сдвигать го^ ловку на одну ячейку вправо (на выходной ленте должно вы­ писывать скобочное представление системы составляющих для

- 28 -

анализируемой фразы) ; г ) на каждом шаге машина работает только на одной ленте ;

д) в начальный момент все три головки находятся в крайних ле­ вых ячейках соответствующих лент, рабочая и выходная ленты пусты.

Работа машины заканчивается, когда головка на входной ленте дойдет до первой пустой ячейки.

Для каждого ^-автомата можно рассматривать множество, состоящее из всех тех и только тех цепочек (обрезков текстов), которые он способен проанализировать. Это множество является языком, определяемым M-автоматом. Доказано, что

а) для каждого М-автомата можно построить эквивалентную ему КС-грамматику;

б) для каждой КС-грамматики можно построить эквивалент­ ный ей М-автомат.

Последнее обстоятельство указывает на практическую цен­ ность понятия Ц-автомата, на базе которого строятся многие типы трансляторов.

- 29 -

Г л а в а И

ХАРАКТЕРИСТИКА НАИБОЛЕЕ РАСПРОСТРАНЕННЫХ АЛГОРИТМИЧЕСКИХ ЯЗЫКОВ

§I . Краткий обзор алгоритмических языков

иобласти кх применения

Смомента появления первых алгоритмических языков (1 9 3 - -1955 г г .) до настоящего времени разработано несколько тысяч различных алгоритмических языков. Так как их разработка ве­ лась зачастую независимо, причем для одинаковых классов за­ дач, многие из язшсоз были весьма сходны между собой. С появ­ лением международного универсального алгоритмического' языка АЛГОЛ-бО многие другие языки вышли из употребления. Однако

после появления ШГОЛа разработчики и потребители ЦВМ пришли

к выводу, что невозможно создать единый алгоритмический язык,

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

- 30 -

Поэтому в настоящее время можно насчитать несколько де­

сятков алгоритмических языков, которые широко используется.

И хотя многие из них дублирует друг друга, так как разраба­ тывались независимо друг от друга для одних классов задач,

но применительно к различным типам ЦВ!і, следует указать язы­

ки,которые, по-видимому, сохранятся или будут усовершенство­ ваны, но не отомрут в ближайшем будущем.

Для решения математических и научно-технических задач

разработаны языки: АЛГОЛ-60, ФОРТРАН, АКИ (Автокод-Инненер).

О АЛГОЛ-60 удобен для записи алгоритмов автоматического управления, сводящихся к численным методам. К таким алгорит­ мам откосятся алгоритма оптимизации, моделирования производ­ ственных процессов, распознаваніи образов и др ., использус-

щие методы решения систем алгебраических, дифференциальных,

разностных и др. типов уравнений. Преимущества АЛГОЛа для решения указанного класса задач заключайтея в близости язы­ ка к общепринятому в математике способу записи задач, в не­ зависимости языка от конкретной вычислительной машины и боль­

шой универсальности, т .е . в возможности расширения АЛГОЛа и

приспособления его для решения других близких классов задач. Существенным достоинством АЛГОЛа является то, что он был первым языком, получившим строго формальное описание с ис­ пользованием метаязыка БЭКУСа.

Широкие возможности АЛГОЛа породили тенденцію рассмат­ ривать его как универсальный язык программирования, пригод­ ный £ля решения любых классов задай, Однако попытки исполь­ зовать АЛГОЛ для записи несвойственных ему алгоритмов без из­

- 31 -

менения структуры языка всегда вызывают существенные труд - ности.

Следует отметить, что для получения высокого качества программ, записанных на АЛГОЛе, приходится создавать очень сложные трансляторы объемом в несколько тысяч команд. Ис­

пользование более простых трансляторов резко ухудшает качест­

чен для решения задач, сводящихся к методам вычислительной математики. Он довольно сильно похож на АЛГОЛ, однако беднее его, особенно логическими возможностями. В нем отсутствуй, напргшер, символы отношений и некоторые логические операторы,

ФОРТРАН был разработан раньше АЛГОЛа. Разработка велась в ос­ новном применительно к ЭВМ фирмы IBM. Каждой модификации ма­

шины этой, фирмы соответствует своя модификация ФОРГРАНа. Для І5У-7С4 - ФОРТРАН, ІЗМ-650 - ФОРТРАНЗИТ, і ВМ-1620 СоІтП ;

затем были разработаны расширения ФОРТРАНа: ФОРТРАН ІІ, ФОРТ­ РАН ІУ.. Особенностью ФОРТРАНа является широкое использование библиотеки стандартных подпрограмм и ориентировка на конк - ретные типы ЦВМ. Трансляторы ФОРТРАНа проще, чем у АЛГОЛа.

АКй (автокод-инженер) предназначен для описания алго - . ритмов, чаще всего встречающихся в инженерной практике: в ос­ новном, это задачи вычислительного характера. АКИ был разра­ ботан в СССР в І96І-І964 гг., под руководством Г.К. Столярова. Существенное влияние на состав и структуру языка оказало стремление авторов использовать уже имеющуюся отечественную

- 32 -

аппаратуру для перенесения фраз языка АКИ на перфоленту, В

качестве такой аппаратуры используется обычный телетайп СТА-

который разработан в настоящее вреая для ряда отечественных ЦВМ ("Минск-2").

Для обработки больших объемов числовой и алфавитно-циф­ ровой информации, характеризующей, например, качество сырья,

описанию. Одним из наиболее распространенных языков для та­ кого рода задач является COBOL (■ Common ßu&Lness Осівп-

iie d Запуснф [7]. Он был разработан к концу 1955 года, а окончательный зариант его был принят в 1961 году. Язык пред­ назначен для переработки на ЭВЫ экономической информации, за­ писанной на английском языке с очень небольшой степенью фор­ мализации. Так как форма представления такой информации дос­ таточно произвольна, то транслятор к нему, как и к АЛГОЛу, сложен.

АЛГЭЫ предназначен для программирования экономических и

математических задач. Разработан в СССР под руководством Kn­ ot

това в 1966 году.- По существу, он является расширением АЛГОЛа. Помимо экономических задач, АЛГЭМ может быть применен и при решении других информационно-логических задач, связанных с

- 33 -

обработкой больших пассивов информации, имевшей сложную струн

туру (обработка историй болезней в клиниках, информация и об­

работка результатов экспериментов, машинный перевод с одного языка на другой и т .д .) .

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

ка, разработаны также специальные языки KOMMT, ЛИСП, ИШІ-5. Кроме указанных языков, получивших довольно широкое рас­

пространение, разработаны специализированные языки для прог­

раммирования узкого крута задач.

симскрипт (1963 г о д ) S a i p t ) - {біт иС айоп

Ргодіаттіп^ language') предназначен для составления прог­ рамм статистического моделирования производственных процес- . сов, использующих аппарат теории вероятностей и теории мас­ сового обслуживания.

Алгоритмический язык ЛЯПАС используется для программи­ рования алгоритмов синтеза дискретных автоматов и близких к ним задач. Этот язык разработан в Томском университете (1964 год). Язык имеет два уровня. Первый уровень предназначается для представления не слишком сложных алгоритмов и имеет до­ вольно компактный транслятор. Язык второго уровня предназ­ начен для моделирования сложных алгоритмов.

Кроме перечисленных языков, разработаны такие, которые предназначены для решения задач управления производством,сос­ тавления схем набора аналоговых машин, обмена информации меж­ ду вычислительными машинами и даже для разработки языков про­ граммирования.