LL-парсер

LL-аналізатор — алгоритм синтаксичного аналізу методом рекурсивного спуску для підмножини контекстно-вільних граматик. Він обробляє вхід зліва направо (тому перша буква означає Left) та будує рядка (тому його порівнюють з ). Клас граматик, що розпізнаються цим аналізатором, називається LL-граматиками.

Далі описується табличний аналізатор — альтернатива алгоритму рекурсивного спуску, який зазвичай кодується вручну (хоча не завжди, дивіться наприклад ANTLR для генератора аналізаторів LL(*)-граматик методом рекурсивного спуску).

LL-аналізатори називаються LL(k)-аналізаторами, якщо вони дивляться на k токенів вперед протягом аналізу виразу. Якщо такий аналізатор існує та може розпізнавати вирази граматики без бектрекінгу, тоді граматика називається LL(k)-граматикою. З цих граматик найпопулярнішою граматикою є граматика LL(1), бо незважаючи на її обмеженість, вона має дуже простий аналізатор. Мови, що відповідають LL(k)-граматикам з великим k, вважаються такими, що важко аналізуються, хоча сьогодні це не зовсім вірно через доступність та поширеність генераторів синтаксичних аналізаторів, що підтримують LL(k)-граматики.

LL-аналізатор називається LL(*)-аналізатором, якщо він не обмежений скінченним числом токенів для попереднього перегляду, а може приймати рішення визначаючи чи належать вхідні токени регулярній мові (наприклад використовуючи ДСкА).

Існує конкуренція між «європейською школою» проектування мов, яка віддає перевагу LL-граматикам, та «американською», яка частіше використовує LR-граматики. Це багато в чому завдяки традиціям викладання та детальному опису методів та інструментів в літературі. Інший вплив іде від досліджень Ніклауса Вірта в Вищій технічній школі Цюріха, які описували багато способів оптимізації LL(1)-мов та компіляторів.

Загальний випадок

Аналізатор працює на рядках з певної контекстно вільної граматики.

Аналізатор складається з

• вхідного буфера, в якому зберігається вхідний рядок
• стека, в якому зберігають термінальні та нетермінальні символи з граматики, що аналізується.
• таблицю аналізу, яка каже яке (якщо існує ) правило граматики застосувати залежно від символів на вершині стеку, та наступного вхідного токена.

Аналізатор застосовує правило з таблиці, яке відповідає символу на вершині стеку (рядок таблиці) та символу з вхідного потоку (стовпець).

Коли аналізатор запускається, стек вже містить два символи:

[ S, $ ] 

де '$' — спеціальний термінал, що вказує на дно стека, та кінець вхідного потоку, а 'S' — . Аналізатор спробує змінити вміст стека на те, що він знайде на вході. Тим не менш він тільки тримає в стеку те, що має бути переписаним.

Конкретний приклад

Ініціалізація

Щоб пояснити як це працює, ми візьмемо наступну невелику граматику:

1. S → F
2. S → ( S + F )
3. F → a

яка аналізує наступний вхід:

( a + a )

Таблиця аналізу для цієї граматики виглядає так:

	(	)	a	+	$
S	2	—	1	—	—
F	—	—	3	—	—

(Зауважте, що є також стовпчик для спеціального терміналу $, що позначає кінець вводу.)

Процедура аналізу

На кожному кроці парсер читає наступний доступний символ з вхідного потоку, та символ на вершині стеку. Якщо вхідний символ та символ на вершині стеку співпадають, парсер відкидає їх обох, залишаючи тільки символи, що не співпали.

Тому на першому кроці аналізатор читає вхідний символ '(' та символ на вершині стеку 'S'. Інструкції з таблиці аналізу приходять від колонки з заголовком '(' та рядком з заголовком 'S'; ця клітинка містить '2', що вказує аналізатору застосувати правило (2). Аналізатор має замінити 'S' на '( S + F )' на вершині стеку та вивести правило номер 2. Стек приймає вигляд:

[ (, S, +, F, ), $ ] 

Так як '(' з вхідного потоку не співпадає з символом на вершині стеку, 'S', він не видаляється, та залишається як наступний доступний вхідний символ, для наступного кроку.

На другому кроці аналізатор видаляє ( з вхідного потоку, та з стеку, так як вони співпадають. Стек стає:

[ S, +, F, ), $ ] 

Тепер на вході 'a' та 'S' у стеку. Таблиця каже застосувати правило (1) граматики та вивести правило (1) у вихідний потік. Стек стає:

[ F, +, F, ), $ ] 

Аналізатор має 'a' на вході, та 'F' на вершині стеку. Таблиця каже застосувати правило (3). Стек стає:

[ a, +, F, ), $ ] 

На наступних двох кроках аналізатор читає 'a' та '+' з вхідного потоку, та, так як вони співпадають з символами в стеку теж видаляє їх звідти. Результат:

[ F, ), $ ] 

