Оптимальні програми

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

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

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

В -> 12

C -> 136

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

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

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

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

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

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

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

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

•правильність розкладення дужок (приклад неправильного розкладення ")А+В(" );

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

•правильність виклику арифметичних функцій (чи є потрібна кількість аргументів, чи записані вони через кому, чи немає зайвих).

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

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