Для каждого правила

K -> V

(где K —нетерминал, V —слово, содержащее терминалы и нетерминалы) определим множество «направляющих терминалов», обозначаемое Напр(K‑>V). По определению оно равно Нач(V), к которому добавлено Послед(K), если из V выводится пустое слово.

Определение. Грамматика называется LL(1)-грамматикой, если для любых правил K‑>V и K‑>W с одинаковыми левыми частями множества Напр(K‑>V) и Напр(K‑>W) не пересекаются.

Является ли грамматика

K -> K #

K ->

(выводимыми словами являются последовательности диезов) LL(1)-грамматикой?

Решение. Нет: символ # принадлежит множествам направляющих символов для обоих правил (для второго —поскольку # принадлежит Послед(K)).

Написать LL(1)-грамматику для того же языка.

Решение.

K -> # K

K ->

Как говорят, «леворекурсивное правило»заменено на «праворекурсивное».

Следующая задача показывает, что для LL(1)-грамматики существует не более одного возможного продолжения левого вывода.

5.5.5. Пусть дано выводимое в LL(1)-грамматике слово X, в котором выделен самый левый нетерминал К: X=AKS, где A —слово из терминалов, S —слово из терминалов и нетерминалов. Пусть существуют два различных правила грамматики с нетерминалом K в левой части, и мы применили их к выделенному в X нетерминалу K, затем продолжили вывод и в конце концов получили два слова из терминалов, начинающихся на A. Доказать, что в этих словах за началом A идут разные буквы.