26
правок
Изменения
Новая страница: «{{Определение |definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит непосредственную леву…»
{{Определение
|definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит непосредственную левую рекурсию, если она содержит правило вида <tex>A \rightarrow A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит левую рекурсию, если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}
==Алгоритм устранения левой рекурсии==
Приведем алгоритм, позволяющий для к.с. грамматики '''без ε-правил''' построить эквивалентную ей к.с. грамматику (без ε-правил), не содержащую левой рекурсии.
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом
#воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления ε-правил]]. Получим грамматику без ε-правил для языка <tex>L(\Gamma) \ \lbrace \epsilon \rbrace</tex>
#воспользоваться алгоритмом для новой грамматики
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
===Устранение непосредственной левой рекурсии===
Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow A\alpha</tex> для фиксированного нетерминала <tex>A</tex>.
Запишем все правила вывода из <tex>A</tex> в виде
<math>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </math>
где
* <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \ne \epsilon </tex>)
* <tex>\beta</tex> - непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.
Заменим правила вывода из <tex>A</tex> на:
<math>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</math>
И создадим новый нетерминал
<math>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime</math>
===Устранение произвольной левой рекурсии===
Пусть множество всех нетерминалов <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex>
: for i = 1 to n {
::for j = 1 to i – 1 {
:::* рассмотреть все правила вывода из <math>A_j</math>
:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>
:::* заменить каждое правило <math>A_i \rightarrow A_j \gamma</math> на
:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</math>
::}
:: устранить прямую левую рекурсию для <math>A_i</math>
:}
Инвариант: после <tex>j</tex> итераций внутреннего цикла для <tex>i</tex>
*для <tex>k < i</tex> правые части правил вывода из <tex>A_k</tex> не начинаются с <tex>A_1, A_2, \ldots , A_k</tex>
*правые части правил вывода из <tex>A_i</tex> не начинаются с <tex>A_1, A_2, \ldots , A_j</tex>
*правые части правил вывода не начинаются с добавленных алгоритмом нетерминалов <tex>A_k ^{\prime}</tex>
*грамматика не содержит ε-правил
(проверяется индукцией по парам <tex>(i,j)</tex>)
Таким образом, после применения алгоритма все правила вывода имеют вид
*<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал, <tex>A</tex> - произвольный нетерминал
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> - нетерминалы из исходной грамматики
*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> - новый нетерминал, <tex>A_j</tex> - нетерминал из исходной грамматики
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал
*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>
|definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит непосредственную левую рекурсию, если она содержит правило вида <tex>A \rightarrow A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит левую рекурсию, если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}
==Алгоритм устранения левой рекурсии==
Приведем алгоритм, позволяющий для к.с. грамматики '''без ε-правил''' построить эквивалентную ей к.с. грамматику (без ε-правил), не содержащую левой рекурсии.
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом
#воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления ε-правил]]. Получим грамматику без ε-правил для языка <tex>L(\Gamma) \ \lbrace \epsilon \rbrace</tex>
#воспользоваться алгоритмом для новой грамматики
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
===Устранение непосредственной левой рекурсии===
Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow A\alpha</tex> для фиксированного нетерминала <tex>A</tex>.
Запишем все правила вывода из <tex>A</tex> в виде
<math>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </math>
где
* <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \ne \epsilon </tex>)
* <tex>\beta</tex> - непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.
Заменим правила вывода из <tex>A</tex> на:
<math>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</math>
И создадим новый нетерминал
<math>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime</math>
===Устранение произвольной левой рекурсии===
Пусть множество всех нетерминалов <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex>
: for i = 1 to n {
::for j = 1 to i – 1 {
:::* рассмотреть все правила вывода из <math>A_j</math>
:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>
:::* заменить каждое правило <math>A_i \rightarrow A_j \gamma</math> на
:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</math>
::}
:: устранить прямую левую рекурсию для <math>A_i</math>
:}
Инвариант: после <tex>j</tex> итераций внутреннего цикла для <tex>i</tex>
*для <tex>k < i</tex> правые части правил вывода из <tex>A_k</tex> не начинаются с <tex>A_1, A_2, \ldots , A_k</tex>
*правые части правил вывода из <tex>A_i</tex> не начинаются с <tex>A_1, A_2, \ldots , A_j</tex>
*правые части правил вывода не начинаются с добавленных алгоритмом нетерминалов <tex>A_k ^{\prime}</tex>
*грамматика не содержит ε-правил
(проверяется индукцией по парам <tex>(i,j)</tex>)
Таким образом, после применения алгоритма все правила вывода имеют вид
*<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал, <tex>A</tex> - произвольный нетерминал
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> - нетерминалы из исходной грамматики
*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> - новый нетерминал, <tex>A_j</tex> - нетерминал из исходной грамматики
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал
*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>
