LR-1

Программная реализация LR(1) - разбора

Первоначальная грамматика языка

<A> - аксиома
<A>::= <B>|<D>
<B>::= <B><C><C>|a      
<C>::= ba      
<D>::= <C>a<D>|b 

Преобразованная грамматика под LR(1)

1. A::=₁B₂
2. A::= ₁D₃
3. B::= ₁a₄Z₅
4. Z::= _4,9b₆a₇b₈a₉Z₁₀
5. Z::= _4,9Λ_4,9
6. D::= _1,14b₁₁X₁₂
7. X::= ₁₁a₁₃a₁₄D₁₅
8. X::= ₁₁Λ₁₁

Λ - означает пустую строку

Правило "С" было удаленно, так как содержало только терминальные символы. Поэтому везде где был вызов "С", были поставленны терминальные символы.

Рекомендуется сначала ознакомится с LL(1) интерпертацией данной грамматики здесь

Таблица

№	A	B	Z	C	D	X	a	b	$
1	ДОПУСК	Shift 2	ошибка	ошибка	Shift 3	ошибка	Shift 4	Shift 11	ошибка
2	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 1
3	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 2
4	ошибка	ошибка	Shift 5	ошибка	ошибка	ошибка	ошибка	Shift 6	Reduction 5
5	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 3
6	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Shift 7	ошибка	ошибка
7	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Shift 8	ошибка
8	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Shift 9	ошибка	ошибка
9	ошибка	ошибка	Shift 10	ошибка	ошибка	ошибка	ошибка	Shift 6	Reduction 5
10	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 4
11	ошибка	ошибка	ошибка	ошибка	ошибка	Shift 12	Shift 13	ошибка	Reduction 8
12	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 6
13	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Shift 14	ошибка	ошибка
14	ошибка	ошибка	ошибка	ошибка	Shift 15	ошибка	ошибка	Shift 11	ошибка
15	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	ошибка	Reduction 7