Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ IV. АЛГОРИТМИ

0 c

1

3a

4b

5d

…

m-1

Рис. 4.6

Нехай m = 8 і ключі елементів a , b мають хеш-значення h (a ) = 3 , h (b) = 3 , відповідно. Тоді, якщо ми хочемо вставити елемент b , а се-

гмент 3 уже зайнятий, то можна перевіряти на зайнятість сегменти 4, 5, 6, 7, 0, 1, 2 (саме в такому порядку).

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

Одним із найкращих методів є подвійне хешування. Тут функція h

має вигляд h(i) (k)= (h1 (k)+ih2 (k))%m , h1 та h2 – звичайні хеш-функції. Щоб послідовність випробуваних місць покривала всю таблицю, значення h′′ має бути взаємно простим із m . Для цього потрібно виб- рати за m степінь двійки, а функцію h′′ узяти таку, щоб набувала не-

парних значень.

Приклад 4.30. Реалізація простого словника на основі закритого хешування з використанням лінійного методу:

Лістинг.

#define countKey 701

char *Dictionary[countKey];

int hаshFunction(char *x)

{

541

ПРОГРАМУВАННЯ

int h=0, sum=0; int len=strlen(x);

for(int i=0; i<len; i++){ sum+=x[i]; h=sum%countKey;

}

return h;

}

void makenull(void)

{

for(int i=0; i<countKey; i++){ strcpy(Dictionary[i], "\0");

};

}

/*переглядає словник, починаючи від елемента hаshFunction(x), поки не зустріне слово x, порожній

елемент або не досягне кінця таблиці (в останніх випадках вважається, що таблиця не містить слово x).

Результат – позиція, де зупинився пошук*/ int locate(char *x)

{

int i=0, initial=hаshFunction(x);

while((i<countKey)&&(Dictionary[(initial+i)%countKey]!=x)&&

(Dictionary[(initial+i)%countKey]))

i++;

return (initial+i)%countKey;

}

/*те саме, що й locate, але при досягненні значення deleted зупиняється*/

int locate1(char *x)

{

int i=0, initial=hаshFunction(x);

while((i<countKey)&&(!strcmp(Dictionary[(initial+i)%countKey ], x))&&

(!strcmp(Dictionary[(initial+i)%countKey],"\0"))&& (!strcmp(Dictionary[(initial+i)%countKey], "*********\0")))

i++;

return (initial+i)%countKey;

}

int hаshMember(char *x)

{

542

Розділ IV. АЛГОРИТМИ

return (Dictionary[locate(x)]==x);

}

void hаshInsert(char *x)

{

if(Dictionary[locate(x)]==x) return; /*слово x уже є у слов-

нику*/

int bucket=locate1(x); if((strcmp(Dictionary[bucket], "\0"))||

(strcmp(Dictionary[bucket], "*********\n"))) strcpy(Dictionary[bucket],x);

else

printf("ERROR");

}

void hаshDelete(char *x)

{

int bucket=locate(x);

if(strcmp(Dictionary[bucket], x)) strcpy(Dictionary[bucket], "*********\n");

}

■

4.4.8. ТАБЛИЦІ У ВИГЛЯДІ ДЕРЕВ ПОШУКУ

У підрозд. 3.7.2 ми розглянули програму для підрахунку частоти входжень службових слів у текст С-програми, що вводиться з клавіа- тури (прикл. 3.63). Для розв'язання задачі було побудовано таблицю з двома стовпчиками: у першому – усі службові слова мови С у лекси- кографічному порядку, у другому – частота їхніх входжень у С- програму. Така таблиця має фіксовану структуру, тому для її подання було обрано звичайний упорядкований масив структур. Тепер уза- гальнимо задачу і спробуємо порахувати частоту входжень усіх іден- тифікаторів у С- програму. Така постановка потребує вже побудови динамічної таблиці з тією самою структурою рядків. Для цього скори- стаємося деревом пошуку, яке дозволяє обмежити час пошуку елеме- нта висотою дерева (див. підрозд. 1.4.4). Порядок на ідентифікато- рах, як і раніше, лексикографічний. У програму включено заголовний файл "def.h", що містить описи функцій: int getword (char *, int)

