Основы программирования

Для заданной КС-грамматики написать синтаксический анализатор, реализующий метод рекурсивного спуска без откатов. Результатом работы синтаксического анализатора должно быть левое порождение входной строки, представленное списком правил грамматики, использованных в процессе порождения.

Использовать теорию контекстно-свободных грамматик.
1. Устранить левую рекурсию из грамматики (если это необходимо).
2. Выполнить левую факторизацию грамматики (если это необходимо).
3. Написать функции, реализующие правила грамматики для каждой переменной грамматики и использующие сведения из множеств FIRST.
4. Написать программу синтаксического анализатора.
5. Результаты работы программы на входных данных.

Устранение непосредственной левой рекурсии
A->Aα₁|Aα₂|...|Aα_n|β₁|β₂|...|β_m

A->β₁A'|β₂A'|...|β_mA'
A'->α₁A'|α₂A'|...|α_n|ε

Алгоритм устранения левой рекурсии, которая не является непосредственной рекурсией (гарантированно работает с грамматикой, не имеющей циклов и ε-правил).
1. Расположить все элементы грамматики в определённом порядке A₁, A₂,..., A_n.
2.for i=1 to n do begin
for j=1 to i-1 do begin
Заменить каждое правило вида
A_i->A_jα правилом
A_i->δ₁α|δ₂α|...|δ_kα,
где A_j->δ₁|δ₂|...|δ_k.
end
Устранить НЛР для A_i
end

Левая факторизация КСГ
Когда не ясно, каким из 2х правил для переменной A воспользоваться, переписать эти правила так, чтобы отложить принятие решения до тех пор, пока из входного потока не будут прочитано достаточно символов для правильного выбора.
Для каждой переменной A находим самое длинное начало строки α, общее для двух или более правых частей.
Если α≠ε, заменить правила A->αβ₁|...|αβ_n|γ, где γ не начинается с α-подстроки.
A->αA'|γ
A'->β₁|...|β_n
Повторять эти два варианта, пока не будут иметь одинакового начала.

Во многих случаях устранение левой рекурсии и проведение левой факторизации позволяет получить грамматику, которая может быть проанализирована синтаксическим анализатором, работающим методом рекурсивного спуска без отката.

Условие:
S->T+S|T-S|T
T->F*T|F
F->a|b

Левая рекурсия отсутствует, проводим левую факторизацию:
S->TA
A->+S|-S|e
T->FB
B->*T|e
F->a|b

Функции, реализующие правила грамматики для каждой переменной грамматики и использующие сведения из множеств FIRST:
FIRST(F)={a,b}
FIRST(A)={+,-,e}
FIRST(B)={*,e}
FIRST(T)=FIRST(F)={a,b}
FIRST(S)=FIRST(T)=FIRST(F)={a,b}

void S() { T(); A(); }
void T() { F(); B(); }
void F() { 
	switch(NextChar())
	{
		case 'a': MoveToNext('a');break;
		case 'b': MoveToNext('b');break;
		default: ErrorMsg();
	}
}
void A() {
	switch(NextChar())
	{
		case '+': MoveToNext('+'); S(); break;
		case '-': MoveToNext('-'); S(); break;
		default: break;
 
	} 
}
void B() {
	switch(NextChar())
	{
		case '*': MoveToNext('*'); T(); break;
		default: break;	
	}
}

Исходный код нисходящего синтаксического анализатора, реализующего заданную КСГ, находится в приложенном архиве.