Реферат на тему:

Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами

1. Алгоритм обчислення виразу за його ЗПЗ

Позначення операндів у ЗПЗ передують знакам операцій, які до них
застосовуються, тому при читанні ЗПЗ спочатку обчислюються та
запам’ятовуються операнди, а потім до них застосовується операція.

ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але
тепер це вже магазин операндів, а не знаків операцій. Числа, що є
значеннями сталих чи змінних, переносяться в магазин. Якщо черговою
лексемою є знак двомісної операції, то з магазина вилучаються два верхні
елементи, і результат застосування операції до цих значень записується в
магазин. За знаку одномісної операції з магазина вилучається лише один
елемент. Ім’я функції на вході задає її застосування до елемента з
верхівки магазина та вміщення результату в магазин. Після закінчення
вхідного списку лексем у магазині зберігається лише одне число –
значення всього виразу.

Процес обчислення можна подати послідовністю пар вигляду

(магазин операндів; непрочитана частина ЗПЗ).

Спочатку магазин порожній, а в кінці в ньому єдине значення.

Приклад 1. Обчислення ЗПЗ «2 3 * 4 +» подається так:

( ; 2 3 4 * — );

( 2 ; 3 4 * — ) – число 2 перенесено в магазин;

( 2 3 ; * 4 -) – те саме з 3;

( 6 ; 4 — ) – до операндів 2 і 3 застосовано множення;

( 6 4 ; — ) – число 4 перенесено в магазин;

(2 ; ) – до операндів 6 і 4 застосовано віднімання.

За обчислення ЗПЗ «2 3 4 * -» утвориться така послідовність:

( ; 2 3 4 * — );

(2 3 4 ; * -) – перенесено три числа в магазин;

(2 12 ; — ) – 3 і 4 перемножено;

(-10 ; ) – від 2 віднято 12. ?

Уточнимо обробку ЗПЗ таким алгоритмом:

while на вході є лексема C do

case C of

стала чи ім’я змінної: заштовхнути її значення в магазин;

знак двомісної операції: виштовхнути з магазину два верхні елементи;
обчислити результат застосування до них операції зі знаком С та
заштовхнути результат в магазин;

знак одномісної операції: виштовхнути з магазину верхній елемент;
обчислити результат застосування до нього операції зі знаком С та
заштовхнути результат в магазин;

end;

видати верхній елемент магазина як результат.

2. Записи з варіантами.

У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище
алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми
скористаємося зручним засобом мови Паскаль, який досі не розглядався, –
це записи з варіантами.

У нашій задачі ЗПЗ виразу будується у вигляді послідовності лексем.
Послідовність можна подати масивом, списком, або файлом. У будь-якому
разі це буде послідовність однотипних елементів. Проте у виразах є
лексеми чотирьох різновидів: сталі, імена, знаки операцій і дужки.
Природно у ЗПЗ зберігати не сталі чи імена змінних, а їх значення. Знаки
операцій та дужки є символами, а імена функцій – рядками. Отже,
доводиться говорити про кілька різних типів для подання лексем. Але
незрозуміло, як різнотипні елементи зібрати в одну послідовність.

Одним із розв’язань цієї суперечності є використання записів із
варіантами. Подивимося на лексеми як на пари вигляду (різновид,
значення). Наприклад, стала 12 подається як (стала, 12), ім’я функції
sin – (ім’я, ‘sin’), відкриваюча дужка – як (дужка, ‘(‘). Для задання
множини різновидів лексем означимо тип-перелік Ttlx:

type Ttlx = (con, nam, ops, par, err).

Ці імена є скороченнями від constant, name, operation sign, parenthesis
та error – стала, ім’я, знак операції, дужка та помилка відповідно.

Отже, нам потрібен тип пар, першими компонентами яких є типи лексем,
тобто елементи з переліку Ttlx, а другими – значення відповідних типів.
У мові Паскаль для подання пар природно скористатися структурними
типами, яких нам потрібно 5, разом із типом для помилкових лексем.

Об’єднати різні типи структур в один можна за допомогою означення типу
структур (записів) із варіантами. Вираз, що задає тип таких записів,
схожий на вирази, якими задаються типи записів, або структур. Його
загальний вигляд такий:

record

спільна частина;

варіантна частина

end;

У спільній частині означаються поля, наявні в усіх об’єднуваних типах
(їх список може бути порожнім). У варіантній частині після ключового
слова case означається селектор – додаткове поле перелічуваного типу.
Насправді воно є спільним в усіх об’єднуваних типах. Потім записуються
значення селектора разом із відповідними варіантами наборів полів, якими
відрізняються об’єднувані типи. Варіантом є список означень полів,
записаний у дужках.

Звернімо увагу, що слово end в означенні лише одне – можна вважати, що
воно є «закриваючою дужкою», яка відповідає як record, так і case.

Приклад 2. Нехай у виразах імена й помилкові лексеми мають не більше
восьми символів, і діють означення типів st8 = string[8] та Ttlx. Тип
лексем задається означенням

type Tlx = record { спільна частина порожня }

case stl : Ttlx of

con : (numb : real);

nam : (name : st8 );

ops : (sig : char);

par : (prt : char);

err : (wrlx : st8 )

end

Тут stl є ім’ям селектора, а в дужках указано варіанти – списки означень
полів, поставлені у відповідність його значенням. Щоправда, тут усі ці
списки мають по одному елементу.?

Тип селектора задається тільки ім’ям, а імена полів повинні бути
унікальними в межах означення типу запису. Синтаксис списку полів
варіанта такий самий, як і списку полів запису (зокрема, можливі спільна
й варіантна частини з таким самим синтаксисом).

Приклад. 3. Означити тип записів для подання таких відомостей про
студента: прізвище, ім’я, курс, оцінки останньої сесії, а також рік
народження та відношення до військової служби юнаків, або знак Зодіаку
та колір очей дівчат.

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

type Sex=(male, female); {тип «стать» – чоловіча або жіноча}

type Student=

record

surname, name : string[30]; {прізвище та ім’я – рядкові}

course : integer; marks : string[10]; {курс та оцінки}

case sexslc : Sex of

male : (year : integer; military : boolean);

female : ( Zodiak : string[10]; eyecolor : string[10])

end ?

Під варіантні частини змінних-записів виділяється стільки пам’яті,
скільки її потрібно для «найдовшого» з варіантів. Так, селектор змінних
типу Tlx займає 1 байт, а довжина варіантної частини визначається
«найдовшим» типом st8 (9 байтів у Турбо Паскаль). Дані типу Student
займають 31+31+1+11+11=85 байтів.

Селектор призначений для відображення типу варіантної частини запису.
Але доступ до ділянок пам’яті варіантної частини запису здійснюється
через імена полів незалежно від значення селектора в записі, тобто
засоби мови не забезпечують відповідності значень селектора й варіантів
у змінних-записах. Тому потрібна особлива увага, щоб не робити помилок
на зразок наступної:

var lx : Tlx; a : real; …

lx.stl := con;

lx.nam := ‘sin’; { створено невідповідність !!! }

if lx.stl = con then a:= lx.numb { значення a – ??? }

Похожие записи