Інтерпретатор

Білоруський Державний Университет.

Інформатики і Радиоэлектроники.

Контрольна работа.

по дисциплине.

«Системне програмне забезпечення ЭВМ».

Виконав студент групи 500 501.

Балахонів Е.В.

Задание.

Розробити интерпретатор.

1. Загальне описание.

Цей інтерпретатор реалізує основних арифметичних дії вигляді инфиксных операцій над числами з плаваючою точкою. Наприклад вхідний потік має вид:

r=2.5 area=pi*r*r.

(тут pi має визначене значення). Тоді програма калькулятора выдаст:

2.5.

19.635.

Результат обчислень перша вхідний рядки дорівнює 2.5, а результат для другий рядки — це 19.635. Програма інтерпретатора складається з чотирьох основних частин: аналізатора, функції введення, таблиці імен та драйвера.

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

2. Анализатор.

Граматика мови калькулятора такими правилами:

программа:

END // END — це кінець введення списків-виражень END.

списків-виражень: вираз PRINT // PRINT — це «n «чи »; «вираз PRINT список-выражений.

вираз: вираз + терм вираз — терм терм.

терм: терм / первинне терм * первинне первичное.

первичное:

NUMBER // число з плаваючою коми в С++.

NAME // ім'я у мові З++ крім «_ «.

NAME = выражение.

— первичное.

(вираз).

Інакше кажучи, програма є послідовність рядків, а кожна рядок містить одне чи кілька висловів, розділених точкою з коми. Основні елементи висловлювання — це числа, імена та проведення операції *, /, +, — (унарный і бінарний мінус) і =. Імена необов’язково описувати до использования.

Для синтаксичного аналізу використовується метод, зазвичай званий рекурсивним спуском. Це поширений і очевидний метод. У таких мовами як З++, тобто у яких операція виклику не пов’язані з великими накладними видатками, це метод ефективний. До кожного правила граматики є своя функція, що викликає інші функції. Термінальні символи (наприклад, END, NUMBER, + і -) розпізнаються лексичним аналізатором get_token (). Нетермінальні символи розпізнаються функціями синтаксичного аналізатора expr (), term () і prim (). Щойно обидва операнда висловлювання чи подвыражения відомими, воно обчислюється. У цьому трансляторе на той час створюються команди, вычисляющие выражение.

Аналізатор використовує для введення функцію get_token (). Значення останнього виклику get_token () зберігається у глобальній перемінної curr_tok. Змінна curr_tok приймає значення елементів перерахування token_value:

enum token_value {.

NAME, NUMBER, END,.

PLUS= «+ », MINUS= «- «, MUL= «* », DIVX= «/ «,.

PRINT= «; «, ASSIGN= «= «, LP= «(«, RP= «) «.

}; token_value curr_tok;

Всім функцій аналізатора передбачається, що get_token () вже був викликана, і у curr_tok зберігається наступна лексема, підлягаючий аналізу. Це дозволяє аналізатору зазирати однією лексему вперед. Кожна функція аналізатора завжди читає однією лексему більше, ніж потрібно для розпізнавання того правила, котрій вона викликалася. Кожна функція аналізатора обчислює «своє «вираз і повертає його результат. Функція expr () обробляє складання і віднімання. Вона вже з циклу, у якому розпізнані терми складаються чи вычитаются:

double expr () // складає і вычитает.

{ double left = term ();

for (;;) // ``вічно «» switch (curr_tok) { case PLUS: get_token (); // випадок «+ «left += term (); break; case MINUS: get_token (); // випадок «- «left -= term (); break; default: return left;

}.

}.

Зазначимо, що висловлювання виду 2−3+4 обчислюються як (2−3)+4, що визначається правилами грамматики.

Функція term () справляється з множенням і розподілом аналогічна тій, як функція expr () зі складанням і вычитанием:

double term () // множить і складывает.

{ double left = prim ();

for (;;) switch (curr_tok) { case MUL: get_token (); // випадок «* «left *= prim (); break; case DIVX: get_token (); // випадок «/ «double d = prim (); if (d == 0) return error («розподіл на 0 »); left /= d; break; default: return left;

}.

}.

Перевірка відсутності розподілу на нуль необхідна, оскільки результат розподілу на нуль невизначений і, зазвичай, призводить до катастрофе.

Функція error () розглядатиметься пізніше. Змінна d з’являється у програмі там, де справді потрібна, відразу ж инициализируется.

Функція prim, обробна первинне, багато в чому справляє враження функції expr і erm ().

double number_value; char name_string[256];

double prim () // обробляє первичное.

{ switch (curr_tok) { case NUMBER: // константа з плаваючою точкою get_token (); return number_value; case NAME: if (get_token () == ASSIGN) { name* n = insert (name_string); get_token (); n->value = expr (); return n->value;

} return look (name_string)->value; case MINUS: // унарный мінус get_token (); returnprim (); case LP: get_token (); double e = expr (); if (curr_tok ≠ RP) return error («потрібно) »); get_token (); return e; case END: return 1; default: return error («потрібно первинне »);

}.

}.

