Построение FIRST и FOLLOW — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} Для данной LL(1)-грамматики оказы...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 5 участников)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.  
 
Для данной [[LL(k)-грамматики, множества FIRST и FOLLOW#defLLK | LL(1)-грамматики]] оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator] </ref>.  
  
Строка 7: Строка 5:
 
Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.
 
Для построения <tex> \mathrm{FIRST} </tex> воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть <tex> \alpha, \beta </tex> {{---}} цепочки из терминалов и нетерминалов, <tex> c </tex> {{---}} символ из алфавита.
 
{{Лемма
 
{{Лемма
|id=lemmafirst1.
+
|id=lemmafirst1
 
|author=1
 
|author=1
 
|statement=<tex> \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) </tex>
 
|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>.
+
Рассмотрим лемму подробней. Пусть правило из нетерминала <tex> A </tex> имеет вид <tex> A \to X_1 X_2 \dots X_k </tex>, где <tex> X_i,\ (1 \leqslant i \leqslant k) </tex> {{---}} произвольный терминал или нетерминал. Тогда по лемме в <tex> \mathrm{FIRST}[A] </tex> нужно добавить <tex> \mathrm{FIRST}(X_i) </tex>, если для всех <tex> 1 \leqslant j < i </tex> верно, что <tex> X_j \Rightarrow^* \varepsilon </tex>.
 
{{Лемма
 
{{Лемма
|id=lemmafirst2.
+
|id=lemmafirst2  
 
|author=2
 
|author=2
 
|statement=
 
|statement=
Строка 20: Строка 18:
 
}}
 
}}
 
=== Псевдокод ===
 
=== Псевдокод ===
Алгоритм строит для каждого терминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.
+
Алгоритм строит для каждого нетерминала грамматики <tex>\Gamma = \langle \Sigma, N, S, P \rangle</tex> отображение в множество символов. Перед запуском алгоритма необходимо избавиться от [[Удаление бесполезных символов из грамматики | бесполезных символов]]. Изначально каждое правило отображается в пустое множество.
<code>
+
  '''function''' constructFIRST():
  '''function''' constructFIRST():
 
 
       '''for''' <tex>( A  \in N )</tex>
 
       '''for''' <tex>( A  \in N )</tex>
 
           <tex>\mathrm{FIRST}[A] =  \varnothing </tex>
 
           <tex>\mathrm{FIRST}[A] =  \varnothing </tex>
 
       changed = ''true''
 
       changed = ''true''
 
       '''while''' changed
 
       '''while''' changed
           changed = ''true''
+
           changed = ''false''
 
           '''for''' <tex>( A \to \alpha \in P )</tex>
 
           '''for''' <tex>( A \to \alpha \in P )</tex>
 
               <tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
 
               <tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex>
               changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился
+
               changed = ''true'' '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился        
</code>
 
 
{{Утверждение
 
{{Утверждение
|id=proposalfirstcorrect.
+
|id=proposalfirstcorrect  
 
|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.
 
|statement=Приведённый алгоритм правильно строит множество <tex> \mathrm{FIRST} </tex> для данной грамматики.
 
|proof=
 
|proof=
Строка 53: Строка 49:
 
Для <tex> \beta </tex> алгоритм правильно построил <tex> \mathrm{FIRST} </tex> по предположению индукции, а для <tex> A </tex> он правильно построит по [[#lemmafirst1 | леммам]], следовательно, переход доказан.
 
Для <tex> \beta </tex> алгоритм правильно построил <tex> \mathrm{FIRST} </tex> по предположению индукции, а для <tex> A </tex> он правильно построит по [[#lemmafirst1 | леммам]], следовательно, переход доказан.
  
К тому же алгоритм завершится за конечное число шагов, так как в <tex> \mathrm{FIRST} </tex> для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
+
К тому же, алгоритм завершится за конечное число шагов, так как в <tex> \mathrm{FIRST} </tex> для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
 
}}
 
}}
 +
 
== Построение FOLLOW ==
 
== Построение FOLLOW ==
{{TODO | t = Пример с арифметическими выражениями}}
+
Сформулируем похожие утверждения для построения <tex> \mathrm{FOLLOW} </tex>.
{{TODO | t = Псевдокоды разбора арифметических выражений}}
+
{{Лемма
{{TODO | t = Одна-две картинки}}
+
|id=lemmafollow1
{{TODO | t = Пример с арифметическими выражениями}}
+
|author=3
{{TODO | t = Построение таблицы}}
+
|statement=Для каждого правила <tex> A \to \alpha B \beta </tex> верно, что <tex>(\mathrm{FIRST}(\beta) \setminus \{\varepsilon\}) \subset \mathrm{FOLLOW}(B) </tex>
 +
}}
 +
{{Лемма
 +
|id=lemmafollow2
 +
|author=4
 +
|statement=Для каждого правила вида <tex> A \to \alpha B </tex> или <tex> A \to \alpha B \beta,\ \varepsilon \in \mathrm{FIRST}(\beta)</tex> верно, что <tex>\mathrm{FOLLOW}(A) \subset \mathrm{FOLLOW}(B) </tex>
 +
}}
 +
=== Псевдокод ===
 +
Реализация построения <tex> \mathrm{FOLLOW} </tex> получается сразу из [[#lemmafollow1 | лемм]]. Для алгоритма сначала требуется выполнить построение <tex> \mathrm{FIRST} </tex> для грамматики.
 +
 
 +
  '''function''' constructFOLLOW():
 +
      '''for''' <tex>( A  \in N )</tex>
 +
          <tex>\mathrm{FOLLOW}[A] =  \varnothing </tex>
 +
      <tex>\mathrm{FOLLOW}[S] =  \{\$\} </tex>  <font color=green> // в стартовый нетерминал помещается символ конца строки </font>
 +
      changed = ''true''
 +
      '''while''' changed
 +
          changed = ''false''
 +
          '''for''' <tex>( A \to \alpha \in P )</tex>
 +
              '''for''' <tex>( B : \alpha = \beta B \gamma)</tex>
 +
                  <tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} </tex>
 +
                  '''if''' <tex> \varepsilon \in \mathrm{FIRST}(\gamma) </tex>
 +
                      <tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A]</tex>
 +
                  changed = ''true'' '''if''' <tex> \mathrm{FOLLOW}[B] </tex> изменился
 +
 
 +
Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования <tex> \mathrm{FIRST} </tex>.
 +
 
 +
== Пример ==
 +
Рассмотрим, как будут строиться множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой <tex> n </tex> для простоты. Интуитивная грамматика для арифметических выражений выглядит следующим образом:
 +
 
 +
<tex> E \to E + E \mid E \times E \mid (E) \mid n </tex>
 +
 
 +
Однако данная грамматика содержит [[Устранение левой рекурсии | левую рекурсию]], [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | правое ветвление]] и является [[Существенно неоднозначные языки#defambigous |неоднозначной]]. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для рассматриваемого языка. Например, она может иметь следующий вид:
 +
 
 +
<tex>
 +
E \to T + E \mid T \\
 +
T \to F \times T \mid F \\
 +
F \to n \mid (E)
 +
</tex>
 +
 
 +
Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика примет вид:
 +
 
 +
<tex>
 +
E \to TE' \\
 +
E' \to +E \mid \varepsilon \\
 +
T \to FT' \\
 +
T' \to \times T \mid \varepsilon \\
 +
F \to n \mid (E)
 +
</tex>
 +
 
 +
А затем для простоты анализирования раскрыть нетерминалы <tex> E </tex> и <tex> T </tex> в правилах для <tex> E' </tex> и <tex> T' </tex>.
 +
 
 +
<tex>
 +
E \to TE' \\
 +
E' \to +TE' \mid \varepsilon \\
 +
T \to FT' \\
 +
T' \to \times FT' \mid \varepsilon \\
 +
F \to n \mid (E)
 +
</tex>
 +
 
 +
=== Конструирование FIRST для арифметических выражений ===
 +
Рассмотрим, как будет выглядеть множество <tex> \mathrm{FIRST} </tex> после очередной итераций цикла <tex> \mathrm{while} </tex>.
 +
 
 +
'''После 1ой итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FIRST
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|}
 +
'''После 2ой итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FIRST
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|}
 +
'''После 3eй итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FIRST
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|}
 +
Далее никаких изменений происходить не будет, и на этом алгоритм завершит свою работу.
 +
=== Конструирование FOLLOW для арифметических выражений ===
 +
Теперь рассмотрим построение таблицы <tex> \mathrm{FOLLOW} </tex> после каждой итераций цикла <tex> \mathrm{while} </tex>. Стартовым нетерминалом будет <tex> E </tex>, поэтому в него добавим сразу <tex> \$ </tex>.
 +
 
 +
'''До цикла while:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FOLLOW
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$ \ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \}</tex>
 +
|}
 +
'''После 1ой итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FOLLOW
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$ \ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ \} </tex>
 +
|}
 +
'''После 2ой итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FOLLOW
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ \} </tex>
 +
|}
 +
'''После 3ей итерации:'''
 +
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| Правило
 +
!style="background-color:#EEE"| FOLLOW
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
 +
|}
 +
На этом построение множества <tex> \mathrm{FOLLOW} </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>E</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>E'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \varepsilon\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \$,\ )\ \} </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>T'</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times,\ \varepsilon\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ +,\ \$\ ,\ )\ \}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>F</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ n,\ (\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ \times, \ +,\ \$\ ,\ )\ \} </tex>
 +
|}
 +
 
 +
