IV. Трансляция выражений
2. Метод Дейкстра
2.3. Перевод в обратную польскую запись выражений с указателями функций.
Например, выражение y — f(x,y+1,z) содержит указатель функции с идентификатором f. Указатель функции отличается от переменной с индексами лишь тем, что после идентификатора функции записана строка, заключенная в круглые, а не в квадратные скобки, поэтому дерево для указателя функции и алгоритм перевода указателя функции в обратную польскую запись почти те же, что для переменных с индексами.
Вводится операция ФУНКЦИЯ, операнды которой – идентификатор функции и значения (или идентификаторы) ее аргументов, а результат – значение функции (адрес значения функции). Тогда выражение можно представить в виде дерева:
Обход этого дерева дает обратную польскую запись выражения.
Как и в случае переменных с индексами, в обратной польской записи целесообразно вместе со знаком операции ФУНКЦИЯ указывать количество операндов, что облегчает последующую трансляцию указателя функции в машинные команды и позволяет контролировать правильность обращения к функции (соответствие числа фактических и формальных параметров).
Операция ФУНКЦИЯ обозначается символами kФ, где k – количество операндов, а Ф – знак операции ФУНКЦИЯ. Тогда обратная польская запись выражения примет вид:
y f xy 1 + z4Ф-
Алгоритм перевода в обратную польскую запись функции, имеющей не менее одного параметра, такой же, что для переменной с индексами, но различие состоит в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, используют специальную переменную состояния f (признак функции), которая обычно имеет значение 0. В момент появления идентификатора функции f принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую скобку, записанную вместе со значением счетчика операндов, заносит это значение в выходную строку, записывает туда знак Ф и уничтожает в стеке круглую скобку и значение счетчика операндов.
V. Введение в теорию формальных языков
1. Способы определения языков
Описание языков программирования опирается на теорию формальных языков, которая является основой для организации синтаксического анализа и перевода.
Существует два основных способа определения языков:
механизм порождения (генератор);
механизм распознавания (распознаватель).
Эти способы связаны между собой (первый обычно используется для описания языков, а второй для их реализации) и позволяют описать языки конечным образом, несмотря на бесконечное число порождаемых ими цепочек.
Неформально язык L – это множество цепочек конечной длины в алфавите T.
Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой, которая представляет собой наиболее распространенный класс описаний языков.
При описании грамматики необходимо определить алфавита языка, который задается как набор допустимых – терминальных символов (терминалов). Затем необходимо определить набор правил вывода вида α→β, в соответствии с которыми строятся цепочки (предложения) языка. В левой и правой частях правил могут встречаться специальные – нетерминальные символы (нетерминалы), которые в процессе вывода заменяются с помощью соответствующих правил до полной замены на соответствующие терминалы. Кроме того, грамматика должна включать в себя начальный символ (аксиому), с которого начинается получение любого предложения языка.
Достоинство определения языка с помощью грамматик состоит в том, что операции, производимые в ходе синтаксического анализа и перевода, можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик.
Механизм распознавания использует алгоритм, который для произвольной входной цепочки останавливается по ветке да после конечного числа шагов, если эта цепочка принадлежит языку; если цепочка не принадлежит языку, то в соответствии с алгоритмом будет выработан признак нет.
Распознаватели используются непосредственно при построении синтаксических анализаторов и являются их формальной моделью; строятся на основе теории конечных автоматов и автоматов с магазинной памятью.