- •Е.И.Чигарина, м.А.Шамашов
- •Isbn 978-5-7883-0506-6
- •Глава 1. Языки и грамматики. Обозначения, определения и классификация 6
- •Глава 1. Языки и грамматики. Обозначения, определения и классификация
- •1.1 Понятие грамматики языка. Обозначения
- •1.2. Классификация грамматик по Хомскому
- •1.3. Техника построения кс - и а - грамматик
- •1.4. Синтаксические деревья вывода в кс-грамматиках. Представление а-грамматик в виде графа состояний. Неоднозначность грамматик
- •1.5. Синтаксический анализ а-языков
- •Упражнения к первой главе
- •Глава 2. Распознаватели и автоматы
- •Глава 3. Автоматные грамматики и конечные автоматы
- •3.1. Автоматные грамматики и конечные автоматы
- •3.2. Эквивалентность недетерминированных и детерминированных а-грамматик
- •Упражнения к третьей главе
- •Глава 4. Эквивалентные преобразования контекстно-свободных и автоматных грамматик
- •4.1. Декомпозиция правил грамматики
- •4.2. Исключение тупиковых правил из грамматик
- •4.3. Обобщенные кс-грамматики и приведение их к удлиняющей форме
- •4.4. Устранение левой рекурсии и левая факторизация
- •Упражнения к четвертой главе
- •Глава 5. Свойства автоматных и контекстно-свободных языков
- •5.1. Общий вид цепочек а-языков и кс-языков
- •5.2. Операции над языками
- •5.2.1. Операции над кс-языками
- •5.2.2 Операции над а-языками
- •5.2.3. Операции над контекстными языками
- •5.3. Выводы для практики
- •5.4. Неоднозначность кс-грамматик и языков
- •Упражнения к пятой главе
- •Глава 6. Синтаксический анализ кс-языков
- •6.1.Методы анализа кс-языков. Грамматики предшествования
- •6.2. Грамматики предшествования Вирта
- •6.3. Грамматика предшествования Флойда
- •6.4 Функции предшествования
- •Упражнения к шестой главе
- •Глава 7. Введение в семантику
- •7.1. Польская инверсная запись
- •7.2. Интерпретация полиЗа
- •7.3. Генерирование команд по полиЗу
- •7.4. Алгоритм Замельсона и Бауэра перевода выражений в полиз
- •7.5. Атрибутные грамматики
- •Упражнения к седьмой главе
- •Глава 8. Основные фазы компиляции
- •Заключение
- •Приложение
- •Список рекомендуемой литературы
- •Чигарина Елена Ивановна
4.4. Устранение левой рекурсии и левая факторизация
В целом ряде приложений требуется, чтобы грамматика рассматриваемого языка не содержала левой рекурсии. Наличие леворекурсивных правил в исходной грамматике не фатально, так как для любой КС-грамматики существует эквивалентная грамматика без левой рекурсии.
Рассмотрим случай, когда правила грамматики саморекурсивны, то есть левая часть правила и край правой части совпадают. Пусть нетерминал A имеет m леворекурсивных правил A A i для 1 i m и n правил A j для 1 j n , которые не являются леворекурсивными (отметим, что отсутствие последних делает A тупиком).
Заменив эти правила на правила A j <список A> для 1 j n
<список A> i <список A> для 1 i m <список A> , где <список A> - новый нетерминал, мы получим эквивалентную группу правил без левой рекурсии.
Пример 4.7. Самой короткой грамматикой для представления идентификатора является леворекурсивная грамматика
<И> б<И>б<И>ц ,
где б - любая буква, а ц - любая цифра. В данной грамматике два леворекурсивных правила и одно правило без левой рекурсии.
Заменяя их на правила
<И> б<И1>
<И1> б<И1> ц<И1> ,
мы получим обобщенную праворекурсивную грамматику идентификатора. Заметим, что исключение аннулирующего правила приведет нас к грамматике из примера 4.3.
Если в грамматике имеется группа правил вида
A 1... n ,
то цепочку можно “вынести за скобку” и преобразовать данную группу правил к виду
A B
B 1... n .
Этот прием носит название левой факторизации и его необходимо знать для ряда приложений.
Упражнения к четвертой главе
4.1. В грамматике
S abAcDkY
A nmDkyvaxYejab
D ghYokh
Y fd устраните правила A nmDkyvaxYejab и D ghYokh
и проведите декомпозицию относительно Y. Подсчитайте количество правил результирующей грамматики до проведения преобразований.
4.2. Исключите тупики из следующих грамматик:
(а)
S aBcDkLMp L f M
B cLpDqpDcf M LkpMLc
D f Drf pq K r F
F abcab
(б)
S ABBCkL A aAbLc
B BSAL L cBjp
C QSdC Q qQaC
M xNyMzSh N xCvwM
(в)
S BACBAL C QSdC
A aAbBcC Q qQaC
B BSALg M xNyMzSh
L cBjCp N xCvwM
4.3. Устраните аннулирующие правила из следующих грамматик:
(а)
S abCDeKp
C dSde
D dDDDef K
K emcf
(б)
S aSbSbSaS
(в)
S ABC A BB
B CCa C AAb
4.4. Устраните цепные правила из грамматики
E E+TT
T TFF
F (E)a
4.5. Найдите приведенную грамматику, эквивалентную грамматике
S AB A CD
B DE C Sa
D Sb E Sc
4.6. Устраните левую рекурсию в следующих грамматиках:
(а)
E E+TE-TT-T
T TFT/FF
F (E)a
(б) S AB
A AaAbde
B qKrBBfBg
K vSw.