Коли з’являється NUMBER (тобто константа з плаваючою точкою), повертається його значення. Функція введення get_token () поміщає значення константи в глобальну зміну number_value. Якщо програмі використовуються глобальні перемінні, то часто це те що, що структура не опрацьована, і тому потрібно деяка оптимізація. Саме такими стан справ у разі. У ідеалі лексема має складатися з двох частин: значення, визначального вид лексеми (у програмі це token_value), і (якщо потрібно) власне значення лексеми. Але тут є лише одне проста змінна curr_tok, для зберігання останнього прочитаного значення NUMBER потрібно глобальна змінна number_value. Таке рішення проходить оскільки калькулятор переважають у всіх обчисленнях спочатку вибирає одне число, та був зчитує інше з вхідного потока.

Якщо останнє значення NUMBER зберігається у глобальній перемінної number_value, то строковое уявлення останнього значення NAME зберігається в name_string. Перш ніж, як щось робити безпосередньо з ім'ям, інтерпретатор повинен зазирнути наперед, аби з’ясувати, було б йому присвоюватися значення, або ж буде тільки є його значення. У обох випадках треба звернутися до таблиці імен. Ця таблиця складається з записів, мають вид:

struct name { char* string; name* next; double value;

};

Член next використовується лише службовими функціями, котрі працюють із таблицей:

name* look (const char*); name* insert (const char*);

Обидві функції повертають покажчик на запис name, що відповідає їх параметру-строке. Функція look () «лається », якщо ім'я був занесено в таблицю. Це означає, що у калькуляторі можна використовувати ім'я без попереднього описи, але у вперше може з’явитися лише у лівої частини присваивания.

3. Функція ввода.

Одержання вхідних даних — часто сама заплутана частина програми. Причина у цьому, що ваша програма повинна взаємодіяти з користувачем, тобто «миритися «з його примхами, враховувати прийняті угоди, і передбачати удавані рідкісними ошибки.

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

Правила введення для інтерпретатора були спеціально обрані кілька громіздкими для потокових функцій введення. Незначні зміни у визначеннях лексем перетворили б get_token () в оманливе просту функцию.

Перша складність у тому, що символ кінця рядки «n «важливий для калькулятора, але потокові функції введення сприймають його вважається символом узагальненого прогалини. Інакше висловлюючись, тих функцій «n «має значення лише вважається символом, завершальний лексему. От і доводиться аналізувати все узагальнені прогалини (прогалину, табуляція тощо.). Це потрібно в операторі do :

char ch;

do { // пропускає прогалини крім «n «if (!cin.get (ch)) return curr_tok = END;

} while (ch≠ «n «&& isspace (ch));

Функція cin. get (ch) читає один символ з стандартного вхідного потоку в ch. Значення умови if (!cin.get (ch)) — брехня, коли з потоку cin не можна одержати ані одного символу. Тоді повертається лексема END, щоб закінчити роботу калькулятора. Операція ! (NOT) потрібна оскільки у разі успішного зчитування get () повертає ненульове значение.

Функция-подстановка isspace () з перевіряє, перестав бути її параметр узагальненим прогалиною. Вона повертає ненульове значення, якщо є, і нуль інакше. Перевірка реалізується як звернення до таблиці, для швидкості краще викликати isspace (), ніж перевіряти самому. Те ж саме сказати про функції isalpha (), isdigit () і isalnum (), які у get_token ().

Після пропуску узагальнених прогалин наступний лічений символ визначає, яким буде начинающаяся від нього лексема. Перш, ніж привести всю функцію, розглянемо деякі випадки окремо. Лексеми «n «і «; «, завершальні вираз, обробляються наступним образом:

