LL(k)-грамматики, множества FIRST и FOLLOW — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(FIRST и FOLLOW)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 6 участников)
Строка 10: Строка 10:
 
* <tex> S \Rightarrow^* p A \beta \Rightarrow  p \alpha' \beta \Rightarrow^* p y \xi </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> 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)-грамматикой'''.
+
Если из выполнения условий, что <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>.  
 
LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки <tex> y </tex> один символ <tex> c \in \Sigma \cup \{\varepsilon\} </tex>.  
Строка 17: Строка 17:
  
 
== FIRST и FOLLOW ==
 
== FIRST и FOLLOW ==
Ключевую роль в построении парсеров для LL(1)-грамматик играю множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>.  
+
Ключевую роль в построении парсеров для 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> следующим образом:  
 
Пусть <tex> c </tex> {{---}} символ из алфавита <tex> \Sigma </tex>, <tex> \alpha,\ \beta </tex> {{---}} строки из нетерминалов и терминалов (возможно пустые), <tex> S,\ A </tex> {{---}} нетерминалы грамматики (начальный и произвольный соответственно), <tex> \$ </tex> {{---}} символ окончания слова. Тогда определим <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> следующим образом:  
Строка 23: Строка 23:
 
|id=deffirst
 
|id=deffirst
 
|definition=
 
|definition=
<tex> \mathrm{FIRST}(\alpha) = \{c \mid \alpha \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha \Rightarrow^* \varepsilon \} </tex>  
+
<tex> \mathrm{FIRST}(A) = \{c \mid A \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} </tex>  
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 30: Строка 30:
 
<tex> \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} </tex>
 
<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}(A) </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(A) = \{w \mid A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} </tex>
 +
}}
 
=== Примеры ===
 
=== Примеры ===
 
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
 
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
Строка 42: Строка 49:
 
!style="background-color:#EEE"| FOLLOW
 
!style="background-color:#EEE"| FOLLOW
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| A
+
|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 30px"| <tex>\{\ (,\  \varepsilon\ \} </tex>
 
|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\  \$\ \} </tex>
 
|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\  \$\ \} </tex>
 
|-
 
|-
|style="background-color:#FFF;padding:2px 30px"| B
+
|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>\{\ (,\  \varepsilon\ \} </tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\  \$\ \} </tex>
 
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\  \$\ \} </tex>
Строка 70: Строка 77:
 
<tex> \Rightarrow </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> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}(A) \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 \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> S \Rightarrow^* p A \gamma \Rightarrow  p \beta \gamma \Rightarrow^* p c \beta' \gamma </tex>
Строка 103: Строка 110:
 
<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </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> \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 \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex>
Строка 109: Строка 116:
 
<tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex>
 
<tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex>
  
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он завершится за конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.
+
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.
  
'''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является необходимым условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
+
'''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
  
 
== См. также ==
 
== См. также ==

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

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

LL(k)-грамматика

Дадим теперь формально определение LL(k)-грамматики.

Определение:
Пусть [math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — КС-грамматика. Рассмотрим два произвольных левосторонних вывода слова [math] w [/math] в этой грамматике:
  • [math] S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta [/math]
  • [math] S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi [/math]

где [math] p [/math] и [math] y [/math] — цепочки из терминалов, уже разобранная часть слова [math] w [/math], [math] A [/math] — нетерминал грамматики, в которой есть правила [math] A \to \alpha [/math] и [math] A \to \alpha' [/math], причём [math] \alpha, \alpha', \beta, \eta, \xi [/math] — последовательности из терминалов и нетерминалов.

Если из выполнения условий, что [math] |y| = k [/math] или [math] |y| \lt k, \eta = \xi = \varepsilon [/math], следует равенство [math] \alpha = \alpha' [/math], то [math] \Gamma [/math] называется LL(k)-грамматикой.

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

Неформально это означает, что, посмотрев на очередной символ после уже выведенной части слова, можно однозначно определить, какое правило из грамматики выбрать.

FIRST и FOLLOW

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

Пусть [math] c [/math] — символ из алфавита [math] \Sigma [/math], [math] \alpha,\ \beta [/math] — строки из нетерминалов и терминалов (возможно пустые), [math] S,\ A [/math] — нетерминалы грамматики (начальный и произвольный соответственно), [math] \$ [/math] — символ окончания слова. Тогда определим [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math] следующим образом:

Определение:
[math] \mathrm{FIRST}(A) = \{c \mid A \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} [/math]


Определение:
[math] \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} [/math]

Другими словами, [math] \mathrm{FIRST}(A) [/math] — все символы (терминалы), с которых могут начинаться всевозможные выводы из [math] \alpha [/math], а [math] \mathrm{FOLLOW}(A) [/math] — всевозможные символы, которые встречаются после нетерминала [math] A [/math] во всех небесполезных правилах грамматики.