Используя [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | теорему]], можно убедиться, что грамматика арифметических выражений на самом деле является LL(1)-грамматикой.
 +
 
 
== См. также ==
 
== См. также ==
 +
* [[LL(k)-грамматики, множества FIRST и FOLLOW]]
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>
 
== Источники информации ==
 
== Источники информации ==
 +
* [http://en.wikipedia.org/wiki/LL_parser Wikipedia {{---}} LL parser]
 +
* [http://citforum.ru/programming/theory/serebryakov/4.shtml СitForum {{---}} Синтаксический анализ]
 +
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8
  
 
[[Категория: Методы трансляции]]
 
[[Категория: Методы трансляции]]
 
[[Категория: Нисходящий разбор]]
 
[[Категория: Нисходящий разбор]]

Текущая версия на 19:31, 4 сентября 2022

Для данной LL(1)-грамматики оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик[1].

Чтобы написать парсер для LL(1)-грамматики, необходимо построить множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math], после чего по ним можно составить таблицу синтаксического анализатора.

Построение FIRST

Для построения [math] \mathrm{FIRST} [/math] воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть [math] \alpha, \beta [/math] — цепочки из терминалов и нетерминалов, [math] c [/math] — символ из алфавита.

Лемма (1):
[math] \mathrm{FIRST}(\alpha \beta) = \mathrm{FIRST}(\alpha) \cup (\mathrm{FIRST}(\beta)\ \mathrm{if}\ \varepsilon \in \mathrm{FIRST}(\alpha)) [/math]

Рассмотрим лемму подробней. Пусть правило из нетерминала [math] A [/math] имеет вид [math] A \to X_1 X_2 \dots X_k [/math], где [math] X_i,\ (1 \leqslant i \leqslant k) [/math] — произвольный терминал или нетерминал. Тогда по лемме в [math] \mathrm{FIRST}[A] [/math] нужно добавить [math] \mathrm{FIRST}(X_i) [/math], если для всех [math] 1 \leqslant j \lt i [/math] верно, что [math] X_j \Rightarrow^* \varepsilon [/math].

Лемма (2):
[math] \mathrm{FIRST}(c \alpha) = \{c\}[/math]
[math] \mathrm{FIRST}(\varepsilon) = \{\varepsilon \}[/math]

Псевдокод

Алгоритм строит для каждого нетерминала грамматики [math]\Gamma = \langle \Sigma, N, S, P \rangle[/math] отображение в множество символов. Перед запуском алгоритма необходимо избавиться от бесполезных символов. Изначально каждое правило отображается в пустое множество.

  function constructFIRST():
     for [math]( A  \in N )[/math]
         [math]\mathrm{FIRST}[A] =  \varnothing [/math]
     changed = true
     while changed
         changed = false
         for [math]( A \to \alpha \in P )[/math]
             [math] \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) [/math]
             changed = true if [math] \mathrm{FIRST}[A] [/math] изменился          
