Раздел 5.

«АЛГОРИТМ РАЗБОРА ДЛЯ LL(1)-ГРАММАТИК»

Задание 5.2.7.    Построить управляющую таблицу и промоделировать работу LL(1)-анализатора для КС-грамматики G = < T, N, S, R >.

T = { a, b, c }, N = { S, A, B },

R = {S  → aAB, S  → bA, S → ε, A → aAb, A → ε, B  → bB, B  → c };

Управляющая таблица:

R = { S → aAB(1), S → bA(2), S → ε(3), A→ aAb(4), A → ε(5), B → bB(6), B  → c(7) };

	a	b	с	ε
S	aAB, 1	bA, 2		ε, 3
A	aAb, 4	ε, 5		ε, 5
B		bB, 6	c, 7
a	Выброс
b		Выброс
c			Выброс
⊥				Допуск

 Пример разбора цепочки (aaabbbc), порождаемой заданной LL(1)-грамматикой, с помощью разработанного алгоритма:

(aaabbbc, S , ε) →

(aaabbbc, aAB , 1) →

(aabbbc, AB , 1) →

(aabbbc, aAbB , 14) →

(abbbc, AbB , 14) →

(abbbc, aAbbB , 144) →

(bbbc, AbbB , 1445) →

(bbbc, bbB , 1445) →

(bbc, bB , 1445) →

(bc, B , 1445) →

(bc, bB , 14456) →

(c, B , 144567) → ДОПУСК