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

Пункт F→•(Е) дає запис action[0, ( ]= “перенесення 4”, пункт F→• id – запис action[0, id]= “перенесення 5”. Інші пункти I₀ до записів actionне приводять. Тепер розглянемо I₁ :

Е'→ E• ,                     Е→Е•+Т .

Перший пункт дає action[1, $]= “допуск”, а другий – action[1, +]= “перенесення 6”. Перейдемо до  I ₂:

Е→ Т• ,                      T→Т•*F .

Оскільки FOLLOW(E)= {$, +,)}, з першого пункту випливає action[2, $]= action[2, +]= action[2, )]=        = “згортання Е→ Т”. Другий пункт дає action[2, *]= “перенесення 7”. Продовжуючи в такий спосіб розгляд множин пунктів, ми одержимо таблицю 4.5. У ній номери продукцій у згортках ті самі, що й номери, під якими продукції наведені у вихідній граматиці (4.3), тобто Е→Е+Т має номер 1, Е→Т – номер 2 і т.д.

Приклад 4.4

Будь-яка SLR(1)-граматика однозначна, але існує множина однозначних граматик, що не є SLR(1). Розглянемо граматику з продукціями:

S → L=R ,                  L → id ,          (4.5)

S → R ,                       R→ L .

L → *R ,

Ми можемо розглядати Lі Rяк позначення l- і r-значень відповідно (l -значення вказує місце розташування, r-значення – значення, що зберігається у місці розташування), а оператор * – як оператор “вміст”. Канонічна система множин LR(0)-пунктів цієї граматики показана нижче.

I₀ :       S'→ S ,                       L → •*R ,           

S → •L=R ,                 L → • id,

S →•R ,                      R → • L  .                   

I₁ :       S'→ S•  .                               

I₂ :       S →L• =R ,                R →L• .

I₃ :       S → R•  .

I₄ :       L → *• R ,                   L → • R ,

R → •L ,                      L → • id  .

I₅ :       L → id • .                   

I₆ :       L → L= •R ,                L → • *R ,                                          R → •L ,             L → • id  .

I₇ :       L → *R•  .

I₈ :       R → L•  .

I₉ :       S →L=R•  .

Розглянемо множину пунктів I₂. Перший пункт у цій множині встановлює action[2,=] як “перенесення 6”. Оскільки FOLLOW(R)містить “=”, другий пункт визначає action[2,=] як “згортання R → L”. Отже, запис action[2,=] визначений двічі, а оскільки для неї є і запис перенесення, і запис згортання, стан 2 приводить до конфлікту перенесення/згортання при вхідному символі =.

Граматика (4.5) не є неоднозначною. Виявлений конфлікт породжується тим, що метод SLR недостатньо могутній, щоб запам'ятати лівий контекст, необхідний для прийняття рішення про дії синтаксичного аналізатора при вхідному символі = і переглянутому рядкові, який виводиться з L. Канонічний метод, розглянутий нижче, успішно працює з великою кількістю граматик, включаючи граматику (4.5).

4.11 Побудова канонічних таблиць LR-аналізу

Розглянемо найбільш загальну технологію побудови таблиці LR-аналізу для граматики. Згадаємо, що в SLR-методі стан i викликає згортання за продукцієюї А→α, якщо множина пунктів I_i містить пункт [А→α•] і aFOLLOW(А). У деяких ситуаціях, однак, коли стан i розміщується на вершині стека, активний префікс βαу стеку такий, що в правосентенціальній формі за βA не може йти символ а. Отже, згортка по продукції А→α буде неприпустимою при вхідному символі а.

Приклад 4.5

Знову звернемося до прикладу 4.4, де у стані 2 був пункт R →L•, що міг відповідати наведеній вище продукції А→α, і а міг бути знаком =, що належить FOLLOW(R). Таким чином, SLR-аналізатор у стані 2 з черговим вхідним символом = викликає згортання за продукцією R→L. Однак у граматиці правосентенціальна форма, що починається з R = ..., відсутня. Отже, стан 2, що відповідає тільки активному префіксові L, не повинен викликати згортання цього Lв R.

 Стан може містити додаткову інформацію, що дозволить виключити деякі з таких некоректних згортань за продукцією А→α. Розділяючи за необхідності стани, ми можемо змусити кожен стан LR-аналізатора точно вказувати, який вхідний символ може йти за основою α, для якої існує можливе згортання в А.