Утверждение:
Приведённый алгоритм правильно строит множество [math] \mathrm{FIRST} [/math] для данной грамматики.
[math]\triangleright[/math]

[math] \Leftarrow [/math]

Алгоритм на каждом шаге использует леммы, чтобы построить списки [math] \mathrm{FIRST} [/math] для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в [math] \mathrm{FIRST} [/math].

[math] \Rightarrow [/math]

Покажем, что алгоритм найдёт все символы из множества [math] \mathrm{FIRST} [/math].

Предположим, что в грамматике возможен вывод [math] A \Rightarrow^* c \gamma [/math], и алгоритм не включил [math] c [/math] в [math] \mathrm{FIRST}[A] [/math]. Докажем индукцией по числу шагов [math] \mathrm{while} [/math], что этого не может быть.

Пусть за [math] k [/math] шагов алгоритм добавит символы [math] c [/math] в множество [math] \mathrm{FIRST} [/math] для каждого нетерминала [math] A [/math], если [math] A \Rightarrow^k c \gamma [/math]. База индукции для числа шагов [math] 0 [/math] верна, если считать, что для всех терминалов нам известны [math] \mathrm{FIRST} [/math]. Если алгоритм корректно отрабатывает на [math](k-1)[/math]-ом шаге, то он правильно отработает их на [math]k[/math]-ом шаге, потому что