для читання з клавіатури чергового ідентифікатора (див. при- кл. 3.63), void treeprint (Itemptr3) для прямого виведення дерева,

543

ПРОГРАМУВАННЯ

Itemptr3 talloc(void) для відведення місця під вузол дерева, char *strdub(char *) для створення копії рядка.

Лістинг.

typedef struct item { /*вузол дерева*/ char *key; /*покажчик на слово*/

int count; /*кількість входжень*/ struct item *left; /*ліве піддерево*/ struct item *right; /*праве піддерево*/ }*Itemptr3;

#include "def.h" #include <stdio.h> #include <ctypeh.> #include <string.h> #define MAXWORD 100

Itemptr3 search2 (Itemptr3, char*);

/*частотний словник тексту програми*/ main()

{

Itemptr3 root;

char word [MAXWORD]; root=NULL;

while (getword (word, MAXWORD)!=EOF)

if (isalpha (word [0])) root= search2 (root, word); treeprint (root);

return 0;

}

/*search2: шукає й обробляє вузол зі словом word у піддереві р або нижче нього. Якщо такий вузол відсутній - то вставляє його в дерево. На відміну від аналогічної функції search із прикл. 4.25, search2 повертає покажчик на знайдений або побудований вузол*/

Itemptr3 search2(Itemptr3 p, char *word)

{

int cond;

if(p==NULL) { /*ідентифікатор зустрічається вперше*/

if (p=talloc())==NULL){puts("No mamory"); exit(0);} /*створюється новий вузол*/

if((p->key=strdub(word))==NULL) { puts("No mamory"); exit(0);}; p->count=1;

544

Розділ IV. АЛГОРИТМИ

p->left=p->right=NULL;

}

else if ((cond=strcmp(word, p->key))==0) p->count++; /*ідентифікатор уже є в дереві*/

else if (cond<0) /*менше кореня лівого піддерева*/ p->left=addtree(p->left, word);

else /*більше кореня правого піддерева*/ p->right=addtree(p->right, word);

return p;

}

■

Ми розглянули таблиці в мові C. Для їхнього подання засобами C++ зручно користуватися контейнерними типами, що входять до складу стандартної бібліотеки C++ (див. вправу 32, підрозд. 4.3).

*Література для CР:. подання таблиць і методи роботи з ними

– [8, 55, 65].

Контрольні запитання та вправи

1.Що таке таблиця?

2.Що таке рядок таблиці?

3.Що таке таблиця як: а) масив; б) динамічний масив?

4.Які основні операції над таблицями?

5.Що таке таблиця як зв'язаний список рядків?

6.У чому полягає ідея хешування таблиць?

7.Що таке хеш-функція?

8.Що таке хеш-таблиця з прямою адресацією?

9.Що таке колізія рядків у хеш-таблиці?

10.Що таке відкрите й закрите хешування?

11.У чому полягає різниця між відкритим і закритим хешуванням?

12.Написати програму для обробки таблиць у вигляді динаміч- них масивів:

а) каталог книг у бібліотеці: містить інформацію про авто- ра, назву книжки, рік видання, видавництво й кількість сторінок; б) список студентів у групі: містить інформацію про ПІБ

студента, рік вступу, рік народження, адресу й телефон; в) список товарів у магазині: містить інформацію про назву товару, виробника, кількість одиниць товару в наявності;

г) список клієнтів банку: містить інформацію про ПІБ кліє- нта, номер рахунку, кількість грошей на рахунку;

545

ПРОГРАМУВАННЯ

д) телефонний довідник: містить інформацію про ПІБ, но- мер телефону, адресу.

13.Те саме, що й у вправі 12, але таблиці подати однозв'язним списком.

14.Те саме, що й у вправі 12, але таблиці подати двозв'язним списком.

15.Те саме, що й у вправі 12, але таблиці подати у вигляді за- критих хеш-таблиць.

16.Те саме, що й у вправі 12, але таблиці подати у вигляді від- критих хеш-таблиць.

17.Створити заголовний файл "def.h" для реалізації таблиці у

вигляді дерева пошуку з підрозд. 4.4.8.

18. Побудувати частотний словник у вигляді дерева пошуку для тексту, який задається: а) у файлі; б) символьним рядком.

