Інтерпретативний підхід має на меті одноразове обчислення виразу. Процес обчислення не такий швидкий як у відкомпільованої програми, але зате немає потреби витрачати багато часу і ресурсів на компіляцію.
Не можна однозначно сказати який з цих підходів є кращим. Кожен з них має свою сферу застосування. У таких відомих математичних пакетах як MathCad, Mathematica, Derive та інших застосовують інтерпретативний підхід, оскільки користувачів найчастіше цікавить отримання одиничного результату. Зате при обчисленнях в пакетах математичного моделювання кожна зайва операція в циклі обробки моделі значно збільшує час, необхідний для розрахунків, тому тут найчастіше звертаються до компіляції виразів.
§2. Перевірка правильності виразів.
Перед тим, як почати обчислювати значення виразу, логічним є спочатку перевірити його на правильність. Взагалі кажучи, задача зчитування довільної послідовності символів і прийняття рішення про те, що вона являє собою правильний арифметичний чи логічний вираз, є нетривіальною. Її вирішення торкається теорії формальних мов і складає окрему частину теорії компіляції.
Цілком очевидно, що ті обмеження, які ми накладали раніше на арифметичні вирази є дуже жорсткими і для практичних обчислень їх потрібно зняти. Тому надалі вважаємо наступне:
Очевидно також те, що для всіх ідентифікаторів, які зустрічаються у виразі, нам потрібно мати таблицю значень. Ця таблиця ставить у відповідність всім змінним і константам їх числове значення, а для арифметичних функцій визначає адресу в пам’яті, де знаходиться процедура обчислення значення даної функції.
Серед методів аналізу виразів можна виділити три основні: лексичний, синтаксичний і семантичний.
Лексичний аналіз (від грецького lexikos - той, що відноситься до слова) ставить на меті визначити правильність запису та використання символів, знаків, слів, ідентифікаторів - так званих лексем мови. У випадку арифметичних виразів лексичний аналіз має визначити:
На практиці разом з лексичним аналізом виконують лексичну згортку виразу. Ця процедура спрямована на спрощення подальших маніпуляцій з виразом і суть її полягає в тому, що всі символьні ідентифікатори та числові константи у виразі замінюються спецсимволами-посиланнями на таблицю значень лексем. Тобто замість символьного запису назви змінної чи послідовності символів-цифр, які позначають число, ми одразу будемо мати адресу комірки пам’яті, де зберігається значення (змінної чи константи), а замість назви функції - адресу початку процедури, яка виконує обчислення даної функції.
Приклад лексичної згортки:
вираз 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, бо якщо вираз містить тільки двохмісні арифметичні операції, то сумарна ємність вдвічі більша за кількість функцій. Доводиться дане твердження аналогічно попередньому.
Поняття сумарної ємності всіх функцій арифметичного виразу є важливим в тому плані, що воно є певним інваріантом, відносно якого можна робити оцінки по кількості операцій алгоритмів.