16. Висхідний аналіз
У цьому розділі буде розглянуто основний метод висхідного синтаксичного аналізу, відомий як синтаксичний аналіз типу "перенесення/згортка" (shift-reduce) і званий далі скорочено ПС-аналізом. Простий для реалізації вид ПС-аналізу, що називається синтаксичним аналізом пріоритету операторів. ПС-аналіз намагається будувати дерево розбору для вхідного рядка, починаючи з листя (знизу) та працюючи у напрямку до кореня дерева (вгору). Цей процес можна розглядати як згортку рядка w до стартового символу граматики. На кожному кроцізгорткиreduction step) деякий підрядок, що відповідає правій частині продукції, замінюється символом з лівої частини цієї продукції, і якщо на кожному кроці підрядка вибираються коректно, то ми отримуємо звернене праве породження.
Виділяють 3 базові поняття.
Основарядки А – це підрядок, для якої існує правило у цій граматиці
Згортка– це заміщення основи на лівий символ, правила в ланцюжку виведення (наB)
Перенесення– перенесення з вхідного рядка у стікову форму подання ланцюжка виведення.
Вхідний рядок bdc
ПС-аналізатор (перенесення, згортка)
Стековареалізація ПС-аналізу
Існує дві проблеми при синтаксичному аналізі методом обрізання основ. Перша полягає у виявленні підрядка для згортки у правосентенційній формі, а я — у визначенні, яка саме продукція має бути обрана, якщо є тільки продукція з відповідним підрядком у правій частині. Перед тим як відповісти на ці питання, спочатку розглянемо структури даних, які використовуються в ПС-аналізаторі.
Досить зручний шлях реалізації ПС-аналізатора полягає у використанні стека зберігання символів граматики та вхідного буфера для зберігання аналізованоїрядки. Як маркер дна стека ми використовуємо $, і цей символ є маркером правого кінця вхідного рядка. Спочатку стек порожній, а вхідний буфер містить рядокw.
Синтаксичний аналізатор працює шляхом перенесення нуля або кількох символів у стек доти, доки на вершині стека не виявиться основа β. Потім він згортає β
Лівою частини відповідної продукції. Синтаксичний аналізатор повторює цей цикл, доки не буде виявлено помилку або він не прийде в конфігурацію, коли в стеку знаходиться тільки стартовий символ, а вхідний буфер порожній:
Потрапивши в цю конфігурацію, синтаксичний аналізатор припиняє роботу та повідомляє про успішний розбір вхідного рядка.