4.10 Побудова таблиць SLR-аналізу
Покажемо, яким чином можна побудувати таблицю LR-аналізу для даної граматики. Перший метод – простий LR (simple LR, SLR), – найбільш слабкий з них за кількістю граматик, з якими він працює, однак найбільш простий в реалізації. Таблицю, побудовану таким методом, будемо називати SLR-таблицею, синтаксичний аналізатор, який працює з SLR-таблицею, – SLR-аналізатором, а відповідну граматику – SLR-граматикою.
LR(0)-пункт, або просто пункт граматики G,– продукція з точкою в деякій позиції правої частини. Для покращання читання пункт іноді будемо записувати у квадратних дужках. Отже, продукція A→XYZ дає чотири пункти:
A→ •XYZ ,
A→ X•YZ ,
A→ XY•Z ,
A→ XYZ• .
Продукція A→εгенерує тільки один пункт A→•. Пункт може бути представлений парою цілих чисел, перше з яких представляє номер продукції, а друге – позицію точки. Пункт показує, яку частину продукції ми вже бачили в даній точці у процесі синтаксичного аналізу. Наприклад, перший пункт, наведений вище, визначає, що у вхідному потоці ми очікуємо зустріти рядок, породжуваний ХУZ. Другий пункт указує, що в нас уже є рядок, породжений X, і ми очікуємо одержати з вхідного потоку рядок, породжуваний УZ.
Основна ідея SLR-методу полягає у тому, щоб спочатку побудувати на базі граматики детермінований скінченний автомат для розпізнавання активних префіксів. Ми групуємо пункти у множини, що приводять до станів SLR-аналізатора. Пункти можуть розглядатися як стани недетермінованого скінченного автомата, що розпізнає активні префікси, і тоді групування являє собою не що інше як побудову замикання.
Система LR(0)-пунктів, яку назвемо канонічною, забезпечує основу для побудови SLR-аналізаторів. Для побудови канонічної LR(0)-системи граматики ми визначимо розширену граматику і дві функції – closureі goto.
Якщо G – граматика зі стартовим символом S, то G', розширена граматика граматики G, являє собою G з новим стартовим символом S' і продукцією S'→S. Призначення цієї нової стартової продукції указати синтаксичному аналізаторові, коли він повинен припинити розбір і оголосити про допуск вхідного рядка. Таким чином, допуск рядка відбувається тоді і тільки тоді, коли синтаксичний аналізатор виконує згортання, що відповідає продукції S'→S.
Розглянемо, як виконується операція замикання. Якщо I – множина пунктів граматики G, то closure(1) – множина пунктів, побудована з I за такими правилами:
1 Спочатку в closure (I) входять усі пункти з I.
2 Якщо А→α•Вβ входить у closure (I) і В→γ являє собою продукцію, то додаємо в closure(I) пункт B→• γ (якщо його там ще немає). Ми застосовуємо це правило доти, поки не внесемо всі можливі пункти в closure(I).
Наявність А→α•Вβ в closure(I) указує, що в деякий момент у процесі синтаксичного аналізу ми вважаємо, що можемо зустріти у вхідному потоці підрядок, виведений з Вβ. Але якщо є продукція В→γ, то, природно, ми також можемо зустріти в цей момент рядок, виведений з γ, тому включаємо B→• γ в closure(I).
Приклад 4.1
Розглянемо розширену граматику арифметичних виразів:
Е'→ Е , T→T*F | T , (4.4)
Е→ E+T | T , F→ (E) | id .
Якщо I являє собою множину з одного пункту {Е'→•E}, то closure(I)містить пункти:
E'→ • E , T→ •F ,
E→•E+T , F→• (E) ,
E→•T , F→• id .
T→•T*F ,
Тут E'→• E міститься в closure(I)відповідно до правила (1). Оскільки Е розміщене безпосередньо за точкою, відповідно до правила (2) додаються також Е-продукції з точкою зліва, тобто E→•E+T і E→•T. Тепер, оскільки серед пунктів є Т,щойде за точкою, ми додаємо T→ •T*Fі T→•F і, аналогічно, F→• (E) і F→• id. Більше додавати в closure(I)нічого.
При реалізації обчислень зручно ввести масив булевих величин added, проіндексований нетерміналами G так, що added[B] дорівнює true, якщо ми додаємо пункти B→• γ для кожної В-продукції B→ γ.
Алгоритм 4.6 Обчислення функції closure
function closure(I);
begin
J:=I
repeat
for кожного елемента А→α•Вβ з J і кожної
продукції B→ γ, такої, що B→• γ не входить в J
do додати B→• γ в J
until більше додавати нічого
return J
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.