ОПС для условных, циклических и составных операторов

В условных и циклических операторах должно вычисляться логическое выражение. В самом простом случае это операция сравнения двух арифметических выражений. Всего операций сравнения шесть: =, ≠, <, >, <=, >=. ОПС для любой операции сравнения записывается и выполняется так же, как арифметическая операция, отличие лишь в том, что результат операции сравнения – логическое значение true или false. Далее рассмотрим пример грамматики с условными операторами и генерацию соответствующей ОПС.

Пример 15. Расширим грамматику присваиваний и арифметических выражений с индексами для одно- и двумерных массивов (A – начальный нетерминал), рассмотренную в примере 14.

Порождающее правило для выражения, содержащего сравнение, можно определить с помощью общего обозначения всей группы операций сравнения через <c>:

C → S<c>S

Вначале преобразуем это правило, добавив новый нетерминал D, для того, чтобы при входном символе <c> была замена в стеке нетерминала D, на правую часть, начинающуюся с конкретной операции сравнения:

C → SD

D → <c>S

Затем первое правило преобразуем к нормальной форме Грейбах:

C → (S)VUD | aHVUD

При работе анализатора, если верхний символ в магазине будет C, то при входном символе открывающей скобке в магазин будет копироваться последовательность: (S)VUD, а при входном символе имя или константа – последовательность: aHVUD. Соответственно в дополнительный магазин будет записываться:□□□□□□ или a□□□□.

При верхнем символе D в магазине и при входном символе <c> в магазин будет копироваться: <c>S□, а в дополнительный магазин: □□<c>, для того, чтобы операция сравнения записывалась в ОПС после того, как в ОПС полностью сгенерирован второй операнд.

Условный оператор в полной и сокращенной формах можно определить порождающими правилами, начинающимися с нетерминала A:

A → if C then AE

E → else A | λ

Эти правила позволяют записывать не только условные операторы с присваиваниями (так как нетерминал A может порождать присваивания), но и вложенные условные операторы.

При работе анализатора, если верхний символ в магазине будет A, то при входном символе if в магазин будет копироваться последовательность: if C then AE, а в дополнительный магазин: □□<1>□□. Здесь и далее обозначение <1>, <2> и т.д. означает номер семантической программы, генерирующей ОПС, и которая будет выполняться при выталкивании этого элемента из дополнительного магазина.

При верхнем символе E в магазине и при входном символе else в магазин будет копироваться: else A□, а в дополнительный магазин: <2>□<3>. Если же будет другой входной символ (не else), то в магазин будет копироваться: □, а в дополнительный магазин: <3>.

Семантические программы будут генерировать такие операнды, как метки (<m1>, <m2> и т.д.), и операции условного (<jf> – переход при условии false) и безусловного перехода (<j>). Метка представляет собой номер элемента в генерируемой ОПС, куда будет производиться переход при выполнении операции перехода. Для такой генерации будет использоваться еще один магазин – магазин меток.

Рассмотрим эти семантические программы. В них будет использована переменная k – счетчик (номер) очередного генерируемого элемента ОПС. Этот счетчик увеличивается на 1 всякий раз, как только генерируется очередной элемент ОПС.

Программа <1>.

1. В магазин меток записывается k.

2. В ОПС записывается пустой элемент – место для будущей метки.

3. В ОПС записывается операция <jf> – переход при условии false.

Программа <2>.

1. Через верхний элемент магазина меток, как ссылку на ранее заготовленное место для метки, записывается k + 2.

2. В магазин меток записывается k.

3. В ОПС записывается пустой элемент – место для будущей метки.

4. В ОПС записывается операция <j> – безусловный переход.

Программа <3>.

1. Через верхний элемент магазина меток, как ссылку на ранее заготовленное место для метки, записывается k.

Конец программ.

Если, например, на входе будет цепочка:

if a>b then a:=b else b:=a _┴

то будет сгенерирована следующая ОПС:

a b > <m1> <jf> a b := <m2> <j> b a :=

↑ ↑

<m1> <m2>

Пусть, например, a = 5, b = 2. Тогда при вычислении этой ОПС содержимое магазина интерпретатора будет изменяться таким образом:

В результате получится a = 2, b = 2 (изменилось a).

Если же a = 2, b = 5, то вычисление будет таким:

В результате получится a = 2, b = 2 (изменилось b).

Конец примера.

Рассмотрим пример грамматики с циклами и генерацию ОПС для них.

Пример 16. Расширим грамматику, рассмотренную в примере 15, задав цикл порождающим правилом, начинающимся с нетерминала A:

A → while C do A

При работе анализатора, если верхний символ в магазине будет A, то при входном символе while в магазин будет копироваться последовательность: while C do A□, а в дополнительный магазин: <4>□<1>□<5>.

Рассмотрим семантические программы <4> и <5>.

Программа <4>.

1. В магазин меток записывается k.

Программа <5>.

1. В ОПС записывается метка, значение для которой читается из магазина меток.

2. В ОПС записывается операция <j> – безусловный переход.

Конец семантических программ.

Если, например, на входе будет цепочка:

while a>b do a:=b _┴

то будет сгенерирована следующая ОПС:

a b > <m1> <jf> a b := <m0> <j>

↑ ↑

<m0> <m1>

Пусть, например, a = 5, b = 2. Тогда при вычислении этой ОПС содержимое магазина интерпретатора будет изменяться таким образом:

В результате получится a = 2, b = 2 (цикл выполнился один раз, и изменилось b).

Конец примера.

А теперь рассмотрим пример грамматики с составными операторами и генерацию ОПС для них.

Пример 17. Расширим грамматику, рассмотренную в примере 16, задав составной оператор порождающими правилами, начинающимися с нетерминала A:

A → begin Q end

Q → A ; Q | λ

Т.е. составной оператор представляет собой последовательность из произвольного числа таких операторов, как присваивание, условный, цикл, составной, которые записаны через точку с запятой и взяты в операторные скобки begin – end.

Вторую группу правил (для нетерминала Q) преобразуем к обобщенной нормальной форме Грейбах:

Q → aH := S ; Q | if C then AE ; Q | while C do A; Q | begin Q end A ; Q | λ

При работе анализатора, если верхний символ в магазине будет Q, то при входном символе begin в магазин будет копироваться последовательность: begin Q end ; Q, а в дополнительный магазин: □□□□□. Если же входной символ будет имя или константа, или if, или while, то в магазин будут копироваться последовательности, как для присваивания или условного оператора, или цикла, дополненные двумя символами: ; Q. В дополнительный магазин при этом будут копироваться соответствующие последовательности, дополненные двумя символами: □□.

Конец примера.

Дата добавления: 2015-07-26; просмотров: 120; Нарушение авторских прав

Мы поможем в написании ваших работ!