4.5. Синтаксичний аналіз і обчислення виразів

¾Лексичний аналіз виразів

¾Синтаксичний аналіз

¾Обчислення виразів

Ключові слова: синтаксичний аналізатор (парсер), синтаксичний аналіз, ле- ксичний аналіз, синтаксичне дерево, таблиця ідентифікаторів, метод рекурсивного спуску з поверненням, утиліти Lex та Yacc.

Як транслятори, розроблені для компіляції програм, написаних мо- вами програмування високого рівня, перетворюють їхні тексти на команди, виконувані комп'ютером? Як компілятор відшукує помилки в тексті програми? Спробуємо розв'язати ці й подібні питання, відпо- вівши спочатку на простіше: як написати програму, що одержує на вході символьний рядок, який містить числовий вираз, наприклад 7 – 2 * 3, а на виході видає результат? Процедура, що передує виконанню цієї дії, називається синтаксичним аналізом виразів (англ. – expression parsing) і є основою всіх компіляторів та інтерпретаторів мов, електронних таблиць та інших програм, в яких потрібно пере- творювати числові вирази на програмний код. Зрозумівши механізм роботи синтаксичного аналізу виразів, ми навчимося створювати складніші синтаксичні аналізатори, а також зрозуміємо механізм ро- боти програм-трансляторів.

546

Розділ IV. АЛГОРИТМИ

Синтаксичний аналізатор (парсер) – це програма, що виконує синтаксичний аналіз тексту програми, на першому кроці якого вико-

нується лексичний аналіз, потім будується синтаксичне дерево про-

грами – дерево її виведення в граматиці мови програмування. Парсер входить до структури транслятора.

Розглянемо принципи побудови парсерів на прикладі аналізу скла- дних арифметичних виразів – звичайних арифметичних виразів і ви- разів присвоювання, а також процес обчислення значення таких ви- разів [136]. Незважаючи на те, що складні вирази можуть утворюва- тися з даних довільних типів, обмежимося лише числовими виразами. Вважатимемо, що вони складаються з таких елементів: числа, змінні, операції +, -, /, *, ^ (піднесення до степеня), %, = і дужки.

Перелічені елементи можна комбінувати у виразах відповідно до пра- вил побудови інфіксних термів (див. підрозд. 1.1.1) з урахуванням пріо-

ритету операцій, наприклад: (11+a)/2*6; 7+8; a+b–c; a=9–b; 10^3.

Нехай операції мають пріоритет у порядку спадання:

(Вищий) (унарні +, -) (^) (*, /, %) (+, -) (присвоювання =) (Нижчий).

Операції з однаковим пріоритетом виконуються зліва направо. Для спрощення вважатимемо, що імена змінних не залежать від

регістра та є однолітерними (допускається 26 змінних, від А до Z). На- приклад, b та B позначають ту саму змінну. Кожне числове значення має тип double. Контроль за помилками – мінімальний.

Мову складних арифметичних виразів можна задати такою грама- тикою G :

<складний-вираз>→ <присвоювання> | <вираз> <присвоювання>→ <змінна>=<вираз> <вираз>→ <доданок> [<операція1> <доданок> ]

<доданок> → <множник >[<операція2> <множник>] <множник> → <степінь>[<операція3> <множник>]

<степінь> → <операція1>(<вираз>) | (<вираз>)| <змінна> | <число> <операція1> → + | - <операція2> → * | / | % <операція3> → ^ <число> → (<цифра>)*

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <змінна> → a | b | … | z | A | B | … | Z

З теоретичними відомостями стосовно граматик можна ознайоми- тися в підрозд. 1.4.4.

547

ПРОГРАМУВАННЯ

Зрозуміло, що не становить принципової складності розширити та- кий синтаксичний аналізатор на випадок загального іменування, чут- ливого до регістра.

Спробуємо обчислити вираз 7 – 2 * 3. Зрозуміло, що значення дорі- внює 1. Спочатку може спасти на думку такий алгоритм:

a=одержати перший операнд while(є операнд){

op=одержати операцію b=одержати другий операнд a=a op b

}

