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

Материал из Викиконспекты
Версия от 22:02, 27 июня 2014; Shersh (обсуждение | вклад) (добавлено введение, поправлено определение)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют LL(1)-грамматики, так как для них возможно построение нисходящих парсеров без возврата, то есть без корректировки выбранных правил в грамматике. LL(1)-грамматики являются подмножеством КС-грамматик. Однако для достаточно большого количества формальных языков можно построить LL(1)-грамматику, например, для языка арифметических выражений и даже для некоторых языков программирования, в частности можно и для языка Java.

LL(k)-грамматика

Дадим теперь формально определение LL(k)-грамматики.

Определение:
Пусть [math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — КС-грамматика. Рассмотрим возникновение следующей ситуации во время левостороннего вывода в этой грамматике слова [math] w [/math]:
  • [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 [/math] — цепочки из терминалов, уже разобранная часть слова [math] w [/math], [math] A [/math] — нетерминал грамматики, в которой есть правила [math] A \rightarrow \alpha [/math] и [math] A \rightarrow \alpha' [/math], [math] \alpha, \alpha', \beta, \eta, \xi [/math] — последовательности из терминалов и нетерминалов.

Тогда если при выполнении условий, что [math] |y| = k [/math] или [math] |y| \lt k, \eta = \xi = \varepsilon [/math], верно, что [math] \alpha = \alpha' [/math], то [math] \Gamma [/math] называется LL(k)-грамматикой.


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

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

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

TODO: Пара следствий

TODO: Какие-нибудь примеры