Перевод условных выражений в ОПЗ
Пусть имеется условие вида:
Это условие в языках программирования записывается как условное выражение вида:
y=if x=<0 then a+b else c*d;
В отличие от простых выражений, где порядок выполнения действий определяется старшинством операций или скобками и в процессе выполнения программы этот порядок не меняется, в условных выражениях он изменяется в зависимости от значения условия (в нашем примере x <= 0).
Таким образом, понятие условного выражения должно быть также введено в ОПЗ представления исходной программы. Для этого вводятся так называемые динамические деревья.
Рассмотрим ряд понятий и особенностей для динамических деревьев:
- узлы и ветви деревьев могут помечаться метками;
- пустой узел - это такой узел, в котором отсутствует операция. Из пустого узла может исходить любое количество ветвей. Пустой узел вводится для объединения нескольких последовательных действий или разветвления некоторого вычислительного процесса;
- условный оператор перехода по значению 'ложь'. Оператор имеет следующее представление:
<условие> <метка> УПЛ
- оператор безусловного перехода:
<метка> БП
С учетом введенных понятий ОПЗ выражения
y+(IF a>b THEN x+y ELSE x+2)
принимает следующий вид:
yab>M1 УПЛ x1+M2 БП М1: x2+M2:+
Для обобщения алгоритма Дейкстры на условные выражения требуется модифицировать таблицу приоритетов, исходя из следующих соображений. Нетрудно заметить, что IF играет роль открывающей скобки, а THEN и ELSE - запятых. Теперь с учетом данного обстоятельства модифицированная таблица приоритетов примет следующий вид (табл. 2.4).
Таблица 2.4
| Входной элемент | Приоритет |
| IF ( [ АЭМ Ф | |
| , ) ] THEN ELSE | |
| V | |
| & | |
| Отношения | |
| + - | |
| * / | |
| возведение в степень |
Обработка символов операций будет дополнена правилами обработки ключевых слов условных выражений следующим образом:
- символ IF из входной строки заносится в стек;
- символ THEN выталкивает в выходную строку все операции из стека до ближайшего IF. В стеке к символу IF добавляется рабочая метка Мi и после этого в выходную строку записывается часть Мi УПЛ;
- ELSE выталкивает из стека все символы до ближайшего IF Мi. IF Mi превращается в IF Mi+1 и в выходную строку выталкивается часть Мi+1 БП Мi:
- Символ «)» указывает на конец условного выражения и выталкивает из стека все символы до ближайшего символа «(», при этом сам IF уничтожается, а в выходную строку помещается метка Мi+1: .
Например, для приведенного выражения процесс перевода в ОПЗ имеет вид:
| Выходная строка | y | a | b | > | M1 УПЛ | x | + | M2 БП M1: | x | + | M2: | - | ||||||||
| С Т Е К | - | ( | IF | > | IF M1 | + | IF M2 | + | ||||||||||||
| - | ( | IF | ( | IF M1 | ( | IF M2 | ||||||||||||||
| - | - | ( | - | ( | - | |||||||||||||||
| - | - | |||||||||||||||||||
| Входная строка | y | - | ( | IF | a | > | b | THEN | x | + | ELSE | x | + | ) | g |
Примечание. Описанная выше обработка условных выражений связана с правильной организацией передачи управления внутри объектного кода, что и составляет внутреннюю семантику обработки условных выражений в ОПЗ.
Перевод оператора присваивания в ОПЗ
Формат оператора присваивания имеет вид:
<переменная> := <выражение>
а его ОПЗ представляется следующим образом:
<переменная> <выражение> :=
Для включения в ОПЗ оператора присваивания необходимо решить вопрос о месте этого оператора в таблице приоритетов. При выборе приоритета будем руководствоваться следующими соображениями:
- приоритет оператора присваивания должен быть выше, чем у любой арифметической или логической операции, чтобы знаки не могли вытолкнуть оператор присваивания из стека;
- приоритет должен быть меньше, чем у знака ';'.
С учетом этого, таблица приоритетов операций принимает следующий вид (табл. 2.5).
Таблица 2.5
| Входной элемент | Приоритет |
| IF ( [ АЭМ Ф | |
| , ; ) ] THEN ELSE | |
| := | |
| V | |
| & | |
| Отношения | |
| + - | |
| * / | |
| возведение в степень |