LL(k)-грамматика, множества FIRST и FOLLOW

Материал из Викиконспекты
Версия от 15:55, 21 июня 2014; Shersh (обсуждение | вклад) (определение LL(k)-грамматики)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!


TODO: Небольшое введение


Определение:
КС-грамматика [math] \Gamma [/math] называется LL(k)-грамматикой, если при возникновении следующей ситуации:
  • [math] S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta [/math]
  • [math] S \Rightarrow^* p A \beta' \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi [/math]

где [math] S [/math] — стартовый нетерминал грамматики, [math] p [/math] — цепочка из терминалов, уже разобранная часть слова, —

и при выполнении условий, что [math] |y| = k [/math] или [math] |y| \lt k, \eta = \xi = \varepsilon [/math], верно, что [math] \alpha = \alpha' [/math].


TODO: LL(1)-грамматика

TODO: FIRST и FOLLOW, примеры (скобочные последовательности)

TODO: Теорема об LL(1)-грамматиках

TODO: Псевдокоды построения множеств FIRST и FOLLOW

TODO: Примеры арифметических выражений с табличками, левая рекурсия правое ветвление