И далее

... ‑> [()TE]E -> [()(E)E]E -> [()(TE)E]E -> [()([E]E)E]E ->

-> [()([]E)E]E -> [()([])E]E -> [()([])]E -> [()([])].

Что требуется от грамматики, чтобы такой метод поиска левого вывода был применим? Пусть, например, на очередном шаге самым левым нетерминалом оказался нетерминал K, т.е. мы имеем слово вида AKU, где A —слово из терминалов, а U — слово из терминалов и нетерминалов. Пусть в грамматике есть правила

K -> L M №

K -> P Q

K -> R

Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор, глядя на первый символ той части входного слова, которая выводится из KU.

Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются непустые слова, выводимые из LMN. (Это множество равно Нач(L), объединенному с Нач(M), если из L выводится пустое слово, а также с Нач(N), если из L и из M выводится пустое слово.) Чтобы описанный метод был применим, надо, чтобы Нач(LMN), Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть так, например, что из LMN будет выведено пустое слово, а из слова U будет выведено слово, начинающееся на букву из Нач(PQ). Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было дано только для слова из терминалов. Оно очевидным образом обобщается на случай слов из терминалов и нетерминалов. Можно также говорить о выводимости одного слова (содержащего терминалы и нетерминалы) из другого. (Если говорится о выводимости слова без указания того, откуда оно выводится, то всегда подразумевается выводимость в грамматике, т.е. выводимость из начального нетерминала.)

Для каждого слова X из терминалов и нетерминалов через Нач(X) обозначаем множество всех терминалов, с которых начинаются непустые слова из терминалов, выводимые из X. (В случае, если из любого нетерминала выводится хоть одно слово из терминалов, не играет роли, рассматриваем ли мы при определении Нач(X) слова только из терминалов или любые слова. Мы будем предполагать далее, что это условие выполнено.)

Для каждого нетерминала K через Послед(K) обозначим множество терминалов, которые встречаются в выводимых словах сразу же за K. Кроме того, в Послед(K) включается символ EOI, если существует выводимое слово, оканчивающееся на K.