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

{{В разработке}}

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

== LL(k)-грамматика ==
Дадим теперь формально определение LL(k)-грамматики.
{{Определение
|id=defLLK 
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика. Рассмотрим возникновение следующей ситуации во время левостороннего вывода в этой грамматике слова <tex> w </tex>:
* <tex> S \Rightarrow^* p A \beta \Rightarrow  p \alpha \beta \Rightarrow^* p y \eta </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)-грамматикой'''.
}}
Неформально это означает, что если мы уже вывели какой-то префикс разбираемого слова, то, посмотрев на следующие <tex> k </tex> cимволов, сможем одназначно выбрать правило вывода.
{{TODO | t = картинка}}

LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки <tex> y </tex> один символ <tex> c \in \Sigma \cup \{\varepsilon\} </tex>.

== FIRST и FOLLOW ==
Ключевую роль в построении парсеров для LL(1)-грамматик играю множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>. 

Пусть <tex> c </tex> {{---}} символ из алфавита <tex> \Sigma </tex>, <tex> \alpha,\ \beta </tex> {{---}} строки из нетерминалов и терминалов (возможно пустые), <tex> S,\ A </tex> {{---}} нетерминалы грамматики (начальный и произвольный соответственно), <tex> \$ </tex> {{---}} символ окончания слова. Тогда определим <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> следующим образом: 
{{Определение
|id=deffirst
|definition=
<tex> \mathrm{FIRST}(\alpha) = \{c \mid \alpha \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha \Rightarrow^* \varepsilon \} </tex> 
}}
{{Определение
|id=deffirst
|definition=
<tex> \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} </tex>
}}
Другими словами, <tex> \mathrm{FIRST}(\alpha) </tex> {{---}} все символы (терминалы), с которых могут начинаться всевозможные выводы из <tex> \alpha </tex>, а <tex> \mathrm{FOLLOW}(A) </tex> {{---}} всевозможные символы, которые встречаются после нетерминала <tex> A </tex> во всех правилах грамматики.
=== Примеры ===
{{TODO | t = Какие-нибудь примеры}}

== Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW ==
{{TODO | t = Теорема об LL(1)-грамматиках}}
{{TODO | t = Пара следствий}}

== См. также ==
== Источники информации ==
*


[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]