5.2.2 Обрізка основ

Звернене праве породження може бути отримане за допомогою "обрізки основ". Ми починаємо процес із рядка терміналів w, що хочемо проаналізувати. Якщо w – речення розглянутої граматики, то w=γ_n, де γ_n – n-а правосентенціальна форма деякого, ще невідомого правого породження S = γ_{0 rm}→ γ_{1 rm}→ γ_{2 rm}→ … _rm→ γ_{n-1 rm}→ γ_{n rm}→ w.

Для відтворення цього породження у зворотному порядку ми знаходимо основу β_n, в γ_n і заміняємо її лівою частиною продукції A_n ::= β_п для одержання (n-1)-й сентенціальної форми γ_n-1. Помітимо, що поки ми не знаємо, яким чином шукати основи, але незабаром познайомимося з відповідними методами.

Потім ми повторюємо описаний процес, тобто знаходимо в γ_п основу β_п-1 і згортаємо її для одержання правосентенціальної форми γ_n-2. Якщо після чергового кроку правосентенціальна форма містить тільки стартовий символ S, ми припиняємо процес і повідомляємо про успішне завершення аналізу. Звернена послідовність продукцій, використаних у згортках, являє собою праве породження вхідного рядка.

Приклад 5.9. Розглянемо граматику (5.1) з приклада 5.8 і вхідний рядок id₁+id₂*id₃. Послідовність згорток, що приводить вхідний рядок до стартового символу E, показана на рис. 5.13. Звернемо увагу на те, що послідовність правосентенціальних форм у цьому прикладі являє собою зворотню послідовність правих породжень з приклада 5.8.

Правосентенціальна форма	Основа	Згортаюча продукція
іd1+id2*id3	іd1	E ::= id
E+id2*id3	іd2	E ::= id
E+E*id3	іd3	E ::= id
E+E*E	E*E	E ::= E * E
E+E	E+E	E ::= E+E
E

Рис. 5.13. Згортки, виконувані ПЗ-аналізатором

5.2.2 Стекова реалізація пз-аналізу

Існує дві проблеми при синтаксичному аналізі методом обрізки основ. Перша полягає у виявленні підрядка для згортки в правосентенціальній формі, а друга - у визначенні, яка саме продукція повинна бути обрана, якщо є декілька продукцій з відповідним підрядком у правій частині. Перед тим як відповісти на ці питання, спочатку розглянемо структури даних, використовувані в ПЗ-аналізаторі.

Досить зручний шлях реалізації ПЗ-аналізатора складається у використанні стека для зберігання символів граматики й вхідного буфера для зберігання аналізованого рядка. Як маркер дна стека ми використаємо $, і цей же символ є маркером правого кінця вхідного рядка. З самого початку стек порожній, а вхідний буфер містить рядок w:

Стек Вхід

$ w$

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

Стек Вхід

$S $

Потрапивши в цю конфігурацію, синтаксичний аналізатор припиняє роботу й повідомляє про успішний розбір вхідного рядка.

Приклад 5.10. Пройдемо покроково всі дії, виконувані синтаксичним аналізатором при розборі вхідного рядка id₁+id₂*id₃ граматики (5.16), використовуючи перше породження з прикладу 5.8. Послідовність дій показана на рис. 5.14. Помітимо, що оскільки граматика (5.1) має два правих породження для даного вхідного рядка, існує ще одна послідовність переносів і згорток, які може виконати аналізатор.

№	Стек	Вхід	Дія
1	$	id1+id2*id3$	Перенос
2	$id1	+id2*id3$	Згортка по E ::= id
3	$E	+id2*id3$	Перенос
4	$E+	id2*id3$	Перенос
5	$E+ id2	*id3$	Згортка по E ::= id
6	$E+E	*id3$	Перенос
7	$E+E*	id3$	Перенос
8	$E+E* id3	$	Згортка по E ::= id
9	$E+E*Е	$	Згортка по E ::= E*Е
10	$E+E	$	Згортка по E ::= E+Е
11	$E	$	Допуск

Рис. 5.14. Конфігурації ПЗ-аналізатора для вхідного рядка id₁+id₂*id₃$

Основними операціями синтаксичного аналізатора є перенос і згортка, але насправді ПЗ-аналізатор може виконувати чотири дії: (1) перенос, (2) згортка, (3) допуск, (4) помилка.

1. При переносі черговий вхідний символ переноситься на вершину стека.

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

3. При допускі синтаксичний аналізатор повідомляє про успішний розбір вхідного рядка.

4. При помилці синтаксичний аналізатор виявляє помилку у вхідному потоці й викликає програму відновлення після помилок.

Розглянемо дуже важливий факт, що пояснює використання стека в ПЗ-аналізаторі: основа завжди перебуває на вершині стека й ніколи – усередині нього. Це стає очевидним при розгляді можливих видів двох послідовних кроків у будь-якому правому породженні. Ці два кроки можуть бути наступними:

(1) S _rm→^* αAz _rm→^* αβByz _rm→^* αβγ yz

(2) S _rm→^* αBxAz _rm→^* αBxyz _rm→^* αγ xyz

У випадку (1) А заміняється на βBy, а потім крайній справа нетермінал B в правої частини – на γ. У випадку (2) А також заміняється першим, але цього разу права частина являє собою рядок y, що складається тільки з терміналів. Наступний крайній справа нетермінал B знаходиться ліворуч від y.

Розглянемо випадок (1) у зворотному порядку, починаючи з моменту, коли ПЗ-аналізатор досяг конфігурації

Стек Вхід

$αβγ yz$

Тепер синтаксичний аналізатор згортає основу γ у В і переходить у конфігурацію

Стек Вхід $αβВ yz$

Оскільки В є крайнім справа нетерміналом в αβByz, правий кінець основи рядка αβByz не може перебувати усередині стека. Таким чином, синтаксичний аналізатор може перенести рядок y у стек для одержання конфігурації

Стек Вхід

$αβBy z$

у якій βBy є основою й згортається в А.

У випадку (2) у конфігурації

Стек Вхід $αγ xyz$

основа γ перебуває на вершині стека. Після згортки γ в B синтаксичний аналізатор може перенести рядок ху для одержання наступної основи γ на вершині стека:

Стек Вхід

$ αBxy z$

Тепер синтаксичний аналізатор згортає γ в А.

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