[math] A \Rightarrow \beta \Rightarrow^{k-1} c \gamma [/math]

Для [math] \beta [/math] алгоритм правильно построил [math] \mathrm{FIRST} [/math] по предположению индукции, а для [math] A [/math] он правильно построит по леммам, следовательно, переход доказан.

К тому же, алгоритм завершится за конечное число шагов, так как в [math] \mathrm{FIRST} [/math] для каждого нетерминала не может добавиться больше символов, чем есть в алфавите.
[math]\triangleleft[/math]

Построение FOLLOW

Сформулируем похожие утверждения для построения [math] \mathrm{FOLLOW} [/math].

Лемма (3):
Для каждого правила [math] A \to \alpha B \beta [/math] верно, что [math](\mathrm{FIRST}(\beta) \setminus \{\varepsilon\}) \subset \mathrm{FOLLOW}(B) [/math]
Лемма (4):
Для каждого правила вида [math] A \to \alpha B [/math] или [math] A \to \alpha B \beta,\ \varepsilon \in \mathrm{FIRST}(\beta)[/math] верно, что [math]\mathrm{FOLLOW}(A) \subset \mathrm{FOLLOW}(B) [/math]

Псевдокод

Реализация построения [math] \mathrm{FOLLOW} [/math] получается сразу из лемм. Для алгоритма сначала требуется выполнить построение [math] \mathrm{FIRST} [/math] для грамматики.

  function constructFOLLOW():
     for [math]( A  \in N )[/math]
         [math]\mathrm{FOLLOW}[A] =  \varnothing [/math]
     [math]\mathrm{FOLLOW}[S] =  \{\$\} [/math]   // в стартовый нетерминал помещается символ конца строки 
     changed = true
     while changed
         changed = false
         for [math]( A \to \alpha \in P )[/math]
             for [math]( B : \alpha = \beta B \gamma)[/math]
                 [math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} [/math]
                 if [math] \varepsilon \in \mathrm{FIRST}(\gamma) [/math]
                     [math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A][/math]
                 changed = true if [math] \mathrm{FOLLOW}[B] [/math] изменился

Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования [math] \mathrm{FIRST} [/math].

Пример

Рассмотрим, как будут строиться множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math] на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой [math] n [/math] для простоты. Интуитивная грамматика для арифметических выражений выглядит следующим образом:

[math] E \to E + E \mid E \times E \mid (E) \mid n [/math]

Однако данная грамматика содержит левую рекурсию, правое ветвление и является неоднозначной. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для рассматриваемого языка. Например, она может иметь следующий вид:

[math] E \to T + E \mid T \\ T \to F \times T \mid F \\ F \to n \mid (E) [/math]

Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика примет вид:

[math] E \to TE' \\ E' \to +E \mid \varepsilon \\ T \to FT' \\ T' \to \times T \mid \varepsilon \\ F \to n \mid (E) [/math]

