Бєда Вельмиповажний, VIII ст.н.е.

Числовий вираз – це запис, складений за певними правилами зі сталих, імен, знаків операцій та дужок. Сталі та імена у виразі позначають операнди, а знаки операцій з дужками задають послідовність операцій, виконання яких породжує значення виразу. У цьому розділі ми займемося питанням, як за виразом відтворити виконання операцій та обчислити його значення.

Зробимо деякі уточнення. Будемо вважати, що структура виразів і правила вилучення зайвих дужок відповідають означенням із підрозділу 2.2.4. Вирази містять:

- цілі й дійсні сталі та імена змінних;

- символи "+", "-", "*", "/" двомісних арифметичних операцій;

- імена (ідентифікатори) одномісних функцій sin та cos;

- дужки "(" та ")".

Звичною формою виразів є інфіксна, коли знак бінарної операції записується між позначеннями операндів цієї операції, наприклад, a+b. Розглянемо запис знаків операцій після позначень операндів, тобто постфіксний запис, наприклад, ab+. Такий запис має також назву зворотного польського, оскільки його запропонував польський логік Ян Лукасевич. Далі словосполучення "зворотний польський запис" позначатимемо ЗПЗ.

Опишемо відповідність між звичними інфіксними виразами та їх ЗПЗ. Нехай E, E₁, E₂ позначають вирази в інфіксній формі, <op₁>, <op₂> – знаки унарної та бінарної операцій, <opf> – ім'я функції. Виразу E залежно від його вигляду відповідає ЗПЗ L(E) згідно з правилами:

E	L(E)
стала чи ім'я змінної	E
'(' E1 ')'	L(E1)
<op1>E1	L(E1) <op1>
E1<op2>E2	L(E1) L(E2) <op2>
<opf>'('E1')'	L(E1) <opf>

Вираз є послідовністю символів – цифр, букв та інших знаків. Але вони утворюють лексичні одиниці, або лексеми, чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Будемо дивитися на вираз саме як на послідовність лексем, які ми одержуємо послідовним читанням виразу зліва направо.

Розглянемо докладніше побудову вихідної послідовності лексем L(E) за лексемами виразу E.

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

Порядок знаків операцій змінюється: у вхідному виразі вигляду E₁ op₂ E₂ знак op₂ передує знакам операцій виразу E₂, а у вихідному виразі L(E₁) L(E₂) op₂ – навпаки. Тому знак op₂ треба запам'ятати, видати L(E₂), а після нього – op₂. Знаки операцій у виразах E₁ та E₂ потрібно так само зберігати й видавати після ЗПЗ виразів, що позначають операнди цих операцій. Таке змінювання порядку знаків досягається за використання магазина, або стека; знаки операцій надходять у нього й вилучаються у вихідний вираз за принципом "останнім увійшов – першим вийшов" ("Last In – First Out", або LIFO).

На порядок знаків у вихідному виразі впливає їх старшинство, або пріоритет:

Операція '*' старша за '+', тому в першому виразі операція '+' застосовується до значень a та b*c. У другому виразі старшинство '+' та '-' однакове, операції мають властивість лівостороннього зв'язування, тому '+' застосовується до a і b, а '-' – до a+b і c.

Отже, коли у вхідній послідовності читається знак операції op₂, з верхівки магазина треба видати у вихідний вираз усі знаки, пріоритети яких не нижчі від пріоритету op₂ (усі вони є знаками з виразу E₁), і тільки після цього запам'ятати op₂ у магазині. Якщо пріоритет знака з верхівки магазина нижче ніж у op₂, то op₂ записується в магазин, оскільки має появитися у вихідному виразі раніше.

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

(вихідна послідовність лексем;

Приклад 20.1. Початок перетворення виразу a+b*c зображається послідовністю трійок

( ; ; a + b * c ) – початковий стан: вихідна послідовність і магазин порожні;

( a ; ; + b * c ) – ім'я перенесено у вихідну послідовність;

( a ; + ; b * c ) – знак перенесено в магазин;

( a b ; + ; * c ) – ім'я перенесено у вихідну послідовність.

Після цього знак '*' вміщується в магазин над знаком '+':

Пріоритет операції '*' вищий від '+', тому b є операндом '*', а не '+'.

При перетворенні виразу a+b-c результатом читання його початку a+b буде

Пріоритети '+' і '-' рівні, тому b пов'язується з операцією '+' ліворуч.ç

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

20.1.* Побудувати ЗПЗ виразів за правилами з п.20.2.1 та імітувати процес перетворень виразів у вигляді послідовності трійок (ЗПЗ; магазин; вхід):

а)a+(b-c)*b*c; б) a-(b+c*d); в) a+b-(c+d).

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

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

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

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

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

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

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

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

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

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

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

