Карпов - Основы построения трансляторов (2005) (943926), страница 21
Текст из файла (страница 21)
Существенными символами грамматики 641 являются Г|г~И'2= (Я, А, В„ а, о, с~. Редуцируем грамматику 04 ~, выбросив из нее бесполезные продукции. Оставшиеся продукции: 04.~: 1. Я вЂ” +ВсА 2. А-+ВсЯ 3. А-+асЬ 4. В-+ЬВ задают редуцированную грамматику, эквивалентную исходной. ПРИМЕР 4.1. Построим эквивалентную редуцированную грамматику по следующей грамматике: Определение 4.5. Язык называется а-свободным, если он не включает пус- той цепочки.
По любой КС-грамматике можно проверить, является ли порождаемый ею язык е-свободным. Для этого нужно проверить, есть ли в эквивалентной я-свободной грамматике продукция Я-+е. Любую КС-грамматику можно преобразовать в неукорачивающую с некоторым изменением порождаемого языка. Это изменение состоит в том. что в конце каждой выводимой в языке цепочки добавляется концевой маркер 3.
Преобразование грамматики в неукорачивающую можно выполнить, добавив в грамматику новый нетерминал Т и продукцию Я' — +Я, где Я вЂ” начальный нетерминал исходной грамматики, после чего применив алгоритм приведения грамматики к е-свободному виду. 4.1.3. Циклические символы Продукции вида А — +В в КС-грамматике называются сингулярными. Существует эффективный алгоритм, позволяющий по любой е-свободной КС- грамматике построить эквивалентную КС-грамматику без сингулярных продукций. Действительно, включим в множество Я продукций грамматики 6 вместо каждой сингулярной продукции вида А — +В все продукции А — +Д такие, что продукция  — +~3е11 и несингулярна.
ПРИМЕР 4.3. Для грамматики: 64.2 1 ° ~-~ +В ~ 2. А-+С~ ас 3.  — +Ь 4. С вЂ” +А эквивалентная грамматика без сингулярных продукций имеет вид: ~~4.2: 1 ~-+ВА 2. А-+ас 3.  — +Ь 4. С->ас В результате последующего приведения этой грамматики последняя продукция будет выброшена, потому что символ С не выводим. В языках программирования сингулярные продукции используются достаточно часто, и их выбрасывание может нарушить очевидность структуры продукций. Исключение составляет специальный случай сингулярных продукций, которые приводят к циклу вида А ==>~ А. Теория контекстно-свободных языков Определение 4.6. КС-грамматика, в которой не существует вывода А ==>* А, называется ациклической. Любую КС-грамматику можно привести к эквивалентному ациклическому виду. Для этого нужно построить эквивалентную е-свободную грамматику и затем привести ее к эквивалентному виду без сингулярных продукций. 4.1.4.
Левая рекурсия Определение 4.7. КС-грамматика называется леворекурсивной, если в ней существует вывод А ==>* А~3. Леворекурсивные грамматики не всегда удобны. В частности, нисходящие методы синтаксического анализа, восстанавливающие дерево вывода от его корня, не могут быть применены для такого класса грамматик. Существует алгоритм, позволяющий привес~и любую КС-грамматику к эквивалентному виду без левой рекурсии. Рассмотрим здесь случай так называемой "прямой левой рекурсии", т.
е. случай, когда грамматика имеет продукции вида А-+Аа. Очевидно, что А будет существенным символом, только если в грамматике есть продукции вида А — +~3. Рассмотрим простейший случай. Пусть в грамматике есть пара продукций А-+Аа ~ р, Очевидно, что в соответствии с этими продукциями в дереве вывода цепочек языка, порождаемого данной грамматикой, будет присутствовать следующий фрагмент (рис. 4.1, а).
б) Рис. 4.1. Дерево вывода цепочки Рааа. 'а) в грамматике с прямой левой рекурсией; б) в грамматике без левой рекурсии Пара продукций А-+Ап ~ р может быть эквивалентно заменена следующими нелеворекурсивными продукциями: 140 Глава 4 При этом цепочка ~Заа...а будет иметь другое дерево вывода ~рис. 4.1, б), и при трансляции, конечно, необходимо подобрать другие семантические правила в соответствии с новой грамматикой. Оказывается, что часто такое изменение грамматики позволяет использовать более простые и удобные методы синтаксического анализа. Заметим, что правила вида А — +аАР или А-+аА не являются леворекурсивными, если цепочка а не пуста, они не представляют неудобств при нисходящем синтаксическом анализе.
ПРИМЕР 4.4. Рассмотрим правила классической грамматики арифметических выражений: е-г+т~ т Используя вышеуказанный алгоритм, преобразуем эти правила с прямой ле- вой рекурсией к следующему эквивалентному виду: Š— + У'Е' Е' — ++ТЕ' ~ е Этот метод легко обобщается на случай, когда нетерминал имеет несколько альтернатив с прямой левой рекурсией (см. задачу 5). Более сложный общий случай избавления от непрямой левой рекурсии требует более сложного ал- горитма. Такой алгоритм представлен в ~АЯ3861. 4.1.5.
Факторизация грамматик Если грамматика содержит пару правил вида: Х вЂ” +~3 Пример такой пары правил дает язык Милан, в котором определены как пол- ный, так и сокращенный условный операторы: го восстановление дерева вывода с помощью нисходящего анализа обычно невозможно. Простой метод построения эквивалентной грамматики, называемый факторизацией, позволяет привести грамматику к виду, для которого эта проблема не возникает. Введем новый нетерминал Х и определим следующую эквивалентную замену; Теория контекстно-свободных языков Я вЂ” н1ГВ Феп Е еЬе Е Й Я вЂ” +БВ1Ьеп А й Факторизация позволяет заменить эту пару правил следующими тремя экви- валентными правилами: 5 — н~ГВ ФЬеп ЕХ Х вЂ” +еЬе Е Й После такой замены проблем с применением нисходящего алгоритма синтак- сического анализа в этом фрагменте грамматики не возникнет.
4.2. Нориапьные фориы грамматик 4.2.1. Нормальная форма Хамского КС-грамматика 6 = (Т, У, Я, Я) представлена в нормальной форме Хомского, если она неукорачивающая и каждое ее правило имеет одну из следующих форм: А-+ВС или А — +а, где А, В, СяЖ, ая Т. Простыми эквивалентными преобразованиями любую неукорачивающую грамматику можно привести к нормальной форме Хомского. Действительно, построим по исходной грамматике б = ~Т, Л~, Я, Я) эквивалентную грамматику 6' = (Т, У', 5, Я') следующими преобразованиями: 1. В множество продукций А' включаем все продукции вида А — +ВС и А — +а из Я.
2. Для каждой продукции из Я вида А — +Х1 Х2 ... Х~ включаем в Я' продукции А-+Х'1 '-Х2 " А'-', ~Х2 " А.'-+Х'2~ХЗ " А»;" ~А-1А~-+Х'~-1 Х'ь где для всех г: Х'; = Х, если Х нетерминал; л"., — новый нетерминал, если Х терминальный символ; <Х; ... Х~> — новый нетерминал. 3.
Для каждого нового нетерминала Х'„введенного на предыдущем шаге вместо терминала а, включим во множество А' продукцию Х',-+а. ПРИМЕР 4.5. В качестве примера приведем к нормальной форме Хомского грамматику: Глава 4 1. Я вЂ” +ВуА 2. А-+ВЯ 3. А — +х 4.  — кгА Изменяем продукции грамматики: Вместо Я вЂ” +ВУА вводим три новые продукции Л"-+В0, .0 — +УА, Г-+у; Продукцию А-+ВЯ включаем без изменения; Продукцию А-+х включаем без изменения; Вместо  — +;гА вводим две новые продукции  — +ХА, У-+г. Окончательно преобразованная эквивалентная грамматика в нормальной форме Хомского имеет вид: Я вЂ” +В.0 .0 — + г'А А — +х  — +УА У-+г 4.2.2.
Нормальная форма Грейбах Нормальная форма Грейбах (бге~Ьас61 Хоггпа! Гогт) используется для установления многих формальных свойств КС-грамматик. В этой форме ограничения накладываются не на длину правой части продукций грамматики, а на ее вид. Будем говорить, что КС-грамматика представлена в нормальной форме Грейбах, если она я-свободна и все продукции ее имеют вид: А — +ау, где а — терминал, а у — произвольная цепочка нетерминалов, возможно пустая. Существуют простые правила перевода КС-грамматики в нормальную форму Грейбах. Приведем примеры такого перевода. ПРИМЕР 4.6.
Приведем к нормальной форме Грейбах грамматику Теория контекстно-свободных языков 3. А — +х 4.  — +гАу Во-первых, в продукциях 1 и 2 заменим первый нетерминал В правой частью продукции 4: Я вЂ” +гАуА А-юАЯ А — +х Далее, введем новый нетерминал У, и заменим во всех продукциях теминал у этим нетерминалом с добавлением новой продукции К вЂ” >у к множеству продукций грамматики. Окончательно грамматика в форме Грейбах, эквивалентная исходной грамматике, имеет вид: Я вЂ” +гА УА А — к."АЯ А-+х Без доказательства приведем следующую теорему.
° ТЕОРЕМА 4.2. Для каждой КС-грамматики б, такой, что е ~ Ц6), суще- ствует эквивалентная грамматика в нормальной форме Грейбах. 4.3. Функции НЙЗТ и ЕО~.~.ОШ При разработке алгоритмов синтаксического анализа контекстно-свободных языков часто используются функции НКЯТ и ГОП.0%. Аргументом функции НК5Т является строка символов объединенного словаря грамматики. Определение 4.8. Для произвольной строки а изтерминальных и нетерминальных символов НК5Т(и) определяет множество тех терминальных символов„с которых могут начинаться строки, выводимые из и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
