ОБЧИСЛЕННЯ ВИРАЗІВ
У ПРОГРАМУВАННІ
1. Задача обчислення виразів
Числовий вираз – це запис, складений за певними правилами зі сталих, імен, знаків операцій та дужок. Сталі та імена у виразі позначають операнди, а знаки операцій з дужками задають послідовність операцій, виконання яких породжує значення виразу. У цьому розділі ми займемося питанням, як за виразом відтворити виконання операцій та обчислити його значення.
Зробимо деякі уточнення. Будемо вважати, що структура виразів і правила вилучення зайвих дужок відповідають означенням із підрозділу 2.2.4. Вирази містять:
- цілі й дійсні сталі та імена змінних;
- символи "+", "-", "*", "/" двомісних арифметичних операцій;
- імена (ідентифікатори) одномісних функцій sin та cos;
- дужки "(" та ")".
Задачу обчислення значення виразу розіб'ємо на дві підзадачі:
1) прочитати вираз і побудувати його внутрішнє подання;
2) за внутрішнім поданням виразу обчислити його значення.
Для початку будемо вважати, що вирази читаються з "зовнішнього світу", не уточнюючи поки що, звідки саме.
Існує кілька способів представити послідовність операцій, задану виразом. Один із них – це подання виразу його зворотним польським записом. Саме ним ми і скористаємося.
2. Зворотний польський запис
та алгоритм його побудови
2.1. Зворотний польський запис.
Звичною формою виразів є інфіксна
, коли знак бінарної операції записується між позначеннями операндів
цієї операції, наприклад, a
+b
. Розглянемо запис знаків операцій після позначень операндів
, тобто постфіксний запис
, наприклад, ab
+. Такий запис має також назву зворотного польського
, оскільки його запропонував польський логік Ян Лукасевич. Далі словосполучення "зворотний польський запис" позначатимемо ЗПЗ.
Опишемо відповідність між звичними інфіксними виразами та їх ЗПЗ. Нехай E
, E1
, E2
позначають вирази в інфіксній формі, <op1
>, <op2
> – знаки унарної та бінарної операцій, <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
( b
* c
) = b
c
* ;
L
( -(-a
) ) = L
( (-a
)) - = a
--;
L
( a
+ b
* c
) = L
(a
) L
(b
*c
) + = a
b
c
* + ;
L
( a
+ b
- c
) = L
( a
+ b
) L
( c
) - = a
b
+ c
- ;
L
( 1-sin( a
+b
) ) = L
(1) L
( sin( a
+b
) ) - = 1 L
( a
+b
) sin - =1 a
b
+ sin - .
Вирази зі знаками унарних операцій далі не розглядаються.
2.2. Алгоритм побудови ЗПЗ.
Вираз є послідовністю символів – цифр, букв та інших знаків. Але вони утворюють лексичні одиниці, або лексеми, чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Будемо дивитися на вираз саме як на послідовність лексем, які ми одержуємо послідовним читанням виразу зліва направо.
Розглянемо докладніше побудову вихідної послідовності лексем L
(E
) за лексемами виразу E
.
З правил побудови L
(E
) випливає, що порядок елементарних позначень операндів (сталих чи імен змінних) у виразах E
і L
(E
) однаковий, тому сталі й імена змінних можна одразу записувати у вихідну послідовність.
Порядок знаків операцій змінюється: у вхідному виразі вигляду E
1
op2
E
2
знак op2
передує знакам операцій виразу E
2
, а у вихідному виразі L
(E
1
) L
(E
2
) op2
– навпаки. Тому знак op2
треба запам'ятати, видати L
(E
2
), а після нього – op2
. Знаки операцій у виразах E
1
та E
2
потрібно так само зберігати й видавати після ЗПЗ виразів, що позначають операнди цих операцій. Таке змінювання порядку знаків досягається за використання магазина
, або стека
; знаки операцій надходять у нього й вилучаються у вихідний вираз за принципом "останнім увійшов – першим вийшов
" ("L
ast I
n – F
irst O
ut", або LIFO
).
На порядок знаків у вихідному виразі впливає їх старшинство, або пріоритет:
L
( a
+ b
* c
) = a
b
c
* + ; L
( a
+ b
- c
) = a
b
+ c
- .
Операція '*' старша за '+', тому в першому виразі операція '+' застосовується до значень a
та b
*c
. У другому виразі старшинство '+' та '-' однакове, операції мають властивість лівостороннього зв'язування, тому '+' застосовується до a
і b
, а '-' – до a
+b
і c
.
Отже, коли у вхідній послідовності читається знак операції op2
, з верхівки магазина треба видати у вихідний вираз усі знаки, пріоритети яких не нижчі від пріоритету op2
(усі вони є знаками з виразу E
1
), і тільки після цього запам'ятати op2
у магазині. Якщо пріоритет знака з верхівки магазина нижче ніж у op2
, то op2
записується в магазин, оскільки має появитися у вихідному виразі раніше.
Процес побудови ЗПЗ виразу можна подати послідовністю трійок вигляду
(вихідна послідовність лексем
;
магазин
;
непрочитана частина виразу
).
Верхівку магазина будемо вказувати праворуч.
Приклад 1.
Початок перетворення виразу a
+b
*c
зображається послідовністю трійок
( ; ; a
+ b
* c
) – початковий стан: вихідна послідовність і магазин порожні
;
( a
; ; + b
* c
) – ім'я перенесено у вихідну послідовність
;
( a
; + ; b
* c
) – знак перенесено в магазин
;
( a
b
; + ; * c
) – ім'я перенесено у вихідну послідовність
.
Після цього знак '*' вміщується в магазин над знаком '+':
( a
b
; + * ; c
).
Пріоритет операції '*' вищий від '+', тому b
є операндом '*', а не '+'.
При перетворенні виразу a
+b
-c
результатом читання його початку a
+b
буде
( a
b
; + ; - c
),
після чого знак '-' "виштовхне" з магазина '+', тобто наступною буде трійка
( a
b
+ ; - ; c
).
Пріоритети '+' і '-' рівні, тому b
пов'язується з операцією '+' ліворуч.-
Відкриваюча та відповідна їй закриваюча дужки задають початок і кінець виразу, всі знаки операцій якого мають з’явитися у вихідному виразі раніше від знаків, що є в магазині перед появою відкриваючої дужки. Для відокремлення цих знаків відкриваюча дужка записується в магазин. За появи на вході закриваючої дужки всі знаки операцій до відкриваючої дужки виштовхуються з магазина у вихідний вираз, а дужка вилучається з магазина, тобто дужки "взаємно знищуються".
Ім'я функції записується в магазин і видається безпосередньо за ЗПЗ виразу її аргумента. Ім'я функції виштовхується з верхівки з появою у вхідному виразі знака операції або закриваючої дужки.
Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; їх треба записати у вихідну послідовність.
Отже, уся описана обробка лексем подається таким алгоритмом:
while
на вході є лексема C
do
case
C
of
стала чи ім'я змінної
: скопіювати її у вихідну послідовність;
знак операції
: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки, чий пріоритет не нижчий від пріоритету С; заштовхнути С в магазин;
відкриваюча дужка
: заштовхнути С в магазин;
закриваюча дужка
: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки операцій; виштовхнути відкриваючу дужку;
end;
3. Алгоритм обчислення виразу за його ЗПЗ
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.
ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів
, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.
Процес обчислення можна подати послідовністю пар вигляду
(магазин операндів
; непрочитана частина ЗПЗ
).
Спочатку магазин порожній, а в кінці в ньому єдине значення.
Приклад 20.2.
Обчислення ЗПЗ "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;
видати верхній елемент магазина як результат.
Задачі
20.2.
* Імітувати процес обчислення ЗПЗ:
а) 1 2 3 4 + - *; б) 1 2 3 + 4 - *; в) 1 2 + 3 - 4 *.
20.3.
У процесі побудови ЗПЗ, якщо знак операції потрапляє до вихідної послідовності, то її операнди уже перебувають там, і операцію можна застосувати до них. Поміняти алгоритм побудови ЗПЗ так, щоб замість побудови одразу обчислювалося значення початкового виразу. Можна використати два магазини – знаків операцій та операндів.
4. Записи з варіантами.
У підрозділах 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
.
Приклад 3.
Нехай у виразах імена й помилкові лексеми мають не більше восьми символів, і діють означення типів 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 є ім'ям селектора, а в дужках указано варіанти – списки означень полів, поставлені у відповідність його значенням. Щоправда, тут усі ці списки мають по одному елементу.
Тип селектора задається тільки ім'ям, а імена полів повинні бути унікальними в межах означення типу запису. Синтаксис списку полів варіанта такий самий, як і списку полів запису (зокрема, можливі спільна й варіантна частини з таким самим синтаксисом).
Приклад
. Означити тип записів для подання таких відомостей про студента: прізвище, ім'я, курс, оцінки останньої сесії, а також рік народження та відношення до військової служби юнаків, або знак Зодіаку та колір очей дівчат.
Зберемо означення спільних даних для юнаків та дівчат у спільну частину означення, а селектор статі та означення відповідних полів – у варіантну:
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 – ???
}
5. Програма обчислення виразів
Програма буде розроблятися із застосуванням так званого методу послідовних уточнень
– коли задача розбивається на підзадачі, розв'язання яких перекладається на підпрограми. Програма розв'язання задачі має досить просту структуру та містить виклики цих підпрограм. Далі розробляються підпрограми для розв'язання підзадач, у яких виділяються свої підзадачі. Для їх розв'язання розробляються відповідні підпрограми тощо.
Таким чином, програма та її складові частини не записуються одразу, а розробляються послідовним їх уточненням. У процесі розробки можливі повернення до підпрограм, розроблених раніше, та їх уточнення. Зауважимо, що в цьому процесі окремі частини програми можуть розроблятися одночасно різними програмістами.
Алгоритм обчислення значення виразу в його інфіксній формі уточнимо програмою, у тіло якої запишемо лише виклики двох підпрограм. Перша з них уточнює алгоритм побудови ЗПЗ, друга – алгоритм обчислення значення за ЗПЗ.
В обох алгоритмах неважко виділити операції, які виконуються над послідовністю та магазином лексем – додавання елементів, їх вилучення тощо. Нехай усі ці операції разом із необхідними означеннями, зокрема, типу послідовності лексем Sqlx, зібрано в модулі Sllx. Використання цього модуля укажемо в програмі, а його розробка залишається вправою.
Крім модуля Sllx, у програмі використовується модуль Glx. У ньому мають міститится всі означення, необхідні для читання виразу "з зовнішнього світу". Це читання буде здійснюватися багаторазовим викликом підпрограми getlx читання чергової лексеми виразу. Розробку цього модуля представлено в підр. 20.9–20.10.
Побудову ЗПЗ оформимо функцією ipllx, з якої повертається значення true
, якщо в процесі читання виразу не було якихось помилок, і false
у противному разі. Побудована послідовність запам'ятовується в змінній Llx. Значення виразу обчислюється за виконання виклику функції llxval і друкується. Отже, програма має вигляд:
program
calcul ( input, output );
uses
Glx, Sllx;
var
Llx : Sqlx;
function
ipllx … end
;
function
llxval … end
;
begin
if
ipllx( Llx )
then
writeln( llxval( Llx ) )
end
.
Розробка функцій ipllx і llxval розкривається в наступних двох підрозділах.
20.6. Уточнення алгоритму побудови ЗПЗ
Напишемо функцію ipllx читання та побудови ЗПЗ виразу, з якої повертається ознака відсутності помилок у виразі. Зробимо уточнення постановки задачі: будемо вважати, що вхідні вирази не містять імен змінних
, а
елементарними позначеннями операндів є лише числові сталі
.
Читання чергової лексеми виразу задається функцією getlx із модуля Glx, в якому також означено типи Tlx і Ttlx лексем та їхніх різновидів.
Вважатимемо, що модуль Sllx містить усе необхідне для роботи з послідовністю та магазином лексем, які подаються змінними типів Sqlx і Stlx відповідно. Ініціалізація порожніх послідовності та магазина задається процедурами із заголовками відповідно
procedure
initl( var
Llx : Sqlx );
procedure
inits( var
Slx : Stlx );
запис лексеми в магазин – процедурою із заголовком
procedure
push( var
Slx : Stlx; lx : Tlx );
вилучення лексеми з магазина та повернення її типу – функцією
function
pop( var
Slx : Stlx; var
lx : Tlx) : Ttlx;
добування лексеми з верхівки магазина без вилучення та повернення її типу – функцією
function
gett(Slx : Stlx; var
lx : Tlx ) : Ttlx;
додавання лексеми в кінець списку –
procedure
put( var
Llx : Sqlx; lx : Tlx ).
Крім того, функція prior задає обчислення пріоритетів лексем.
Читання чергової лексеми задається в модулі Glx функцією getlx, заголовок якої
function
getlx(var
lx : Tlx) : boolean;
з її виклику повертається ознака наявності чергової лексеми та сама лексема за допомогою параметра-змінної.
Розроблювана функція ipllx матиме одну особливість. Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; за алгоритмом вони записуються у вихідну послідовність. У цій функції весь вхідний вираз штучно "береться в дужки". Перед його читанням у магазин записується відкриваюча дужка, що відмічає його дно. В кінці магазин лексем обробляється так, ніби на вході з'явилася закриваюча дужка, тобто всі знаки до відкриваючої дужки виштовхуються та копіюються у вихідну послідовність.
function
ipllx ( var
Llx : Sqlx ) : boolean;
var
Slx : Stlx; lx, lx1 : Tlx;
lt : Ttlx; ok : boolean;
begin
initl( Llx ); inits( Slx );
ok := true
;
lx.stl := par; lx.prt := '(';
push( Slx, lx);
while
(getlx( lx ) and
ok) do
case
lx.stl of
con : put(Llx, lx);
par : case
lx.prt of
'(' : push( Slx, lx);
')' : while
pop(Slx, lx1) <> par do
put( Llx, lx1);
end
;
ops : begin
lt := gett( Slx, lx1);
while
( lt = nam ) or
( ( lt = ops ) <
(prior(lx1.sig) >= prior(lx.sig) ) do
begin
lt := pop( Slx, lx1);
put( Llx, lx1);
lt := gett( Slx, lx1)
end
;
push( Slx, lx)
end
;
nam : push( Slx, lx)
else
ok := false
end
; {case
та while
}
if
ok then
while
pop( Slx, lx1) <> par do
put(Llx, lx1);
ipllx := ok
end
;
Ця підпрограма має суттєвий недолік. Справа в тім, що вона не задає структурного, або синтаксичного, аналізу вхідного ланцюжка символів
. Наприклад, недопустима вхідна послідовність лексем "1 2 3 + *" буде прочитана та оброблена як інфіксний вираз, за ним буде створено ЗПЗ "1 2 3 * +", а далі обчислено значення 7, що не має ніякого змісту.
Поняття, необхідні для аналізу структури виразів, розглядаються в розділі 21.
7. Уточнення алгоритму обчислення виразу
Напишемо функцію llxval обчислення значення виразу за його ЗПЗ, що подається послідовністю лексем. У цій функції використовуються засоби з модуля SLlx:
- функція перевірки вичерпання послідовності лексем із заголовком
function
isemllx ( Llx : Sqlx ) : boolean;
-процедура добування й вилучення першого елемента послідовності лексем із заголовком
procedure
get ( var
Llx : Sqlx; var
lx : Tlx ).
Крім того, використовуються підпрограми обробки магазина лексем, про які сказано в попередньому підрозділі.
function
llxval ( var
Llx : Sqlx ) : real;
var
Slx : Stlx; lx, lx1, lx2 : Tlx; ok : boolean;
begin
inits( Slx ); ok := true
;
while
not
isemllx( Llx ) and
ok do
begin
get( Llx, lx);
case
lx.stl of
con : push( Slx, lx );
ops : begin
pop( Slx, lx2 ); pop( Slx, lx1 );
case
lx.sig of
'+' : lx1.numb := lx1.numb + lx2.numb;
'-' : lx1.numb := lx1.numb - lx2.numb;
'*' : lx1.numb := lx1.numb * lx2.numb;
'/' : if
lx2.numb <> 0 then
lx1.numb := lx1.numb / lx2.numb
else
ok := false
end
;
if
ok then
push( Slx, lx1 )
end
;
nam : begin
pop( Slx, lx1 );
if
lx.name = 'sin' then
lx1.numb := sin( lx1.numb ) else
if
lx.name = 'cos' then
lx1.numb := cos( lx1.numb );
push( Slx, lx1 )
end
end
{ case
lx.stl }
end
; { while
}
if
ok then
begin
pop( Slx, lx1); llxval := lx1.numb end
else
begin
writeln( '***zerodivide***' ); llxval := 0
end
end
;
8. Множини в мові Паскаль
У підпрограмах розроблюваного модуля читання лексем доведеться мати справу з множинами символів. Подання та обробку множин символів та значень інших перелічуваних типів у мові Паскаль зручно задавати з використанням спеціальних типів множин
.
Стала-множина задається в дужках [] переліком елементів або діапазонів. Наприклад, множина чисел {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' – з 226
підмножин малих латинських літер. Тип 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
1
= S
2
(S
1
<> S
2
) задають перевірку на рівність (нерівність) значень однотипних множинних виразів S
1
і S
2
. Аналогічно вирази S
1
<= S
2
(S
1
>= S
2
) задають перевірку включення S
1
у S
2
(S
2
в S
1
). Наприклад, значеннями виразів [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. Тоді:
1) процедура Symset задає побудову множини SS символів рядка A:
procedure
Symset ( A : Str; var
S : SS );
var
i : integer;
begin
S := [];
for
i:= 1 to
length(A) do
S := S + [ A[i] ]
end
;
2) функція EqSS задає перевірку рівності множин символів двох рядків:
function
EqSS ( A, B : Str ) : boolean;
var
S1, S2 : SS;
begin
Symset (A, S1);
Symset (B, S2);
EqSS := (S1 = S2)
end
;
3) функція SettoStr задає побудову рядка з символів-елементів множини в порядку їхнього кодування:
function
SettoStr ( S : SS) : Str;
var
A : Str; c : char;
begin
A := '';
for
c := chr(0) to
chr(255) do
if
c in S then
A := A + c;
SettoStr := A
end
.
9. Читання лексем виразу
Вираз є послідовністю лексичних одиниць (лексем) чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Виділення лексем із виразу називається його лексичним аналізом
. Лексеми виділяються в ході побудови внутрішнього подання виразу багаторазовим розв'язанням задачі добування чергової лексеми виразу
.
Тут ми представимо розробку модуля, що забезпечує все необхідне для добування лексем. Створюючи цей модуль, ми повністю відділяємо обробку лексем виразу від їх добування
. Якщо колись нам доведеться міняти добування лексем, ми внесемо зміни лише в цей модуль.
9.1. Алгоритм добування лексеми
Розв'язання задачі добування чергової лексеми буде описано функцією getlx. За її виконання обчислюється ознака того, чи є ще лексема у вхідній послідовності символів, і за її наявності вона присвоюється параметру-змінній функції. Помістимо функцію getlx і допоміжні для неї засоби в модуль Glx.
Алгоритм добування лексеми має такий загальний вигляд:
відшукати перший символ лексеми
;
if
відшукали
then
прочитати символи лексеми та
створити її подання
else
зафіксувати відсутність лексеми
.
9.2. Модуль розпізнавання лексем
У цьому модулі треба означити все необхідне для читання лексем. За межами модуля використовуються тип st8 імен, типи лексем Tlx та їх різновидів Ttlx, а також функція getlx. Означення цих типів та заголовок функції мають бути в інтерфейсному розділі модуля.
У розділі реалізації означимо необхідні сталі, а також масив Namf, що зберігає множину імен функцій. Означимо змінні Bcon, Bnam, Bops, Bpar та Blex для зберігання множин символів, якими починаються лексеми відповідних різновидів, та їх об'єднання. Ініціалізацію всіх цих змінних задає процедура glxinit, виклик якої записується в розділі ініціалізації модуля. Останньою в розділі реалізації записується основна функція getlx, а перед нею – допоміжні для неї підпрограми та інші означення.
Отже, модуль Glx, записаний мовою Турбо Паскаль, має такий загальний вигляд:
Unit
Glx ( input, output );
Interface
type
st8=string[8];
Ttlx = (con, nam, ops, par, err);
Tlx = record
case
stl : Ttlx of
con : (numb : real);
nam : (name : st8 );
ops : (sig : char);
par : (prt : char);
err : (wrlx : st8 )
end
;
function
getlx ( var
lx : Tlx ) : boolean;
Implementation
const
fnum = 2; {кількість імен функцій}
var
Namf : array
[ 1..fnum ] of
st8;
Bcon, Bnam, Bops, Bpar, Blex : set
of
char;
procedure
glxinit; … end
;
… { Допоміжні для getlx означення}
function
getlx; … end
;
Begin
glxinit
End
.
Одразу наведемо процедуру ініціалізації:
procedure
glxinit;
begin
Bcon := [ '0'..'9' ]; Bnam := [ 'a'..'z' ];
Bops := [ '+', '*', '-', '/' ]; Bpar := [ '(', ')' ];
Blex := Bcon + Bnam + Bops + Bpar;
Namf[1] := 'sin'; Namf[2] := 'cos'
end
;
9.3. Функція getlx
Будемо вважати, що вираз записано в тексті, між його лексемами можуть бути пропуски в довільній кількості, і що вираз може займати кілька рядків тексту. Інших уточнень поки що не робимо. Текст читається по одному символу, і нехай
читання й повернення наступного символу тексту задає функція getc
.
Нехай останній прочитаний символ тексту
, який ми називаємо поточним
, зберігається в глобальній у модулі змінній tempc
. Вона ініціалізується символом ' ' (пропуск), тобто перед виразом штучно додається пропуск.
Добування лексеми починається з пошуку її першого символу у вхідній послідовності. Нехай
пошук першого символу описується функцією getbglx
.
З її виклику повертається або перший символ лексеми, або, коли лексеми вичерпано, символьна стала chr(0), яку можна вважати "фіктивним символом". Іменування цієї сталої ім'ям finch додамо до означень модуля
.
| <D>
|
<L>
|
'+', '*', '-', '/'
|
'(', ')'
|
інший символ
|
| con
|
nam
|
ops
|
par
|
err
|
Подальша обробка лексеми залежить від її різновиду й визначається її першим символом. Нехай <D> позначає цифру з діапазону '0'..'9', а <L> – літеру з 'a'..'z'. Залежність різновиду від першого символу лексеми (за її наявності) подамо так:
Щоб добути знак операції чи дужку, досить узяти поточний символ.
Добування сталих та імен (елементів типу real і st8) опишемо функціями відповідно getcon і getnam
.
Побудуємо функції getcon і getnam так, щоб після виконання їх виклику поточним був символ, наступний за останнім символом добутої лексеми. У такому разі до обробки знаків операцій і дужок додамо указання переходу до наступного поточного символу tempc := getc. Імена, що не є іменами функцій із масиву Namf, будемо вважати помилковими лексемами. Якщо лексема подається змінною lx типу Tlx, то залежно від першого символу лексеми потрібно виконати такі дії:
<D> ® lx.stl := con; lx.numb := getcon;
<L> ® lx.name := getnam;
if
lx.name представлено в Namf
then
lx.stl := nam
else
lx.stl := err;
'+', '*', '-', '/' ® lx.stl := ops; lx.sig := tempc; tempc := getc;
'(', ')' ® lx.stl := par; lx.prt := tempc; tempc := getc;
інше ® lx.stl := err; lx.wrlx := tempc; tempc := getc;
В усіх випадках повертається значення true
– ознака наявності лексеми. За символу finch повертається false
. Наведена залежність є основою функції getlx:
function
getlx ( var
lx : Tlx ) : boolean;
begin
getlx := true
; tempc := getbglx;
if
tempc in
Bcon then
begin
lx.stl := con; lx.numb := getcon
end
else
if
tempc in
Bnam then
begin
lx.name := getnam;
if
isfn ( lx.name ) then
lx.stl := nam
else
lx.stl := err
end
else
if
tempc in
Bops then
begin
lx.stl := ops; lx.sig := tempc; tempc := getc
end
else
if
tempc in
Bpar then
begin
lx.stl := par; lx.prt := tempc; tempc := getc
end
else
if
tempc = finch then
getlx := false
else
begin
lx.stl := err; lx.wrlx := tempc; tempc := getc
end
end
;
Функція isfn перевірки, чи представлено ім'я lx.name в масиві Namf, залишається для самостійної розробки.
9.4. Допоміжні підпрограми
Алгоритм процедури getbglx дуже простий: поки поточний символ не потрапив у множину Blex перших символів лексем, викликається функція getc для одержання нового поточного символу. Якщо при цьому вираз вичерпується, то наступним поточним вважається "фіктивний символ" finch.
function
getbglx : char;
begin
while
not
((tempc in
Blex )or
( tempc = finch ) ) do
tempc := getc;
getbglx := tempc
end
;
Функція getcon задає читання символів сталої з образу та побудову за ними відповідного значення типу real. Нехай синтаксис сталої задається метавиразом <D> { <D> } [ '.' { <D> } ]. Розглянемо побудову значення типу real за сталою. Цифри до крапки задають цілу частину числа. Значення чергової цифри додається до результату обробки попередніх цифр, помноженого на 10. Перед обробкою першої цифри результатом є 0. Крапка пропускається, а значення цифр праворуч від неї множаться на відповідні від'ємні степені числа 10 і додаються до числа:
function
getcon : real;
var
v, d : real;
begin
v := 0; d := 1;
repeat
v := v*10 + ord(tempc) - ord('0'); tempc := getc;
until
not (tempc in
Bcon);
if
tempc = '.' then
tempc := getc;
while
tempc in
Bcon do
begin
d := d/10; v := v + ( ord(tempc) - ord('0') )*d; tempc := getc
end
;
{сталу прочитано; поточним є символ, наступний за її останнім}
getcon := v
end
;
Запишемо функцію getcon у інший спосіб, який реально застосовується в побудові підпрограм лексичного аналізу в системах програмування. Обробка чергового символу залежить від того, чи є він цифрою в цілій або дробовій частині сталої, крапкою або символом після сталої.
Додамо змінну 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
майже механічно:
function
getcon : real;
type
Tcp = ( ip, fp, out );
var
v, d : real; cp : Tcp;
begin
v := 0; d := 1; cp := ip;
while
cp <> out do
case
cp of
ip : case
tempc of
'0'..'9' : begin
v := v*10 + ord(tempc) - ord('0');
tempc := getc
end
;
'.' : begin
cp := fp; tempc := getc
end
else
cp := out
end
;
fp : case
tempc of
'0'..'9' : begin
d := d/10;
v := v + (ord(tempc) - ord('0'))*d;
tempc := getc
end
else
cp := out
end
end
; { оператора case
cp of
та циклу while
}
getcon := v
end
Функція getnam записується аналогічно й залишається для самостійної розробки.
9.5. Читання символів
Нарешті ми уточнимо, як читаються символи виразу з тексту, написавши функцію getc добування наступного символу.
Її розробку почнемо з уточнення задання виразу. Нехай вираз записано в текстовому файлі, у кількох рядках, довжини яких не більше 80. Ознакою кінця виразу є кінець файла. Суміжні лексеми відокремлюються довільними послідовностями пропусків, можливо, порожніми.
Скористаємося обмеженням на довжину рядків тексту та організуємо читання тексту не окремими символами, а рядками. Черговий рядок стає значенням змінної рядкового типу Str, яка називається образом вхідного рядка
, або буфером
. Саме з буфера символи по одному добуваються за викликів функції getc.
Функцію getc разом із іншими необхідними означеннями помістимо в окремий модуль Inbuf. Створюючи цей модуль, ми повністю відокремлюємо обробку символів виразу від їх конкретного джерела – файла на диску, клавіатури чи ще чогось
.
Додамо указання використання модуля Inbuf до модуля Glx.
Для роботи з буфером, тобто змінною buf типу Str, додамо змінні bufl, bufp та tempc, що зберігатимуть відповідно довжину
буфера (кількість символів), позицію
в ньому, якою закінчується оброблена частина виразу, та її останній, або поточний символ
. Означимо ще сталу finch = chr(0), яка стає значенням поточного символу при закінченні виразу. Стала finch та змінна tempc експортуватимуться з модуля, і за його межами рядок "буде видно крізь віконце tempc".
Перенесемо означення імен finch і tempc з модуля Glx до модуля Inbuf
.
Ініціалізацію змінних модуля задає процедура bufinit, виклик якої записано в розділі ініціалізації. Вона також забезпечує можливість задати ім'я файла, з якого треба читати вираз. Функція newln описує заповнення буфера новим вхідним рядком та повернення його першого символу.
Модуль Inbuf має такий загальний вигляд:
Unit
Inbuf ( input, output );
Interface
const
finch=chr(0);
var
tempc : char;
function
getc : char;
Implementation
const
bufml = 80;
type
Str=string[bufml];
var
buf : Str;
bufl, bufp : integer;
f : text; nam : Str;
procedure
bufinit;
begin
buf := ''; {спочатку буфер – порожній рядок}
bufl := 0; bufp := 0;
tempc := ' '; {штучний пропуск перед початком першого рядка}
writeln('Уведіть ім''я текстового файла з виразом'); readln(nam);
assign(f, nam); reset(f)
end
;
function
newln : char; … end
;
function
getc; … end
;
Begin
bufinit
End
.
Наведемо, нарешті, функції getc і newln.
function
getc : char;
begin
bufp := bufp + 1;
if
bufp <= bufl then
tempc := buf[bufp]
else
{ рядок вичерпано } tempc := newln;
getc := tempc
end
;
При виконанні функції newln у разі наявності наступного рядка повертається пропуск. Він штучно додається перед першим символом рядка, аби той не продовжував лексему в попередньому рядку. У разі кінця файла повертається finch – ознака закінчення виразу:
function
newln : char;
begin
if
eof(f) then
tempc := finch
else
begin
readln (f, buf );
bufp := 0; bufl := length ( buf );
tempc := ' '
end
;
newln := tempc
end