Разработка компиляторов
LL(k)-грамматика
Определение. Грамматика G = (VT, VN, P, S) называется LL(k)-грамматикой, если для любых двух левых выводов
S =>* wAv => wuv =>* wx S =>* wAv => wu1v =>* wy,
для которых FIRST k (x) = FIRSTk (y) верно, что u=u1 .
То есть если для данной цепочки wAv , состоящей из терминальных и нетерминальных символов и k первых символов (если они есть), выводящихся из Av , существует не более одного правила, которое можно применить к A , чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминалами.
Пример. Рассмотрим грамматику с правилами:
и два вывода
(1) S =>* wSv => wuv =>* wx (2) S =>* wSv => wu1v =>* wy
Пусть цепочки x и y начинаются с a. Это означает, что в выводе участвовало правило . Следовательно, u = u1 = aAS . Пусть цепочки x и y начинаются с b . Это означает, что в выводе участвовало правило . Следовательно, u = u1 = b .
Для выводов
(3) S =>* wAv => wuv =>* wx (4) S =>* wAv => wu1v =>* wy
рассуждение аналогично. Таким образом, грамматика обладает свойством LL(1).
Для LL(1)-грамматик может быть построен анализатор методом рекурсивного спуска без возвратов.
