Смекни!
smekni.com

Оптимальні програми обчислення виразів (стр. 3 из 6)

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

Не можна однозначно сказати який з цих підходів є кращим. Кожен з них має свою сферу застосування. У таких відомих математичних пакетах як MathCad, Mathematica, Derive та інших застосовують інтерпретативний підхід, оскільки користувачів найчастіше цікавить отримання одиничного результату. Зате при обчисленнях в пакетах математичного моделювання кожна зайва операція в циклі обробки моделі значно збільшує час, необхідний для розрахунків, тому тут найчастіше звертаються до компіляції виразів.

§2. Перевірка правильності виразів.

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

Цілком очевидно, що ті обмеження, які ми накладали раніше на арифметичні вирази є дуже жорсткими і для практичних обчислень їх потрібно зняти. Тому надалі вважаємо наступне:

  • змінні та константи в арифметичному виразі можуть позначатися не тільки великими буквами латинського алфавіту, але і довільним ідентифікатором (Ідентифікатор - послідовність букв і цифр, яка починається з букви і не містить пробілів всередині);
  • допустимим є використання числових констант, записаних у вигляді десяткового дробу;
  • допустимими є посилання на N-місні арифметичні функції, якщо це посилання має вигляд ІДЕНТИФІКАТОР(ПАРАМЕТР_1, . . . , ПАРАМЕТР_N), де N - натуральне число, ІДЕНТИФІКАТОР - ідентифікатор, що однозначно визначає арифметичну функцію, ПАРАМЕТР_1 . . . ПАРАМЕТР_N - правильні арифметичні вирази;
  • допускається застосування правил пріоритету операцій (табл. 1) замість використання дужок.

Очевидно також те, що для всіх ідентифікаторів, які зустрічаються у виразі, нам потрібно мати таблицю значень. Ця таблиця ставить у відповідність всім змінним і константам їх числове значення, а для арифметичних функцій визначає адресу в пам’яті, де знаходиться процедура обчислення значення даної функції.

Серед методів аналізу виразів можна виділити три основні: лексичний, синтаксичний і семантичний.

Лексичний аналіз (від грецького lexikos - той, що відноситься до слова) ставить на меті визначити правильність запису та використання символів, знаків, слів, ідентифікаторів - так званих лексем мови. У випадку арифметичних виразів лексичний аналіз має визначити:

  • правильність запису ідентифікаторів (чи всі функції та змінні названо правильно);
  • правильність запису числових констант ( "123,125.45" - неправильний запис);
  • відсутність сторонніх символів (чи, наприклад, не вжито десь фігурні дужки замість круглих).

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

Приклад лексичної згортки:

вираз Value(12) + 136 / Max

згортається до A(B)+C/D

де А -> адреса функції Value

В -> 12

C -> 136

D -> значення змінної/константи Мах.

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

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

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

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

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

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

  • правильність розкладення дужок (приклад неправильного розкладення ")А+В(" );
  • правильність взаємного розміщення знаків операцій і операндів (в інфіксній формі представлення виразу запис "/АВ+С" є неправильним );
  • правильність виклику арифметичних функцій (чи є потрібна кількість аргументів, чи записані вони через кому, чи немає зайвих).

Семантичний аналіз (від грецького semantikos - означаючий) покликаний дослідити зміст та сутність лексем і елементів виразу. Зокрема він відповідає за виявлення явних спроб ділення на нуль, взяття квадратного кореня із від’ємного числа і тому подібних випадків.

Після того, як до виразу було застосовано всі описані типи аналізів і виконано лексичну згортку, він може бути оброблений раніше розглянутими алгоритмами, які потрібно незначно модифікувати, з врахуванням того факту, що операція або арифметична функція може потребувати не двох операндів, а іншу їх кількість; тобто в алгоритмі POSTFIX просто доведеться забирати з стеку необхідну кількість операндів, а в алгоритмі ІТР застосовувати рекурсивний виклик самого себе для обробки кожного аргументу функції (який, взагалі кажучи, сам може бути складним арифметичним виразом).

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

§3. Оцінка складності алгоритмів.

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

· ввід та вивід елемента даних, присвоювання змінної - 1,

· запис на стек та зчитування зі стеку - 1,

· виклик процедури або функції - 1,

· умовний перехід (порівняння) - 1,

· виконання арифметичних чи логічних операцій - по кількості операцій,

· складність циклу рівна складності тіла циклу, помноженій на кількість повторів.

Введемо наступні означення. Ємністю арифметичної функції назвемо кількість дійсних (таких, що належать полю дійсних чисел) аргументів цієї функції. Всі натуральні і цілі числа надалі узагальнюємо до дійсних чисел. Наприклад: sign(x), (-x) - функції ємності 1, а - функція ємності 2. Якщо абстрагуватися від формату запису арифметичної функції, то можна сказати, що всі двохмісні алгебраїчні операції є функціями ємності 2. Приймаючи це до уваги, можемо сформулювати наступне твердження:

Твердження 3.

Кількість операндів у правильно записаному арифметичному виразі є числом, яке можна отримати, віднявши від сумарної ємності всіх функцій (операцій), що входять у вираз, кількість цих самих функцій і додавши одиницю:

К-сть операндів = сумарна ємність – к-сть функцій + 1.

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

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