LL-аналізатор

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

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

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

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

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

[ S, $ ]

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

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

[ S, +, F, ), $ ]

[ F, +, F, ), $ ]

[ a, +, F, ), $ ]

[ F, ), $ ]

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

[ 2, 1, 3, 3 ]

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

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

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

#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;
}

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

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

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

Щоб заповнити таблицю аналізу, ми маємо з'ясувати яке правило використовувати, коли аналізатор бачить нетермінал 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) граматикою.

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

• Синтаксичне дерево
• Аналіз зверху вниз
• Аналіз знизу вверх
• JFLAP

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

• ANTLR
• Coco/R
• JavaCC

• Просте пояснення множин First та Follow (англ.) (спроба пояснити процес створення цих множин у більш прямолінійний спосіб)
• Інструкція реалізації LL(1)-аналізатора на C# (англ.)
• Симулятор аналізатора.