РЕКУРСИВНЫЙ СПУСК

Рассмотрим подкласс КС-грамматик - S-грамматики

Определение 5.2. S-грамматики — это подкласс контекстно-свободных грамматик, таких что:

1. Правая часть каждого правила начинается с терминала.

A ® ab | ba

2. Если в грамматике есть альтернативные правила, то они обязательно начинаются с разных терминальных символов

A ® ab | ba, причём a ¹ b.

S-грамматики часто называют разделёнными или простыми.

Пример 5.3. G[S]:

1. S ® aT

2. S ® TbS

3. T ® bT

4. T ® ba

G[S] не является S-грамматикой, так как в правиле 2 первый символ — нетерминальный, а это противоречит условию 1 для S-грамматик. Также 3 и 4 правила не удовлетворяют условию 2, так как два альтернативных правила начинаются с одного терминального символа.

Пример 5.4. G’[S]:

1. S ® abR

2. S ® bRbS

3. R ® a

4. R ® bR

G’[S] — удовлетворяет всем условиям и является S-грамматикой.

Анализ S-грамматик весьма эффективен методом рекурсивного спуска.

Метод рекурсивного спуска. Основная идея метода рекурсивного спуска состоит в том, что каждому нетерминалу грамматики ставится в соответствие определённая программная единица, процедура или функция (например в языке С — функция), которая распознаёт цепочку, порождаемую этим нетерминалом. Эти процедуры (функции) вызываются в соответствии с правилами грамматики, причём иногда вызывают сами себя рекурсивно. Следовательно, языком реализации этого метода, может быть лишь такой язык, который допускает рекурсию.

Пример 5.5. G[S]:

1. S ® aAS

2. S ® b

3. A ® cASb

4. A ® L

Легко видеть, что G[S] —S - грамматика. Приведем анализ G[S] методом рекурсивного спуска (рис. 5.18.).

 

Корневой сегмент	Процедура S	Процедура A
“Начало”   Установим вход = первый входной символ; S; Если вход ¹ то ERROR; Иначе STOP;   /* — признак окончания программы */	Переход по символу:	Переход по символу:
Символ	Метка	Символ	Метка
a	M1	a	M4
b	M2	b	M4
c	ER	с	M3
	ER		ER
Другой	ER	Другой	ER
M1: Scan; A; S; Возврат; M2: Scan; Возврат; ER: ERROR; Возврат;	M3: Scan; A; S; Если вход ¹ ‘b’ то ERROR; Иначе Scan; Возврат; M2: Возврат;

Рис. 5.18. Алгоритм работы функции

 

На рис. 5.18. проиллюстрирован алгоритм работы функции (нетерминалов) A, S и корневого сегмента на некотором псевдоязыке. В соответствии с правилами 1, 2 грамматики G[S] процедура S должна начинаться с терминалов a или b и не может начинаться с терминалов c или , поэтому переход по этим символам влечёт ошибку, то есть переход на метку ERROR.

Приведем еще пример реализации метода рекурсивного спуска для грамматики “инструкция”

G[<инструкция>]

1. <инстр> ® <пер> = <выр> |

IF <выр> THEN <инстр> [ ELSE <инстр> ]

2. <пер> ® i[(<выр>)]

3. <выр> ® T{+T}

4. T ® O{*O}

5. O ® <пер> | (<выр>)

По классификации Хомского легко показать, что G[<инстр>] является контекстно-свободной и разделённой, то есть грамматикой типа LL(1) (LastLeft — самый крайний левый символ). В общем случае рассматривают грамматики LL(К), в которых по К левым символам определяется принадлежность цепочки к соответствующему правилу грамматики. Грамматики этого класса удовлетворяют главному критерию однозначности и безвозвратности разбора. Эти грамматики также как и S-грамматики эффективно анализировать методом рекурсивного спуска. Учитывая выше приведённый алгоритм рекурсивного спуска, покажем реализацию синтаксического процессора методом рекурсивного спуска на Алголоподобном языке с принятыми следующими допущениями:

1) Переменная nx (от слова next) всегда содержит очередной символ, по которому определяется альтернативами LL(1) - грамматики.

2) scan готовит очередной символ исходной программы и помещает его в nx.

3) error процедура, обрабатывающая ошибки синтаксиса (управление передаётся в вызывающую программу).

Следуя методу рекурсивного спуска, все нетерминалы грамматики G[<инстр>] обозначим своими процедурами, несущими туже аббревиатуру, что и нетерминалы.

instr /* <инстр> */

{

if (nx=“IF”) then

begin

scan;

expr;

if (nx!=“THEN”) then

error;

else

begin

scan;

instr;

if (nx=“ELSE”) then

begin

scan;

instr;

end;

end;

end;

else

begin

var;

if (nx!=“=”) then

error;

else

begin

scan;

expr;

end;

end;

}

/*---------------------------------------------------------------------*/

var /* <пер> */

{

if (nx!=“i”) then error;

else

begin

if (nx!=“(”) then

begin

scan;

expr;

if (nx!=“)”) then error;

else scan;

end;

end;

}

/*---------------------------------------------------------------------*/

 

expr /* <выр> */

{

t;

while (nx=“+”) do

begin

scan;

t;

end;

}

/*---------------------------------------------------------------------*/

t /* Т */

{

o;

while (nx=“*”) do

begin

scan;

o;

end;

}

/*---------------------------------------------------------------------*/

o; /* O */

{

if (nx=“(”) then

begin

scan;

expr;

if (nx!=“)”) then error;

else scan;

end;

else var;

}