Разработка компиляторов

       

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)-грамматик может быть построен анализатор методом рекурсивного спуска без возвратов.



Содержание раздела