На наступних трьох кроках аналізатор замінить 'F' зі стеку на 'a, виведе правило 3 та видалить 'a' та ')' зі стеку та з вхідного рядка. Аналізатор таким чином завершить роботу коли '$' міститиметься як на вході, так і у стеку.

В такому випадку аналізатор скаже що він приймає вхідний рядок, та виведе наступний список номерів правил у вихідний потік:

[ 2, 1, 3, 3 ]

Це насправді список правил для ліворекурсивного виведення вхідного рядка у даній контекстно-вільній граматиці, які утворюють такий ланцюжок:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

Реалізація аналізатора на C++

Нижче дана реалізація на табличного LL-аналізатора для мови, що була дана в прикладі:

Реалізація аналізатора на C++

#include <iostream> #include <map> #include <stack> enum Symbols { // the symbols: // Terminal symbols: TS_L_PARENS,// ( TS_R_PARENS,// ) TS_A,// a TS_PLUS,// + TS_EOS,// $, in this case corresponds to '\0' TS_INVALID,// invalid token // Non-terminal symbols: NTS_S,// S NTS_F }; /* Converts a valid token to the corresponding terminal symbol */ enum Symbols lexer(char c) { switch(c) { case '(': return TS_L_PARENS; break; case ')': return TS_R_PARENS; break; case 'a': return TS_A; break; case '+': return TS_PLUS; break; case '\0':// this will act as the $ terminal symbol return TS_EOS; break; default: return TS_INVALID; break; } } int main(int argc, char **argv) { using namespace std; if (argc < 2) { cout << "usage:\n\tll '(a+a)'" << endl; return 0; } map< enum Symbols, map<enum Symbols, int> > table; // LL parser table, maps < non-terminal, terminal> pair to action stack<enum Symbols>ss;// symbol stack char *p;// input buffer // initialize the symbols stack ss.push(TS_EOS);// terminal, $ ss.push(NTS_S);// non-terminal, S // initialize the symbol stream cursor p = &argv[1][0]; // setup the parsing table table[NTS_S][TS_L_PARENS] = 2;table[NTS_S][TS_A] = 1; table[NTS_F][TS_A] = 3; while(ss.size() > 0) { if(lexer(*p) == ss.top()) { cout << "Matched symbols: " << lexer(*p) << endl; p++; ss.pop(); } else { cout << "Rule " << table[ss.top()][lexer(*p)] << endl; switch(table[ss.top()][lexer(*p)]) { case 1:// 1. S → F ss.pop(); ss.push(NTS_F);// F break; case 2:// 2. S → ( S + F ) ss.pop(); ss.push(TS_R_PARENS);// ) ss.push(NTS_F);// F ss.push(TS_PLUS);// + ss.push(NTS_S);// S ss.push(TS_L_PARENS);// ( break; case 3:// 3. F → a ss.pop(); ss.push(TS_A);// a break; default: cout << "parsing table defaulted" << endl; return 0; break; } } } cout << "finished parsing" << endl; return 0; }

Примітки

Як можна було бачити на прикладі, аналізатор виконує три види кроків залежно від того чи на вершині стеку термінал, нетермінал, чи спеціальний символ $:

• Якщо на вершині нетермінал, тоді він шукає в таблиці аналізу за базисом нетерміналу та символом у вхідному потоці яке граматичне правило варто використати, щоб замінити його у стеку. Номер правила записується у вихідний потік. Якщо таблиця каже що потрібного правила не існує, то виводиться помилка, і робота припиняється.
• Якщо на вершині термінал, тоді він порівнюється з символом на вході, та якщо вони рівні, вони обидва видаляються. Якщо вони не рівні, аналізатор виводить помилку та зупиняється.
• Якщо на вершині стеку $ та у вхідному потоці теж, тоді аналізатор доповідає про успішний аналіз вхідного потоку, інакше виводить помилку. В обох випадках аналіз зупиняється.

Ці кроки повторюються аж до зупинки аналізатора, і в результаті отримуємо або ланцюжок виведення, або повідомлення про помилку.

Побудова таблиці LL(1)-аналізатора

Щоб заповнити таблицю аналізу, ми маємо з'ясувати яке правило використовувати, коли аналізатор бачить нетермінал A на вершині стеку та символ a на вході. Легко побачити що це правило має мати форму A -> w та що мова що відповідає w має мати хоч одне слово, що починається з w. З такою метою ми описуємо First-set для w що записується тут як Fi(w), як множину терміналів, що можуть знаходитись на початку будь-якого слова з w, плюс ε якщо порожнє слово теж належить w. Маючи граматику з правилами A₁ → w₁, …, A_n → w_n, ми можемо обчислити Fi(w_i) та Fi(A_i) для кожного правила так:

