XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 106
Текст из файла (страница 106)
8.37). Эта информация, по которой беступиковый анализатор выбирает нужную команду на каждом шаге работы с входной цепочкой, организована в виде упра- Входная лента вляющей таблицы (конкретные формы таких таблиц будут рассмотрены ниже). При этом левый вывод цепочки х = твои, если х Е Ь(С), может Головка Матаакк быть представлен следующим образом: из аксиомы вывоДитсЯ Цепочка Вяок шАа, затем нетерминал А заменяет- укравкеккя ся в соответствии с правилом А -+ у и из цепочки уст выводится терми- Рис. 8.87 нальная цепочка ои, где ( ~о~ ( к и Я ~-' шАа ~- исусе ~-" юии (символ 1- означает левую выводимость). Описанное вьппе представление левого вывода цепочки или предполагает, что мы произвольно в этом выводе фиксировали некий шаг, состоящий в замене нетерминала А посредством 676 8.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ применения правила вывода А -+ у. Так как в левом выводе на каждом шаге производится замена самого левого вхождения нетерминального символа, то слева от А в цепочке юАа, полученной перед рассматриваемым шагом, должны быть только терминальные символы. Следовательно, определенный вьппе левый контекст ю есть не что иное, как левое крыло вхохсдеиил нетерминала А в цепочку юАа. Моделируя этот левый вывод, т.е. читая записанную на входной ленте цепочку х = юои, МП-автомат читает левый контекст ю, а затем с помощью управляющей таблицы, „видя" в магазине символ А, учитывая левый контекст и и зная аванцепочку о, принимает единственно правильное решение, применяя команду, соответствующую правилу А-+7. Так на интуитивном уровне можно определить ключевое свойство ЩЙ)-грамматики.
Переходим теперь к построению формального определения ЩЙ)-грамматики. Пусть дана КС-грамматика С. Для цепочки а в обьедииеиком алфавише грамматики С и положительного натурального Й определим множество Рь (а), состоящее из всех терминальных цепочек, которые либо выводятся из цепочки а (если их длина строго меньше Й), либо являются Й-буквенными префиксами терминальных цепочек, выводимых из а (обратим внимание на то, что везде речь идет о левом выводе). Таким образом, Рь(а) = (о: (а ~* о)ЙЩ ( Й) Ч (Зх Е У")(а ~-' ох)ЙЩ = Й) ). Нетрудно видеть, что для всякой терминальной цепочки х получим Рл(х) = (х), если /х~ < Й, и Рь(х) = 1х(1)х(2)...х(Й)), если !х~ > Й.
Множества Рь(а) (для разных цепочек а) иногда будем называть Рь-миожесгпвами. Пример 8.23. Зададим грамматику 6 с терминальным алфавитом (а, 6, с, д) и нетерминальным алфавитом, состоящим Д.Вд. О методах скктакскческото акааава КС-юыков 677 из одной аксиомы Я, следующим множеством правил вывода: Я -+ аЯЬЯс ~ аЯЬ | ЬЯс ~ И. Вычислим множество Рз(аЯЬЯс). Первая буква всех терминальных цепочек, выводимых нз заданной, уже фиксирована— это буква а. Нетерминал Я может быть заменен буквой И, после чего возникнет трехбуквенный префикс адЬ. Но символ Я можно заменить и цепочками аЯЬЯс, аЯЬ, ЬЯс. В силу этого первые две буквы цепочки, выводимой из исходной, могут быть либо аа, либо аЬ.
Продолжение вывода, как нетрудно понять, может дать третью букву — либо а, либо 6, либо Ы. Окончательно получаем Рз(аЯЬЯс) = (аЫЬ, ааа, ааЬ, аай, аЬа, аЬЬ, аЫ). Определение 8.11. КС-грамматику С = (т", У, Я, Р) называют ЬЬ(й)-граммптвиееоб (для произвольно фиксированного й ) 1), если дла любых ел Е 'т", А Е Ф, сх Е (У 0 Ф)', таких, что существуют левые выводы Я ~-' шАсх ~ ю13сх 1-' еу Я 1- * юАа 1- итуа ~- ' ия, из Ра(у) = Рь(х) следует 13 = 7. Таким образом, из этого определения следует, что для с.Ь(к)-грамматики левый контекст ю нетерминала А в цепочке шАсх и не более чем Й символов, с которых начинается терминальная цепочка у, выводимая из Аа, однозначно определяют то правило, которое нужно применить к цепочке шАа (заменяя в ней выделенное, т.е.
первое, вхождение нетерминала А), чтобы сделать очередной шаг в левом выводе цепочки шу (и именно этой цепочки!) из аксиомы грамматики С. При совпадении множеств Ра(у) и Ра(я), как следует из сформулированного определения, указанные два вывода „сливаются" в один, т.е. тогда р= ю 678 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ (8.26) Определение ЩЙ)-грамматики является само по себе труднопроверяемым. Нужно какое-то условие, проверка которого позволила бы дать ответ на вопрос, является ли заданная КС-грамматика ЩЙ)-грамматикой. Доказывается, что дать ответ на этот вопрос можно, только фиксирован число Й. Построить же алгоритм, отвечающий на вопрос, является ли данная КС-грамматика ЩЙ)-грамматикой для некоторого Й (не задавая его заранее), невозможно.
Следующая теорема (формулируемая без доказательства) дает соответствующий критерий (необходимое и достаточное условие) при фиксированном Й. Теорема 8.12. КС-грамматика С является И(Й)-грамматикой (для фиксированного Й > 1) тогда и только тогда, когда для любой цепочки ш Е 1"' выполняется следующее условие: для любых А Е Ф, а Е (У 0 Ф)', таких, что В 1-' юАа, и любых двух различных правил А -+ ~3 и А -+ у грамматики С имеет место ЫРо) ~РЙЬа) = О У Условие теоремы называют часто ЬЬ(Й)-условием. Его следует проверять, фиксируя по очереди левые контексты (т.е. различные цепочки ш) для всех нетерминалов грамматики.
Рассмотрим пример, в котором, используя теорему 8.12, мы убедимся в том, что заданная КС-грамматика является ЬЬ(Й)-грамматикой (для фиксированного Й). Пример 8.24. Грамматика С задается системой правил В -+ аЬА ~ Л, (1) 1(2) А -+ Яаа~Ь. (3) ~(4). Докажем, что данная грамматика является ЬЦ2)-грамматикой. Чтобы проверить условие теоремы 8.12, достаточно для каждого нетерминала В Е 1о, А1 нашей грамматики проделать следующее: 1) вычислить все такие цепочки ю Е (а,Ь1' и а Е Н (а, Ь, Я, А), что имеет место левая выводимость Ь' 1-* юВа; д.8.ь О методах синтаксического эюииээ кС-хэыиоэ 679 2) фиксирован „левый контекст" ю, для каждой пары различных правил вывода В -+ 7 и В -~ Я вычислить множества Рз(фа) и Рз( усе) для всех таких сх, что при фиксированном ю выполняется (8.26), и убедиться в том, что их пересечение пусто. Если выполнение п. 2 для всех возможных левых контекстов ю и всех нетерминаяов В подтвердит истинность условия теоремы 8.12, то тем самым и будет доказано, что перед нами Щ2)-грамматика.
Следует заметить, что в общем случае вычисление пар цепочек (ео, а), удовлетворяющих условию (8.26) (для всех нетерминалов В КС-грамматики), требует применения специального алгоритма. Но для конкретной грамматики нашего примера эти пары цепочек достаточно просто вычисляются из анализа выводов грамматики. По очереди проанализуем оба нетерминала, т.е. Я и А, грамматики С.
Нетермннал Я. В этом случае имеем, во-первых, тривиальную выводимость Я с-О Я за нуль шагов, т.е. в этом случае цепочки то и сх обе являются пустыми: ю = сх = Л. Нетерминал Я может быть заменен согласно правилу (1) с правой частью аЬА или согласно правилу (2) с пустой правой частью. Вычислим тогда множества Рз(аЬА) и Рз(Л). Ясно, что Рз(аЬА) = (аЬ), а Рг(Л) = (Л1 и эти множества не пересекаются. Проанализируем теперь, каким образом в заданной грамматике может быть выведена из аксиомы Я за число шагов, большее нуля, цепочка вида асс для некоторых терминальной цепочки ш и цепочки в объединенном алфавите сх.
Так как вхождение Я может возникнуть только после применения правила (3), а чтобы применить его, нужно сначала применить правило (1), то, чередуя применение этих правил и > 1 раз, получим вывод: Я 1- аЬА ~- аЬЯаа ~- аЬаЬАаа ~ >- аЬаЬЯаааа ~... ~ (аЬ)" Я(аа)". (8.27) 680 в.
контнкстно-сноноднын языки Это значит, что все возможные пары (ю, а), такие, что Я 1-' вЯо (с учетом уже ранее рассмотренного случая, когда обе цепочки пусты), есть ти = (аЬ)" и а = (аа)", и > О. Вычисляем множества Рэ(аЬА(аа)") и Рэ(Л(аа)") для различных и ) )О. Первое множество, как нетрудно видеть, для всех п будет равно (аЦ, а второе при и = 0 будет состоять иэ одной пустой цепочки, а при и > 0 — из цепочки аа, т.е.
можно утверждать, что для всех и > 0 пересечение Рэ(аЬА(аа)") П Рэ(Л(аа)") = и. Итак, для нетерминала Я (аксиомы грамматики С) условие теоремы 8.12 выполнено. Нетерминал А. Рассматривая вывод (8.27), легко убедиться в том, что все пары (щ, а), для которых имеет место ! левая выводимость Я~-" шАо, есть и = (аЬ)", а = (аа)" 1 для всех и > 1. Нетерминал А является левой частью двух правил вывода (3) и (4) с правыми частями Яаа и Ь соответственно. Вычисляем соответствующие Рэ-множества: Рэ(Яаа(аа)" 1) = 1аЬ, аа1, а Рэ(Ь(аа)" 1) = (Ь), если и = 1, и Рэ(Ь(аа)" 1) = (Ьа)> если и > 1.
Как видно, при всех и пересечение укаэанных множеств пусто. Тем самым доказано, что и для нетерминала А критерий теоремы 8.12 выполнен и заданная грамматика является ЬЬ(2)-грамматикой. Полученный результат показывает также, что эта грамматика является Щ2)-грамматикой, не являясь Щ1)-грамматикой. Действительно, для нетерминала Я получим Р1(аЬА(аа)") = (а) при всех а > О, а Р1 (Л(аа)") = (а) при всех и > 1.
Следовательно, при всех п > 1 указанные множества совпадут, что означает д.В.ь О методах сиитаксического эиэлиээ кС-языков 681 невыполнение ЬЬ(1)-условия. Заметим, что для нетерминала А 1 Ц1)-условие выполняется. Результаты анализа представлены в табл. 8.1. Таблица 8.1 Внутри таблицы указаны номера применяемых правил. Прочерк означает, что данная пара (нетерминал, аванцепочка) не определяет никакого правила, и возникновение такой пары в процессе анализа сигнализирует о синтаксической ошибке. Мы видим, что в данном случае номер применяемого на каждом шаге правила вывода однозначно определяется только двумя факторами: нетерминалом в верхней ячейке магазина и аванцепочкой.
11(й)-грамматики, в которых выполняется такое условие, называют сильнымп л л (й)-гральматппмама. Таблица подобного вида для сильной ЬЬ(Й)-грамматики и является примером управляющей таблицы. Именно она обеспечивает в данном случае тот механизм управления выводом, который позволяет МП-автомату, построенному по заданной сильной Щи)-грамматике, на каждом шаге однозначно выбирать правило вывода и для „правильной" цепочки строить ее левый вывод, а для „неправильной" — сигнализировать об ошибке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
