Изменения

{{TODO Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют LL(1)-грамматики, так как для них возможно построение нисходящих парсеров без возврата, то есть без корректировки выбранных правил в [[Формальные грамматики | t = Небольшое введение}}грамматике]]. LL(1)-грамматики являются подмножеством [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#csgrammar | КС-грамматик]]. Однако для достаточно большого количества [[Основные определения, связанные со строками#deflanguage | формальных языков]] можно построить LL(1)-грамматику, например, для языка арифметических выражений и даже для некоторых языков программирования, в частности можно и для языка Java.

КС-грамматика Пусть <tex> \Gamma =\langle \Sigma, N, S, P \rangle</tex> называется '''LL(k){{---}} КС-грамматикой''', если при возникновении грамматика. Рассмотрим возникновение следующей ситуацииво время левостороннего вывода в этой грамматике слова <tex> w </tex>:

* <tex> S \Rightarrow^* p A \beta' \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi </tex>где <tex> S </tex> {{---}} стартовый нетерминал грамматики, <tex> p </tex> и <tex> y </tex> {{---}} цепочка цепочки из терминалов, уже разобранная часть слова<tex> w </tex>, <tex> A </tex> {{---}} нетерминал грамматики, в которой есть правила <tex> A \rightarrow \alpha </tex> и <tex> A \rightarrow \alpha' </tex>, <tex> \alpha, \alpha', \beta, \eta, \xi </tex> {{---}} последовательности из терминалов и нетерминалов.<br>и Тогда если при выполнении условий, что <tex> |y| = k </tex> или <tex> |y| < k, \eta = \xi = \varepsilon </tex>, верно, что <tex> \alpha = \alpha' </tex>, то <tex> \Gamma </tex> называется '''LL(k)-грамматикой'''.