Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 43
Текст из файла (страница 43)
Следовательно, мы не получаем тот же самый язык, нз чего и следует требуемый результат. Р Подобные противоречия могут быть получены во многих ситуациях, когда информация, содержащаяся в более ранней части строки, влияет на требуемую структуру последующей подстроки. Следующий пример является типичным в этом отношении. Пример 3.4. Язык г (1г: ршХ, р — простое число) не является контекстно-свободным: Ь (11, 111, 11111, ). Предположим, что г' является КСЯ. Так как существует бесконечное множество простых чисел, то имеется простое число о такое, что 14 пщрлу, пх Л, по'ия'р ш г для всех 1 а Х (это следует из приведенной выше леммы).
Таким образом, существуют а, Ь, с, Н, е такие, что 1' 1'Р1'1Ч' при Ь+Н) О и 1 = а'(1 ) 1" (1") 1'знг для всех 1шХ, так что д а+Ь+с+П+е= простое число и у~1, а о, а+с+а+(Ь+г()1 — простое число для всех 1шХ. В частности, д — простое число при 1 а+ Ь+с+ И+ а+ 1, и в этом случае д,=(а+с+а)+(Ь+ с) (а+ Ь+ с+И+ е+1) (а+ с+ е)+(Ь+ Н) ((а+ с+ е)+(Ь+ И)+ 1) ((а+ с+ е)+(Ь+ и) ) (1+(Ь+ и) ) д(1+ Ь+ И). Однако д) 1 и Ь+ О+1) 1; следовательно, р® не является простым числом для всех (ш Х, и мы получаем противоречие. Поэтому т' (1г: р ш Х, р — простое число) не является КСЯ. г" Этот пример также демонстрирует практическую важность связанного и несвязанного синтаксисов.
Можно придумать жесткий фиксированный синтаксис, который И! включает правильную семантику. Однако, где это вовможно, часто гораздо удобнее и аффективнее разрешить испольвование более широкого яаыка, порожденного (обычно контекстно-свободной) грамматикой, а ватам, если необходимо, сузить множество путем дальнейшей семантической проверки.
В примере 3.4 мы могли бы испольаовать правило 8- 1Я11, чтобы породить все строки Р: д) 1, и после этого проверить, что «д — простое число», с помощью подходящего арифметического алгоритма. Короче говоря, контекстно-вависимые грамматики являются сложными и не изучены с достаточной полнотой. С другой стороны, контекстно-свободным грамматикам уделяется достаточно много внимания, и они составляют основу почти всех практических компьютерных трансляционных систем. У п р а ж н е н н е 8.3.
1. Вывести КСГ, которая порождает множество всех строк над (а, Й, имеющих равное количество а и 6. 2. Построить грамматики, порождающие следующие языки: а) (а'" п>1) б) (а"6~ '. и, т > 1); в) (а"б": и > 1), и, и ж Х. 3. Используя лемму о разрастании, показать, что язык Е (а: ненг(( не является контекстно-свободным. 4. Показать, что если Ь| и Ьр являются КСЯ, то таким же является язык Ь~ У Ем 5. Доканать, что множества (х"р"з: и'-1, и> 1), (х р"х": п> 1, т> 0 являются КСЯ; покаэать, что если яаыки Ь| и Ег являются контекстно-свободными, то отсюда не следует, что явык Ь~ д Еа является контекстно-свободным, 5 4. Понятия грамматического разбора и грамматических модификаций Наиболее непосредственный и очевидный контакт, который средний пользователь имеет с процессами перевода (трансляцией с одного языка на другой),-это использование различного рода компиляторов для таких языков высокого уровня, как Паскаль, Фортран, Кобол, Алгол и др.
При использовании такого языка программа, которую мы написали, транслируется в эквивалентную программу в машинном коде (объектную програшму), которая может быть расшифрована и выполнена компью« тером. Общая схема компиляции изображена на рис. 8.6. Исходвак программа ! л,, г„, тор Лексическая форма — — — 'Хаблица символов ! Дерево грамматического разбора Генератор кода Объектная программа Оптимизатор Оптимизированная объектная программа р .ав В общем случае стадии процесса компиляции могут рассматриваться связанными последовательно, как это изображено на диаграмме; однако на практике они часто выполняются одновременно. Генерация кода требует зна.
ния семантических интерпретаций, которые связаны о 383 каждой синтаксической структурой внутри программы, Для оптимизации машинного кода необходимо знать тонкости строения машины. Мы пе будем рассматривать эти стадии, а ограничимся лишь обсуждением трансляции ключевой программы в дерево грамматического разбора. Ключевая (исходная) программа является просто строкой символов. Внутри атой строки часто встречаются некоторые комбинации символов, в которых отдельные символы не имеют смысла, однако комбинация символов передает смысл. (См. пример 2 1; «доя» имеет значение, а буква «о» внутри «бой», очевидно, отдельно не несет смысловой нагрузки.) Такие составные символы, называемые также лексемами, не являются абсолютно необходимыми и могут не использоваться в некоторых языковых трансляторах, однако обычно опи существуют и кодируются одним символом (для каждой комбинации свой символ), чтобы сократить длину исходной программы (на данныи момент в ее лексической форме) и избежать необходимости рассматривать ненужные детали на следующих этапах.
Типичными лексемами являются: а) ключевые слова, т. е. слова с постоянным значением в языке; например, Ьея1п СОТО епб Паскаль, РО Фортран, ч«ЬПе .ОК. +, —, «, / в большинстве языков; б) числа 52, 3$.65 и т. п:„ в) строки или последовательности символов; г) идентификаторы, введенные программистом. Лексемы обычно описываются регулярными грамматиками.
Следовательно, мы свели исходную проблему к грамматическому разбору строки лексем. Графически это означает — заполнить треугольник на рис. 8.7 таким образом, чтобы он в н ...," а„был совместим с продукцией правил грамматики. 4Л. Процедуры приведения. В об- щем случае нам не разрешается изменять строку и ° а»аэ...а„; поэтому вся деятельность до проведения процесса грамматического раабора должна быть направлена на грамматику. Потенциально нам 2И будет необходимо осуществить достаточно сложные преобразования грамматики, чтобы проверить, что все нстерминалы действительно можно использовать в грамматическом разборе. Существует два варианта, в которых нетерминалы могут пе подходить для проведения произвольного грамматического разбора; опишем их формально.
Определение. Пусть С-(У, Т, Р, д) есть КСГ. Тогда говорят, что петерминальный символ Хый является: а) недоступным, если ХФВ и не существует вывода вида д=~-аХр для а, () ~ т'»; б) непродуктигным, если не существует строки (ез ш Т» такой, что Х=ь.у; в) бесполезным, если он недоступен или непродуктивен. Грамматика, не имеющая бесполезных нетерминалов, называется редуцированной. г Ясно, что бесполезные символы не играют никакой роли в построении предложений. Хотя хотелось бы не включать в грамматику бесполезность символов, они могут быть введены алгоритмами, предназначенными для модификации грамматики с целью соответствия некоторым требованиям (см.
нил~е). Бесполезные символы не обязательно увеличивают размер грамматического разбора, и сейчас мы опишем процесс их удаления. Пусть 0 (У, Т, Р, В) есть КСГ. Определим множество У' как Л' УО(т), где т — новый символ (г Ф т'), и отношение р на У' сле- дующим образом: (А, В)~ар, если А- аВ()жР при А, ВжУ, сг, ()ж'т'»; (А, т)ыр, если А - (ыР при кеко- тором (ж Т». Предложение.
а) А доступно тогда и только тогда, когда А 8 или (В, А)ыр+; б) А является продуктивным тогда и только тогда, когда (А, т)1и р+. Доказательство. а) А доступно тогда и только тогда, когда существует вывод вида В=г аАр для а, рж У» или, что зквивалент- 2И но, тогда и только тогда, когда существует (Э-О такое, что я ...
Ао Когда ЯФА, это имеет место лишь в случае Яр+А; по~ этому (Я, А)жр+. б) А продуктивно тогда и только тогда, когда А=о.у для некоторого ~ > О и (ж Т*, т. е. тогда и только тогда, когда существует последовательность сентенциальных Форм ао, аь °, а; таких, что А ~ ао ~ а~ ~- ... =о. а, т, т. е. когда существует последовательность А =Ао, Аь ... ..., А, 1ои Л~ такая, что А, является подстрокой а„ и, следовательно, АорА ь А~рАо, °, А -орА<-ь А -1-+ ~), где ~) — подстрока (, т. е. АорАь А1рАо, ..., А< ~рт.
По- этому Ар+т. Р На практике р+ можно вычислять, используя алго- ритм Уоршолла. Пусть У„~)У вЂ” множество бесполезных символов 6 и У =М\М„, Р Р'~Р„, где Є— множество продукций, содержащих элементы У„. Тогда 6' (Ж', Т', Р', Я), где Т' — мноноество терминальных символов, по- являющихся в продукциях Р', эквивалентно КСГ без бесполезных символов. Алгоритм.
Удаление бесполезных символов. Вход: КСГ 6 (У, Т, Р, Я). Выход: эквивалентная КСГ 6' (Л", Т', Р', Я) без бесполезных символов. Метод: построить )У', Т', Р', как указано выше. г П риме р 4.т. Рассмотрим грамматику 6 ((А, В, С, Р), (х, у, р, д, и~, а), Р, А), где Р (А -+х~уРС~Р, В-+д(Вх, С- Сх!уС, Р- Ра~Си~р). Искользуем отношение р, определенное выше, и его предотавление в матричной ф~рме: АВСРт А В м(р) =с Р О О г $ 0 $ О О г О О Х О О О О т $ О О О О о В этом примере имеем М(р+)=М(р)=М. Таким образом, М,=М„-О, и поэтому В недоступно, а С непродуктивно.
Следовательно, грамматика сводится к 6' ((А, Р), (х, а, р), Р', А), где Р' = (А - х~Р, Р ~- Ра!р). » После удаления бесполезных символов каждый оставшийся нетерминальный символ Х встречается по крайней мере в одном дереве вывода (рис. 8.8) с Х, связанным вверх с Б и вниа с некоторыми терминальными строками а~...а . /~~!Ь Один «очевидный» путь грамматического разбора строки— ато вывести все строки, отметить их соответствующие канонические последовательности, а затем про- /) верить предложение, сравнивая его с каждой строкой. При совпадении использовать выводящую ... и а» - ° ° - и последовательность, чтобы определить дерево грамматического Рвс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
