Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 63
Текст из файла (страница 63)
ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 276 Š— э а ) Ь ( 1п ( ТЬ | !О ) 11 ~ (Е1 ~ Т Я Е Как видно, цепных продукций для Е нет. Заметим, что продукция Е э а не явллегнся цепной, единственный символ в ее теле — терминал, а не переменная. Представленная выше техника расширения цепных продукций до их исчезновения работает довольно часто. Однако она терпит неудачу, если в грамматике есть пнкл из цепных продукций, вроде А — э В,  — > С и С вЂ” г А.
Техника, гарантирующая результат, включает первоначальное нахождение всех пар переменных А н В, для которых А =ь В получается с использованием последовательности лишь цепных продукций. Заметим, что А => В возможно и без использования цепных продукций, например, с помощью продукций А — э ВС и С вЂ” ь а Определив все подобные пары, любую последовательность шагов порождения, в ко- юрой А~ В, ~ В, ~ ... =ь В„=ь а с неценной продукцией „— + гт, можно заменить продукцией А У сс Однако вначале рассмотрим индуктивное построение пар (А, В), для которых А =ь В получается с использованием лишь цепных продукций, Назовем такую пару Неллой лирой (ипп ран).
Базис. (А, А) является цепной парой для любой переменной, т.е. А =ь А за нуль шагов. Индукции. Предположим, что пара (А, В) определена как цепная, и  — > С вЂ” продукция с переменной С. Тогда (А, С) — цепная пара. Пример 7АО. Рассмотрим грамматику выражений из примера 5.27, воспроизведенную выше. Базис дает цепные пары (Е, Е), (Т, Т), (Е, )г) и (1, !). На индуктивном шаге южно сделать следующие порождения пар. 1. (Е, Е) и продукция Š— э Т дают пару (Е, Т). (Е, Т) и продукция Т вЂ” э Š— пару(Е, Е). 3, (Е, Р) и Е -э !дают пару (Е, !). 4.
(Т, Т) и Т вЂ” эŠ— пару(Е, Гэ. 5, (Т, Ц и Š— э ! — пару (Т, 1), 6. (Е, )г) и Е-+! — пару(Е, 1). Больше пар, которые можно было бы вывести, нет. На самом деле этн десять пар представляют все порождения, использукпцие только цепные продукции, П Способ построения пар теперь очевиден. Нетрудно доказать, что предложенный алюритм обеспечивает порождение всех нужных пар. Зная эти пары, можно удалить цепные продукции из грамматики и показать эквивалентность исходной и полученной грамматик. 7,1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Теорема 7.11. Приведенный выше алгоритм находит все цепные пары грамматики С, и только их. Доказательство.
С помощью индукции по порядку обнаружения пар нетрудно пока- зать, что если пара (А, В) обнаружена, то А =з В получается с использованием лишь а цепных продукций. Это оставляется в качестве упражнения. Предположим, что А =-~ В получено с использованием лишь цепных продукций. Поп кажем с помощью инлукции по длине порождения, что пара (А, В) будет обнаружена. Базис. Нуль шагов. Тогда А = В, и пара (А, В) обнаруживается согласно базису. Индукции. Предположим, что А =э В получено за и шагов, и > О, и на каждом из них с применялась цепная продукция. Тогда порождение имеет вид А ~ С~ В.
Порождение о А =э С состоит из и — 1 шагов, и по предположению индукции пара (А, С) обнаружива- 6 ется, Наконец, используем индуктивную часть алгоритма, чтобы по паре (А, С) и продукции С -з В обеспечить обнаружение пары (А, В).П Для удаления цепных продукций по КС-грамматике С=(1; Т, Р,5) построим КС- грамматику С, = (1;, Т, Рь 5) следующим образом. !. Найдем все цепные пары грамматики б.
2. Для каждой пары (А, В) добавим к Р, все продукции А — > а, где  — + а — нецепная продукция из Р. Заметим, что при А = В все нецепные продукции для В из Р просто добавляются к Рл Пример 7.12. Продолжим пример 7.!О, где был выполнен шаг! описанного построения для грамматики выражений из примера 5.27.
На рис. 7. ! представлен шаг 2 алгоритма, строящий новое множество продукций. При этом первый член пары становится головой продукций, а в качестве их тел используются все тела нецепных продукций для второго члена. На заключительном шаге из грамматики (см. рис. 7, !) удаляются все цепные продукции. В итоге получается следующая грамматика без цепных продукций, которая порождает то же самое множество выражений, что и грамматика, изображенная на рнс. 5.
19. Š— + Е+ Т! Т* Р)(Е) ! а ~ Ь | Та)ТЬ !70! П Т вЂ” + Т * Р ! (Е) ! а ( Ь ! Уа ! ТЬ ( 10 ( П Е вЂ” > (Е) ) а ) Ь ! 1а ! УЬ | 70 ! П ! †> а ! Ь | Уа ! ТЬ | ЬЗ ) П Е) Теорема 7.13. Если грамматика С, построена по грамматике б с помощью алгоритма удаления цепных продукций, описанного выше, то ЦС~) = ЦС). ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 278 Рис. 7 Е Грамматика, построенная на шаге 2 алгоритма удаления цепных продукций Доказательство. Докажем, что и ц Е(б,) тогда и только тогда, когда и и Е1С), Яостаточносгпь) Предположим, з =о зи.
Поскольку каждая продукция грамматики 6, 0> эквивалентна последовательности из нуля или нескольких цепных продукций б, за которой следует нецепная продукция С, из а ~ )3 следует а =Р )). Таким образом, кажа, о дый шаг порождения в б, может быть заменен одним или несколькими шагами в б. Со- брав этн последовательности шагов вместе, получим, что о .=л и.
с Яеобходимость) Предположим, что ш н Е(О). Тогда в соответствии с эквивалент- аостяии из раздела 5.2 цепочка ш имеет левое порождение, т.е. о =л ш. Где бы в левом 1 порождении ни использовалась цепная продукция, переменная ее тела становится крайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в С можно разбить на последовательность "шагов", в которых нуль или несколько цепных продукций сопровождаются неценной. Заметим, что любая неценная продукция, перед которой нет цепных, сама по себе образует такой "шаг". Но по построению грамматики б, каждый из этих шагов может быть выполнен одной ее про- яукцией.
Таким образом, 5 ~ н. С) о, Подведем итог различным упрощениям грамматик, описанным выше. Нам желательво преобразовывать любую КС-грамматику в эквивалентную, которая не имеет беспо- 7.Ь НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК лезных символов, с-продукций и цепных продукций. При этом немаловажен порядок применения преобразований. Безопасным является следуюьций. 1.
Удалить к-продукции. 2. Удалить цепные продукции. 3. Удалить бесполезные символы. Заметим, что подобно тому, как в разделе 7.1.1 результат удаления бесполезных символов зависел от порядка соответствующих шагов, данные три шага должны быть упоря- дочены именно так, иначе в грамматике могут остаться удаляемые элементы.
Теорема 7.14. Если б — КС-грамматика, порождающая язык, в котором есть хотя бы одна непустая цепочка, то существует другая грамматика Сп не имеющая бесполезных символов, кчзродукций и цепных продукций, у которой Е(С~) = ЦС) — 1к). Доказательство. Начнем с удаления е-продукций методом, описанным в разделе 7.1,3, Если затем удалить цепные продукции 1см, раздел 7.1.4), то в-продукции не появятся, поскольку каждое из тел новых продукций совпадает с некоторым телом одной из старых. Наконец, удалим бесполезные символы методом раздела 7,1.1. Поскольку это преобразование только удаляет продукции и символы, не вводя новых, то получаемая грамматика будет по-прежнему свободна от цепных и г-продукций.
Е3 7.1.5. Нормальная форма Хомского Завершим изучение грамматических упрощений, показав, что для каждого непустого КС-языка, не включающего к, существует грамматика С, все продукции которой имеют одну из следующих двух форм. 1. А — э ВС, гдеА, В и С вЂ” переменные. 2, А -+ а, гле А — переменная, а — терминал. Кроме того, б не имеет бесполезных символов. Такая форма грамматик называется лор.чальной формой Холюкого, или НФХ, а грамматики в такой форме — НФХ-грамматикамм Для приведения грамматики к НФХ начнем с ее формы, удовлетворяющей теореме 7.14, т.е, грамматика свободна от бесполезных символов, цепных и е-продукций.
Каждая продукция такой грамматики либо имеет вид А -+ а, допустимый НФХ, либо имеет тело длиной не менее 2. Нужно выполнить следующие преобразования: а) устроить так, чтобы все тела длины 2 и более состояли только из переменных; б) разбить тела длины 3 и более на группу продукций, тело каждой из которых состоит из двух переменных, Конструкция для а следующая. Для каждого терминала а, встречающегося в продукции длины 2 и более, создаем новую переменную, скажем, А. Эта переменная имеет единственную продукцию А — э а.
Используем переменную А вместо а везде в телах про- ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 280 дукцнй длины 2 и более. Теперь в теле каждой продукции либо одиночный терминаз, либо как минимум две переменные и нет терминалов. Для шага б нужно разбить каждую продукцию вида А — » В,В»...В», где 1» > 3, на групву продукций с двумя переменными в каждом теле. Введем )с — 2 новых переменных С„ Ср, ..., С» р н заменим исходную продукцию на 1» — 1 следующих продукций.
А-» В»С,,С, — » В»Ср, ..., С»» — » В» рС» р, С» р — +В»,В» Пример 7.!5. Приведем грамматику из примера 7.12 к НФХ. Для части а заметим, что у грамматики есть восемь терминалов, а, Ь, О, 1, +, *, ! и ), каждый из которых встречается в теле, не являющемся одиночным терминалом. Таким образом, нужно ввести восель новых переменных, соответствующих этим терминалам, и восемь следующих продукцлй, где переменная заменяется "своим" терминалом. А — »а  — »Ь 2 — »О Π— +1 Р— >+ М +* Š— >( Я вЂ” ») Введя зти продукции и заменив каждый терминал в теле, не являющемся одиночным тер- ивнакон, соответствующей переменной, получим грамматику, изображенную на рис. 7.2. Š— + ЕРТ ~ ТМЕ! 1 ЕВ ( а ! Ь ! 1А ( 1В ! 12 ! 10 Т вЂ” » ТМЕ ! ЕЕВ ! а ) Ь ! 1А ! 1В ) 12 ( Ю Е' — » /Ел ! а ! Ь ) 1А ( 1В ! 12 ( 10 1-+ а ) Ь | 1А ! 1В ! 12 ! Ю А — +а В-+Ь 2 — эО 0 — р! Е-»(  — э) Рис.
7.2 Преобразование »пел к одиночным ьперминолом или нескольким переменным Теперь все продукции находятся в НФХ, за исключением тех, тела которых имеют длину 3: ЕРТ, ТМГ, ЕЕК. Некоторые из этих тел встречаются в нескольких продукциях, во каждое тело преобразуется один раз. Для тела ЕРТ вводится новая переменная Сь и продукция Š— » ЕРТ меняется на Е-р ЕС, и Ср — + РТ. Для тела ТМЕ вводится переменная Ср. Две продукции с этим телом, Е-» ТМР и Т вЂ” » ТМЕ;меняются на Š— > ТСр, Т вЂ” о ТС, и С вЂ” » МЕ Для ЕЕВ вводится С, и трн продукции с этим телом, Е-+ ЕЕЯ, Т вЂ” » ЕЕЯ и Е-+ ЕЕВ, меняются на Š— » ЕС„ 7-» ЕСм Š— > ЕС» и С, — » ЕЯ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
