3622
правки
Изменения
Новая страница: «{{В разработке}} Для данной LL(1)-грамматики оказы...»
{{В разработке}}
Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.
Чтобы написать парсер для LL(1)-грамматики, необходимо построить [[LL(k)-грамматики, множества FIRST и FOLLOW#deffirst | множества]] <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>, после чего по ним можно составить таблицу синтаксического анализатора.
== Построение FIRST ==
Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.
{{Лемма
|id=lemmafirst1.
|author=1
|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>
}}
Данная лемма означает, что в множество <tex> \mathrm{FIRST} </tex> правила <tex> A \to X_1 X_2 \dots X_k </tex>, где <tex> X_i,\ (1 \leqslant i \leqslant k) </tex> {{---}} произвольный терминал или нетерминал, {{---}} нужно добавить <tex> \mathrm{FIRST}(X_i) </tex>, если для всех <tex> 1 \leqslant j < i </tex> верно, что <tex> X_j \Rightarrow^* \varepsilon </tex>.
{{Лемма
|id=lemmafirst2.
|author=2
|statement=
<tex> \mathrm{FIRST}(c \alpha) = \{c\}</tex> <br>
<tex> \mathrm{FIRST}(\varepsilon) = \{\varepsilon \}</tex>
}}
=== Псевдокод ===
Алгоритм строит для каждого терминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.
<code>
'''function''' constructFIRST():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FIRST}[A] = \varnothing </tex>
changed = ''true''
'''while''' changed
changed = ''true''
'''for''' <tex>( A \to \alpha \in P )</tex>
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился
</code>
{{Утверждение
|id=proposalfirstcorrect.
|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.
|proof=
<tex> \Leftarrow </tex>
Алгоритм на каждом шаге использует [[#lemmafirst1 | леммы]], чтобы построить списки <tex> \mathrm{FIRST} </tex> для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в <tex> \mathrm{FIRST} </tex>.
<tex> \Rightarrow </tex>
Покажем, что алгоритм найдёт все символы из множества <tex> \mathrm{FIRST} </tex>.
Предположим, что в грамматике возможен вывод <tex> A \Rightarrow^* c \gamma </tex>, и алгоритм не включил <tex> c </tex> в <tex> \mathrm{FIRST}[A] </tex>. Докажем индукцией по числу шагов <tex> \mathrm{while} </tex>, что этого не может быть.
Пусть за <tex> k </tex> шагов алгоритм добавит символы <tex> c </tex> в множество <tex> \mathrm{FIRST} </tex> для каждого нетерминала <tex> A </tex>, если <tex> A \Rightarrow^k c \gamma </tex>. База индукции для числа шагов <tex> 0 </tex> верна, если считать, что для всех терминалов нам известны <tex> \mathrm{FIRST} </tex>. Если алгоритм корректно отрабатывает на <tex>(k-1)</tex>-ом шаге, то он правильно отработает их на <tex>k</tex>-ом шаге, потому что
<tex> A \Rightarrow \beta \Rightarrow^{k-1} c \gamma </tex>
Для <tex> \beta </tex> алгоритм правильно построил <tex> \mathrm{FIRST} </tex> по предположению индукции, а для <tex> A </tex> он правильно построит по [[#lemmafirst1 | леммам]], следовательно, переход доказан.
К тому же алгоритм завершится за конечное число шагов, так как в <tex> \mathrm{FIRST} </tex> для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
}}
== Построение FOLLOW ==
{{TODO | t = Пример с арифметическими выражениями}}
{{TODO | t = Псевдокоды разбора арифметических выражений}}
{{TODO | t = Одна-две картинки}}
{{TODO | t = Пример с арифметическими выражениями}}
{{TODO | t = Построение таблицы}}
== См. также ==
== Примечания ==
<references/>
== Источники информации ==
[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]
Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.
Чтобы написать парсер для LL(1)-грамматики, необходимо построить [[LL(k)-грамматики, множества FIRST и FOLLOW#deffirst | множества]] <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>, после чего по ним можно составить таблицу синтаксического анализатора.
== Построение FIRST ==
Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.
{{Лемма
|id=lemmafirst1.
|author=1
|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>
}}
Данная лемма означает, что в множество <tex> \mathrm{FIRST} </tex> правила <tex> A \to X_1 X_2 \dots X_k </tex>, где <tex> X_i,\ (1 \leqslant i \leqslant k) </tex> {{---}} произвольный терминал или нетерминал, {{---}} нужно добавить <tex> \mathrm{FIRST}(X_i) </tex>, если для всех <tex> 1 \leqslant j < i </tex> верно, что <tex> X_j \Rightarrow^* \varepsilon </tex>.
{{Лемма
|id=lemmafirst2.
|author=2
|statement=
<tex> \mathrm{FIRST}(c \alpha) = \{c\}</tex> <br>
<tex> \mathrm{FIRST}(\varepsilon) = \{\varepsilon \}</tex>
}}
=== Псевдокод ===
Алгоритм строит для каждого терминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.
<code>
'''function''' constructFIRST():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FIRST}[A] = \varnothing </tex>
changed = ''true''
'''while''' changed
changed = ''true''
'''for''' <tex>( A \to \alpha \in P )</tex>
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился
</code>
{{Утверждение
|id=proposalfirstcorrect.
|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.
|proof=
<tex> \Leftarrow </tex>
Алгоритм на каждом шаге использует [[#lemmafirst1 | леммы]], чтобы построить списки <tex> \mathrm{FIRST} </tex> для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в <tex> \mathrm{FIRST} </tex>.
<tex> \Rightarrow </tex>
Покажем, что алгоритм найдёт все символы из множества <tex> \mathrm{FIRST} </tex>.
Предположим, что в грамматике возможен вывод <tex> A \Rightarrow^* c \gamma </tex>, и алгоритм не включил <tex> c </tex> в <tex> \mathrm{FIRST}[A] </tex>. Докажем индукцией по числу шагов <tex> \mathrm{while} </tex>, что этого не может быть.
Пусть за <tex> k </tex> шагов алгоритм добавит символы <tex> c </tex> в множество <tex> \mathrm{FIRST} </tex> для каждого нетерминала <tex> A </tex>, если <tex> A \Rightarrow^k c \gamma </tex>. База индукции для числа шагов <tex> 0 </tex> верна, если считать, что для всех терминалов нам известны <tex> \mathrm{FIRST} </tex>. Если алгоритм корректно отрабатывает на <tex>(k-1)</tex>-ом шаге, то он правильно отработает их на <tex>k</tex>-ом шаге, потому что
<tex> A \Rightarrow \beta \Rightarrow^{k-1} c \gamma </tex>
Для <tex> \beta </tex> алгоритм правильно построил <tex> \mathrm{FIRST} </tex> по предположению индукции, а для <tex> A </tex> он правильно построит по [[#lemmafirst1 | леммам]], следовательно, переход доказан.
К тому же алгоритм завершится за конечное число шагов, так как в <tex> \mathrm{FIRST} </tex> для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
}}
== Построение FOLLOW ==
{{TODO | t = Пример с арифметическими выражениями}}
{{TODO | t = Псевдокоды разбора арифметических выражений}}
{{TODO | t = Одна-две картинки}}
{{TODO | t = Пример с арифметическими выражениями}}
{{TODO | t = Построение таблицы}}
== См. также ==
== Примечания ==
<references/>
== Источники информации ==
[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]
