Ll(1)-граматика.

Це граматика такого типу, на основі якої можна отримати детермінований синтаксичний аналіз за принципом зверху вниз.

Дві букви L в LL(1) означає, що рядок розбирається зліва направо і використовується самі ліві виводи, а цифра 1 – що варіанти породжуючих правил вибираються за допомогою одного попереднього символу.

LL(1)-граматика являється узагальненням S-граматики:

1. права частина кожного породжуючого правила розпочинається з терміналу;

2. в тих випадках, коли в лівій частині більше ніж одне породжуюче правило з’являється нетермінал, відповідні частини розпочинаються з різних терміналів.

Розглянемо граматику:

Вводиться поняття символа-попередника. Він позначається як S(T)={q}

де A – нетермінальний символ, - рядок терміналів та/ чи нетерміналів, а S(A) означає множину символів-попередників A. Розглянемо приклад

S(RY)={p};

S(TZ)={q}.

В LL(1)-граматиці можуть бути пусті рядки. Необхідною умовою для того, щоб граматика була LL(1)-граматикою, є те, що множина символів-попередників для альтернативних правих сторін породжуючих правил не перетинались. Приклад :

Множини символів-попередників: S(AB)={a,b,c}, S(BQ)={b,c}. Вони перетинаються, тому дана граматика не є LL(1)-граматикою. Розглянемо інший приклад :

Множини символів-попередників будуть : S(BC)={b,l}, S(PQ)={p,q}, але PQ має пустий рядок, тому вводиться поняття символів слідування та позначаються D(PQ)={b,l} – можуть слідувати за нетерміналом, який породжує пустий рядок. Символи-попередники і символи слідування називаються направляючими символами і позначаються:

DS(A,BC)={{b,l}};

DS(A,PQ)={{p,q},{b,l}}.

Ці множини перетинаються, тому і ця граматика не є LL(1).

Означення:

Граматика є LL(1)-граматикою, якщо множини направляючих символів для альтернативних правих частин правил не перетинаються.

Приведення до ll(1)-граматики.

Не існує теоретичних доказів того, що можна перетворити чи ні. Практика показує, що більшість граматик можна перетворити в LL(1)-граматику. Існують такі методи:

1. Усунення лівої рекурсії:

2. Факторизація:

Алгоритм перевірки належності граматики до класу ll(1)-граматик.

Розглянемо на прикладі:

Щоб проаналізувати дану граматику необхідно побудувати три матриці:

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

S	A	B	C	P	Q
-	+	-	-	+	+

2. Будується матриця безпосередніх попередників:

	A	B	C	P	Q	b	c	p	q	e	f
A		1		1	1	1*		1*	1*	1*
B						1				1
C							1				1
P								1
Q									1
S	1	1		1*	1*	1*		1*	1*	1*

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

1* - в таблиці позначені ті конфігурації, які отримані в результаті транзитивного замикання.

3.Матриця слідування:

	A	B	C	P	Q	b	c	p	q	l	f
A		1				1				1
B			1				1				1
C		1				1				1
P					1				1
Q		1				1				1
S

Побудувавши ці матриці, зробимо їх аналіз:

DS(A,BC)={b,l};

DS(A,PQ)={p,q,b,l}.

Як видно ці множини перетинаються, тому ця граматика не являється LL(1)-граматикою.

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

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

Перш за все потрібно пронумерувати всі термінали та нетерміналі. Правила нумерації:

• нумеруються зліва направо;

• спершу нумеруються ліві частини альтернативних правил, а потім їх праві частини.

Таблиця розбору.

№	Очікувані термінали	Пере- хід	При- йняти	В стек	Із стеку	По- милка
1.	begin	2	-	-	-	+
2.	begin	3	+	-	-	+
3.	ідентифікатор	7	-	4	-	+
4.	,	5	+	-	-	+
5.	оператор	15	-	6	-	+
6.	end	0	+	-	-	+
7.	ідентифікатор	8	-	-	-	+
8.	ідентифікатор	9	+	-	-	+
9.	; ,	10	-	-	-	+
10.	;	12	-	-	-	-
11.	,	14	-	-	-	+
12.	;	13	+	-	-	+
13.	ідентифікатор	7	-	-	-	+
14.	,	0	+	-	+	+
15.	оператор	16	-	-	-	+
16.	оператор	17	+	-	-	+
17.	; end	18	-	-	-	+
18.	;	20	-	-	-	+
19.	end	22	-	-	-	-
20.	;	21	+	-	-	+
21.	оператор	15	-	-	-	+
22.	end	0	+	-	+	+

Правила побудови таблиці розбору:

Очікувані термінали:

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

Перехід:

• якщо в правій частині правила стоїть перший термінал - перехід до наступного стану в правій частині;

• якщо нетермінал в правій частині – стан першого з альтернативних правил для цього нетерміналу, а якщо за ним стоїть терміна або нетермінал - цей стан заносимо в стек, якщо пусто – із стеку;

Помилка:

• скрізь, крім альтернативних лівих частин правил.

LL(1)-граматика має ланцюг переваг:

1. Не потрібне повертання, оскільки цей метод – детермінований.

2. Час розбору (приблизно) пропорційний довжині програми. Для процесу компіляції цілком може виявитися не так, оскільки деякі дії, які виконуються під час компіляції, наприклад, пошук в таблиці, можуть витратити різний час в залежності від розмірів таблиці, що в свою чергу пов’язане з розміром таблиці.

3. Мають хороші діагностичні характеристики та існує можливість виправлення помилок, так як синтаксичні помилки розпізнаються по першому не вірному символу, а в таблиці розбору є перелік можливих символів речення.

4. Таблиці розбору менші, ніж відповідні таблиці в інших методах розбору.

5. LL(1)-розбір застосовується для широкого класу мов – всіх мов, які мають LL(1)-граматику.

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