20.2.* Імітувати процес обчислення ЗПЗ:

а) 1 2 3 4 + - *; б) 1 2 3 + 4 - *; в) 1 2 + 3 - 4 *.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20.4. Означити тип записів для подання деяких геометричних фігур

б) в просторі – прямого прямокутного паралелепіпеда, правильної трикутної та чотирикутної піраміди, прямого кругового циліндра, конуса та сфери.

20.5. Означити (Р)БНФ, що задають синтаксис означень типу записів із варіантами.

В обох алгоритмах неважко виділити операції, які виконуються над послідовністю та магазином лексем – додавання елементів, їх вилучення тощо. Нехай усі ці операції разом із необхідними означеннями, зокрема, типу послідовності лексем Sqlx, зібрано в модулі Sllx. Використання цього модуля укажемо в програмі, а його розробка залишається вправою.

Крім модуля Sllx, у програмі використовується модуль Glx. У ньому мають міститится всі означення, необхідні для читання виразу "з зовнішнього світу". Це читання буде здійснюватися багаторазовим викликом підпрограми getlx читання чергової лексеми виразу. Розробку цього модуля представлено в підр. 20.9–20.10.

Побудову ЗПЗ оформимо функцією ipllx, з якої повертається значення true, якщо в процесі читання виразу не було якихось помилок, і false у противному разі. Побудована послідовність запам'ятовується в змінній Llx. Значення виразу обчислюється за виконання виклику функції llxval і друкується. Отже, програма має вигляд:

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

Вважатимемо, що модуль Sllx містить усе необхідне для роботи з послідовністю та магазином лексем, які подаються змінними типів Sqlx і Stlx відповідно. Ініціалізація порожніх послідовності та магазина задається процедурами із заголовками відповідно

Крім того, функція prior задає обчислення пріоритетів лексем.

Читання чергової лексеми задається в модулі Glx функцією getlx, заголовок якої

Розроблювана функція ipllx матиме одну особливість. Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; за алгоритмом вони записуються у вихідну послідовність. У цій функції весь вхідний вираз штучно "береться в дужки". Перед його читанням у магазин записується відкриваюча дужка, що відмічає його дно. В кінці магазин лексем обробляється так, ніби на вході з'явилася закриваюча дужка, тобто всі знаки до відкриваючої дужки виштовхуються та копіюються у вихідну послідовність.

end; {case та while}

Ця підпрограма має суттєвий недолік. Справа в тім, що вона не задає структурного, або синтаксичного, аналізу вхідного ланцюжка символів. Наприклад, недопустима вхідна послідовність лексем "1 2 3 + *" буде прочитана та оброблена як інфіксний вираз, за ним буде створено ЗПЗ "1 2 3 * +", а далі обчислено значення 7, що не має ніякого змісту.

Поняття, необхідні для аналізу структури виразів, розглядаються в розділі 21.

Напишемо функцію llxval обчислення значення виразу за його ЗПЗ, що подається послідовністю лексем. У цій функції використовуються засоби з модуля SLlx:

-процедура добування й вилучення першого елемента послідовності лексем із заголовком

У підпрограмах розроблюваного модуля читання лексем доведеться мати справу з множинами символів. Подання та обробку множин символів та значень інших перелічуваних типів у мові Паскаль зручно задавати з використанням спеціальних типів множин.

Стала-множина задається в дужках [] переліком елементів або діапазонів. Наприклад, множина чисел {1, 2, 3, 5} подається як [1, 2, 3, 5] або [1..3, 5], порожня множина Æ – як [], множина символів {'a', 'i', 'j', 'k', 'l', 'm', 'n'} – як ['a', 'i'..'n'].

Якщо T задає перелічуваний тип, то вираз set of T означає множинний тип. Елементами його носія є підмножини носія типу T. Наприклад, носій типу set of Boolean складається з 4-х множин бульових значень: [], [false], [true], [false, true]; носій типу set of 'a'..'z' – з 2²⁶ підмножин малих латинських літер. Тип T називається базовим для типу set of T.

