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

2017-06-14T22:34:44Z

78.37.136.251: /* Алгоритм устранения правого ветвленения */ s/необходимым/достаточным/

Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют 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> p </tex> и <tex> y </tex> {{---}} цепочки из терминалов, уже разобранная часть слова <tex> w </tex>, <tex> A </tex> {{---}} нетерминал грамматики, в которой есть правила <tex> A \to \alpha </tex> и <tex> A \to \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)-грамматикой'''.
}}
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> во всех [[Удаление бесполезных символов из грамматики | небесполезных]] правилах грамматики.

'''Замечание:''' более общим случаем множества <tex> \mathrm{FIRST} </tex> является множество <tex> \mathrm{FIRST}_k </tex>, однако в данном конспекте оно не используется.
{{Определение
|id=deffirstk
|definition=
<tex> \mathrm{FIRST}_k(\alpha) = \{w \mid \alpha \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha \Rightarrow^* \varepsilon \} </tex>
}}
=== Примеры ===
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.

* <tex> A \to (A)A \mid \varepsilon </tex>
* <tex> B \to BB \mid (B) \mid \varepsilon </tex>

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило
!style="background-color:#EEE"| FIRST
!style="background-color:#EEE"| FOLLOW
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>A</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\ \$\ \} </tex>
|-
|style="background-color:#FFF;padding:2px 30px"| <tex>B</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\ \$\ \} </tex>
|}

== Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW ==
Далее будет показано, как множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> связаны с понятием LL(1)-грамматики.
{{Теорема
|id=thLL1
|statement= <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} LL(1)-грамматика <tex> \Leftrightarrow </tex>
# <tex> A \to \alpha,\ A \to \beta, A \in N \ \Rightarrow \ \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing</tex>
# <tex> A \to \alpha,\ A \to \beta, A \in N,\ \varepsilon \in \mathrm{FIRST}(\alpha) \ \Rightarrow \ \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) = \varnothing</tex>
|proof=
<tex> \Leftarrow </tex>

Предположим, что данная грамматика не будет LL(1)-грамматикой. Значит, у какого-то слова <tex> w </tex> существует два различных левосторонних вывода.
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma </tex>
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma </tex>
Но это противоречит тому, что <tex> \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing </tex>.

Аналогично проверятся второе условие. Если, например, <tex> \alpha \Rightarrow^* \varepsilon </tex>, то <tex> \varepsilon \in \mathrm{FIRST}(\alpha) </tex>, и <tex> \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) \ne \varnothing </tex>

<tex> \Rightarrow </tex>

Предположим, что есть два различных правила <tex> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) </tex>. Тогда:
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma </tex>
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma </tex>
Последний переход можно совершить, так как <tex> c </tex> лежит в пересечении множеств <tex> \mathrm{FIRST} </tex> двух правил вывода. Так как грамматика <tex> \Gamma </tex> является LL(1)-грамматикой, то из [[#defLLK | определения]] следует, что <tex> \alpha = \beta </tex>. Это противоречит предположению, что <tex> \alpha </tex> и <tex> \beta </tex> {{---}} различные правила.

Второе условие проверяется аналогичным образом.
}}
=== Следствия ===
Сформулируем несколько важных cледствий из теоремы.
==== Левая рекурсия ====
{{Утверждение
|author=1
|statement=Грамматика <tex> \Gamma </tex> cодержит левую рекурсию <tex> \Rightarrow \ \Gamma </tex> не является LL(1)-грамматикой.
|proof=
Если грамматика содержит левую рекурсию, значит, в ней существует какой-то нетерминал <tex> A </tex> с правилами <tex> A \to A \alpha \mid \beta </tex>, где <tex> \beta </tex> {{---}} строка из терминалов и нетерминалов, не начинающаяся с <tex> A </tex>.

Тогда понятно, что <tex> \mathrm{FIRST}(A\alpha) \cap \mathrm{FIRST}(\beta) \ne \varnothing </tex>, и это противоречит первому условию [[#thLL1 | теоремы]].
}}
Чтобы избавиться от левой рекурсии, можно воспользоваться [[Устранение левой рекурсии | алгоритмом устранения левой рекурсии]].
==== Левая факторизация ====
{{Утверждение
|author=2
|statement=Грамматика <tex> \Gamma </tex> cодержит правое ветвление <tex> \Rightarrow \ \Gamma </tex> не является LL(1)-грамматикой.
|proof=
Наличие в грамматике правого ветвления означает, что существует правило <tex> A \to \alpha \beta \mid \alpha \gamma, \alpha \ne \varepsilon </tex>.

Очевидно, что <tex> \mathrm{FIRST}(\alpha \beta) \cap \mathrm{FIRST}(\alpha \gamma) \ne \varnothing </tex>. Поэтому грамматика не будет LL(1)-грамматикой по первому условию [[#thLL1 | теоремы]].
}}
===== Алгоритм устранения правого ветвленения =====
Чтобы избавиться от правого ветвления, нужно воспользоваться алгоритмом левой факторизации. Его суть заключается в следующем: для каждого нетерминала <tex> A </tex> ищем самый длинный префикс, общий для двух или более правил вывода из <tex> A </tex>. Важно, чтобы как можно больше строк имело общий префикс, и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально, рассмотрим правила

<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>

Причём <tex> \alpha \ne \varepsilon </tex>, а наибольший общий префикс <tex> \alpha </tex> и <tex> \gamma_i\ (1 \leqslant i \leqslant m</tex>) равен <tex> \varepsilon </tex>. Тогда изменим грамматику следующим образом, введя новый нетерминал <tex> A' </tex>:

<tex> A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>

<tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex>

Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.

'''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.

== См. также ==
* [[Нормальная форма Хомского]]
* [[Существенно неоднозначные языки]]

== Источники информации ==
* [http://en.wikipedia.org/wiki/LL_grammar Wikipedia {{---}} LL grammar]
* [http://www.math.spbu.ru/user/mbk/PDF/Ch-11.pdf LL(k)-грамматики и трансляция]
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8

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

Викиконспекты - Вклад участника [ru]

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