Delphi World - Основи компіляції - Лекція 5
Матеріал до лекції 5. Розбір знизу догори. Зсув-згортка. Просте та операторне попередження.
Розглянемо розбір знизу-вгору, при якому проміжні ви води переміщаються по дереву у напрямку до кореня. Якщо вважати символи ланцюжка зліва направо, то дерево розбору буде виглядати наступним чином:
Граматики простого попередження
Граматика називається оборотною, якщо в ній немає двох правил з однаковими правими частинами. Нагадаємо, що граматика називається наведеною, якщо в ній немає e-правил, марних символів та циклів.
Задамося метою ввести на множині термінальних і нетермінальних символів три відносини (так звані "відносини попередження") (будемо позначати їх ') так, щоб у момент, коли потрібно згортка ланцюжка z, відносини між символами побудованої частини виведення ( ланцюжка x у позначеннях з початку лекції) і черговим символом b були наступними:
Якщо вдасться побудувати такі відносини, то LR-розбір для зворотної граматики можна проводити дуже просто:
Граматика називається граматикою простого попередження, якщо вона наведена, оборотна і між будь-якими двома терміналами або нетерміналами виконується не більше одного відношення попередження.
Практично відносини попередження можна обчислити наступним чином (X,Y - термінали або нетермінали, A,B,C-нетермінали, y - термінал, . - будь-яка ланцюжок (м.б. порожня)):
Обчислюючи відносини попередження для граматики S: aSSbc, отримаємо: a = S, S = S, S = b, . Ця граматика є граматикою простого попередження.
На практиці іноді зручно вважати, що на початку і наприкінці цієї нирки мови стоять символи-обмежувачі #. Їх відносини попередження визначаються так:
Відносинипередування зручно занести в матрицю, в якій рядки і стовпці позначені терміналами і нетерміналами грамоти. Вправа: Заповніть цю матрицю. Що означає ситуація, у якій між символами не виконується жодного із відносин попередження?
Граматики операторного попередження
Якщо у правилах наведеної оборотної граматики не зустрічаються поруч два нетермінали, кажуть, що граматика є операторною. Класичний приклад – граматика арифметичних формул. Для таких граматик можна обчислювати відносини попередження тільки на безлічі термінальних символів. Для цього модифікуємо правила обчислення відносин попередження:
Якщо між будь-якими двома терміналами виконується не більше одного відношення попередження, операторна граматика називається граматикою операторного попередження.
Обчислимо матрицю операторного попередження для граматики арифметичних формул:
Ці відносини дозволяють визначати термінали, що входять у праву частину правила, що згортається, але не нетермінали. Однак, при практичному розборі формул немає необхідності розрізняти не термінали S, T і E. Вони були введені тільки для надання грамоті однозначності та обліку пріоритету та асоціативності операцій. Тепер, отримавши відносини попередження, можна знову замінити ці штучно запроваджені нетермінали на S:
і отримати аналіз, обробляючи всі нетермінали однаково.
Лінеаризація матриці попередження
Якщо отриманий граф циклічний, лінеаризація неможлива. Інакше покласти f[i] рівним довжині найдовшого шляху з F[i], g[i] рівним довжині найдовшого шляху із G[i].
Застосувавши цей метод для збудованої матриці операторного попередження, отримаємо:
Ще одинкомпілятор формул (операторне попередження)
Для реалізації компілятора формул у польський постфіксний запис зв'яжемо з кожним згортком дію:
Побудований частковий висновок будемо зберігати в стеку:
Завдання на рішення на ЕОМ:
- Переробіть компілятор так, щоб він не допускав помилкових (тобто не породжуваних граматикою) ланцюжків.
- Додайте в компілятор операцію зведення в ступінь (право | асоціативна операція "^" з найвищим пріоритетом).
- Перетворіть компілятор формул на інтерпретатор.
- Додайте до компілятора операцію "унарний мінус".