Карпов - Основы построения трансляторов (2005) (943926), страница 38
Текст из файла (страница 38)
На рис. 7.2 более ясным образом представлены зависимости ситуаций. Горизонтальные указатели связывают одно и то же правило с последовательно перемещаемой меткой ~такие ситуации последовательно порождены счигггывателем и завершапгелем), а вертикальные связывают ситуации, порожденные предсказателем. Для двусмысленных цепочек от одного не- терминала может идти более чем один вертикальный указатель, что показывает возможность неоднозначного построения дерева вывода.
Рис. 7.2. Множество существенных ситуаций По рис. 7.3 очевидна справедливость следующей теоремы. ° ТЕОРЕМА?.1. Ситуация <А — +ие~3; г) находится в множестве М тогда и только тогда, когда существует такой вывод Я ==>~ улб, что: у ==>*а1а2 ... а„и а==: *а,.~ а,.2 ... а,. Легко видеть, что ситуации Эрли практически совпадают с ситуациями Кнута в 1.К-распознавателях. Работа Эрли написана через 5 лет после классической работы Кнута ~К651 и тесно связана с ней. В ~Е701 Эрли сам указывает, что техника использования множеств ситуаций взята из работы Кнута об ЬК(К)- грамматиках.
Однако два этих метода распознавания отличаются в следующих главных пунктах: 1. Распознаватель для 1 К(~)-грамматик может быть использован только для подкласса грамматик, а алгоритм Эрли универсальный, он подходит для всех КС-грамматик. 256 Глава 7 2. Распознаватель для 1.К(~)-грамматик выполняет восходящий анализ, восстанавливая правый канонический вывод, а алгоритм Эрли выполняет нисходящий анализ и восстанавливает левый канонический вывод. 3. Состояния (.й(К)-распознавателя (характеристические множества ситуаций) строятся по грамматике до обработки входной цепочки и используются затем для анализа любых цепочек языка.
Алгоритм Эрли строит состояния распознавателя динамически, непосредственно при обработке конкретной цепочки языка. Для каждой цепочки языка множества ситуаций, строящиеся при ее распознавании, уникальны, каждое такое множество связано с конкретным местом в распознаваемой цепочке. Рис. 7.3. Списочное представление вывода цепочки $а+а$ после работы анализатора Эрли В общем случае алгоритм Эрли затрачивает 0(~~') шагов при распознавании цепочки длиной и, используя при этом емкость памяти 0(и'). Если же грамматика недвусмысленна и приведена.
то алгоритму требуется только 0(л') шагов. В работе,1Е70~ Эрли показал, что для широкого класса недвусмысленных грамматик время распознавания этим алгоритмом линейно. Конечно, если принять во внимание постоянный коэффициент при и, то, как указывает Эрли, "наш алгоритм не столь хорош". Описанный нами анализатор можно назвать "бесконтектным". Аналогично тому, что Кнут предложил в анализаторах 1 К(~) грамматик, Эрли рекомендует добавить в каждую ситуацию терминальную цепочку длиной 1 — так называемый допустимый терминальный контекст, который может встретиться в цепочках языка после того, как данное правило будет применено. Контекст используется завершателем для принятия решения о том, возможно ли применение закончившегося правила.
Приписанный правилу контекст сравнивается с последующей подцепочкой входной цепочки длиной К, и правило счи- Универсальные методы синтаксического анализа тается примененным, только если эти цепочки совпадают. Использование контекста может повысить эффективность распознавателя: лишние ветви анализа могут быть отброшены раньше, и на их обработку время и память не будут тратиться.
С другой стороны, ведение и расчет контекста также требуют ресурсов. Эрли не рекомендует использовать контекст длины более 1. 7.2. Алгоритм Кока — Янгера — Касаии Алгоритм Кока — Янгера — Касами строит снизу вверх все возможные выводы сначала для всех подстрок входной строки длиной 1, затем — длиной 2 и т. д. до тех пор, пока не будет проанализирована вся строка. Основная идея алгоритма состоит в том, что результаты синтаксического анализа более коротких подстрок, полученные на предыдущих шагах, используются для определения тех правил грамматики, которые могут быть использованы для порождения более длинных строк.
КС-грамматика в этом методе должна быть приведена в нормальную форму Хомского (т. е. к виду правил А — эВС' или А-+а), что позволяет анализировать разбиение любой подстроки входной строки длиной >1 на две части, синтаксический анализ каждой из которых уже произведен на предыдущих шагах и запомнен в таблице. Это универсальный алгоритм для всех КС-грамматик. Алгоритм был независимо (с некоторыми вариациями) разработан тремя учеными: Дж. Коком, Д. Янгером и Т. Касами. Алгоритм осуществляет восходящий синтаксический анализ.
Сложность алгоритма — 0(и ), используемая емкость памяти 0(~~'). В процессе выполнения алгоритм строит треугольную таблицу разбора У непосредственно по анализируемой цепочке. В каждую клетку 4 таблицы помещается множество нетерминалов, из которых можно вывести отрезок входной строки длиной /г, начинающийся с а;: 1; = (.4 ~А =е" и;...а;„~~. Содержимое каждой клетки таблицы вычисляется очень просто по грамматике в нормальной форме Хомского. Действительно, ~л = ~А ~А-+и,еЛ,, а ~; = = ~А ~ А-+ВСеЛ Й (ЛЙ:1 < Й < ~):Вн4 Й СнГ+~, ~~. Входная цепочка принадлежит языку, порождаемому грамматикой, если в клетке ~~„встретится начальный нетерминал.
Рассмотрим алгоритм подробнее. Нижняя строка таблицы Т заполняется так: в 1;~ помещаются все нетерминалы А, для которых есть правило вывода А — +а~. Пусть теперь заполнены все строки таблицы Т до~' — 1-й строки включительно. Рассмотрим клетку ~, таблицы. Эта клетка соответствует фрагменту <а, ... а,+, ~> входной строки. Разбиваем этот фрагмент всеми способами на пары соседних строк <а,> и <а,х;~ ...
а,+, ~>; <а;а;+1> и <а,+2 ... а,+, 1> и т. д. Глава 7 Каждому варианту разбиения соответствует пара клеток таблицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара клеток — (~'„~"). В рассматриваемую клетку ~, помещаем нетерминал А, если среди правил грамматики есть правило А — +ВС, и нетерминал В входит в клетку ~', а С входит в клетку ~". Рассмотрим, например, клетку 1з4 на рис. 7.4. В нее должны быть помещены нетерминалы, из которых выводится фрагмент входной строки, начинающийся с аз, длина фрагмента — четыре символа, т. е. это цепочка аза4а5аг,. Этот фрагмент тремя способами можно разбить на пары непустых соседних фрагментов: (1) аз и а4а;аб, (2) аза4 и а5аб, (3) аза~а5 и а~. Этим трем парам фрагментов соответствуют пары клеток, в которых могут стоять нетерминалы, из которых эти фрагменты выводятся: (1) для пары цепочек аз и а4а;аб это ~з1 и 64з, (2) для пары азад и а5аь это ~з2 и 62' (3) для пары азарта~ и аь это ~зз и ~ы.
Если в первой клетке из пары есть нетерминал В, во второй — С, а среди правил грамматики найдется правило А-~ВС, то нетерминал А помещается в клетку 1з4. Именно это схематично показано на рис. 7.4. Рис. 7.4. Таблица разбора для алгоритма Кока — Янгера — Касами для цепочки из шести символов ПРИМЕР 7.2.
Проведем синтаксический анализ цепочки ()()() в двусмысленной грамматике: ь- ю~ы А — +) Таблица разбора представлена на рис. 7.5. В ней нетерминалы, стоящие в клетке 1,-, помечены индексом у*. Второй шаг алгоритма — это восстановление дерева вывода цепочки, Это восстановление осуществляется с помощью рекурсивной процедуры бЕХ(г, у, А), которая порождает левый вывод А ==>'к а,а, ~ ... а, ~. 260 Глава 7 Задачи к главе 7 1.
Провести синтаксический анализ алгоритмом Эрли и алгоритмом Кока— Янгера — Касами цепочки хххх, порождаемой двусмысленной грамматикой 7-эх ~ оЬ'. 4. Провести синтаксический анализ алгоритмом Эрли и алгоритмом Кока— Янгера — Касами цепочки аааЬ, порождаемой грамматикой 5-+аВ; В-+аВ ~ Е 5.
Провести синтаксический анализ алгоритмом Эрли и алгоритмом Кока— Янгера — Касами цепочки ~+~+ю+г, порождаемой двусмысленной грамматикой Е-+Е+Е ~ !'. 6. Сравнить эффективность использования контекста длиной 1= 1 с бескон- текстным алгоритмом Эрли для грамматики арифметического выражения. 2. Провести синтаксический анализ алгоритмом Эрли и алгоритмом Кока— Яигера — Каеами цепочки хххх, порождаемой грамматикой Š— >х ~ хЕх. 3. Провести синтаксический анализ алгоритмом Эрли и алгоритмом Кока — Янгера — Касами цепочки аЬЫ, порождаемой грамматикой Я-+Ао; А-+а ~ АЬ. ГЛАВА 8 Обобщения грамматик Хомского Удивительная эффективность применения грамматик Хомского к задаче обработки искусственных языков породила многочисленные попытки использования тех жс идей в областях, совершенно отличных от трансляции языков программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
