Математическая энциклопедия

Алгоритмический Язык

Алгоритмический Язык
АЛГОРИТМИЧЕСКИЙ ЯЗЫК

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

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

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

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

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

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

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