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

Наприклад, 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. Труднощі виникають, коли α=ε або αε. У цьому  випадку потрібно  розгорнути A у α, якщо поточний вхідний символ  належить FOLLOW(A)  або  якщо з вхідного потоку одержано $  і  $FOLLOW(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)  якщо βε, то з α не виводиться  ніякий  рядок, що починається з терміналу з FOLLOW(A).
Мову, для якої можна побудувати LL(1)-граматику, називають LL(1)-мовою.
 

4.6 Висхідний аналіз

У цьому розділі розглянемо основний метод висхідного синтаксичного аналізу, відомий як “перенесення-згортання”. Далі будемо коротко називати його ПЗ-аналіз.
У процесі розбору типу “перенесення-згортання” будується дерево розбору вхідного рядка, починаючи з  листів (знизу) до кореня (вгору). Цей процес можна розглядати як “згортання” рядка w до початкового символа  граматики.  На  кожному  кроці процесу згортання підрядок, який  можна зіставити правій частині деякої продукції, заміняється  символом з лівої  частини цієї продукції, і  якщо  на  кожному  кроці  вибирається правильний підрядок, то у зворотному порядку  простежується праве породження.
Розглянемо граматику
S  aABe,
A  Abc | b ,
B d  .
Рядок abbcde зводиться до Sза допомогою таких кроків:
abbcde
aAbcde
aAde
aABe
S.