Инфиксная запись формул

Для многих программистов трудным барьером на пути к овладению языком Форт оказывается используемая в нем обратная польская форма для записи выражений. Опишем простую надстройку над языком Форт, которая позволяет записывать формулы в обычной инфиксной форме с использованием скобок. Будем по-прежнему считать все элементы такого выражения (скобки, знаки операций и элементарные термы) отдельными форт-словами и разделять их при записи пробелами. Задача состоит в том, чтобы вычисления на стеке автоматически перегруппировывались исходя из инфиксной формы записи. Например, чтобы вместо текста 2 5 + 7 3 - * можно было писать ( ( 2 + 5 ) * ( 7 + 3) ). Внешние скобки нужны для того, чтобы отмечать конец выражения. При желании это можно задавать и каким-нибудь другим способом.

Для операций в инфиксной записи вводится понятие приоритета (старшинства), которое определяет порядок вычислений при отсутствии скобок. Приоритет обозначается целым числом, и операции с меньшим приоритетом выполняются после операций с большим приоритетом. Например, в выражении А+В/С подразумевается следующая расстановка скобок: (А+(В/С)), т.е. сначала выполняется деление и только потом сложение, потому что приоритет деления выше приоритета сложения. В случае равных приоритетов, например в выражении А+В+С, будем выполнять операции слева направо: ((А+В)+С). Традиционно используемые приоритеты двухместных операций показаны в табл. 3.1. Все одноместные операции (ABS, NEGATE, NOT и др.) имеют максимальный приоритет (обычно 9).

Таблица 3.1. Приоритеты двухместных операций

Приоритет	2	3	4	5	6	7	8
Операция	OR XOR	AND	=	< >	+ -	* / MOD	**

Опишем вспомогательную структуру данных — стек ОПРЦ, элементами которого являются пары значений: приоритет операции и адрес кода, который ее вычисляет. Размер стека определяется максимальной глубиной вложенности формул, которую мы допускаем: CREATE ОПРЦ HERE 2 + , 40 ALLOT. Первым элементом в поле параметров слова ОПРЦ является указатель вершины этого стека (адрес первого свободного байта), далее зарезервирована память на 5 элементов по 4 байта (два значения) каждый.
По аналогии со словами >R, R@ и R&gt; определим слова для работы со стеком ОПРЦ:

: >ОПРЦ ( A --->) ОПРЦ @ ! 2 ОПРЦ +! ; : ОПРЦ@ ( ---> A) ОПРЦ @ 2- @ ; : ОРПЦ> ( ---> A) ОПРЦ@ -2 ОПРЦ +! ;

Обработка операций в инфиксной форме состоит в том, что операция не выполняется, а помещается вместе со своим приоритетом на стек операций, выталкивая из него на исполнение все операции с меньшим или равным приоритетом. В состоянии исполнения вытолкнутая операция исполняется, а в состоянии компиляции — компилируется. Предполагая, что в стеке ОПРЦ сначала размещается адрес поля кода для исполнения операции, а за ним приоритет, определим слово для такого выталкивания операций:

: >ОПРЦ> ( N:ПРИОРИТЕТ---> ) >R BEGIN ОПРЦ@ R@ < NOT WHILE ОПРЦ> DROP ОПРЦ> ( CFA) STATE @ IF , ELSE EXECUTE THEN REPEAT R> DROP ;

Теперь введем определяющие слова для двухместных и одноместных операций и переопределим через них стандартные арифметические форт-слова:

: 2-ОП ( N:ПРИОРИТЕТ-&gt) &gtIN @ &gtR ' ( N,CFA) R&gt &gtIN ! CREATE IMMEDIATE ( N,CFA) , , DOES&gt ( PFA-&gt) 2@ ( N,CFA) &gtR &gtR R@ &gtОПРЦ&gt R&gt R&gt &gtОПРЦ &gtОПРЦ ; : 1-ОП ( -&gt) 9 2-ОП ; 2 2-ОП OR 2 2-ОП XOR 3 2-ОП AND 4 2-ОП = 5 2-ОП < 5 2-ОП > 6 2-ОП + 6 2-ОП - 7 2-ОП * 7 2-ОП / 7 2-ОП MOD 1-ОП NOT 1-ОП ABS 1-ОП NEGATE

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

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

В заключение осталось переопределить круглые скобки, явно задающие порядок вычислений:

: ( 0 &gtОПРЦ ; IMMEDIATE : ) 1 &gtОПРЦ&gt ОПРЦ&gt DROP ; IMMEDIATE

Открывающая скобка кладет на стек значение 0 — ограничитель для выталкивания операций. Закрывающая скобка выталкивает все операции до ближайшего ограничителя и удаляет его из стека. Переопределение открывающей скобки делает невозможным ее использование в прежнем смысле — как знака комментария. Поэтому программисту, вводящему такую надстройку, следует подумать и о решении этого вопроса.

Развивая описанную надстройку дальше, определим простой входной язык с описаниями переменных и присваиваниями, которые записываются обычным образом. В качестве знака присваивания пусть используется слово :=, а в качестве разделителя операторов — слово ;. Если переменная использована как получатель присваивания (слева от знака :=), то ее исполнение оставляет на стеке адрес значения; а если данная переменная входит в правую часть присваивания, то ее исполнение кладет на стек само значение данной переменной. Для управления поведением переменных нашего языка введем рабочую переменную ?ЗНАЧ, которая имеет значение 0 при обработке левой части присваивания и значение -1 при обработке правой, и определим слово ПЕРЕМ для описания переменных нашего языка:

VARIABLE ?3НАЧ : ПЕРЕМ CREATE 0 , DOES> [COMPILE] LITERAL ?ЗНАЧ @ IF STATE @ IF COMPILE @ ELSE @ THEN THEN ; IMMEDIATE

Для записи присваиваний определим слова := и ; через уже определенные скобки:

: := [COMPILE] ( -1 ?3НАЧ ! ; IMMEDIATE : ; [COMPILE] ) STATE @ IF COMPILE SWAP COMPILE ! ELSE SWAP ! THEN 0 ?ЗНАЧ ! ; IMMEDIATE

Слово := кладет на стек ОПРЦ ограничитель для выталкивания операций и устанавливает переменную ?ЗНАЧ на обработку правой части присваивания. Слово ; выталкивает со стека ОПРЦ все накопившиеся там операции, в результате на вершине стека данных оказывается значение правой части. Непосредственно под ним располагается адрес переменной, оставленный левой частью данного присваивания.

Слова SWAP и ! выполняют присваивание, причем в состоянии компиляции они компилируются, а состоянии исполнения исполняются. В заключение переменная ?ЗНАЧ переустанавливается на режим обработки левой части следующего присваивания.

Благодаря словам := и ; отпадает необходимость в дополнительных внешних скобках для всего выражения. Входной текст в описанном расширении выглядит вполне традиционно:

ПЕРЕМ A ПЕРЕМ B А := 10 ; B := 15 ; A := ( A + B ) * ( A - B ) + 2 ;

и вместе с тем это текст на языке Форт! Такие операторы присваивания можно исполнять непосредственно или включать в тело определений через двоеточие. Однако переопределение точки с запятой усложняет написание новых определений в таком расширении. Чтобы решить эту проблему, можно предусмотреть специальные средства для определения новых слов, как и слова для включения комментариев. Описанный пример еще раз показывает, что средства, которые язык Форт предоставляет программисту, позволяют ему реализовать практически любые необходимые инструментальные надстройки, исходя из конкретных требований и особенностей данной задачи и пожеланий пользователей, с ней работающих.

Содержание раздела