В історії розвитку мови Паскаль склалося так, що носій базового типу не може мати більше 256 елементів. Наприклад, вираз set of 1..512 недопустимий. У внутрішньому зображенні множини кожному елементу носія базового типу відповідає 1 біт і дані множинних типів займають не більше 256/8 = 32 байтів.

Найпростішими виразами типу множина є сталі, тобто списки виразів і діапазонів базового типу в квадратних дужках []. Інші вирази будуються з однотипних множинних сталих і змінних та знаків бінарних операцій '+', '*', '-', що позначають відповідно об'єднання, перетин і різницю множин.

Приклад. Нехай за дії означення var v : set of 0..9 виконано оператор присвоювання v:=[1..3]. Тоді вираз v+[2..4] має значення [1..4], v*[2..4] – значення [2..3], v-[2..4] – значення [1].ç

Бульові вирази вигляду S₁ = S₂ (S₁ <> S₂) задають перевірку на рівність (нерівність) значень однотипних множинних виразів S₁ і S₂. Аналогічно вирази S₁ <= S₂ (S₁ >= S₂) задають перевірку включення S₁ у S₂ (S₂ в S₁). Наприклад, значеннями виразів [1..3]=[1, 2, 3] та [1, 2]<=[1..3] є true, а виразів [1]>=[1..2] та [1, 2]<>[2, 1] – false.

Булів вираз вигляду e in S, де тип виразу e є базовим для множинного типу виразу S, задає перевірку належності значення e множині S.

Приклад 20.4. Нехай діє означення типів рядків Str і множин символів SS = set of char. Тоді:

20.6. Написати вираз, що задає перевірку, чи непорожній перетин двох множин.

20.7. Означити (Р)БНФ, що задають синтаксис

20.8. Написати процедуру друкування елементів

а) множини символів; б) множини цілих із діапазону 1..256.

20.9. Написати програму друкування простих чисел від 2 до 256 із застосуванням решета Ератосфена: з множини всіх чисел викреслюються числа, кратні 2, потім кратні 3 тощо.

Вираз є послідовністю лексичних одиниць (лексем) чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Виділення лексем із виразу називається його лексичним аналізом. Лексеми виділяються в ході побудови внутрішнього подання виразу багаторазовим розв'язанням задачі добування чергової лексеми виразу.

Розв'язання задачі добування чергової лексеми буде описано функцією getlx. За її виконання обчислюється ознака того, чи є ще лексема у вхідній послідовності символів, і за її наявності вона присвоюється параметру-змінній функції. Помістимо функцію getlx і допоміжні для неї засоби в модуль Glx.

відшукати перший символ лексеми;

if відшукали

зафіксувати відсутність лексеми.

У цьому модулі треба означити все необхідне для читання лексем. За межами модуля використовуються тип st8 імен, типи лексем Tlx та їх різновидів Ttlx, а також функція getlx. Означення цих типів та заголовок функції мають бути в інтерфейсному розділі модуля.

У розділі реалізації означимо необхідні сталі, а також масив Namf, що зберігає множину імен функцій. Означимо змінні Bcon, Bnam, Bops, Bpar та Blex для зберігання множин символів, якими починаються лексеми відповідних різновидів, та їх об'єднання. Ініціалізацію всіх цих змінних задає процедура glxinit, виклик якої записується в розділі ініціалізації модуля. Останньою в розділі реалізації записується основна функція getlx, а перед нею – допоміжні для неї підпрограми та інші означення.

читання й повернення наступного символу тексту задає функція getc.

Нехай останній прочитаний символ тексту, який ми називаємо поточним, зберігається в глобальній у модулі змінній tempc. Вона ініціалізується символом ' ' (пропуск), тобто перед виразом штучно додається пропуск.

Добування лексеми починається з пошуку її першого символу у вхідній послідовності. Нехай

пошук першого символу описується функцією getbglx.

З її виклику повертається або перший символ лексеми, або, коли лексеми вичерпано, символьна стала chr(0), яку можна вважати "фіктивним символом". Іменування цієї сталої ім'ям finch додамо до означень модуля.

Добування сталих та імен (елементів типу real і st8) опишемо функціями відповідно getcon і getnam.

