Вашій увазі пропонується невеличке керівництво та описання реалізації алгоритму рекурсивного спуску на мові програмування C++.
Вступ Незважаючи на те, що стандарт мови C++ досить обширний, деякі теми, такі як синтаксичний аналіз виразів в ньому не розглядаються. Програми синтаксичного аналізу використовуються для обчислення значень алгебраїчних виразів, наприклад (100-23)*213. Сьогодні синтаксичні аналізатори оточені певною загадковістю. З різних причин, процедури що використовуються в процесі синтаксичного аналізу відомі небагатьом. Навіть дуже розумні програмісти іноді пасують перед необхідністю синтаксичного аналізу.
Насправді синтаксичний аналіз виразів - досить проста процедура. Ця простота є наслідком строгих правил алгебри. В цій роботі ми оглянемо програму аналізу методом рекурсивного спуску (recursive-descent parser) та всі її процедури. Однак перш ніж приступити до розробки, варто трохи розповісти про вирази і правила їх граматичного поділу.
Вирази Оскільки програма синтаксичного поділу обчислює арифметичні вирази, необхідно ясно уявити перед собою, з яких частин складається вираз. Розглянемо вирази з наступних компонентів: Числа Операції Дужки Змінні
В нашому синтаксичному аналізаторі символ “^” буде означати піднесення до степеня. Символ ”=” означає оператор присвоювання. Вище згадані компоненти об’єднуються у вираз, відповідно правилам алгебри. Наприклад: 123-23 (123-435)*334/34 х^3-1 x=1
Встановимо наступні пріоритети операторів.
Високий + - (унарні) ^ * / % + -Низький =
Оператори, котрі мають однаковий пріоритет, обчислюються зліва направо.
В прикладах, показаних по процесу пояснення, всі змінні позначаються однією буквою. Регістр літер не береться до уваги. В першій версії аналізатора всі числові змінні приводяться до дійсного типу.
Синтаксичний аналіз виразів: постановка задачі Існує багато способів синтаксичного аналізу і обчислення виразів. В рамках алгоритму рекурсивного спуску вирази розглядаються як рекурсивні структури данних. Якщо б вираз міг складатися із операцій +, -, *, / і дужок, то всі вирази можна було б визначити такими правилами:
<вираз> ::= <доданок> [+ <доданок>] [- <доданок>] <доданок> ::= <атом> [* <атом>] [/ <атом>] <атом> ::= <змінна> | <число> | (<вираз>)
Квадратні дужки містять необов'язковий елемент, а символ ::= інтерпритується як "породжує". Правила, вказані вище, часто називають породжуючими правилами, або продукціями. Тому, визначення доданка можна було б озвучити так: "Доданок породжує атом чи атом помножений чи поділений на атом". Зверніть увагу на те, що породжуючі правила неявно враховують пріоритет операцій.
Вираз: 10+5*Х складається з двох доданків: 10 і 5*X. Другий доданок складається з двох атомів: 5 і Х. Ці атоми складаються з одного числа і однієї змінної.
З іншого боку, вираз 14*(7-Х) складається з двох атомів: 14 і (7-Х). Атоми складаються з одного числа і одного виразу, поміщеного в дужки. Вираз в дужках складається з двох доданків.
Цей процес виявляє базис рекурсивного спуску, що представляє собою набір взаємнорекурсивних функцій, що реалізують створені правила. На кожному кроці аналізатор виконує операції, послідовність яких визначена правилами алгебри. Щоб продемонструвати, як породжені правила застосовуються для синтаксичного аналізу виразів, подивимося наступний приклад. 9/3-(100+56) Для синтаксичного аналізу треба виконати такі дії: Знайти перший терм 9/3. Знайти кожний атом і поділити цілі числа. Результат буде рівний 3. Знайти другий атом, (100+56). Запустити рекурсивний аналіз другого підвиразу. Знайти всі атоми і додати їх. Результат 156. Повернутися з рекурсивного виклику і відняти 156 від 3 отримавши -153.
Потрібно знати дві речі: Породжені правила неявно враховують приорітет операторів. Цей метод аналізу і обчислення виразу дуже схожий на спосіб, з допомогою якого люди самі обчислюють математичні вирази.
Далі ми розглянемо три програми синтаксичного аналізу виразів. Перша програма аналізує і рахує вираз з дійсним типом, що складається лише з констант. Потім ми розглянемо синтаксичний аналізатор, що дозволяє приймати змінні. А третя версія аналізатора буде реалізована у вигляді шаблонного класу, який можна застосувати для синтаксичного аналізу виразів довільного типу.
Клас parser В основі програми синтаксичного аналізу виразів лежить клас parser. Перша версія цього класу приведена нижче. Наступні версії будуть створюватись на основі модифікацій першої.
class parser { char *exp_ptr; char token; char tok_type; double vars[NUMBER];
void eval_exp2(double &result); void eval_exp3(double &result); void eval_exp4(double &result); void eval_exp5(double &result); void eval_exp6(double &result);
void atom(double &result); void get_token(); void putback(); void serror(int error); double find_var(char *s); int isdelim(char c); public: parser(); double eval_exp(char *exp);
Клас parser містить три закриті поля. Вираз є звичайним рядком, на початок якого вказує вказівник exp_ptr. В процесі роботи аналізатор зчитує рядок, переміщуючи вказівник, аж поки не знайдеться його кінець. Так аналізатор обчислює значення виразу що зберігається в простих ASCII-рядках. Інші два поля, token і tok_type, використовуються в лексичному аналізі, про що буде говоритись пізніше.
Початковою точкою аналізу є функція eval_exp(), якій треба передати вказівник на вхідний вираз. Функції eval_exp2() - eval_exp6() разом з функцією atom() реалізують породжені правила вказані вище. В наступних версіях аналізатора до них буде додано функцію eval_exp1().
Функція serror() призначена для обробки синтаксичних помилок, створених у виразі. Функції get_token() і isdelim() використовуються для розбиття виразу на складові частини.
Лексичний аналіз Для того, щоб обчислити вираз, нам потрібно буде розбити його на компоненти. Ця операція називається лексичним аналізом.
Кожен компонент виразу називається лексемою (токеном). Наприклад, вираз A * B - (W + 10) містить лексеми А, *, B, -, (, W +, 10, і ). Кожна лексема представляє собою нерозділювану частину виразу.
Для синтаксичного аналізу необхідна функція (лексичний аналізатор), яка послідовно повертала б окремі лексеми, з яких складається вираз. Крім того, функція повинна ігнорувати пропуски, а також виявляти кінець виразу. Функція, що дозволяє виділяти лексеми, називається - get_token. Вона є членом класу parser.
Нам також потрібно буде знати тип лексем. В нашій програмі використані тільки три типи лексем: VARIABLE (змінна), NUMBER (число) і DELIMITER (розділювач). До типу DELIMITER відносяться також оператори і дужки.
Функція get_token() розглянута нижче. Вона отримує наступну лексему з виразу, на який вказує вказівник exp_ptr і поміщає її в змінну token. Тип отриманої лексеми записується в змінну tok_type. // Отримує наступну лексему. void parser::get_token() { char *temp; tok_type = 0; temp = token; *temp = '\0'; if (!*exp_ptr) return; // в кінці виразу while(isspace(*exp_ptr)) ++exp_ptr; // пропустити пропуски if(strchr("+-*/%^=()", *exp_ptr)) { tok_type = DELIMITER; *temp++ = *exp_ptr++; } else if(isalpha(*exp_ptr)) { while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++; tok_type = VARIABLE; } else if (isdigit(*exp_ptr)) { while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++; tok_type = NUMBER;
*temp = '\0'; }
//Якщо параметр с є роздільником // повертає значення true int parser::isdelim(char c) { if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0) return 1; return 0; }
Придивимось до цих функцій. Після перших ініціалізацій функція get_token() перевіряє, чи не знайдено кінець вхідного рядка. Для цього вона перевіряє символ, на який вказує вказівник exp_ptr. Якщо його значення рівне нулю, то досягнуто кінця виразу. Якщо у виразі залишились ще не вилучені лексеми, функція get_token() ігнорує всі пропуски що йдуть на початку. Оскільки пропуски ігноруються, вказівник exp_ptr може вказувати або на число, змінну, оператор або кінець виразу. Якщо наступним символом є оператор, він записується в змінну token, а в змінну tok_type записується константа DELIMITER. Якщо наступний символ - буква, то припускається, що лексема є змінною, а змінна tok_type = VARIABLE. Якщо наступний символ - цифра, то зчитується все число і записується в змінну token, а в змінну tok_type записується константа NUMBER. Нарешті, якщо наступний символ не має жодного відношення до тих типів, вважається, що функція get_token() досягнула кінця виразу.
Як заявлено раніше, щоб геть зовсім не запутувати код, в ньому пропущена перевірка на помилки, але з декількома домовленостями. Наприклад, передбачається, що вираз не може містити нерозпізнаних символів. Також, в цій версії програми змінні можуть мати довільну довжину, але істотний тільки перший символ.
Щоб краще зрозуміти процес розбиття виразу на лексеми, розглянемо приклад. А + 100 - (B * C) /2 Ось такі лексеми і типи повертає функція get_token() в цьому прикладі: Лексема Тип А VARIABLE + DELIMITER 100 NUMBER - DELIMITER ( DELIMITER В VARIABLE * DELIMITER С VARIABLE ) DELIMITER / DELIMITER 2 NUMBER \0 0
Проста програма синтаксичного аналізу виразів Розглянемо першу версію синтаксичного аналізатора. Він вичислює значення виразів, складених лише з констант, операторів, дужок.
#include <iostream> #include <cstdlib> #include <cctype> #include <cstring>
using namespace std;
enum types { DELIMITER = 1, VARIABLE, NUMBER};
class parser { char *exp_ptr; // вказує на вираз char token; // зберігає поточну лексему char tok_type; // зберігає тип лексеми void eval_exp2(double &result); void eval_exp3(double &result); void eval_exp4(double &result); void eval_exp5(double &result); void eval_exp6(double &result); void atom(double &result); void get_token(); void serror(int error); int isdelim(char c); public: parser(); double eval_exp(char *exp);
// конструктор parser::parser() { exp_ptr = NULL;
//відправна точка parser
double parser::eval_exp(char *exp) { double result; exp_ptr = exp; get_token(); if(!*token) { serror(2); return 0.0; } eval_exp2(result); if(*token) serror(0); return result; } // додати або віднімати два тарма void parser::eval_exp2(double &result) { register char op; double temp; eval_exp3(result); while((op = *token) == '+' || op == '-') { get_token(); eval_exp3(temp); switch(op) { case '-': result = result - temp; break; case '+': result = result + temp; break;
// перемножаємо або ділимо два фактори void parser::eval_exp3(double &result) { register char op; double temp;
eval_exp4(result); while((op = *token) == '*' || op == '/' || op == '%') { get_token(); eval_exp4(temp); switch(op) { case '*': result = result * temp; break; case '/': result = result / temp; break; case '%': result = (int) result % (int) temp; break;
// степінь void parser::eval_exp4(double &result) { double temp, ex; register int t;
eval_exp5(result); if(*token== '^') { get_token(); eval_exp4(temp); ex = result; if(temp==0.0) { result = 1.0; return; } for(t=(int)temp-1; t>0; --t) result = result * (double)ex;
// обчислення унарних операцій + або - void parser::eval_exp5(double &result) { register char op; op = 0; if((tok_type == DELIMITER) && *token=='+' || *token == '-') { op = *token; get_token(); } eval_exp6(result); if(op=='-') result = -result;
// розпізнавання дужок void parser::eval_exp6(double &result) { if((*token == '(')) { get_token(); eval_exp2(result); if(*token != ')') serror(1); get_token(); } else atom(result);
// получаємо число void parser::atom(double &result) { switch(tok_type) { case NUMBER: result = atof(token); get_token(); return; default: serror(0);
// виводить повідомлення про помилку void parser::serror(int error) { static char *e[]= { "Syntax Error", "Unbalanced Parentheses", "No expression Present"
cout << e[error] << endl;
// дістає наступну лексему void parser::get_token() { register char *temp; tok_type = 0; temp = token;