Карпов - Основы построения трансляторов (2005) (943926), страница 27
Текст из файла (страница 27)
На втором шаге 5 ==> асЯЬА ==>? ==> асЬааабЬааа мы имеем подобную же ситуацию: определить по сентенциальной форме У 76 Глава 5 асЯА, какое правило было использовано для подстановки вместо Я, чтобы получилась цепочка асоаааЬЬааа. Отбрасывая совпадающие терминальные префиксы ас, мы приходим к той же проблеме: как по очередному нетерминалу Я и первому терминальному символу Ь остатка входной цепочки оаааЫааа определить правило, использованное при выводе. Для нашей грамматики это может быть только правило Я вЂ” ~БАЙ„и, таким образом, мы можем продолжить вывод — Я =~ ас5ЬА ==> асоАЬЬА ==>? =э асоаааЬЬааа.
Очевидно, что нисходящие алгоритмы восстанавливают канонический левый вывод цепочек языка. Рис. 6.18. Управляющая таблица МП-автомата для распознавания языка У 652 Легко построить общий алгоритм нисходящего синтаксического анализа для з-грамматик. Он реализуется МП-автоматом с одним состоянием. Алфавит магазина этого МП-автомата включает все терминальные и нетерминальные символы грамматики. Вначале в магазин помещается начальный символ грамматики.
В процессе работы очередной терминал входной цепочки и верхний символ магазина определяют, какая цепочка должна быть помещена в магазин, Если верхний символ магазина — нетерминал, то очередной входной терминал — это ключ, определяющий правую часть правила грамматики, которой должен быть заменен нетерминал в восстанавливаемом выводе. Если верхний символ магазина — терминал, он должен совпадать с очередным терминалом входной цепочки. При таком совпадении терминал выбрасывается из магазина (вместо него в верхушку магазина записывается пустая цепочка).
Затем выполняется сдвиг по входной цепочке — анализатор переходит к следующему терминалу входной цепочки. Цепочка распознана, если по исчерпании цепочки магазин пуст. Несовпадение терминала в верхушке магазина с очередным терминалом входной цепочки свидетельствует об ошибке во входной строке. Ошибка также обнаруживается, если для нетерминала, находящегося в верхушке магазина, очередной входной терминал не совпадает ни с одним ключом правил Нисходящие методы синтаксического анализа грамматики для этого нетерминала. Решающая таблица, показывающая для грамматики 05, какую цепочку следует записать в стек на каждом шаге анализа входной цепочки при каждой паре <верхний символ магазина, очередной терминал входной цепочки>, представлена на рис.
5.18, Заметим, что в этой таблице правая часть продукции, которую нужно поместить в стек, записана без своего первого символа-ключа, поскольку он уже распознан. Восстановление вывода 5 ==> асЯ~А ==> асбАЬЬА ==> асбис~ВЬЬА ==> с~сбоаиббА =: асбаааббааВ:==> асбаааббааа с помощью этой решающей таблицы, показано на рис. 5.19. Рис. 5.19.
Последовательность состояний магазина МП-автомата, распознающего входную цепочку асЬаааЬЬааа Как и всякая КС-грамматика, грамматика 652 может быть представлена набором синтаксических диаграмм. Такое представление показано на рис. 5.20. Рис. 5.20. Представление в-грамматики 852 набором синтаксических диаграмм 5.5.1. Синтаксические диаграммы 8-грамматик как скелеты распознающих алгоритмов Синтаксические диаграммы — это удобная графическая форма представления правил порождения КС-языка. Синтаксическая диаграмма для каждого Нисходящие методы синтаксического анализа ления пути, ио коигорому ироходрло порождение входной цеиочкг~. Для того чтобы синтаксические диаграммы, являющиеся моделью порождения цепочек языка, могли служить моделью распознавания структуры цепочки, необходимо и достаточно, чтобы в каждом разветвлении синтаксической диаграммы путь по диаграмме выбирался по входной цепочке однозначно на основе входной цепочки.
Грамматикой рекурсивного спуска является всякая грамматика, для которой возможно эквивалентное преобразование синтаксических диаграмм к виду, допускающему однозначное нисходящее распознавание на основе анализа одного очередного символа входной цепочки. Однозначный выбор пути возможен, например, если все альтернативы каждого нетерминала в правилах КС-грамматики начинаются с различных терминалов (ключей), т. е, в ьграмматиках. У таких грамматик синтаксическая диаграмма каждого нетерминала содержит несколько ветвей, начинающихся различными терминалами, Таким образом, я-грамматики составляют подкласс грамматик рекурсивного спуска. Сформулируем правила построения транслятора рекурсивного спуска для грамматики 6, определенной набором продукций.
Для каждой группы продукций А-+а~ ~ а~ ... !а„грамматики 6 множества !.!КоТ(а,) для всех ! должны не пересекаться. Функция НЮТ(а,) (с,:и. главу 4~ определяет„с каких терминальных символов могут начинаться цепочки, выводимые из нетерминала А в случае, если А на первом шаге вывода будет заменена по правилу А — +а,. В некоторых случаях, даже когда это условие не выполняется. грамматику можно изменить так, чтобы метод рекурсивного спуска можно было использоватьь.
Рассмотрим. как реализовать распознаватель для грамматики по методу ре- курсивного спуска. 1. Для каждого нетерминального символа грамматики б строится своя процедура — программный модуль, задачей которого является распознавание (выделение) во входной строке подцепочки, выводимой из этого нетерминала. Очевидно. что процедура, построенная для начального символа грамматики 6, должна распознать всю входную цепочку, поэтому именно она запускается сначала. 2. Каждая распознающая процедура. построенная для конкретного нетерминала, сканирует текущий входной терминальный символ. Пусть это не- терминал А и входной терминальный символ 'а'.
Пусть нетерминал А стоит в левой части таких продукиий грамматики: А — +а~ ~ а~ ~ ... ~ а„. Если 'а' принадлежит только одному из множеств НАНЯТ(а,), то для дальнейшего анализа выбирается продукция А — >а,. Если 'а' не принадлежит ни одному из множеств НКЯТ(а,), а среди продукций есть продукция А — >с, то работа 180 Глава 5 процедуры распознавания для А завершается. Если среди продукций для А нет продукции А — +е, то распознающая процедура информирует об ошибке. 3.
Для каждой продукции А-+а; в распознающей процедуре строится своя последовательность операций для тех символов, из которых состоит цепочка а,. Пусть а; = Х~Х ..Х~. Рассмотрим операцию для Х.. Если символ Х. нетерминал, то операция состоит в вызове распознающей процедуры для Х„. Если символ Х,— терминал, совпадающий с очередным символом входной цепочки 'а', то из входного потока читается следующий входной символ, и управление передается операции для Х.,1. При несовпадении терминала Х.
с символом 'а' вызывается процедура обработки ошибок. Правила построения транслятора рекурсивного спуска для грамматики, опре- деленной набором синтаксических диаграмм, полностью аналогичны этим правилам. П-+Ьефп Л епд Т;+Ь' ~ Яяет Е Ь'-эЫ пав Е~иЬ11еВ ЙоЕ ой ~ ЫВ $Ьеп Е й ~ ГВ $Ьеп У. еЬе Е 6 ~ иг1Ге!Ь ЕгЬ В-+Е ген Е Е- Еог.Т ~ Т Т вЂ” То1тР ! Р Р-+Ы ~ сопай ~ !Ь Е гЬ ! геай Построим синтаксические диаграммы для каждого нетерминала грамматики. Начальный нетерминал имеет всего одно правило: П вЂ” +Ьерп Е епд Построенная по этому правилу синтаксическая диаграмма не имеет разветв- лений и, следовательно, удовлетворяет требованию однозначности выбора пути: П: — Оед~п — ~ — епд — + Соответствующая распознающая процедура по заданной входной цепочке терминалов — программе на Милане — — проверяет, будет ли первый терминал этой программы служебным словом Ьерп, идет ли после этого терминала Метод рекурсивного спуска может быть применен для синтаксического анализа и компиляции достаточно мощных языков, таких, например, как Паскаль и Модула-2.
Покажем, как распознающие и транслирующие процедуры для трансляции методом рекурсивного спуска строятся для языка Милан. Снова запишем грамматику этого языка: Нисходящие методы синтаксического анализа такая теминальная цепочка, которую можно породить из нетерминала Х, после чего проверяет, будет ли последним терминалом программы служебное слово епо'. Для проверки того, является ли некоторая цепочка терминалов цепочкой, которую можно породить из нетерминала А, эта процедура просто обращается к аналогичной распознающей процедуре, построенной для 1.'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