Побудуємо функції getcon і getnam так, щоб після виконання їх виклику поточним був символ, наступний за останнім символом добутої лексеми. У такому разі до обробки знаків операцій і дужок додамо указання переходу до наступного поточного символу tempc := getc. Імена, що не є іменами функцій із масиву Namf, будемо вважати помилковими лексемами. Якщо лексема подається змінною lx типу Tlx, то залежно від першого символу лексеми потрібно виконати такі дії:

if lx.name представлено в Namf then lx.stl := nam

інше ® lx.stl := err; lx.wrlx := tempc; tempc := getc;

В усіх випадках повертається значення true – ознака наявності лексеми. За символу finch повертається false. Наведена залежність є основою функції getlx:

Алгоритм процедури getbglx дуже простий: поки поточний символ не потрапив у множину Blex перших символів лексем, викликається функція getc для одержання нового поточного символу. Якщо при цьому вираз вичерпується, то наступним поточним вважається "фіктивний символ" finch.

Функція getcon задає читання символів сталої з образу та побудову за ними відповідного значення типу real. Нехай синтаксис сталої задається метавиразом <D> { <D> } [ '.' { <D> } ]. Розглянемо побудову значення типу real за сталою. Цифри до крапки задають цілу частину числа. Значення чергової цифри додається до результату обробки попередніх цифр, помноженого на 10. Перед обробкою першої цифри результатом є 0. Крапка пропускається, а значення цифр праворуч від неї множаться на відповідні від'ємні степені числа 10 і додаються до числа:

Додамо змінну cp типу Tcp=(ip, fp, out), елементи якого позначають місця поточного символу tempc в цілій (ip) та дробовій (fp) частині або за межами сталої (out). Спочатку cp=ip. Залежність її наступного значення від попереднього та від поточного символу tc подамо таблицею, в якій стрілка ліворуч відмічає початкове значення ip (табл.20.1).

Нехай змінна v зберігає результат обробки попередніх цифр, d – від'ємні степені числа 10 (спочатку v=0, d=1). Нехай num(<D>) позначає вираз ord(<D>)-ord('0'). Подамо обробку поточного символу tempc й змінювання значень cp таблицею 20.2. Відсутність присвоювань змінній cp у деяких клітинах табл. 20.2 означає, що її значення не змінюється.

За наведеною таблицею функція getcon записується з уживанням оператора case майже механічно:

end; { оператора case cp of та циклу while}

Нарешті ми уточнимо, як читаються символи виразу з тексту, написавши функцію getc добування наступного символу.

Її розробку почнемо з уточнення задання виразу. Нехай вираз записано в текстовому файлі, у кількох рядках, довжини яких не більше 80. Ознакою кінця виразу є кінець файла. Суміжні лексеми відокремлюються довільними послідовностями пропусків, можливо, порожніми.

Скористаємося обмеженням на довжину рядків тексту та організуємо читання тексту не окремими символами, а рядками. Черговий рядок стає значенням змінної рядкового типу Str, яка називається образом вхідного рядка, або буфером. Саме з буфера символи по одному добуваються за викликів функції getc.

Функцію getc разом із іншими необхідними означеннями помістимо в окремий модуль Inbuf. Створюючи цей модуль, ми повністю відокремлюємо обробку символів виразу від їх конкретного джерела – файла на диску, клавіатури чи ще чогось.

Додамо указання використання модуля Inbuf до модуля Glx.

Перенесемо означення імен finch і tempc з модуля Glx до модуля Inbuf.

Ініціалізацію змінних модуля задає процедура bufinit, виклик якої записано в розділі ініціалізації. Вона також забезпечує можливість задати ім'я файла, з якого треба читати вираз. Функція newln описує заповнення буфера новим вхідним рядком та повернення його першого символу.

buf := ''; {спочатку буфер – порожній рядок}

writeln('Уведіть ім''я текстового файла з виразом'); readln(nam);

Наведемо, нарешті, функції getc і newln.

else { рядок вичерпано } tempc := newln;

Задачі

20.10. Написати підпрограму getnam читання імен довжиною до 8 з успадкуванням модуля Inbuf.

20.11. Написати підпрограму getint читання елементiв типу integer з успадкуванням модуля Inbuf

б) із урахуванням діапазону цілих -2147483648..2147483647 або -32768..32767.

20.12. Послідовність символів набирається в одному рядку довжиною до 80. Написати програму перевірки, чи утворює ця послідовність дійсну сталу вигляду

