Получение ОПЗ для условного оператора

До сих пор мы рассматривали конструкции, в которых порядок действий определяется только старшинством операций и скобками, и в ходе исполнения программы не изменяется.

Такие конструкции изображаются статическим деревом.

Для изображения дерева условного оператора понадобятся динамические деревья.

Для этого введем метки, которыми могут помечаться листья и некоторые узлы динамических деревьев. Введем две операции:

- условный переход по значению «ложь» (УПЛ);

- безусловный переход (БП).

Операция УПЛ имеет два операнда: первый – логическое выражение, а второй – метка.

Если логическое выражение истинно, то операция УПЛ пропускается, а если ложно, то происходит переход на метку.

У операции БП имеется лишь один операнд – метка. Результат перехода БП – переход на метку.

Условный оператор вида: if A then B else C;

где А – логическое выражение;

В и С – операторы, можно представить в виде динамического дерева:

Знак «;» не является знаком операции.

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

В ОПЗ знак «;» можно не переносить. Обход дерева дает ОПЗ:

A m1 УПЛ В m2 БП m1: С m2:

Частным случаем условного оператора является оператор: if A then B;

Его дерево:

Его ОПЗ: A m1 УПЛ В m1:

Ограничители if, then и else играют роль скобок: символ if эквивалентен открывающей скобки, а символы then и else, подобно запятым в списках индексов и фактических параметров, являются закрывающими скобками для предшествующего оператора или выражения и открывающими для последующего.

Закрывающей скобкой для оператора, следующего за else, служит точка с запятой или end.

По этим причинам символу if припишем приоритет 0, а символам then и else – 1.

Рассмотрим особенности обработки:

1. Символ if записывается в стек и используется в качестве «хранителя» рабочих меток операций УПЛ и БП. При появлении символа then запись if превращается в if m_i, а появление символа else превращает последнюю в if m_i m_i+1.

Здесь i – номер очередной рабочей метки.

2. Символ then с приоритетом 1 выталкивает из стека все знаки до первого if исключительно. При этом в выходную строку заносится запись m_i УПЛ,

где i – номер очередной нечетной рабочей метки.

Затем метка m_i заносится в таблицу меток; к символу if в вершине стека дописывается m_i (получается запись if m_i).

3. Символ else с приоритетом 1 выталкивает из стека все знаки до первого if исключительно.

В выходную строку добавляется запись m_i+1 БП m_i:,

затем метка m_i+1 заносится в таблицу меток, а в вершину стека к записи if m_i дописывается метка m_i+1 (получается запись if m_i m_i+1).

4. Конец оператора (; или end) выталкивает из стека его содержимое до записи вида if m_i или if m_i m_i+1; такая запись удаляется из стека, а в выходную строку в первом случае записывается m_i, а во втором – m_i+1:.

Пример: Перевести в ОПЗ оператор if a=b then begin a: =0; goto M end else a: =1;

получается

a b = m1 УПЛ a 0:= М БП m2 БП m1: a 1:= m2:.

То же самое получается обходом дерева:

1.7.

Получение ОПЗ для оператора цикла for

Оператор цикла: for <пц>:= <нз> to <кз> do <тц>; можно представить в виде дерева:

Особенности обработки:

1. Символ for играет роль открывающей скобки и имеет приоритет 0. В вершину стека записывается FOR <пц>.

2. Символ to является закрывающей скобкой для предшествующего выражения, поэтому имеет приоритет 1 и выталкивает из стека все знаки до записи FOR. Новая метка m_i добавляется в таблицу меток и к записи FOR – получается FOR <пц> m_i. В выходную строку записывается m_i: <пц>.

3. Символ do является закрывающей скобкой для предшествующего выражения, поэтому имеет приоритет 1 и выталкивает из стека все знаки до записи FOR. Новая метка m_i+1 добавляется в таблицу меток и к записи FOR – получается FOR <пц> m_i m_i+1. В выходную строку записывается <= m_i+1 УПЛ.

4. Конец оператора цикла (символы «;» и end). При их появлении стек очищается. Если при этом встретится запись FOR <пц> m_i m_i+1, то это означает окончание оператора цикла. В выходную строку добавляется запись <пц> <пц> 1 +:= m_i БП m_i+1: После этого запись FOR из стека удаляется.