Білоруський Державний Університет
Інформатики і радіоелектроніки
Контрольна робота
з дисципліни
«Системне програмне забезпечення ЕОМ»
Виконав студент групи 500501
Балахонов Е.В.
Завдання
Розробити інтерпретатор.
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 ='*', DIV ='/',
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 DIV: get_token ();// випадок '/' double d = prim (); if (d == 0) return error ( "ділення на 0"); left/= d; break; default: return left;
)
) < p> Перевірка відсутності поділу на нуль необхідна, оскільки результатділення на нуль невизначений і, як правило, призводить до катастрофи.
Функція 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 (); return-prim (); case LP: get_token (); double e = expr (); if (curr_tok! = RP) return error ( "потрібно)"); get_token (); return e; case END: return 1; default: return error ( "потрібно первинне "); < p>)
)
Коли з'являється 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 (c) ненульовий, якщо c - буква або цифра, і нульовий вІнакше.
Наведемо функцію введення повністю:
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 * 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.1415926535897932385; insert ( "e") -> value = 2.7182818284590452354; < p> while (1) (get_token (); if (curr_tok == END) break; if (curr_tok == PRINT) continue; cout
