Устранение левой рекурсии — различия между версиями
Строка 52: | Строка 52: | ||
==Литература== | ==Литература== | ||
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.) | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 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 ] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] |
Версия 16:43, 8 декабря 2012
Определение: |
Говорят, что контекстно-свободная(КС) грамматика содержит непосредственную левую рекурсию, если она содержит правило вида . |
Определение: |
Говорят, что КС-грамматика | содержит левую рекурсию, если в ней существует вывод вида .
Содержание
Устранение непосредственной левой рекурсии
Опишем процедуру, устраняющую все правила вида
, для фиксированного нетерминала .- Запишем все правила вывода из
- — непустая последовательность терминалов и нетерминалов ( );
- — непустая последовательность терминалов и нетерминалов, не начинающаяся с .
в виде:
, где
- Заменим правила вывода из на .
- Создадим новый нетерминал .
Устранение произвольной левой рекурсии
Пусть
— множество всех нетерминалов.for i = 1 to n for j = 1 to i – 1 рассмотреть все правила вывода из: . заменить каждое правило на . устранить непосредственную левую рекурсию для .
Таким образом, после применения алгоритма все правила вывода имеют вид:
- , где — терминал, — произвольный нетерминал;
- , где , — нетерминалы из исходной грамматики;
- , где — новый нетерминал, — нетерминал из исходной грамматики.
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:
- , где — терминал;
- , где .
Алгоритм устранения левой рекурсии
Для произвольной грамматики
левую рекурсию можно устранить следующим образом:- Воспользуемся алгоритмом удаления . Получим грамматику без -правил -правил для языка .
- Воспользуемся алгоритмом устранения произвольной левой рекурсии.
- Если присутствовал в языке исходной грамматики, добавим новый начальный символ и правила .
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
- Robert C. Moore — Removing Left Recursion from Context-Free Grammars