Однак при обчисленні виразу 7 – 2 * 3 у результаті виходить 15 за- мість 1, оскільки описана процедура не враховує пріоритет операцій. Не можна просто вибирати операнди й операції ліворуч і праворуч, оскільки за пріоритетом операцій множення застосовується раніше ніж віднімання.

4.5.1. ЛЕКСИЧНИЙ АНАЛІЗ ВИРАЗІВ

Для обчислення виразів необхідно вміти розбивати їх на лексеми (див. підрозд. 3.1.2). Які об'єкти вважати лексемами, залежить від мови програмування. З кожною лексемою пов'язується структура, що складається з пари: тип лексеми й покажчик на поле, де зберігається інформація про конкретну лексему. Кількість типів лексем залежить від конкретної мови, що аналізується (у даному випадку – мова ари- фметичних виразів).

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

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

Конструкції, що розпізнаються лексичним аналізатором, описують- ся автоматною граматикою й регулярними виразами (стосовно скін- ченних автоматів і регулярних виразів див. підрозд. 1.4.4.)

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

548

Розділ IV. АЛГОРИТМИ

В основі лексичного аналізатора лежить діаграма переходів відпо- відного скінченного автомата.

Типами лексем для лексичного аналізу описаного вище арифметич-

ного виразу є: <змінна>, <число>, <операція_1>, <операція_2>, <опе-

рація_3>. Останні три типи зручно об'єднати, додавши до них дужки. Таким чином, для розроблюваного аналізатора використовуються лише три типи лексем: змінна, число й операція або роздільник. У реалізації їм відповідають константи VARIABLE, NUMBER і DELIMITER (DELIMITER ви-

користовується як для операцій, так і для дужок).

Лексичний аналізатор може бути як самостійною фазою трансляції (препроцесорна обробка), так і підпрограмою, що працює за принципом "дай лексему" (getТoken). У першому випадку виходом аналізатора є таб- лиця лексем, у другому – лексема видається при кожному зверненні до аналізатора. При цьому зазвичай ознака класу лексеми повертається як результат функції, що реалізує лексичний аналізатор (getТoken), а зна- чення лексеми передається через глобальну змінну. У процесі обробки лексем аналізатор може або просто видавати значення кожної лексеми (при цьому побудова таблиць ідентифікаторів переноситься на пізніші фази), або самостійно будувати таблиці ідентифікаторів.

У будь-якому разі потрібен метод, що повертає один за одним усі лексеми виразу. Метод, що розбиває вираз на лексеми, має виконува- ти такі дії: 1) ігнорувати роздільники (пробіли, табуляції й переходи на новий рядок); 2) виділяти лексеми з тексту; 3) визначати тип лек- семи. Кожен елемент виразу називається лексемою (token), тому ме- тод, що повертає чергову лексему, часто називається getТoken(). У ньому використовується покажчик на рядок із виразом, що розби- рається. У розглядуваній версії функції getТoken() такий покажчик називається prog. Атрибут prog має зберігати своє значення між ви- кликами функції getToken() і бути доступним іншим методам. Крім значення лексеми, необхідно знати її тип (VARIABLE, NUMBER та DELIMITER). Нижче наведено фрагмент опису класу, відповідального за синтаксичний і лексичний аналіз і текст методу getToken() разом із необхідними деклараціями, константами й допоміжним методом.

Приклад 4.31. Лексичний аналіз:

Лістинг.

#define DELIMITER 1

549

ПРОГРАМУВАННЯ

using namespace std;

class CSimpleParser { public:

CSimpleParser()

{

prog=new (char[100]); if(!prog) {

printf("Помилка при виділенні пам'яті\n"); exit(1);

};

for(int i=0; i<26; i++) vars[i]=0.0;

};

void evalExp(double *answer);

char *prog; /*указує на вираз, що аналізується*/

private:

char token[80]; char tokType;

double vars[26]; /*26 змінних, A-Z*/

void setProg(char *pr)

{

prog=pr;

};

void setToken(char tok[80])

{

strcpy(token,tok);

};

void getToken(); int isdelim(char c);

… … …

};

/*Повернення чергової лексеми*/ void CSimpleParser::getToken()

{

register char *temp='\0';

temp=token;

tokType=0;

550