А затем для простоты анализирования раскрыть нетерминалы [math] E [/math] и [math] T [/math] в правилах для [math] E' [/math] и [math] T' [/math].

[math] E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to \times FT' \mid \varepsilon \\ F \to n \mid (E) [/math]

Конструирование FIRST для арифметических выражений

Рассмотрим, как будет выглядеть множество [math] \mathrm{FIRST} [/math] после очередной итераций цикла [math] \mathrm{while} [/math].

После 1ой итерации:

Правило FIRST
[math]E[/math] [math]\{\ \} [/math]
[math]E'[/math] [math]\{\ +,\ \varepsilon\ \} [/math]
[math]T[/math] [math]\{\ \}[/math]
[math]T'[/math] [math]\{\ \times,\ \varepsilon\ \} [/math]
[math]F[/math] [math]\{\ n,\ (\ \} [/math]

После 2ой итерации:

Правило FIRST
[math]E[/math] [math]\{\ \} [/math]
[math]E'[/math] [math]\{\ +,\ \varepsilon\ \} [/math]
[math]T[/math] [math]\{\ n,\ (\ \} [/math]
[math]T'[/math] [math]\{\ \times,\ \varepsilon\ \} [/math]
[math]F[/math] [math]\{\ n,\ (\ \} [/math]

После 3eй итерации:

Правило FIRST
[math]E[/math] [math]\{\ n,\ (\ \} [/math]
[math]E'[/math] [math]\{\ +,\ \varepsilon\ \} [/math]
[math]T[/math] [math]\{\ n,\ (\ \} [/math]
[math]T'[/math] [math]\{\ \times,\ \varepsilon\ \} [/math]
[math]F[/math] [math]\{\ n,\ (\ \} [/math]

Далее никаких изменений происходить не будет, и на этом алгоритм завершит свою работу.

Конструирование FOLLOW для арифметических выражений

Теперь рассмотрим построение таблицы [math] \mathrm{FOLLOW} [/math] после каждой итераций цикла [math] \mathrm{while} [/math]. Стартовым нетерминалом будет [math] E [/math], поэтому в него добавим сразу [math] \$ [/math].

До цикла while:

Правило FOLLOW
[math]E[/math] [math]\{\ \$ \ \} [/math]
[math]E'[/math] [math]\{\ \}[/math]
[math]T[/math] [math]\{\ \}[/math]
[math]T'[/math] [math]\{\ \}[/math]
[math]F[/math] [math]\{\ \}[/math]

После 1ой итерации:

Правило FOLLOW
[math]E[/math] [math]\{\ \$,\ )\ \} [/math]
[math]E'[/math] [math]\{\ \$ \ \} [/math]
[math]T[/math] [math]\{\ +,\ \$\ \}[/math]
[math]T'[/math] [math]\{\ +,\ \$\ \}[/math]
[math]F[/math] [math]\{\ \times, \ +,\ \$\ \} [/math]

После 2ой итерации:

Правило FOLLOW
[math]E[/math] [math]\{\ \$,\ )\ \} [/math]
[math]E'[/math] [math]\{\ \$,\ )\ \} [/math]
[math]T[/math] [math]\{\ +,\ \$\ \}[/math]
[math]T'[/math] [math]\{\ +,\ \$\ \}[/math]
[math]F[/math] [math]\{\ \times, \ +,\ \$\ \} [/math]

После 3ей итерации:

Правило FOLLOW
[math]E[/math] [math]\{\ \$,\ )\ \} [/math]
[math]E'[/math] [math]\{\ \$,\ )\ \} [/math]
[math]T[/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]T'[/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]F[/math] [math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]

На этом построение множества [math] \mathrm{FOLLOW} [/math] для грамматики закончится.

Итоговая таблица

Правило FIRST FOLLOW
[math]E[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ \$,\ )\ \} [/math]
[math]E'[/math] [math]\{\ +,\ \varepsilon\ \} [/math] [math]\{\ \$,\ )\ \} [/math]
[math]T[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]T'[/math] [math]\{\ \times,\ \varepsilon\ \} [/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]F[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]

Используя теорему, можно убедиться, что грамматика арифметических выражений на самом деле является LL(1)-грамматикой.

См. также

Примечания

Источники информации