АЛЬФА-СИСТЕМА
— система программирования на альфа-языке для
ЭВМ типа «М-20». Разработана в 60-х гг. Составными частями А.-с. являются транслятор — программа, транслирующая программы с алъфа-языка на язык машины, и система отладки. Отличительной особенностью А.-с. является применение двухфазной трансляции с использованием внутреннего языка и наличие спец. алгоритмов оптимизации транслируемой программы на базе Смешанной стратегии программирования и формальных преобразований программы. Транслятор состоит из 24 последовательно работающих блоков общим объемом в 50 тыс. команд. Средняя скорость трансляции — прибл. 150 команд рабочей программы на 1 мин работы транслятора.
Первая фаза трансляции состоит в переводе программ с альфа-языка на внутренний язык, который представляет собой машинно-независимый язык с простой структурой операторов и с фиксированным форматом переменных. Осн. символами внутр. языка являются 15-разрядные двоичные коды, изображающие идентификаторы, знаки операций и операторов и различные разделители. Часть разрядов кода — идентифицирующая, а часть — признаковая, содержащая классификацию основных символов и информацию о некоторых свойствах идентификаторов. Каждый оператор имеет ограниченное к-во операндов, каковыми могут быть только идентификаторы. Осн. типы операторов: пересылки, присваивание результата выполнения арифм. или логич. операции, передачи управления (условные, безусловные и с возвратом), формирование и засылка адресов и обращения к подпрограммам стандартным и системе динамического распределения памяти. В индексах переменных оставлены только линейные зависимости от параметров операторов цикла; остальные вычисления из индексов выносятся.
При переводе на внутр. язык ведут программирование выражений, процедур и действий над комплексными и многомерными величинами. Информация о переменных из описаний переносится в таблицы и признаковые разряды идентификаторов. В конструировании таблиц применяется списковая структура размещения информации. Перевод идентификаторов в 15-разрядный код производится с помощью функции расстановки. Выражения программируются за два просмотра: при 1-м просмотре производится декомпозиция выражений на простые операторы и вводятся символы промежуточных величин, при 2-м - определяются тип и порядки по измерениям промежуточных величин и массивов.
При программировании процедур применяется смешанная стратегия: в трансляторе предусмотрено 8 способов программирования операторов и описаний процедур — от универсального до простейшего, отличающихся друг от друга сложностью реализации и степенью общности. На основе анализа характера вхождений формальных параметров в тело процедуры и степени сложности фактических параметров для каждой процедуры выбирается самый простой способ, обеспечивающий правильность ее применения. Программирование действий над многомерными величинами состоит во введении в программу циклов выполнения покомпонентных действий. При этом производится оптимизация, заключающаяся в объединении нескольких возникающих циклов в один, где это возможно, и в сокращении к-ва промежуточных массивов. Операции над комплексными величинами реализуются в основном открытой вставкой подпрограмм выполнения отдельных действий.
На уровне внутреннего языка транслятор выполняет оптимизирующие формальные преобразования транслируемой программы: чистку циклов и экономию совпадающих выражений. При чистке циклов в участке программы, составляющем цикл, находят операторы, вычисляющие при повторениях данного цикла одно и то же значение (такие операторы выносятся из цикла и помещаются перед ним). Экономия выражений производится в пределах квазилинейных участков программ, состоящих из операторов, выполняющихся строго подряд и допускающих разветвления, вызванные только условными выражениями в исходной программе. Из нескольких совпадающих операторов, вычисляющих одно и то же значение в участке экономии, остается только один и помещается в такое место, где его результат доступен для использования. При отождествлении операторов также применяется ф-ция расстановки. В индексах производятся преобразования линейных форм зависимостей от параметров циклов (приведение подобных, выделение свободного члена), направленные на их упрощение.
Вторая фаза трансляции заключается в переводе программ с внутреннего языка на машинный. После построения машинных команд, реализующих основные вычисл. и логич. операторы внутр. языка, производится программирование циклов. Здесь также применяется смешанная стратегия, суть которой заключается в выборе для каждого заголовка цикла наиболее простого из доступных способа организации пересчета параметра, контроле числа повторений цикла, переадресации и восстановлении переменных команд. Использование индекс-регистра организуется таким способом, чтобы сократить к-во команд сохранения и восстановления индекс-регистра. В конце второй фазы производится глобальная экономия памяти, отводимой для хранения скалярных переменных и массивов заранее известной длины. Сначала по программе строится ее операторная схема. В качестве одного оператора берется квазилинейный участок программы. Для каждого оператора определяются: номера операторов, переменные, являющиеся аргументами и результатами оператора, а также внутренние величины, т. е. переменные, значения которых возникают и используются только в пределах оператора. Для всех внутр. величин отводится общее поле, а для каждой пары остальных переменных на основе анализа
операторной схемы определяется, может ли данная пара располагаться на одном участке памяти. Затем на основе этой информации о попарной совместимости производится экономное памяти распределение. Алгоритмы, применяемые при этом, тесно связаны с алгоритмами раскраски вершин графов (см. Граф раскрашенный). В заключение производится локальная оптимизация полученной программы, использующая машинные команды с совмещением операций, а сама программа после компоновки и присвоения истинных адресов ставится в рабочее положение для немедленного выполнения или выдается на перфокартах.
Система отладки обладает способностью формировать отладочные программы путем модификации исходной программы на альфа-языке, состоящей в изменении параметров программы (задание значения переменных, применение упрощенных процедур и т. п.) и во внесении в текст программы отладочных команд (печатание промежуточных значений, прослеживание переходов и подсчет фактического числа повторений циклов). Модификация осуществляется «нулевым» блоком транслятора. На базе А.-с. создан ряд систем программирования для разных ЭВМ, в т. ч. система Альгибр для ЭЦВМ «БЭСМ-6». Лит.: Альфа-система автоматизации программирования. Новосибирск, 1967; Ершов А. П., Кожухин Г. И., Поттосин И. В. Руководство к пользованию системой Альфа. Новосибирск, 1968.
А. П. Ершов.
