Програмування предиктивного синтаксичного аналізатора (ПСА)

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

Нерекурсивний синтаксичний аналізатор, представлений на рис. 5.5, шукає необхідну для аналізу продукцію в таблиці розбору (далі ми побачимо, яким образом можна побудувати цю таблицю на основі граматики).

Рис. 5.5. Модель нерекурсивного предиктивного синтаксичного аналізатора

Предиктивнй синтаксичний аналізатор, керований таблицею, має вхідний буфер, стек, таблицю розбору й вихідний потік. Вхідний буфер містить аналізований рядок з маркером її правого кінця – спеціальним символом. Стек містить послідовність символів граматики з $ на дні. Завжди стек містить стартовий символ граматики безпосередньо над символом $. Таблиця розбору являє собою двомірний масив M[А,а], де А – нетермінал, a а – термінал або символ $.

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

1. Якщо X = а = $, синтаксичний аналізатор припиняє роботу й повідомляє про успішне завершення розбору.

2. Якщо X = а ≠ $, синтаксичний аналізатор знімає зі стеку X і переміщує покажчик вхідного потоку до наступного символу.

3. Якщо X:: = ε, синтаксичний аналізатор знімає зі стеку X, але не переміщує покажчик вхідного потоку до наступного символу.

4. Якщо X являє собою нетермінал, програма розглядає запис M[X,а] з таблиці розбору М. Цей запис являє собою або X-продукцію граматики або запис про помилку. Якщо, наприклад, M[X,а] = {X::= UVW}, синтаксичний аналізатор заміщує X на вершині стеку на WVU (з U на вершині стека). Ми вважаємо, що як вихід синтаксичний аналізатор просто виводить використану продукцію, але, звичайно ж, тут може виконуватися будь-який необхідний код.

5. Якщо M[X,а] = error, синтаксичний аналізатор викликає програму відновлення після помилки.

Розглянемо послідовність роботи ПСА для рядка var a12: char;

У наведеному рядку роль символа його закінчення виконує символ “, ”, тому ПСА буде закінчувати роботу, коли покажчик стеку досягне симолу $ (дно стеку), а покажчик сканування рядка досягне символу “, ”.

Приклад 1. var a12: char;

Приклад 2. var a12,bc: integer;

Поиск по сайту: