Вначале A пусто, а S состоит из единственного символа —начального нетерминала.

Если в некоторый момент S начинается на терминал t и t = Next, то можно выполнить команду Move и удалить символ t, являющийся начальным в S, поскольку при этом AS не меняется.

Если S начинается на терминал t и t не равно Next, то входное слово невыводимо —ибо по условию любой его вывод должен проходить через AS. (Это же справедливо и в случае Next = EOI.)

Если S пусто, то из условия (И) следует, что входное слово выводимо тогда и только тогда, когда Next = EOI.

Остается случай, когда S начинается с некоторого нетерминала K. По доказанному выше все левые выводы из S слов, начинающихся на символ Next, начинаются с применения к T одного и того же правила —того, для которого Next принадлежит направляющему множеству. Если таких правил нет, то входное слово невыводимо. Если такое правило есть, то нужно применить его к первому символу слова S —при этом свойство (И) не нарушится. Приходим к такому алгоритму:

S := пустое слово;

error := false;

{error => входное слово невыводимо;} {not error => (И)} while (not error) and not ((Next=EOI) and (S пусто)) do begin

| if (S начинается на терминал, равный Next) then begin

| | Move; удалить из S первый символ;

| end else if (S начинается на терминал, не равный Next)

| | then begin

| | error := true;

| end else if (S пусто) and (Next <> EOI) then begin

| | error := true; | end else if (S начинается на нетерминал и Next входит в

| | направляющее множество одного из правил для этого

| | нетерминала) then begin

| | применить это правило

| end else if (S начинается на нетерминал и Next не входит в | | направляющее множество ни одного из правил для этого

| | нетерминала) then begin

| | error := true;

| end;

end; {входное слово выводимо <=> not error}

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