Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 65
Текст из файла (страница 65)
а5Ы будет первой альтернативой петерминала 5, а5 †втор н с †треть. Допустим, что входная цепочка †нас. В дальнейших рассуждениях мы будем употреблять входной указатель, который в начальный момент указывает на самый левый символ входной цепочки. Коротко говоря, нисходящий анализатор пытается построить дерево вывода входной цепочки следующим образом. Процесс начинается с дерева, состоящего из одной вершины, помеченной 5. Это начальная активная вершина. Затем рекурсивно выполняются такие шаги: (!) Если активная вершина помечена нетерминалом, скажем А, то выбрать первую его альтернативу, скажем Х! ...
Хл, и добавить и прямых потомков вершины А с метками Х„..., Х„. Сделать Х активной нершиной. Если Е=О, сделать активной 1 вершину, расположенную непосредственно справа от А. (2) Если активная вер4пина помечена терминалам, скажем а, сравнить текущий входной символ с а, Если они совпадают, сделать активной вершину, расположенную непосредственно т! А. Аяо, Дж. Ульм»и, е, ! 32! ГЛ. И ОБЩИС МЕТОД!и СИНТАКСпс!ВС1СОГО АНАЛИЗА ! 1, СИПТАКСИ'1ЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ справа от а, и сдвинуть входной указатель на один символ вправо.
Если а не совпадает с текущим входным символом, вернуться к вер1пине, к которой применялось предыдущее правило, вернуть, куда надо„входной уиазатель, если это необходимо, и испытать следующую альтернативу. Если альтернатив больше нет, вернуться к следующей предыдущей вершине, и т. д. Всякий раз мы пытаемся сохранить совместимость построенного дерева с входной цепочкой, т. е. если Асс — крона дерева, построенного к данному моменту, где цепочка св либо пуста, -!! Рнс, 4.2. Частичные херевьи разбора. либо начинается нетерминальным символом, то х — префикс ВХОДНОЙ ЦЕПОЧКИ, В пап!ем примере мы начнем с дерева, состоящего из одной вершины, помеченной 5.
Затем применим первое 5-правило, расширяя дерево так, чтобы оно было совместимо с данной входной цепочиой. Здесь применим правило 5 — ва5Ь5, чтобы расширить начальное дерево до дерева, изображенного па рис. 4.2, а. Так каи активной вершиной дерева в этот момент станет а и первый входной символ тоже а, мы передвинем входной указатель на второй входной символ и сделаем петера!Инал 5, стоящий непосредственно справа от а, новым активным символом. Затем развернем этот символ 5 с помощью первой альтернативы и получим дсрсво на рис. 4.2, б. Так как новый активный символ а совпадает со вторым входным символом, передвинем входной указатель иа третин входной символ.
Теперь развернем самый левый петерминал 5 на рис. 4.2, б, но на этот раз нельзя применить пн нерву!о, нн вторую альтер- 322 нативу, так как в результате получится левовыводимая цепочка, „есовместимая с входной цепочкой. Поэтому мы воспользуемся третьей альтернативой придем к рис. 4.2,' Сейчас можно передвинуть входной указатель с третьего на четвертый, а затем яа пятый входной символ, так как с и Ь вЂ” следующие два активных символа левовыводимой цепочки, представленной на рис. 4.2, и. Далее можно с помощью третьей альтернативы для 5 развернуть самый левый символ 5 иа рнс. 4.2, в и получить рис.
4.2, г. (Первые две альтернативы снова несовместимы с входом.) Пятый входной символ — с, и потому входной указатель можно передвинуть на один символ вправо. (Мы предполагаем, что конец входной цепочки обозначается маркером,) Однако дерево на рис. 4.2, г порождает дополнительные символы, а именно Ь5, которых иет во входной цепочке, так что теперь мы знаем, что при поиске правильного разбора входной цепочки пошли по неверному пути. Если вспомнить МП-анализатор из равд. 4.1.1, то окажется, что мы прошли через последовательность конфигураций С„ С„ С„ С„ С„ С„ и из С! переход невозможен.
Итак, пам придется искать какую-то другую левовыводимую цепочку. Сначала посмотрим, нет ли другой альтернативы для правила, использованного при построении дерева па рис. 4.2,г из предыдущего дерева. Оказывается, такой альтернативы нет, так как для получения рис, 4,2,г из рис. 4.2,в использовалось последнее 5-правило 5 с. Тогда мы возвращаемся к дереву рис. 4.2,з и переставляем указатель на позицию 3. Проверяем, есть ли еще альтернативы правила, использованного прн построении дерева на рис.
4.2,в из предыдущего дерева, Видим, что их нет, так как мы применяли правило 5 — с. Поэтому мы возвращаемся к рис. 4.2,б, переставляя входной указатель на позицию 2. Прн переходе к рис. 4,2,б от рис. 4,2,а применялась первая альтернатива, так что теперь испытаем вторую альтернативу и получим дерево на рис. 4,3,а. Входной указатель можно передвинуть вперед па позицию 3, поскольку порожденный символ а совпадает с входным символом а в позиции 2. Далее, чтобы развернуть самый левый символ 5 на рис.
4.3,а и получить рис. 4.3,б, можно применить только третью альтернативу. Входные символы в позициях 3 и 4 совпадают теперь с порожденными, так что можно передвинуть входной указатель на позицию б. К нетерминалу 5 на Рнс 4.3,б можно применить только третью альтернативу и получить рис. 4.3, а. Последний входной символ совпадает с самым правым символом на рис. 4,3, в.
Таким образом, мы знаем теперь, что на рис. 4.3,в изображен правильный разбор входной цепоч- !1* 323 Рне. 4.4. Знаненнн 0(б). 324 325 ГЛ. К ОБЩИЕ МЕТОДЫ СИНТАКСИЧРСКОГО АНАЛИЗА ки. Здесь можно либо сделать возврат, чтобы продолжать по. иск других разборов, либо остановиться. Из-за того, что наша грамматика пе леварекурсивна, мы с помощью возвратов в конце концов исчерпаем все возможности, т.
е. окажемся в корнети все альтернативы для Я будут уже Рне. 4.3. Дальнейшие попытки разбора. испытаны. В этот момент можно остановиться и, если нужпый разбор не обнаружен, выдать сообщение о том, что входная цепочка синтаксически неправильна, В описанной процедуре есть коварная ловушка.
Если грамматика леворекурсивна, то процесс может никогда не остановиться. Например, допустим, что Азь — первая альтернатива для А, Тогда это правило будет применяться всякий раз, когда надо развернуть А. Можно возразить, сказав, чта этой проблемгн можно было бы избежать, испытывая альтернативу Аа последней. Однако левая рекурсия может оказаться гораздо более тонкой и включать несколько правил. Например, первым А-правилом могла бы быль А- ЗС. Тогда если 3 — А — первое Я-правило, то мы получим А =Ь ЯС => АВС, и эта картина будет повторяться. Даже если будет найдено подходящее упорядочение правил, на синтаксически неправильных входных цепочках леворекурсивные циклы будут встречаться снова и снова, так как все предыдущие выборы будут безуспешными. Вторая попытка свести иа нет эффект левой рекурсии ьюглз бы состоять в том, чтобы ограничить число вершин проме- А.п СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ жуточного ДеРева в зависимости ат длины входной цепочки.
Если нам дана КС-грамматика 6 =- ()ь), Х, Р, 5), у которой 4р 1х:=: й, и входная цепочка зв длины и, то можно показать, что для м с 1 (6) существует хотя бы одно дерево вывода, в котором длины всех путей не болыпе йп. Таким образом, можно было бы ограничить поиск деревьями, глубина (длина наибольшего пути) которых не превосходит йл. Однако для некоторых грамматик число деревьев глубины (й может слишком быстро расти с ростом Ы. Рассмотрим, например, грамматику 6 с правилами 5 — 55)е. Для нее число деревьев выводов глубины е( задается рекуррентными соотноше- ниями 0(1)=1 (У(е() =Ф(4 — 1Н'+1 Значения функции 0(е() для е( от 1 до б приведены на рис.4,4. 0(~() растет очень быстро, быстрее, чем 2з~ '.
(См. также упр. 4.!.4.) В результате любую грамматику, в которой встречаются два правила такого вида, нельзя разумно проанализи- ровать с помощью описанного варианта алгоритма нисходящего разбора. По этим причинам общепринятый подход состоит в том, чтобы применять нисходящий алгоритм разбора только к грамматикам без левой рекурсии. 41 3. Алгоритм нисходящего разбора Теперь мы готовы описать наш алгоритм нисходящего разбора с возвратами. В алгоритме используются два магазина (П и Аз) и счетчик, в котором хранится текущая позиция входного Указателя.
Чтобы точно описать алгоритм, воспользуемся не~колько стилизованными обозначениями, похожими на те, что ГЛ. 4, ОВЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.1. СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ употреблялись при описании конфигураций МП-преобразователя. Алгоритм 4.1. Нисходящий разбор с возвратами.
Вход. Не леворекурсивиая КС-грамматика 6 = ()А), Х, Р, 5) и входная цепочка ге=а1а, ... а„(п)0). Предполагается, что правила из Р занумерованы числами 1, 2, ..., р. Выход. Один левый разбор цепочки ш, если таковой существует. В противном случае†слово „ошибка". Метод. (1) Для каждого нетерминала А ~Ь( упорядочить его альтернативы. Пусть А,— индекс 1пй альтернативы нетерминала А. Например, если А — а1 (а, ! ... (аг — все А-правила из Р н альтернативы упорядочены так, как записаны, то А; — индекс альтернативы а„А,— индекс альтернативы а, и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