1. ініціалізуємо кожне Fi(w_i) та Fi(A_i) порожньою множиною.
2. додаємо Fi(w_i) до Fi(A_i) для кожного правила A_i → w_i, де Fi описується так:
   • Fi(a w' ) = { a } для кожного теміналу a
   • Fi(A w' ) = Fi(A) для кожного такого нетерміналу A, що ε не належить Fi(A)
   • Fi(A w' ) = Fi(A) \ { ε } ∪ Fi(w' ) для кожного нетерміналу A, що ε належить Fi(A)
   • Fi(ε) = { ε }
3. додаємо Fi(w_i) до Fi(A_i) для кожного правила A_i → w_i
4. повторюємо кроки 2 та 3, аж поки всі множини Fi не стануть однаковими.

На жаль, множин Fi не достатньо, щоб вирахувати таблицю аналізу. Це тому, що права частина правила w може бути переписана в порожній рядок. Тому аналізатор також має використовувати правило A -> w якщо ε належить Fi(w) та видимий у вхідному потоці, як символ, що може йти за A. Тому ми також потребуємо множину Follow для A, яку запишемо як Fo(A) , яка описується як множина терміналів a таких що існує рядок символів αAaβ які можуть виводитись з початкового символу. Обчислення множини Follow для нетерміналів в граматиці може бути здійснене так:

1. ініціалізувати кожне Fo(A_i) порожньою множиною
2. якщо існує правило виду A_j → wA_iw' , тоді
   • якщо термінал a належить Fi(w' ), то додати a до Fo(A_i)
   • якщо ε належить Fi(w' ), то додати Fo(A_j) до Fo(A_i)
3. повторювати крок 2 поки всі Fo не стануть однаковими.

Тепер ми можемо описати точно, які правила де будуть зберігатись в таблиці аналізу. Якщо T[A, a] позначає місце в таблиці для нетерміналу A та терміналу a, тоді

T[A,a] містить правило A → w тоді і тільки тоді коли

a належить Fi(w) або

ε належить Fi(w) і a належить Fo(A).

Якщо таблиця містить щонайбільше одне правило в кожній клітинці, тоді аналізатор завжди буде знати яке правило він має використати і тому може аналізувати рядки без бектрекінгу. Це точно такий випадок для граматики що названа LL(1) граматикою.

Побудова таблиці аналізу для LL(k)-граматики

До середини 1990-тих вважалось, що LL(k)-аналіз (для k > 1) є непрактичним, так як розмір таблиці аналізу буде (зазвичай в гіршому випадку) мати експоненційну складність від k. Таке сприйняття сильно змінилось з випуском PCCTS близько 1992, коли було показано, що багато мов програмування можуть ефективно аналізуватись синтаксичним аналізатором LL(k)-граматики без використання поведінки для гіршого випадку. Більше того, в деяких випадках LL-аналіз можливий навіть для необмеженого преперегляду. А традиційні генератори аналізаторів, як yacc використовують таблиці аналізу щоб створити обмежений з фіксованим, однотокеневим препереглядом.

Конфлікти

Конфлікти LL(1)

Є три типи LL(1)-конфліктів:

• FIRST/FIRST

Множини FIRST двох різних нетерміналів перетинаються.

• FIRST/FOLLOW

Множини правил граматики FIRST та FOLLOW перетинаються. З ε, що належить множині FIRST, невідомо яку альтернативу вибрати.

Приклад конфліктів LL(1) :

 S -> A 'a' 'b' A -> 'a' | ε 

Множина FIRST для A дорівнює { 'a' ε } та множина FOLLOW { 'a' }.

• ліво-рекурсивний

Ліва рекурсія спричинить конфлікт FIRST/FIRST з усіма альтернативами.

 E -> E '+' term | alt1 | alt2 

Розв'язання конфліктів LL(1)

• Лівостороннє винесення за дужки

Працює приблизно як 3x + 3y = 3(x+y).

 A -> X | X Y Z 

стає

 A -> X B B -> Y Z | ε 

Може застосовуватись коли дві альтернативи починаються з одного і того ж символу, як у конфлікті FIRST/FIRST.

• Підстановка

Підстановка правила в інше правило, щоб вилучити непрямі конфлікти, чи конфлікти FIRST/FOLLOW. Зауважте, що це може спричинити конфлікт FIRST/FIRST.

• Вилучення лівої рекурсії

Простий приклад вилучення лівої рекурсії:

Наступні продуктивні правила мають ліву рекурсію на E

 E -> E '+' T -> T 

Ці правила задають ніщо інше, окрім списку з T, розділених '+'. У формі регулярного виразу записується так: T ('+' T)*. Тому правила можна переписати так

 E -> T Z Z -> '+' T Z -> ε 

Тепер немає лівої рекурсії та конфліктів у жодному з правил.

Див. також

• Синтаксичне дерево
• JFLAP

Генератори синтаксичних аналізаторів:

• ANTLR
• JavaCC

Посилання

• Просте пояснення множин First та Follow [ 3 січня 2019 у Wayback Machine.] (англ.) (спроба пояснити процес створення цих множин у більш прямолінійний спосіб)
• (англ.)
• Симулятор аналізатора [ 24 березня 2010 у Wayback Machine.].

Джерела

1. Modern Compiler Design, Grune, Bal, Jacobs and Langendoen