У задачах 20.13-20.18 вхідний текст набирається на клавіатурі в кількох рядках, довжина яких не більше 80. Ознакою кінця є порожній рядок. У програмах рекомендується успадкувати модуль буферизованого читання (підрозділ 20.3).

20.13. Текст містить вираз, лексеми якого відокремлюються пропусками в довільній кількості n³ 0. Імена у виразі починаються символом із діапазону 'a'..'z'. Синтаксис виразів задається сукупностями РБНФ, у яких нетермінал <ід> позначає імена. Варіанти виразів і відповідних РБНФ:

<елем.кон'юнкція> ::= <елем.множник> { '&' <елем.множник> }

КНФ ::= '1' | '(' <елем.диз'юнкція> ')' { '&' '('<елем.диз'юнкція>')' }

<елем.диз'юнкція> ::= <елем.доданок> { ' or ' <елем.доданок> }

<Пол-Жег> ::= '0' | <доданок> { '+' <доданок> }

<множник> ::= <ід> { '*' <ід> };

<присв> ::= <лів-частина> ':=' <прав-частина>

<прав-частина> ::= <ід> | <ід> { <знак-операц><ід> }

<знак-операц> ::= '+' | '-' | '*';

<означ-змінних> ::= 'var' <список-озн> ';'

<означ> ::= <список-ід> ':' <ід-типу>

<ід-типу> ::= <ід>;

<многочлен> ::= '0' | <одночлен> { <знак-операц><одночлен> }

<множник> ::= <ід> [ '^' <показник> ]

<показник> ::= <цифра-2>

<знак-операц> ::= '+' | '-'

<цифра-2> ::= '2' | '3' | … | '9'

20.14. Текст містить слова в алфавіті 'a'..'z' і цілі сталі, відокремлені пропусками, дужками '(', ')' та знаками пунктуації в довільній кількості n³ 0. Слова й сталі з рядка в рядок не переносяться. Знаками пунктуації є ':', ';', '.', ','. Написати програму

ж) перевірки збігу за змістом двох текстів, тобто чи мають вони той самий порядок слів і знаків пунктуації, але можуть відрізнятися кількістю пропусків та розташуванням по рядках.

20.15. Текст містить літерали, коментарі, слова й сталі, відокремлені пропусками в довільній кількості. Літералом є послідовність символів у апострофах (апостроф усередині літерала позначається подвоєним апострофом ''); коментар – це послідовність символів, що починається '(*', закінчується '*)' і не містить '*)' усередині. Якщо послідовність символів у апострофах записана в коментарі, то вона не є літералом. Аналогічно "коментар" у літералі не є коментарем. Коментарі й літерали можуть продовжуватися в кількох рядках. Написати програму

20.16. Текстом є дужковий вираз, складений зі сталих та знаків операцій між ними. Сталі й знаки відділяються пропусками в довільній кількості n ³ 0.

+, -,

*, div, mod,

+, -,

*, /,

!! ("або"), -> (імплікація), ++ (додавання за модулем 2, тобто "виключне або"),

! ("ні").

20.17. Текстом є послідовність операторів присвоювання, в яких ліворуч записані ідентифікатори, а праворуч – дужкові вирази зі сталими, знаками операцій та ідентифікаторами, що були ліворуч у попередніх операторах. Написати програму друкування стану пам'яті, означеного на ідентифікаторах, після кожного присвоювання. Варіанти (а-в) типів сталих і наборів знаків операцій відповідають варіантам (а-в) попереднього завдання.

20.18. Рекурентна числова послідовність задається рекурентним співвідношенням у вигляді

<рек-співв> ::= <порядок>

<початкова-умова>

де <порядок> задає порядок співвідношення (натуральне k), <ім'я> є ім’ям послідовності (це ідентифікатор, наприклад, S), <початкова-умова> – послідовність із k сталих, які задають S₁,…,S_k, <вираз> – дужковий вираз E зі сталими та операндами вигляду S(-1),…,S(-k), що позначають S_i-1, … , S_i-k у рівнянні

S_i = E ( S_i-1, … , S_i-k ).

Написати програму обчислення елемента рекурентної послідовності, номер якого задається окремо. Варіанти (а-в) типів сталих та наборів знаків операцій відповідають варіантам (а-в) завдання 20.16.