Начальная установка.

S[1]:=(z,0,0,0,0); c:=1; V:=1; j:=1; GOTO<новый человек >//Первое усыновление цель усыновлённого - начальный символ z.

Новый человек.

if( <GOAL – терминал>)

if (input [j]== GOAL)

(j:=j+1; GOTO <успех>}

else GOTO<неудача>

i::= <индекс в GRAMMAR правой части для GOAL> GO TO <цикл>

//Новый человек изучает свою цель. Цель терминал. Если GOAL совпадает с символов из предложения, человек закрывает этот символ и сообщает об успехе, если не совпадает – сообщает о неудаче. Цель нового человека – нетерминал. Подготовка к просмотру правых частей в правилах GOAL.

Цикл.

if(GRAMMAR[i]==j) // просмотр правых частей

if(FAT!=0)

GOTO<успех> // Вы достигли конца правой части, поэтому сообщите

об успехе. Если нет отца, то остановка – окончен

разбор предложения.

else <stop _предложение>

if (GRAMMAR{i]==’$’) //Нет больше правых частей, которые можно было

бы попробовать, поэтому сообщите о неудаче, если нет отца, остановитесь, нераспознав предложение.

if(FAT!=0)

GOTO<неудача>

else<STOP_не предложение>

V:=V+1; //GRAMMAR[i] – другая цель, которую можно попытаться найти. Возьмите сына. Вы его отец. А его старший брат – тот, который до этого был вашим младшим сыном.

S[V]:=(GRAMMAR[i], ,c, ,SON)

SON:=V; c:=V; //Переключение внимание на нового сына

GOTO<Новый человек>

Успех

c:=FAT; //Сообщите об успехе своему отцу, он предпринят следующий шаг.

i:=i+1; GOTO<цикл>

Неудача

c:=FAT; //Сообщите о неудаче своему отцу. Он от вас отречётся и попросит вашего старшего брата предпринять ещё попытку.

V:=V-1;

SON:=S[SON] BRO;

GOTO<ещё раз>

Ещё раз

if (SON==0) //Если у вас есть сын, который может предпринять ещё одну попытку? Нет. Тогда пропустите эту правую часть, это не та, которая нужна – перейдите к следующей.

{while(GRAMMAR[i]!=j)

i:=i+1;

GOTO<цикл> }

i:=i-1; C:=SON; //У вас есть сын. Попросите повторить попытку. Его цель – нетерминал, так что он попытаться ещё раз добиться успеха.

if<GOAL – нетерминал>

GOTO<ещё раз>

j:=j-1; //Его цель – терминал. Попытка не приведён к успеху. Поэтому он открывает свой символ и сообщает о неудаче.

GOTO<неудача> 21.12.2005.

Класс грамматик, допускающих нисходящий распознаватель.

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

Определение: КС – грамматика называется S-грамматикой ( а также раздельной или простой) ,когда выполняются следующие условия:

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

2. Если 2 правила имеют совпадающие левые части, то правые части этих правил должны начинаться различными терминальными символами.

Проверить, является ли данная грамматика S-грамматикой очень просто:

Например:

1. <S>->a<T>

2. <S>-><T>в<S>

3. <T>->в<T>

4. <T>->ва

- не S-грамматика, т.к. правая часть правила 2 не начинается терминалом и => нарушено 1ое условие, кроме того 3 и 4 нарушают условие 2.

С другой стороны, очевидно:

1. <S>->aв<R>

2. <S>->в<R>в<S>

3. <R>->a

4. <R>->в<R>

- является S-грамматикой.

КС – языки можно задать многими грамматиками причём некоторые из них, возможно, являются S-грамматиками, а другие нет. Например, приведённые грамматики с начальным символом <S> , задают один и тот же язык, хотя одно из них является S-грамматикой, а другое нет.

Определение: КС-грамматика, для которой выбор правила A→ на произвольном i-ом шаге левостороннего вывода осуществляется однозначно при к 1 первым символам «хвостовой» подцепочки w' и по цепочке y' , называется LL(к) – грамматикой.

LL(к) – грамматики не могут быть леворекурсивными.

Определение: Грамматика G называется LR(k), для некоторого k≥0,если из условия:

1. S'=>*x'Az=>x' z;

2. S'=>* B ->xαy;

3. F_k(y)=F_k(z)

Следует x'Ay= B , т.е. x'= ,A=B, =y, V_T*.

В определении отображено требование детерминированности выделения правой границы основы α, её однозначности и однозначности выбора А→α, для «свёртки» основы в анализируемой части х=x'α цепочки w_i+1 =xy. Решение принимаемое на основании информации о правостороннем выводе цепочки x=x' и префиксе U цепочки y=Uy', U=F_k(u).

LR(k) грамматика впервые была изучена Кнутом, который нашёл для них эффективный метод построения детерминированных алгоритмов анализа.

Поведение МП автомата определяется верхним символом T_j магазина и k первыми символами (префикс u) непроанализированной части у цепочки w_i+1.