Обобщение опс

Проблема: для некоторых переменных в стек записывается значение, а для некоторых – указатель.

Проще всего бороться с этой проблемой следующим образом:

В момент вычисления для каждого элемента задаем признак того, что хранится в стеке (значение или ссылка). Тогда при записи в стек переменной мы на всякий случай можем помещать не значение, а ссылку, по которой потом всегда можно извлечь значение. При вычислении результата мы записываем значение и признак «Значение», а не ссылку. Любая операция должна проверять содержимое ячейки стека и выполнять соответствующие действия.

Для чего нужны ссылки? Для операции индексирования элементов массива. (если переменная является массивом)

Если нужен элемент x[i], то пишем (<адрес начала>+i)/

X I ind (x – ссылка, i – выражение). Операция в итоге выдает ссылку.

X[i+1] = x i 1 + ind

Y[i,j] = y i j ind2

Y[0..9,0..19] получаем адрес y[i,j] <адр y> + i*10 +j

Операция с n операндами: A1…..An N Опер

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

Т.е. теперь все правила начинаются с терминальных символов, кроме нуль-порождений.

a1:=a2; a3:=a4 _|_

ОПC: a1a2:=a3a4:=

a1:=a2; a3:=a4 _|_

ОПC: a1a2:=a3a4:=

a1[a2]:=a3[a4+a5]_|_

\\|A'|S |:=|D |a |

|:=| | | |a1|

\\|A'|S |:=|] |S |[ |

|:=| | |[]| | |

\\|A'|S |:=|] |T'|F'|D |a |

|:=| | |[]| | | |a2|

\\|A'|T'|F'|D |a |

|:=| | | |a3|

\\|A'|T'|F'|] |S |[

|:=| | |[]| |

\\|A'|T'|F'|] |T'|F'|D |a |

\\|:=| | |[]| | | |a4|

\\|A'|T'|F'|] |T'|F'|F |* |

\\|:=| | |[]| |* | | |

\\|A'|T'|F'|] |T'|F'|D |a |

\\|:=| | |[]| |* | |a5|

\\|

\\|

ОПС: a1a2inda3a4a5*ind:=

Как должна выглядеть ОПС, чтобы реализовать if then else

If E then R else R

R и R – разные

Пример:

If x<y then x:=y else y:=x

ОПС: x y < m1 jf x y := m2 j y x :=…

Операнд Метка – номер символа ОПС, на который эта метка указывает

Jump – операция перехода, передачи управления

Jf – jump false

J – jump

Трансляторы, с промежуточной формой в виде ОПС работают значительно медленнее.

Как должна выглядеть ОПС, чтобы реализовать цикл while

While E do R

Пример

While x<y do begin x:=x+1; … end

X y < m1 if x x 1 + := … m0 j

Дополним грамматику:

A→if E then_*1 RL|while_*4 E do_*1 R_*5

E→S<S|… E→(S)F’T’<S_<|aDF’T’<S_<

L→λ_*2|else_*3 R_*2

R→A|begin P end|aD:=S|if…|while…

Семантические программы: (для их реализации нужен независимый стек, т.е. у нас уже 3 стека, count - номер очередного символа обратной польской строки, который должен выводиться)

*1

count→в 3й стек,

пусто→ОПС,

jf→ОПС

*2

count→ ОПС[3й стек]

*3

(Count+2)→ОПС[3й стек]

count→ ОПС[3й стек]

пусто→ ОПС,

j→ ОПС

пример:

if a<b then x:=a else x:=b

ab< m1 jf xa := m2 j xb :=

| |

M1 M2

*4

В дополнительный 3ий стек записать номер счетчика count

*5

(count+2)→по ссылке из 3-го стека в ОПС

(По ссылке 3-го стека ) →ОПС

j→ОПС

пример

while a<b do a:=a+1

ab < m1 jf aa1 + := m0 j

| |

M0 m1

Цикла while вполне достаточно, поэтому не будем рассматривать реализацию (генерацию) цикла for и других…

Дополним грамматику операторами read и write.

A→ read H_*read | write S_*write

Где H→aD (скалярная переменная, индекс или пусто)

Разберемся теперь с описаниями переменных.

B→ program V; R _|_

B – вся программа

Описание может быть не одно, а несколько. V – возможная группа описания, U – одиночное описание (описывает либо вещественные либо целые переменные)

V→V;U

U→int_**1 a_**2W|real aW

W→λ_**5|[a_**3]_**4

Замена (исправленная грамматика, для анализатора LL(1)):

V→ int aW U’|real aW U’

U’→;U U’|λ

Описания могут быть и пустыми (например, если программа состоит только из оператора вывода). Тогда получаем

V→ int aW U’|real aW U’| λ

U’→;U U’|λ

**1

Тип – целый

**2

Имя a→в таблицу целых переменных (эта таблица – массив целых, где будут храниться значения этой переменной. Там же можно хранить, например, и само имя)

Для простых переменных этих двух программ достаточно, но для массивов – мало.

**3

Константа а →размер массива

**4

Размер → в таблицу

**5

0-размер →в таблицу

Мы рассмотрели действия для целых. Для вещественных те же действия, только отличается 1ый шаг. Ну и в таблице соответственные изменения.

	имя	значение	количество	Ссылки для массивов
1
2			0
3			>0

Для работы с массивами – Ссылки для массивов, плюс в 4ую семантическую программу пишем:

Выделение памяти, в таблицу (номер переменной, размер в байтах)

Т.е. на выходе не только ОПС, но и сформированные таблицы переменных (т.е. таблицы, содержащие формат данных)