АЛГОРИТМИЧЕСКИЙ ЯЗЫК

Значение АЛГОРИТМИЧЕСКИЙ ЯЗЫК в математической энциклопедии:

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

Различают проблемно-ориентированные А. я. (А. я. высокого уровня), предназначенные для записи алгоритмов безотносительно к к.-л. определенным вычислительным машинам, и машинно-ориентированные А. я. (А. я. низкого уровня), уже учитывающие особенности той или иной вычислительной машины (список команд, характеристики запоминающего устройства и т. д.). Обычно под термином "А. я." понимают проблемно-ориентированный язык, противопоставляя его машинному языку, т. е. средству записи, воспринимаемой машиной непосредственно. Над законченными текстами ( программами).в А. я. определен универсальный алгоритм их однозначного выполнения, что отличает А. я. от не алгоритмических языков программирования, в к-рых процесс выполнения текста сугубо неоднозначен или текст служит только материалом для синтеза алгоритма решения задачи. Подобно естественным языкам, А. я. строится над алфлвитом основных символов (вк-ром записывается программа) в виде иерархич. системы своих грамматич. элементов с заданными на них отношениями (подобно словам, словосочетаниям и предложениям в естественном языке, связанным синтаксич. правилами). Элементы низшего уровня, образованные цепочками основных символов, наз. лексемами. Для вхождений лексем в прогамму пределена их принадлежность к нек-рому классу и к области действия- к.-л. однозначно выделяемой части программы, к к-рой относятся все входящие в нее экземпляры лексемы. Среди всех вхождений лексемы выделяется одно, к-рое наз. определяющим; остальные вхождения лексемы в область действия наз. использующим и. Следующие уровни элементов А. я. образуются понятиями. Между понятиями А. я. задается отношение быть (прямой) конституентой (т. е. непосредственной составной частью), а между конституентами данного понятия - отношение конкатенации (текстуального следования). Транзитивное замыкание конституентного отношения однозначно сопоставляет понятию нек-рое подслово текста программы, наз. порождением этого понятия. Существует одно начальное понятие, порождением к-рого является весь текст программы. Среди понятий выделяются позиции и субституенты. Субституента занимает нек-рую позицию, являясь ее прямой конституентой. Дерево, корень к-рого - начальное понятие, концевые вершины - лексемы и основные символы, внутренние вершины - понятия, а дуги - конституентные отношения, наз. деревом разбора программы. Построение этого дерева наз. синтаксическим анализом программы.

Понятия и лексемы обладают атрибутами, т. е. нек-рыми фиксированными описанием А. я. множествами, элементы к-рых сопоставляются элементам А. я. в качестве их характеристик. Нахождение атрибутов элементов А. я., входящих в программу, наз. ее с е-мантическим анализом. Нахождение атрибутов лексем начинается с анализа их определяющих вхождений, к-рые обычно содержат информацию об атрибутах в явном виде. Затем атрибутивная информация в пределах соответствующей области действия переносится на все использующие вхождения лексемы (идентификация). Атрибуты нек-рого понятия находятся индукцией по дереву разбора как функции атрибутов его конституент. Существенной частью се-мантич. анализа, имеющей большое значение для контроля правильности программы, является проверка на совместимость атрибутов позиции и ее субституенты (приведение). Почти во всех А. я. действуют те или иные правила умолчания, т. е. приписывание не специфицированному явно атрибуту нек-рого значения как функции контекста данного понятия. Таким контекстом могут быть: позиция, область действия, вся программа и, наконец, само описание А. я.

Правила синтаксич. анализа задаются либо порождающей грамматикой А. я. (см. Грамматика порождающая), либо анализирующим автоматом (точнее, его различными обобщениями), преобразующим текст программы в дерево разбора. Правила семантич. анализа описываются обычно неформально, однако предпринимались попытки формализовать определение атрибутивной информации и учет контекста с помощью механизма двухступенчатых грамматик (см. Алгол-68).

Алгоритм выполнения программ А. я. задается сопоставлением вершинам дерева разбора различных исполнительных процедур (называемых также трансдукторами, семантическими процедурами). Каждая процедура выполняет нек-рые действия как функцию атрибутов и того или иного контекста данного понятия (или лексемы), а затем определяет последующую процедуру. Действия процедуры либо непосредственно задают вычислительный процесс в терминах нек-рой абстрактной машины (семантика интерпретирующего типа), либо трансформируют порождение данного понятия во фрагмент программы в нек-ром языке низшего уровня (семантика трансляционного типа).

В конкретных А. я. алфавит основных символов обычно состоит из букв латинского (иногда с добавлением русского) алфавита, цифр, парных ограничителей (скобок), разделителей (знаков препинания) и нек-рых знаков операций. В связи с ограниченностью алфавита существуют правила кодирования основных символов комбинациями знаков, воспринимаемых входными устройствами машины. Основные классы лексем - нумералы для изображения чисел, литералы для изображения текстов, идентификаторы для обозначения различных объектов программы, определяемых в ней самой. Основными объектами являются переменные величины, м е т к и (наименования различных частей программы) и процедуры (функциональные обозначения). Смысл и назначение нек-рых идентификаторов фиксируется описанием А. я. (закрепленные слова).

Среди понятий А. я. выделяются базовые конструкции - описания, выражения и операторы. Описания являются источником атрибутивной информации, приписываемой определяющему вхождению лексемы. В основном атрибуты характеризуют тип (вид) значений, вычисляемых при выполнении программы, их представление и режим хранения в памяти ЭВМ. Для составных значений (векторов, матриц, структурных величин) указывается также способ доступа к их элементарным компонентам. Выражения являются источником значений; операторы - единицами законченных действий в программе; базовые операторы- это оператор присваивания значения выражения переменной величине, оператор п е-редачи управления (безусловной или по условию), оператор вызова процедуры, оператор цикла.

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

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

Программирование с использованием А. я. для вычислительной машины требует включения в ее программное обеспечение специальных программирующих процессоров- посредников между программами на А. я. и машиной. Процессор в своем развернутом составе выполняет следующие функции: ввод программы, лексический (выделение и классификация лексем), синтаксический п семантич. анализы с сигнализацией о формальных ошибках, синтез промежуточной формы (представление программы на внутреннем языке нек-рой абстрактной вычислительной машины, удобное для последующей обработки или выполнения программы), оптимизация (систематич. преобразование промежуточной формы, улучшающее такие характеристики программы, как ее размер, скорость и объем расходуемой памяти), генерация (построение машинной программы), выполнение программы. В процессорах транслирующего типа (трансляторы, компиляторы, программирующие программы) выполнение программы происходит после полного построения машинной программы. В процессорах интерпретирующего типа (шаговые, диалоговые, отладочные трансляторы) программа выполняется с помощью нек-рого механизма интерпретацип ее либо промежуточной формы, либо дерева разбора, либо даже исходного текста.

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

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

Лит.:[1] Ингерман П., Синтаксически ориентированный транслятор, пер. с англ., М., 1969; [2] Языки программирования, пер. с англ., М., 1972; [3] Xопгуд Ф., Методы компиляции, пер. с англ., М., (972; [4] Xигман Б., Сравнительное изучение языков программирования, пер. с англ., М., 1974. А. <П. Ершов.