Синтаксичний аналіз. Спадний аналіз. Предиктивний аналізатор. Висхідний аналіз

4 СИНТАКСИЧНИЙ АНАЛІЗ

4.1Спадний аналіз

Синтаксичний аналіз є найбільш важливою частиною процесу компіляції. У теорії компіляції замість терміна “магазин” частіше використовують термін “стек”, тому в даному розділі ми також будемо використовувати цю назву.

Розглянемо спадний аналіз в його загальному вигляді – методом рекурсивного спуску, який може використовувати відкіт, іншими словами, виконувати повторне сканування вхідного потоку.

            Розглянемо граматику:

            S → cAd ,                                                       (4.1)

            A → ab | a

і вхідний рядок  w=cad.

При спадній побудові дерева розбору для цього рядка ми спочатку створюємо дерево, що складається з одного вузла, позначеного як S. Покажчик входу вказує на c, перший символ рядка w. Тепер скористаємося першою продукцією для S, щоб одержати дерево, зображене на рис. 4.1.

Рисунок  4.1 - Дерево 1 для  рядка  w=cad

Крайній ліворуч лист c відповідає першому символу w, перемістимо покажчик входу до a, другого символу рядка w, і розглянемо наступний лист дерева, позначений A. Тепер можна скористатися для A першою альтернативою й одержати дерево, зображене на рис. 4.2.

Рисунок  4.2 - Дерево 2 для  рядка  w=cad

Нами виявлена відповідність зчитаного символа a листу дерева, і ми переходимо до наступного символа d. Однак d не відповідає листу дерева b, а отже, ми повинні повернутися до A для того, щоб вибрати нову альтернативу для роботи.

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

Рисунок  4.3 - Дерево 3 для  рядка  w=cad

Лист a відповідає другому символу w, а лист d – третьому. Оскільки в цей момент нами побудоване дерево розбору для w, ми припиняємо роботу і повідомляємо про успішне завершення розбору.

4.2Предиктивний аналізатор

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

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

Модель предиктивного синтаксичного аналізатора, що керується таблицею, показана на рис. 4.4.

Рисунок 4.4 - Схема предиктивного аналізатора

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

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

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

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

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

Алгоритм 4.1  Нерекурсивний предиктивний аналіз 

Спочатку аналізатор знаходиться у конфігурації з $S (на вершині – стартовий символ S граматики G) і рядком w$ у вхідному буфері.

Установити покажчик ip на перший символ w$;

repeat

      Позначимо через X символ на вершині стека, 

      а через a – символ, на який вказує ip.

      if X – термінал або $ then

             if X=a then видалити X зі стека і перемістити ip

             else error

      else /*X – нетермінал*/

if M[X,a]=X→Y1Y2...Yk then begin

видалити X зі стека; помістити у стек

Yk ,Yk-1 ,... ,Y1 ,  з  Y1 на вершині стека;

               вивести продукцію X→Y1Y2...Yk

end

       else error /*вхід таблиці M порожній*/

until X=$ /*стек порожній*/

Візьмемо знову граматику арифметичних виразів:

E→TE' ,        E’→+TE' | ε,(4.2)

            T → FT ' ,       T’ → *FT ' | ε ,

            F→(E) | id .

Нижче подана табл. 4.1 предиктивного аналізату для цієї граматики. 

Таблиця 4.1