Стан |
action |
goto |
id + * ( ) $ |
E T F |
|
0 1 2 3 4 5 6 7 8 9 10 11 |
s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 |
1 2 3 8 2 3 9 3 10 |
Для вхідного рядка id+id*id послідовність станів стека і вхідного буфера наведена у табл. 4.6.
Наприклад, у першому рядку LR-аналізатор перебуває у стані 0 і читає перший вхідний символ id. Дія s5 у нульовому рядку і стовпці id таблиці action означає перенесення і занесення на вершину стека стану 5. У другому рядку виконується занесення в стек першого символа id і символа стану s5 та видалення id з вхідного потоку.
Після цього поточним вхідним символом стає “*”. Дія для стану s5 і вхідного символа “*” – r6, тобто згортання у відповідності з продукцією F→ id. З вершини стека при цьому знімаються два символи (один символ стану й один символ граматики), і на вершині стека з’являється стан 0. Тепер аналізується нульовий стан. Оскільки goto[0,F] дорівнює s3, у стек заносяться F і 3. Тепер маємо конфігурацію, яка відповідає третьому рядкові. Інші кроки визначаються аналогічно.
Таблиця 4.6
Стек |
Вхідний потік |
Дія |
(1) 0 (2) 0 id 5 (3) 0 F 3 (4) 0 T 2 (5) 0 T 2 * 7 (6) 0 T 2* 7 id 5 (7) 0 T 2* 7 F 10 (8) 0 T 2 (9) 0 E 1 (10) 0 E 1+ 6 (11) 0 E 1+ 6 id 5 (12) 0 E 1+ 6F 3 (13) 0 E 1+ 6T 9 (14) 0 E 1 |
id*id+id $ *id+id $ *id+id $ *id+id $ id+id $ +id $ +id $ +id $ +id $ id $ $ $ $ $ |
Перенесення Згортання за F→ id Згортання за T→ F Перенесення Перенесення Згортання заF→ id Згортання заT→ T*F Згортання заE→ T Перенесення Перенесення Згортання заF→ id Згортання заT→ F Згортання заE→ E+T Допуск |
4.9 LR-граматики
Граматики, для яких можна побудувати таблицю LR-розбору, називаються LR-граматиками. Існують контекстовільні граматики, що не є LR-граматиками, однак практично для опису мов типових конструкцій мов їх можна уникнути.
Щоб граматика була LR-граматикою, аналізатор, що працює зліва направо по типу перенесення-згортання, повинен уміти розпізнавати основи на вершині стека. LR-аналізатор не повинен сканувати весь стек, щоб розпізнати появу основи на вершині стека. Більше того, символ стану на вершині стека містить всю необхідну інформацію. Але якщо можна розпізнати основу, знаючи тільки символи граматики в стеку, то існує скінченний автомат, що може, читаючи символи граматики в стеку зверху вниз, визначити цю основу. Функцією переходів цього скінченного автомата є таблиця переходів LR-аналізатора. Щоб не переглядати стек на кожному кроці аналізу, на вершині стека завжди зберігається той стан, у якому повинен виявитися цей скінченний автомат після того, як він прочитав символи граматики в стеку від дна до вершини.
Для вибору рішення про перенесення або згортання аналізатор переглядає чергові k вхідних символів. Практичний інтерес становлять випадки k=0 і k=1. Наприклад, у колонках action табл. 4.5 використовується тільки один символ. Граматика, для розбору якої LR- аналізатору потрібен перегляд до k вхідних символів на кожному кроці, називається LR(k)-граматикою.
Основна різниця між LL- і LR-граматиками полягає у наступному. Щоб граматика була LR(k), необхідно вміти розпізнавати появу правої частини продукції, бачачи усе, що породжено з цієї правої частини, а також k вхідних символів. Ця вимога істотно менш строга, ніж вимога для LL(k)-граматики, коли необхідно визначити застосовну продукцію, бачачи тільки перші k символів, виведених з її правої частини.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.