Системне програмне забезпечення ЕОМ
Розробка інтерпретатора
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;
)
)
Перевірка відсутності поділу на нуль необхідна, оскільки результат ділення на нуль невизначений і, як правило, призводить до катастрофи.
Функція 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 ( "потрібно первинне");
)
)
Коли з'являється 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 = ii <<1 ^ * pp + +;
if (ii <0) ii =-ii;
ii% = TBLSZ;
Іншими словами, за допомогою операції ^ ( "виключає АБО") всі символи вхідного рядка p черзі додаються до ii. Розряд в результаті x ^ y дорівнює 1 тоді і тільки тоді, коли ці розряди в операнда x і y різні.
До виконання операції ^ значення ii зсувається на один розряд вліво, щоб використовувався не тільки один байт ii. Ці дії можна записати таким чином:
ii <<= 1;
ii ^ = * pp + +;
Для гарного хеш-код краще використовувати операцію ^, ніж +. Операція зсуву важлива для одержання прийнятного хеш-коду в обох випадках.
Оператори
if (ii <0) ii =-ii;
ii% = TBLSZ;
гарантують, що значення ii буде з діапазону 0 ... TBLSZ-1. Нагадаємо, що% - це операція взяття залишку. Нижче повністю приведена функція look:
# include
name * look (const char * p, int ins = 0)
(
int ii = 0;// хеш-код
const char * pp = p;
while (* pp) ii = ii <<1 ^ * pp + +;
if (ii <0) ii =-ii;
ii% = TBLSZ;
for (name * n = table [ii]; n; n = n-> next)// пошук
if (strcmp (p, n-> string) == 0) return n;
if (ins == 0) error ( "ім'я не знайдено");
name * nn = new name;// занесення
nn-> string = new char [strlen (p) +1];
strcpy (nn-> string, p);
nn-> value = 1;
nn-> next = 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 << "error:" < no_of_errors + +;
return 1;
)
Небуферізованний вихідний потік cerr звичайно використовується саме для видачі повідомлень про помилки.
Управління повертається з error () тому, що помилки, як правило, зустрічаються посеред обчислення виразу. Значить треба або повністю припиняти обчислення, або повертати значення, яке не повинне викликати наступних помилок. Для простого калькулятора більше підходить останнє. Якби функція get_token () відстежувала номери рядків, то функція error () могла б вказувати користувачеві приблизне місце помилки. Це було б корисно при неінтерактивному роботі з калькулятором.
Часто після появи помилки програма повинна завершитися, оскільки не вдалося запропонувати розумний варіант її подальшого виконання. Завершити її можна за допомогою виклику функції exit (), яка закінчує роботу з вихідними потоками і завершує програму, повертаючи свій параметр як її результату.
6. Драйвер
Коли всі частини програми визначені, потрібен тільки драйвер, щоб ініціалізувати і запустити процес. У нашому прикладі з цим впорається функція main ():
int main ()
(
// вставити зумовлені імена:
insert ( "pi") -> value = 3.1415926535897932385;
insert ( "e") -> value = 2.7182818284590452354;
while (cin) (
get_token ();
if (curr_tok == END) break;
if (curr_tok == PRINT) continue;
cout <)
return no_of_errors;
)
Прийнято, що функція main () повертає нуль, якщо програма завершується нормально, і нульове значення, якщо відбувається інакше. Нульове значення повертається як кількість помилок. Виявляється, вся ініціалізація зводиться до занесення зумовлених імен в таблицю.
У циклі main читаються вираження і видаються результати. Це робить один рядок:
cout < 7. Параметри командного рядка
Для зручності користування інтерпретатором використовуємо параметри командного рядка.
Як вже було сказано, виконання програми починається викликом main (). При цьому виклик main () отримує два параметри: число параметрів (зазвичай званий argc) і масив рядків параметрів (зазвичай званий argv).
Параметри - це символьні рядки, тому argv має тип char * [argc 1]. Назва програми (в тому вигляді, як воно було зад?? але в командному рядку) передається в argv [0], тому argc завжди не менше одиниці. Наприклад, для командного рядка
dc 150/1.1934
параметри мають значення:
argc 2
argv [0] "dc"
argv [1] "150/1.1934"
argv [2] 0
int main (int argc, char * argv [])
(
switch (argc) (
case 1:// зчитувати зі стандартного вхідного потоку
break;
case 2:// зчитувати з рядка параметрів
cin = * new istream (argv [1], strlen (argv [1]));
break;
default:
error ( "занадто багато параметрів");
return 1;
)
// вставити зумовлені імена:
insert ( "pi") -> value = 3.1415926535897932385;
insert ( "e") -> value = 2.7182818284590452354;
while (cin) (
get_token ();
if (curr_tok == END) break;
if (curr_tok == PRINT) continue;
cout <)
return no_of_errors;
)
При цьому istrstream - це функція istream, яка зчитує символи з рядка, що є її першим параметром. Щоб використовувати istrstream потрібно включити в програму файл , а не звичайний . В іншому ж програма залишилася без змін, крім додавання параметрів у функцію main () і використання їх в операторі switch. Можна легко змінити функцію main () так, щоб вона могла приймати декілька параметрів з командного рядка. Однак це не дуже потрібно, тим більше, що можна кількох виразів передати як один параметр:
dc "rate = 1.1934; 150/rate; 19.75/rate; 217/rate"
Лапки необхідні тому, що символ ';' служить в системі UNIX роздільником команд. В інших системах можуть бути свої угоди про параметри командного рядка.
8. Повний варіант програми:
# include
# include
# include
enum token_value (
NAME, NUMBER, END,
PLUS = '+', MINUS = '-', MUL ='*', DIV ='/',
PRINT =';', ASSIGN ='=', LP ='(', RP = ')'
);
token_value curr_tok;
struct name (
char * string;
name * next;
double value;
);
const TBLSZ = 23;
name * table [TBLSZ];
int no_of_errors;
double error (char * s) (
cerr << "error:" < no_of_errors + +;
return 1;
)
name * look (char * p, int ins = 0)
(
int ii = 0;
char * pp = p;
while (* pp) ii = ii <<1 ^ * pp + +;
if (ii <0) ii =-ii;
ii% = TBLSZ;
for (name * n = table [ii]; n; n = n-> next)
if (strcmp (p, n-> string) == 0) return n;
if (ins == 0) error ( "name not found");
name * nn = new name;
nn-> string = new char [strlen (p) + 1];
strcpy (nn-> string, p);
nn-> value = 1;
nn-> next = table [ii];
table [ii] = nn;
return nn;
)
inline name * insert (char * s) (return look (s, 1);)
token_value get_token ();
double term ();
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;
)
)
double prim ();
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 ( "divide by o");
left/= d;
break;
default:
return left;
)
)
int number_value;
char name_string [80];
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 ( ") expected");
get_token ();
return e;
case END:
return 1;
default:
return error ( "primary expected");
)
)
token_value get_token ()
(
char ch = 0;
do (
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 = 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;
while (1) (
get_token ();
if (curr_tok == END) break;
if (curr_tok == PRINT) continue;
cout <)
return no_of_errors;
)
