Наприклад, id і ліва дужка додаються до FIRST(F) на кроці 3 алгоритму для FIRST, оскільки FIRST(id)={id} і FIRST('(')={ (} у відповідності з кроком 1. На кроці 3 при і=1 відповідно до продукції T→FT' до FIRST(T) додаються також id і ліва дужка. На кроці 2 у FIRST(Е') включається ε.На кроці 1 обчислення множини FOLLOW у FOLLOW(E) включаємо $. На кроці 2, використовуючи продукцію F→(E), до FOLLOW(E) додається також права дужка. На кроці 3, застосованому до правила E→TE', у FOLLOW(Е') включаються $ і права дужка. Оскільки Е'ε, вони також потрапляють у FOLLOW(T). Відповідно до продукції E→TE' на кроці 2 у FOLLOW(T) включається усе з FIRST(Е'), відмінне від ε.
4.4 Побудова таблиць предиктивного аналізу
Для конструювання таблиць предиктивного аналізу даної граматики G може бути використаний алгоритм, ґрунтується на такій ідеї. Припустимо, що A→α – продукція граматики і aFIRST(α). Тоді аналізатор робить розгортання A за α, якщо вхідним символом є a. Труднощі виникають, коли α=ε або α
Алгоритм 4.4 Побудова таблиць предиктивного аналізу
Для кожної продукції A→α граматики виконати кроки 1 і 2.
Крок 1 Для кожного термінала a з FIRST(α) додати A→α в M[A,a].
Крок 2 Якщо εFIRST(α), додати A→α в M[A,b] для кожного термінала b з FOLLOW(A). Якщо ε
FIRST(α) і $
FOLLOW(A), додати A→α в M[A,$].
Крок 3 Прийняти, що всі невизначені входи таблиці M вказують на помилку.
Застосуємо алгоритм до граматики (4.2). Оскільки FIRST(TE')=FIRST(T)={(, id}, у відповідності з продукцією E→TE' входи M[E,(] і M[E,id] стають рівними E→TE'.Відповідно до продукції Е'→+TE' вхід M[Е',+] дорівнює Е'→+TE'. У відповідності з продукцією Е'→ε входи M[Е',)] і M[Е',$] рівні Е'→ε, оскільки FOLLOW(Е') ={ ), $}.Таблиця аналізу, побудована алгоритмом, була представлена вище таблицею 4.1.
4.5 LL(1)-граматики
Алгоритм побудови таблиці M предиктивного аналізу може бути застосований до будь-якої граматики. Однак для деяких граматик M може мати неоднозначно визначені входи. Наприклад, якщо граматика ліворекурсивна або неоднозначна, M буде мати хоча б один неоднозначно визначений вхід.
Граматики, для яких таблиці аналізу не мають неоднозначно визначених входів, називаються LL(1). Перше L означає сканування входу зліва направо, друге L означає, що будується ліве породження, 1 – що на кожному кроці для прийняття рішення використовується один символ непереглянутого ланцюжка.
Можна показати, що алгоритм побудови таблиці предиктивного аналізу для кожної LL(1)-граматики G будує таблиці, за якими розпізнаються всі ланцюжки мови, визначеної граматикою G, і тільки вони.
LL(1)-граматики мають кілька відмітних властивостей.
Неоднозначна, або ліворекурсивна, граматика не може бути LL(1)-граматикою.
Можна також показати, що граматика G є LL(1)-граматикою тоді і тільки тоді, коли для двох правил вигляду A→α | β виконується таке:
1) ні для якого термінала a одночасно з α і β не виводяться рядки, що починаються з a;
2) тільки з одного рядка α або β може виводитися порожній рядок;
3) якщо β
Мову, для якої можна побудувати LL(1)-граматику, називають LL(1)-мовою.
4.6 Висхідний аналіз
У цьому розділі розглянемо основний метод висхідного синтаксичного аналізу, відомий як “перенесення-згортання”. Далі будемо коротко називати його ПЗ-аналіз.
У процесі розбору типу “перенесення-згортання” будується дерево розбору вхідного рядка, починаючи з листів (знизу) до кореня (вгору). Цей процес можна розглядати як “згортання” рядка w до початкового символа граматики. На кожному кроці процесу згортання підрядок, який можна зіставити правій частині деякої продукції, заміняється символом з лівої частини цієї продукції, і якщо на кожному кроці вибирається правильний підрядок, то у зворотному порядку простежується праве породження.
Розглянемо граматику
S → aABe,
A → Abc | b ,
B→ d .
Рядок abbcde зводиться до Sза допомогою таких кроків:
abbcde
aAbcde
aAde
aABe
S.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.