Ограничители if, then, и else играют в некотором смысле роль скобок. Как и обычные скобки, они выделяют подвыражения и порождают новые ветви дерева. В этом смысле символ if эквивалент открывающей скобке, а символы then и else, подобно запятым в списке индексов и фактических параметров, являются закрывающими скобками для предшествующего выражения и открывающими для последующего.
Закрывающей скобкой для выражения следующщего за else может служить либо символ then, как выражение (4) либо другой знак конца условного выражения:
закрывающая круглая скобка, закрывающая индексная скобка, запятая или знак конца оператора (точка с запятой или end).
По этим причинам символу if припишем приоритет 0, а символу — приоритет 1. При переводе условных выражений в обратную польскую запись особенности имеет только обработка символов if, then, else, а также обработка знака конца выражения. Рассмотрим особенности обработки отдельных символов.
1. Символ if, имеющий приоритет 0, как любая открывающая скобка, записывается в вершину стека. Этот символ используется в качестве «хранителя» и «переносчика» рабочих меток операции УПЛ и БП. При символе else превращается в if m(i), а появление символа else превращает запись if m(i) в if if m(i)m(i+l). Здесь i - номер очередной рабочей метки. Как будет видно в дальнейшем, описанные действия дают возможность формировать метки операции УПЛ и БП в нужных местах выходной строки.
2. Символ then с приоритетом 1 выталкивает из стека все знаки до первого if исключительно. После этого анализируется запись в вершине стека. Он может иметь одну из двух форм:
а) if
б) ifm(i)m(i+l), где m(i) и m(i+l)-рабочие метки.
Появление какой - либо другой записи - признак ошибки Случай (а) означает, что между символами if и then нет другого условного логического выражения (пример выражение (1). При этом в выходную строку заносится запись
m(i) УПЛ r(j) (6)
где i - номер очередной нечётной рабочей метки, a j - номер очередной рабочей переменной (рабочей ячейки).
Затем метка m(i) заносится в таблицу меток, к символу if в вершине стека дописывается m(i) (получается запись ifm(i)). На этом обработка символа then закончиваетсь.
Случай (б) означает, что закончилось условное логическое выражение, входящее в другое условное логическое выражение между символами if и then (пример случая (б)-выражение (4)).
Вообще говоря, условное логическое выражение может, в свою очередь, содержать условное логическое выражение после символа else, поэтому случай (б)может означать окончание не одного, а нескольких условных логических выражений, объединенных конструкцией вида
If A then В else if А 1 then В 1 else if A2 then B2 else ... (7)
Каждое условное выражение, входящее в (7), оставляет в стеке «след» в виде записи Ifm(i)m(i+l) (8)
Следовательно, в общем случае конструкция вида (7) порождает в стеке последовательность записей
Ifm(i)m(i+l) Ifm(i-2)m(i-l) (9)
Ifm(i-2k)m(i-2k+l)
первая из которых находится в вершине стека. При излагаемом здесь способе перевода условных выражений все записи, образующие последовательность (9), должны быть удалены из стека, а в выходную строку должна быть добавлена запись вида
:=m(i+l)::=m(i-1):...:=m(i-2k+1):, (10)
где каждая метка помечает место выхода по операции БП. После последовательности (9) непременно следует запись
If,
Являющаяся открывающей скобкой в конструкции вида if ... then. Эта запись соответствует случаю (а), поэтому нужно выполнить описанные выше действия, соответствующие случаю (а). Это означает, что процедура обработки случая (б) непременно завершается процедурой обработки случая (а).
3. Символ else с приоритетом 1 выталкивает из стека все знаки до первого if исключительно. После этого в вершине стека должна быть запись вида ifm(i)
Появление другой записи - признак ошибки ( напомним, что здесь речь идёт только об обработке выражений).
В выходную строку добавляется запись
:=m(i+l)m(i):r(i) (11)
затем метка m(i+l) заносится в таблицу меток, а в вершину стека к записи if m(i) дописывается метка m(i+l) (получается запись ifm(i)m(i+l)).
4. Символ конца условного выражения, отличный от then ( таким символом может быть точка с запятой, запятая, end, а также круглая или индексная скобка) вначале выталкивает из стека его содержимое до ближайшей записи вида
Ifm(i)m(i+l),
Которая в общем случае может быть началом последовательности вида (9), когда одновременно заканчивается несколько условных выражений, объединенных конструкцией вида (7). Обработка такой последовательности выполняется точно так же, как в (б),т.е. последовательность (9) удаляется из стека, а в выходную строку вида (10). На этом обработка условного выражения заканчивается.
Подчеркнём, что рабочая переменная r(j) в записях (6) и (11) одна и та же. Вообще при переводе в обратную польскую запись любого сколь угодно сложного условного выражения используется лишь одна рабочая переменная, которая в итоге содержит значение этого выражения. Конечно, это не означает, что во внутренних подвыражениях не могут использоваться другие рабочие переменные.
Таблица 2 Перевод в обратную польскую запись условного выражения
Пример. Перевести в польскую запись выражение y+(ifa> b then x+1 else 2).
Решение. Решение показано в таблице 2, которая устроена иначе, чем предыдущие таблицы. «Выход» - записи, заносимые в вых. строку.
1.3. Условный оператор
Условный оператор вида If A then В else С;
Где А - логическое выражение;
В - Безусловный оператор;
С - оператор;
Подобно условному выражению можно представить в виде динамического дерева (рис.7). Заметим, что в изображении дерева
Рисунок 7 Дерево, изображающее условный оператор
знак «;» не является знаком операции. Отвечающий ему узел играет роль пустого узла и служит для объединения отдельных ветвей. В обратную польскую запись знак «;» можно не переносить. Обход дерева даёт обратную польскую запись
А т(1) УПЛ В т(2) БП т(1): Ст(2):. Частным случаем условного оператора является оператор «если»:
if A then В.
Соответствующее дерево показано на рис.8. Обратная польская запись оператора (12) имеет вид
Ат(1)УПЛВт(1):.
Сравнивая обратную польскую запись условного выражения и условного оператора, нетрудно увидеть, что для полного условного оператора отличия состоят лишь в «обрамлении» знаков операций УПЛ и БП, а также в ином оформлении конца оператора.
Аналогии оператору «если»в условных выражениях нет. Однако оператор «если» можно рассматривать как особый частный случай полного условного оператора,
По этим причинам алгоритм перевода условных операторов в обратную польскую запись почти тот же, что и для условных выражений. Это даёт возможность использовать в обоих случаях один и тот же блок транслятора.
Рисунок 8 Дерево, изображающее оператор «если»
Чтобы обеспечить специфичную обработку условного оператора, целесообразно при занесении в стек символа if фиксировать вместе с этим символом признак условного оператора, отличающий его от условного выражения. Обозначим этот признак знаком *.
| Обрабатыва -емый символ | Условное выражение | Условный оператор | ||
| Запись в стек | Запись в выходную строку | Запись в стек | Запись в выходную строку | |
| if | if | - | if- | - |
| then | a) ifm(i) b) - | а) т(1)УПЛ b) :=m(i+l):... | a)if m(i) b)- | а) т(ОУПЛ b) m(i+l):... |
| else | Ifm(i)m(i+l) | :=т(1+1)БПт(0:гО) | IfmOmO+l) | т(1+1)БПт(1):гО) |
| Конец выражения (оператора) | - | :=m(i+l):... | а)при очистке стека встретилась запись if* m(i) ( конец оператора «если») m(i): | |
| а)при очистке стека встретилась запись if^ m(i) m(i+l) ( конец оператора «если») m(i+l): | ||||
В соответствии с синтаксисом Алгола — 60 символ if является началом условного оператора, если ему предшествует один из символов: ; : (в конце метки) begin do или символ else, к которому «парным» является if.
Алгоритм обработки условных выражений включает четыре пункта. В таблице 3 приведены изменения, которые нужно внести в этот алгоритм для обработки условных операторов
0 коммент.:
Отправить комментарий