Операторні граматики
Як і раніше, наша мета – вирішити задачу аналізу вхідної послідовності і обійтися при цьому якомога меншими витратами на пошук. Метод, про який йтиметься далі, заснований на понятті пріоритету символів аналізованої послідовності, а точніше - пріоритету операторів (іноді поряд з терміномоператорні граматикивикористовується термінграматики простого попередження).
Нехай даний вхідний ланцюжок символів "….RS…". Спробуємо відразу визначити, яке правило нам буде зручніше виконати (точніше, над якою частиною ланцюжка спочатку робити операції, тобто з якого символу починати). Для цього можна використовувати поняття пріоритету, ґрунтуючись на введеній системі відносин між символами, а саме:
для будь-якого ланцюжка "….RS…" можливі наступні варіанти:
Якщо є правило, що закінчується R,
тоді можна сказати, що R & gt; S.
Якщо є правило, що включає RS,
тоді можна сказати, що R = S.
Якщо є правило, що починається на S,
тоді можна сказати, що R
Рядки та стовпці # відповідають за ситуацію, коли вхідна послідовність порожня (і ми повинні виконати те, що залишилося в стеку OP), і за початок роботи, коли стек порожній і ми повинні занести в черговий OP символ.
Елементи матриці 'X' позначають хибну (заборонену) ситуацію.
Умовою нормального закінчення роботи алгоритму є ситуація, коли в стеку знаходиться єдиний символ # (S = #), а значення R є також #. У всіх інших випадках вважається, що вираз, що розбирається, побудовано некоректно.
Розглянемо приклад аналізу виразу (a*b/c+d)*e#
Перевагою даного методу є його безперечна простота, а також висока швидкість виконання (не витрачається час на пошук правиларедукції). Більше того, цей метод може бути застосований не тільки для аналізу арифметичних виразів, але й для аналізу фраз контекстно-вільних мов взагалі.
Однак усі ці переваги геть тьмяніють перед головним недоліком даного методу. Справа в тому, що тут практично відсутня будь-яка діагностика (і тим більше – локалізація) помилок (крім випадку звернення до елемента матриці X). По-друге, деякі помилки у вихідному виразі не діагностуються зовсім. Наприклад, вирази, в яких зустрічаються дужки «(» і «)», що йдуть поспіль.
І останнє зауваження. Основна наша мета полягала у формуванні деякої проміжної форми представлення вихідної програми. Тут відбуваєтьсябезпосереднє обчисленнявирази. Проте цей метод придатний і для формування як польської форми запису, так і зошит. Формування необхідних вихідних послідовностей відбувається на момент редукції, тобто. у момент виклику процедури семантичної обробки. Наприклад, в стек ARG можна просто поміщати послідовно не тільки операнди, а й оператори, взяті зі стеку S. Тоді в ARG ми отримаємо польську форму запису виразу, що розбирається.