Обсуждение:Устранение левой рекурсии

2012-12-08T14:00:02Z

94.25.228.65:

: {{tick}} написать, почему, собственно, надо ее устранять верно ли что для нормального разбора сверху вних
: {{tick}} англоязычные термины и источники
: {{tick}} а сложность алгоритма какая? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:31, 7 декабря 2012 (GST)

1)Таким образом, после применения алгоритма все правила вывода имеют вид:
*<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>.

казалось бы это бред

Устранение левой рекурсии

2012-12-08T13:43:24Z

94.25.228.65:

{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная(КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''', если она содержит правило вида <tex>A \rightarrow A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>

==Устранение произвольной левой рекурсии==
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} множество всех нетерминалов.
<div>
for i = 1 to n
for j = 1 to i – 1
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>

Таким образом, после применения алгоритма все правила вывода имеют вид:
*<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>.

==Алгоритм устранения левой рекурсии==

Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:
#Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \varepsilon \rbrace</tex>.
#Воспользуемся алгоритмом ''устранения произвольной левой рекурсии''.
#Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \varepsilon </tex>.

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* Robert C. Moore — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

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

Обсуждение:Устранение левой рекурсии

Устранение левой рекурсии