Карпов - Основы построения трансляторов (2005) (943926), страница 33
Текст из файла (страница 33)
Это всего 2 пары: ((Я, Ф), (Я, ~)~. Поскольку четыре символа (а, Т, О, ]~ — это все сим- $ >! волы, которыми могут кончаться цепочки, выводимые из Я, то отношение > будет между каждым из этих четырех символов и каждым символом ~4, ~~. Все три бинарные отношения предшествования обычно задаются квадратной матрицей, на пересечении строки (помеченной Х) и столбца (помеченного У) которой стоит знак отношения ~, если Х~У.
Восходящие алгоритмы синтаксического анализа В табл. 6.1 показана квадратная матрица для грамматики 66 . Табл ица 6.1. Квадратная матрица для грамматики 0„ Если не более одного отношения предшествования существует между каждой парой символов грамматики, то такая грамматика называется грамматикой предшествования. Восходящий синтаксический анализ любой цепочки языка, порождаемого грамматикой предшествования, может быть выполнен очень просто. Связкой в любой сентенциальной форме будет самая левая подстрока, между символами которой выполняется отношение 'А', а левая и правая границы выделены отношениями '<" и ">'. Например, для цепочки д~аЬЬ~Ф, выведенной в грамматике С ~ ~, расставим отношения предшествования: Ц<.
~<е а <е Ь < Ь.>1 >Ф Очевидно, что второе вхо>кдение Ь является связкой, и для получения предыдущей сентенциальной формы ее нужно свернуть к нетерминалу. Меиод иредиесивования не ~оворит, к какому наиермгишлу сверпуть выделенную связку, поэтому в грамматике предшествования не должно быть нескольких разных продукций с одинаковыми правыми частями. После свертки Ь к Т, новая сентенциальная форма имеет вид: Ф[аЬТ~Ф, а с расставленными отношениями предшествования ее можно записать так: й< "1<~а<~ЬХ Т.>'1 >М Из расстановки этих отношений видно, что новая связка — это подцепочка ЬТ, которая, в соответствии с продукциями грамматики 062, должна быть далее свернута к Т. Глава б 214 Таблица 6.2.
Синтаксический анализ для цепочки Ф~аЫ~Ф Отношение между символом вверху стека и очередным символом Стек Остаток входной цепочки Выполняемая операция Примечание цепочки Запись очередных символов Ф~аЫ~Ф 3 в стек Вычисление Редукция Т <== Ь: замена 6 в стеке на Т 1<.Ф< ~< а< О< о отношения между символом Ъ' в сте- ке и новым симво- лом '?', а также между новым символом 'Т' и очередным симво- лом цепочки '~' Редукция Т == оТ: замена ЬТ в стеке на Т Вычисление от- Л < Ф< ~< а< ИТ ношения между (а, 7) и (?; ~) Вычисление отношений между Редукция 5 <== а7': замена 1.< Ф< ~< аАТ т- ~< Ф< ~М ду1 Синтаксический анализ на основе отношений предшествования удобно выполнять с помощью стека. Будем считать, что каждая цепочка языка завершается символом 3 конца цепочки. В стек символ за символом записывается исходная цепочка вместе с отношениями предшествования между соседними символами до тех пор, пока отношение между парой соседних символов не станет ">'.
Найденная связка сворачивается к подходящему (единственному) нетерминалу (т. е. выталкивается из верхушки стека, а соответствующий не- терминал вталкивается вместо нее в стек), определяются отношения предшествования между новым нетерминалом и его соседями, и алгоритм продолжает работу до тех пор, пока цепочка Ф А Я А Ф, представляющая начальную продукцию, не окажется в стеке. Ее редукция к У заканчивает анализ. Для цепочки Ф[аЬЬ~Ф этот анализ представлен табл. б.2. Восходящие алгоритмы синтаксического анализа Т а б л и ц а 6. 2 (окончангге) Отношение между символом ~ вверху стека и очередным символом ~ цепочки Стек Остаток входной цепочки Выполняемаи операции Примечание Рггд1)кг/ггя ~ Я: замена в стеке на 5 Вычисление отношения между ЗиФ счисление в стек ~ < Ф='5 отношения между Фи3 Вычисление укггггя ~ Ф5Ф: замена Ф5Ф в стеке на 5' отношения между Ь' и 3 Допустить цепочку Из этого примера видно.
как правый вывод восстанавливается в грамматике предшествования. На рис. 6.3 показано дерево вывода цепочки Ф~аЫ|Ф в грамматике бб и последовательность сентенциальных форм, построенных выше для этой цепочки с помощью алгоритма, основанного на отношениях предшествования. Еще раз подчеркнем, что для применения метода простого предшествования важно, чтобы все правые части правил грамматики были различны. Например„в грамматике бб! '.
Л' — +аАВ~ А — эАЬс каждая продукция имеет уникальную правую часть, и только по правой части продукции можно определить, каким нетерминалом ее заменить на данном шаге восстановления вывода. Если мы чуть-чуть изменим эту грамматику, например добавим правило  — +Аос, то, найдя методом простого предшествования в промежуточной цепочке вывода связку АЬс, мы не будем знать, к какому нетерминалу, А или В, свернуть эту связку. Восходящие алгоритмы синтаксического анализа Грамматики предшествования составляют довольно узкий класс, в частности, грамматика 06 ~ не принадлежит этому классу (цепочки языка, порождаемого 0~1, не могут быть распознаны этим методом). Однако простота и ясность этого метода синтаксического анализа сделали его классическим.
Существуют модификации этого метода, расширяющие класс тех КС-грамматик, для которых этот подход может быть применен. Мы, однако, не будем рассматривать эти модификации. 6.3. ~ЙОц-грамматики 1.К(~)-грамматики — это наиболее широкий подкласс контекстно-свободных грамматик, допускающих эффективный восходящий детерминированный синтаксический анализ. Буква 'Г в названии Ьй(к) говорит о том, что анализируемая цепочка (сентенциальная форма) просматривается слева направо.
Буква 'К' говорит о том, что восстанавливается правый канонический вывод цепочки языка. Символ А указывает количество символов, которые алгоритм просматривает вперед после правой границы связки для принятия однозначного решения об ее обнаружении. 1 К(К)-грамматики были введены Дональдом Кнутом и являются сейчас основным классом грамматик, для которого строятся практические производственные компиляторы.
1.К(1)-распознаватель, считывая сентенциальную форму символ за символом, имеет целью определить самую левую сворачиваемую подстроку-связку (как и в алгоритме предшествования), а также тот нетерминал левой части, которым следует заменить эту связку. В отличие от алгоритма предшествования, 1.К(~)-распознаватель при поиске связки учитывает информацию не только о парах соседних символов, но и информацию обо всей просмотренной слева до связки части входной цепочки. Итак, 1 йф)-распознаватель принимает на вход цепочки (сентенциальные формы) и выдает ответ: какая продукция определяет очередную связку и где эта связка расположена после просмотра ровно 1 символов сентенциальной формы после найденной связки.
Оказывается, что 1.Ц1)-распознаватель можно рассматривать как автомат, переходящий из состояния в состояние при очередном считываемом входном символе промежуточной цепочки вывода. Классов эквивалентных предысторий, характеризующих поведение такого автомата, конечное число. Действительно, с точки зрепия вошожпых сверток, каждую позицию внутри сентенциальной формы в процессе ее просмотра можно описать множеством так называемых ситуаций.
Ситуацией будем называть продукцию с меткой-указателем в ее правой части, показывающей, в каком месте продукции находится анализатор на данном шаге просмотра сентенциальной формы. Такая помеченная продукция (или ситуация) будет записываться <А-+аеД; у>, где точка указывает позицию (точку про- Восходящие алгоритмы синтаксического анализа тываемой сентенциальной форме мы можем встретить. В этой конкретной грамматике все сентенциальные формы начинаются с символа 'Ф', на это указывает и единственный такой символ, стоящий вслед за точкой в единственной ситуации начального ситуационного множества. Поэтому если в анализируемой строке очередной (в данном случае — первый) символ 'Ф', то распознающий автомат перейдет в следующее состояние, определяемое ситуационным множеством, которое включает эту продукцию с продвинутой меткой-указателем позиции анализа: <5' — >ФеЯФ>.
Действительно, мы видели, что среди сентенциальных форм, которые могут обрабатываться анализатором. есть одна такая, в которой после маркера Ф идет символ 5. Но существуют, очевидно„и другие сентенциальные формы, в которых нетерминал 5 уже заменен в соответствии с каким-нибудь правилом грамматики, у которого символ Я стоит в левой части. Поэтому надо принять во внимание, что, возможно, ЬК(0)-анализатор, после того как встретил символ 'Ф' в начале анализируемой цепочки, находится не внутри связки перед Л' для продукции <У вЂ” +ФЬЮ>, а перед началом какой-то — любой — связки, соответствующей продукциям с нетерминалом Я в левой части правил, т.
е. возможно, что подстрока внутри данной сентепггггальной формы еиге не свернута к 5, по мы точно можем сказаигь, что та ггодсгггрока, которая ложепг быть свернута к Я, начинаеигся и.ченно здесь~ Поэтому ситуационное множество ЬК(0)-анализатора этой грамматики в данном состоянии включает и такие две ситуации: <Я вЂ” +еаЛс>, <Я-+еЬ>. Итак, полное ситуационное множество в данном состоянии содержит следующие ситуации: ~<У-+ФЕЯ>, <5 — ~вас>, <К вЂ” +еЬ>~. Следующее состояние 1 К(0)-анализатора зависит от очередного входного символа анализируемой цепочки.
Вспомним, что мы уже прочли первый символ анализируемой цепочки 4. Если эта входная цепочка 'Ф.Ю, то следующим символом будет нетерминал 5, если эта цепочка 'ИФ', то следующим при анализе встретится терминал К во всех остальных случаях правильной входной цепочки (например, Фа5сФ, ФааЬссФ и т. д.) очередным входом будет терминал а. Но именно эти очередные символы и определяются как следующие в этом состоянии после точки-указателя позиции в ситуациях, что видно из ситуационного множества ~<У вЂ” +4еЯ>, 5 — +<вальс>, <Я вЂ” ~еЬ>~. Очевидно, что каждый возможный входной символ изменяет состояние анализатора. Более формально, определим для построения ситуационных множеств ЕК(0)- распознавателя две операции: сlоюиге (М) и до~о (М, Х), где М вЂ” множество ситуаций, Х вЂ” символ грамматики (терминал или нетерминал).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
