Перевод в обратную польскую запись выражений с указателями функций

Метод Дейкстра

IV. Трансляция выражений

Например, выражение y — f(x,y+1,z) содержит указатель функции с идентификатором f. Указатель функции отличается от переменной с индексами лишь тем, что после идентификатора функции записана строка, заключенная в круглые, а не в квадратные скобки, поэтому дерево для указателя функции и алгоритм перевода указателя функции в обратную польскую запись почти те же, что для переменных с индексами.

Вводится операция ФУНКЦИЯ, операнды которой – идентификатор функции и значения (или идентификаторы) ее аргументов, а результат – значение функции (адрес значения функции). Тогда выражение можно представить в виде дерева:

Обход этого дерева дает обратную польскую запись выражения.

Как и в случае переменных с индексами, в обратной польской записи целесообразно вместе со знаком операции ФУНКЦИЯ указывать количество операндов, что облегчает последующую трансляцию указателя функции в машинные команды и позволяет контролировать правильность обращения к функции (соответствие числа фактических и формальных параметров).

Операция ФУНКЦИЯ обозначается символами kФ, где k – количество операндов, а Ф – знак операции ФУНКЦИЯ. Тогда обратная польская запись выражения примет вид:

y f xy 1 + z4Ф-

Алгоритм перевода в обратную польскую запись функции, имеющей не менее одного параметра, такой же, что для переменной с индексами, но различие состоит в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, используют специальную переменную состояния f (признак функции), которая обычно имеет значение 0. В момент появления идентификатора функции f принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую скобку, записанную вместе со значением счетчика операндов, заносит это значение в выходную строку, записывает туда знак Ф и уничтожает в стеке круглую скобку и значение счетчика операндов.

Дата добавления: 2014-01-11