XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 107
Текст из файла (страница 107)
~К Следующий пример показывает, что существуют Щй)-грамматики, не являющиеся сильными. Пример 8.25. Зададим грамматику С~ системой правил Я -е аАаа ~ ЬАЬа, (1) ~(2) А ~ Ь/ Л. (3) /(4) 682 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Для этой грамматики легко построить все ее деревья вывода (рис. 8.38) и проверить г г.(й)-условие. Ь а Ь Рис.
8.38 ! В данном случае о ~-' шала влечет ш = Л, а = Л и гг(аАаа) = = ~аЬ, аа), а гг(ЬАЬа) = (ЬЬ), т.е. гг(аАаа) Г~ гг(ЬАЬа) = И. Х Из о 1-' юАа следует, что и = а или и = Ь. Если и = а, то о = аа и Рг(Ьаа) = (Ьа), а гг(Лаа) = (аа), т.е. гг(Ьаа)11гг(Ла) = = И. Если же гл = Ь, то а = Ьа и гг(ЬЬа) = (ЬЬ), гг(ЛЬа) = (Ьа), и в этом случае также гг(ЬЬа) й.гг(ЛЬа) = И.
Таким образом, рассматриваемая грамматика есть Щ2)-грамматика. Сведем полученные результаты в табл. 8.2. Таблица 8.3 Д.8.1. О методах сиктакскчеекого акаакэа КС-аэыков 683 Иэ табл. 8.2 следует, что одна и та же пара (А, Ьа) не определяет однозначно применяемого правила и требуется информация о левом контексте. Из этой же таблицы видно, что данная грамматика не является г г (1)-грамматикой, поскольку, например, однобуквеннэя аванцепочка Ь вместе с нетерминалом А и левым контекстом Ь не определяет однозначно применямого правила.
ф Таким образом, для сильных г г (и)-грамматик МП-автомат, который строится по КС-грамматике, может быть преобразован в синтаксический анализатор путем добавления к нему управляющей таблицы и выходной ленты (первоначально пустой), на которой автомат пишет номера правил в порядке их применения, а также сигнал ошибки. В результате анализа для правильной цепочки, записанной на входной ленте, на выходной 'ленте появится ее левый вывод (точнее, „протокол" левого вывода в виде последовательности номеров применямых правил), а для неправильной цепочки на выходной ленте появится сообщение об ошибке (в виде какого-нибудь специального символа). Представим теперь протоколы анализа некоторых цепочек в грамматике С примера 8.24.
Пусть х = аЬаЬЬаа; имеем последовательность конфигураций (четвертая компонента конфигурации — содержимое выходной ленты): (д, аЬаЬЬоа, Я, Л) 1- (д, аЬаЬЬаа, аЬА, 1) 1-~ 1-~ (4, аЬЬоа, А, 1) ~- (д, аЬЬаа, Яаа, 13) 1- 1 — (о, аЬЬаа, аЬАаа, 131) 1 — ~ (о, Ьаа, Ааа, 131) 1- 1- (о, Ьаа, Ьаа, 1314) ~-~ (д, Л, Л, 1314).
Обратим внимание на то, что на каждом шаге вывода наш автомат-анализатор в существенном отличии от обычного распознавателя, который может легко взаблудитьсла (особенно при выборе альтернативы для нетерминала А), использует информацию управляющей таблицы. гг 684 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Посмотрим, как отработает такой анализатор синтаксическую ошибку.
Берем цепочку у = а6ЬЬ, имеем (д, аЬЬЬ, Я, А) 3- (д, аЬЬЬ, аЬА, 1) 1-~ ~ г(~ 66 А 1)~-(о 66 4 1 ВНВОВ«) так как пара (А, ЬЬ) не определяет никакого правила. Для не сильной ЬЦЬ)-грамматики учет левых контекстов в общем случае весьма сложен, и мы его здесь не рассматриваем'. Приведем, наконец, простой пример грамматики с терминальным алфавитом 1а,6,0, 1), не являющейся ЬЦЬ)-грамматикой ни для какого й: Я-» А~В, А -+ аАЬ|О, В -+ аВЬЬ)1. Для любого Й > 1 имеем Я ~ А 1-' а~06~, В ~- В 1-* а" 16з". Одинаковый префикс а" не дает возможности отождествить цепочки )9 = А и у = В, т.е. нет возможности обеспечить выбор альтернативы для нетерминала Я. Восходящий анализ. йК(й)-грамматики.
Ключевым понятием при рассмотрении восходящего синтаксического анализа является понятие основы. Определение 8.12. Пусть сь = (Р; Ф, о, Р) — КС-грамматика, с — цепочка в объединенном алфавите, А + а е Р. При а С с вхождение а в ч (,о, а, у) называют основой, если цепочка ВАу выводима из аксиомы 8 при условии, что цепочка ~ выводима из аксиомы Я. 'См:.
Азо А., Ульмьн Дзс. д.8л. О методах синтаксичесиого авазиза кС-изьпсов 685 Таким образом, по определению, основа — это такое вхождение правой части некоторого правила КС-грамматики в некоторую выводимую из аксиомы цепочку, что после замены этой правой части соответствующим нетерминалом полученная цепочка снова будет выводимой из аксиомы. Заметим, что для не выводимой нз аксиомы цепочки любое вхождение правой части некоторого правила в нее можно считать основой. Замечание 8.13. Ни в коем случае нельзя путать понятие основы в смысле определения 8.12 с понятием основы вхождения (см. 7.1)! Пример. Рассмотрим грамматику, задаваемую системой правил: Я-+Ас~ВИ, А -+ аАЬ | аЬ, В -+ аВЬЬ ~ аЬЬ. Возьмем цепочку х = ааЬЬЬЫ. Мы видим здесь вхождения двух правых частей правил — аЬ и аЬЬ.
Вхождение первой цепочки не является основой. Действительно, заменяя аЬ не- терминалом А, получим цепочку аАЬЬЫ. Для этой цепочки существует единственное правило А -~ аАЬ, правая часть которого входит в нее. еСвертываяа цепочку аАЬ в нетерминзл А, получим АЬЫ вЂ” слово, в которое не входит ни одна правая часть какого-либо правила данной грамматики. Следовательно, ни полученная цепочка, ни предшествующая ей цепочка не являются выводимыми из аксиомы.
Возвращаемся к цепочке х и, заменяя подцепочку аЬЬ нетерминаяом В, получаем аВЬЫ, где единственное вхождение правой части правила — аВЬЬ. Производя замену этого правила нетерминалом В, будем иметь цепочку ВИ, которая „свертываетсяа в аксиому Я. Итак, мы провели в обратном порядке вывод цепочки х из аксиомы: Я 1- Вс1 ~ аВЬЫ Р ааЬЬЬЫ. Ф 686 В.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Задача восходящего анализа и состоит в поиске „редукции" исходной терминальной цепочки в аксиому, где на каждом шаге производится поиск основы в текущую цепочку с последующей заменой ее соответствующим нетерминзлом, т.е. применяется „инверсия" некоторого правила данной КС-грамматики: правая часть правила заменяется левой. Нетрудно понять, что если мы заменяем на каждом шаге такой „редукции" самую левую основу, то восстанавливаем с конца к началу правый вывод исходной цепочки, а если самую правую основу, то ереконструируем" левый вывод. Как и в случае нисходящего анализа, здесь возникает проблема тупиков и связаннал с ней проблема управления выводом.
Мы рассмотрим некоторые простейшие методы построения „беступиковой редукции", а именно такие методы определения основы, при применении которых попадание в тупик на некотором шаге редукции влечет синтаксическую неправильность входной цепочки.
Один из методов состоит в сопоставлении каждому правилу КС-грамматики некоторого бинарного отношения на множестве (УОФ)'. Вхождение правой части некоторого правила является основой тогда и только тогда, когда его крылья принадлежат сопоставленному данному правилу бинарному отношению.
Проблему единственности определяемой таким образом основы, равно как и проблему характеристики класса КС-грамматик, допускающих такую „параметризациюе бинарными отношениями, мы здесь не рассматриваем'. Ограничимся простым примером. Рассмотрим грамматику, порождающую множество непустых палиндромов в заданном алфавите У: Н-+аЯа~аа~а, ееЕ'е'. Каждому правилу сопоставим одно и то же отношение Нп, е):!и! = Ю, 'Сме Геешкое В.М.„Девтекк Г.Е., Ющенко Е.Л. Д.8.1. О методик еиитакеического киелиэк КС-языков 687 так, что этому отношению принадлежат только пары с одинаковой длиной компонент. Тогда осуществима беступиковвл редукция любого палиндрома.
Например: абЬссбба -1 аЬЬЯЬба -1 абЯЬа -1 аЯа -1 Я. В данном случае на каждом шаге принадлежность крыльев вхождения правой части правила введенному отношению однозначно определяет основу, и получение тупиковой цепочки означает ее неправильность. Заметим, что без введенного таким образом управления выводом (т.е. выбором очередного правила) даже при „свертывании" правильной цепочки можно попасть в тупик: аббссЬЬа -1 аЯссбба -1 аЯЯЬЬа -1 аЯЯЯа. Неверное определение основы на первом шаге редукции привело к тупиковой (т.е.
не содержащей ни одного вхождения правой части какого-либо правила) цепочке, хотя входная цепочка является правильной. Несколько более подробно рассмотрим класс КС-языков, допускающих беступиковый восходящий анализ и порождаемых так называемыми ЬВ(й)-грамматиками. Неформально йВ(й)-ерамматпииа, й ) О, — это КС-грамматика, в которой основа однозначно определяется по левому крылу вхождения правой части некоторого правила вывода („левому контексту") и по не более чем й-буквенному пре. фиксу правого крыла („правого контекста"). Строго понятие ыВ(й)-грамматики вводится весьма сложно, и мы его опускаем. Оказывается, что класс языков, порождаемых ЬВ(й)-грамматиками, может быть охарактеризован в терминах детпермипировакныя МП-автпоматпов (ДМП-автпоматпов).
Прежде чем определять ДМП-автоматы, введем в рассмотрение модификацию МП-автомата, называемую расииюрекнььи ЫП-ааптоматттоде, которая как раз ориентирована на представление восходящего синтаксического анализа. 688 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Говоря коротко, отличие расширенного МП-автомата от обычного состоит в том, что в магазине можно заменять не только верхний символ, но и непустую цепочку символов, расположенную в верхних ячейках магазина, так, что первый ее символ есть верхний символ магазина, второй символ — символ, расположенный под верхним, и т.д. Формально расширенный МП-автомат определяется совершенно так же, как обычный (см. определение 8.7), но функция переходов задается системой команд вида оаа -+ с~3, где а Е У 01Л); а и 13 — магазинные цепочки, причем а не пуста.
При записи системы команд расширенного МП-автомата условимся записывать магазинные цепочки от „дна" магазина к его „верху". Можно доказать, что расширенные МП-автоматы допускают в точности тот же класс языков, что и обычные, т.е. можно доказать, что по любому расширенному МП-автомату можно построить зквивалентный ему МП-автомат в смысле определения 8.T. Далее будем говорить „МП-автомат", имея в виду расширенный МП-автомат.
Определение 8.13. МП-автомат называют дехпермнннрованным(ДМП-автпомахпом), если из любой его конфигурации непосредственно выводится не более чем одна конфигурация. Нетрудно доказать следующее утверждение. Теорема 8.13. МП-автомат является ДМП-автоматом тогда и только тогда, когда для любой упорядоченной пары (д, а) Е Я х Г верно одно из двух: 1) для любого а Е У существует не более одной команды с левой частью оаа, причем если для некоторого а Е У такая команда существует, то не существует команды с левой частью дЛа и не существует ни одной команды с левой частью да'а~, где а' Е (а, Л) и а' является концом цепочки сц 'Смх Ахо А., Ухьман Дж.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