Замечание: более общим случаем множества [math] \mathrm{FIRST} [/math] является множество [math] \mathrm{FIRST}_k [/math], однако в данном конспекте оно не используется.

Определение:
[math] \mathrm{FIRST}_k(A) = \{w \mid A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} [/math]

Примеры

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

  • [math] A \to (A)A \mid \varepsilon [/math]
  • [math] B \to BB \mid (B) \mid \varepsilon [/math]
Правило FIRST FOLLOW
[math]A[/math] [math]\{\ (,\ \varepsilon\ \} [/math] [math]\{\ ),\ \$\ \} [/math]
[math]B[/math] [math]\{\ (,\ \varepsilon\ \} [/math] [math]\{\ (,\ ),\ \$\ \} [/math]

Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW

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

Теорема:
[math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — LL(1)-грамматика [math] \Leftrightarrow [/math]
  1. [math] A \to \alpha,\ A \to \beta, A \in N \ \Rightarrow \ \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing[/math]
  2. [math] A \to \alpha,\ A \to \beta, A \in N,\ \varepsilon \in \mathrm{FIRST}(\alpha) \ \Rightarrow \ \mathrm{FOLLOW}(A) \cap \mathrm{FIRST}(\beta) = \varnothing[/math]
Доказательство:
[math]\triangleright[/math]

[math] \Leftarrow [/math]

Предположим, что данная грамматика не будет LL(1)-грамматикой. Значит, у какого-то слова [math] w [/math] существует два различных левосторонних вывода.

  • [math] S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma [/math]
  • [math] S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma [/math]

Но это противоречит тому, что [math] \mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing [/math].

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

[math] \Rightarrow [/math]

Предположим, что есть два различных правила [math] A \to \alpha [/math] и [math] A \to \beta [/math] таких, что [math] c \in \mathrm{FIRST}(A) \cap \mathrm{FIRST}(\beta) [/math]. Тогда:

  • [math] S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma [/math]
  • [math] S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma [/math]

Последний переход можно совершить, так как [math] c [/math] лежит в пересечении множеств [math] \mathrm{FIRST} [/math] двух правил вывода. Так как грамматика [math] \Gamma [/math] является LL(1)-грамматикой, то из определения следует, что [math] \alpha = \beta [/math]. Это противоречит предположению, что [math] \alpha [/math] и [math] \beta [/math] — различные правила.

Второе условие проверяется аналогичным образом.
[math]\triangleleft[/math]

Следствия

Сформулируем несколько важных cледствий из теоремы.

Левая рекурсия

Утверждение (1):
Грамматика [math] \Gamma [/math] cодержит левую рекурсию [math] \Rightarrow \ \Gamma [/math] не является LL(1)-грамматикой.
[math]\triangleright[/math]

Если грамматика содержит левую рекурсию, значит, в ней существует какой-то нетерминал [math] A [/math] с правилами [math] A \to A \alpha \mid \beta [/math], где [math] \beta [/math] — строка из терминалов и нетерминалов, не начинающаяся с [math] A [/math].

Тогда понятно, что [math] \mathrm{FIRST}(A\alpha) \cap \mathrm{FIRST}(\beta) \ne \varnothing [/math], и это противоречит первому условию теоремы.
[math]\triangleleft[/math]

Чтобы избавиться от левой рекурсии, можно воспользоваться алгоритмом устранения левой рекурсии.

Левая факторизация

Утверждение (2):
Грамматика [math] \Gamma [/math] cодержит правое ветвление [math] \Rightarrow \ \Gamma [/math] не является LL(1)-грамматикой.
[math]\triangleright[/math]

Наличие в грамматике правого ветвления означает, что существует правило [math] A \to \alpha \beta \mid \alpha \gamma, \alpha \ne \varepsilon [/math].

Очевидно, что [math] \mathrm{FIRST}(\alpha \beta) \cap \mathrm{FIRST}(\alpha \gamma) \ne \varnothing [/math]. Поэтому грамматика не будет LL(1)-грамматикой по первому условию теоремы.
[math]\triangleleft[/math]
Алгоритм устранения правого ветвленения

Чтобы избавиться от правого ветвления, нужно воспользоваться алгоритмом левой факторизации. Его суть заключается в следующем: для каждого нетерминала [math] A [/math] ищем самый длинный префикс, общий для двух или более правил вывода из [math] A [/math]. Важно, чтобы как можно больше строк имело общий префикс, и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально, рассмотрим правила

[math] A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m [/math]

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

[math] A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m [/math]

[math] A' \to \beta_1 \mid \ldots \mid \beta_n [/math]

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

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

См. также

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