switch (ch) { case "; «: case «n »: cin >> ws; // перепустку узагальненого прогалини return curr_tok=PRINT;

Необов’язково знову пропускати прогалину, але, зробивши це, ми уникнемо повторних викликів функції get_token (). Змінна ws, описана в файлі, використовується лише як приймач непотрібних пробелов.

Помилка у вхідних даних, і навіть кінець введення ні виявлено до наступного виклику функції get_token (). Зверніть увагу, як дещо міток вибору позначають одну послідовність операторів, задану для цих варіантів. Для обох символів («n «і «; «) повертається лексема PRINT, і вона ж міститься у curr_tok.

Числа обробляються наступним образом:

case «0 »: case «1 »: case «2 »: case «3 »: case «4 »: case «5 »: case «6 »: case «7 »: case «8 »: case «9 »: case ". «: cin. putback (ch); cin >> number_value; return curr_tok=NUMBER;

Оскільки оператор >> може читати константу з плаваючою точкою типу double, програма тривіальна: передусім початковий символ (цифра чи точка) повертається у cin, та був константу вважатимуться в number_value. Ім'я, тобто. лексема NAME, окреслюється літера, яку може бути кілька літер чи цифр:

if (isalpha (ch)) { char* p = name_string;

*p++ = ch; while (cin.get (ch) && isalnum (ch)) *p++ = ch; cin. putback (ch);

*p = 0; return curr_tok=NAME;

}.

Цей фрагмент програми заносить в name_string рядок, що закінчувалася нульовим символом. Функції isalpha () і isalnum () визначені у .

Результат isalnum© ненульовий, якщо з — літера чи цифра, й нульовий в противному случае.

Наведемо функцію введення полностью:

token_value get_token ().

{ char ch;

do { // пропускає узагальнені прогалини крім «n «if (!cin.get (ch)) return curr_tok = END;

} while (ch≠ «n «&& isspace (ch));

switch (ch) { case "; «: case «n »: cin >> ws; // перепустку узагальненого прогалини return curr_tok=PRINT; case «* »: case «/ «: case «+ »: case «- «: case «(«: case ») «: case «= «: return curr_tok=token_value (ch); case «0 »: case «1 »: case «2 »: case «3 »: case «4 »: case «5 »: case «6 »: case «7 »: case «8 »: case «9 »: case ». «: cin. putback (ch); cin >> number_value; return curr_tok=NUMBER; default: // NAME, NAME= чи помилка if (isalpha (ch)) { char* p = name_string;

*p++ = ch; while (cin.get (ch) && isalnum (ch)) *p++ = ch; cin. putback (ch);

*p = 0; return curr_tok=NAME;

} error («неприпустима лексема »); return curr_tok=PRINT;

}.

}.

Перетворення операції в значення лексеми нею тривіально, що у перерахування token_value лексема операції було визначено як ціле (код символу операции).

4 Таблиця имен.

Є функція пошуку таблиці имен:

name* look (char* p, int ins =0);

Другий її параметр показує, була символьна рядок, що означає ім'я, раніше занесена в таблицю. Инициализатор =0 задає стандартне значення параметра, що використовується, якщо функція look () викликається лише з однією параметром. Це зручно, тому що писати look («sqrt2 »), що означає look («sqrt2 », 0), тобто. пошук, а чи не занесення в таблицю. Щоб була така ж зручно ставити операцію занесення в таблицю, визначається друга функция:

inline name* insert (const char* p. s) { return look (s, 1); }.

Як раніше згадувалося, запис у цієї таблиці мають такої тип:

struct name { char* string; name* next; double value;

};

Член next використовується для зв’язку записів в таблиці. Власне таблиця — це масив покажчиків на об'єкти типу name:

const TBLSZ = 23; name* table[TBLSZ];

Оскільки за умовчанням все статичні об'єкти инициализируются нулем, таке тривіальне опис таблиці table забезпечує ще й потрібну инициализацию.

Для пошуку імені цього у таблиці функція look () використовує простий хэшкод (записи, у яких імена мають однакову хэш-код, зв’язуються вместе):

int ii = 0; // хэш-код const char* pp = p; while (*pp) ii = iinext = table[ii]; table[ii] = nn; return nn;

}.

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

Додавання нового імені означає створення нової об'єкта name в вільної пам’яті з допомогою операції new, його ініціалізацію і включення до список імен. Останнє виконується, як занесення нового імені цього у початок списку, оскільки можна зробити навіть без перевірки того чи список взагалі. Символьна рядок імені також розміщається у вільному пам’яті. Функція strlen () вказує, скільки пам’яті треба задля рядки, операція new відводить потрібну пам’ять, а функція strcpy () копіює у ній рядок. Усі строковые функції описані у :

extern int strlen (const char*); extern int strcmp (const char*, const char*); extern char* strcpy (char*, const char*);

5. Обробка ошибок.

Оскільки програму є досить простою, зайве особливо турбуватися про обробці помилок. Функція error просто підраховує кількість помилок, видає повідомлення про неї й повертає управління обратно:

int no_of_errors;

double error (const char* s).

{ cerr > WS; return curr_tok=PRINT; case «* »: case «/ «: case «+ »: case «- «: case «(«: case ») «: case «= «: return curr_tok=ch; case «0 »: case «1 »: case «2 »: case «3 »: case «4 »: case «5 »: case «6 »: case «7 »: case «8 »: case «9 »: case ». «: cin. putback (ch); cin >> number_value; return curr_tok=NUMBER; default: if (isalpha (ch)) { char* p = name_string;

*p++ = ch; while (cin.get (ch) && isalnum (ch)) *p++ = ch; cin. putback (ch);

*p = 0; return curr_tok=NAME;

} error («bad token »); return curr_tok=PRINT;

} }.

int main (int argc, char* argv[]) { switch (argc) { case 1: break; case 2: cin = *new istream (strlen (argv[1]), argv[1]); break; default: error («too many arguments »); return 1;

}.

// insert predefined names: insert («pi »)->value = 3.1 415 926 535 897 932 288; insert («e »)->value = 2.7 182 818 284 590 452 736;

while (1) { get_token (); if (curr_tok == END) break; if (curr_tok == PRINT) continue; cout.