Перевод условных выражений в ОПЗ

Пусть имеется условие вида:

Это условие в языках программирования записывается как условное выражение вида:

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
&
Отношения
+ -
* /
возведение в степень