Карпов - Основы построения трансляторов (2005) (943926), страница 30
Текст из файла (страница 30)
Полностью аналогично строится семантическая процедура у2. Если конструкция Р представлена оператором геад, то семантическая процедура должна сгенерировать команду, помещающую в верхушку стека данное из входного потока. Это делает процедура у3. Отметим, что в том случае, когда конструкция Р определена как выражение Е, взятое в скобки, ничего генерировать не надо: в соответствии со сформулированным правилом необходимый код будет построен при распознавании конструкции Е. Рассмотрим теперь синтаксическую диаграмму для нетерминала Т.
При распознавании первой конструкции Р, как мы знаем, будут сгенерированы команды, при выполнении объектной программы помещающие в верхушку стека первый операнд операции о1гп, при распознавании второй конструкции Р сгенерируются команды, помещающие в верхушку стека второй операнд. Первый операнд этой операции будет находиться в этот момент под вторым операндом. Поэтому после генерации кода для вычисления второго операнда следует сгенерировать команду М1Л или ИЧ в зависимости от индекса лексемы ойп. Это делает процедура у4.
Полностью аналогично объяснение процедуры у5. Семантическая процедура уб генерирует соответствующую команду сравнения двух значений, которые будут помещены в стек после выполнения команд, сгенерированных при распознавании конструкций Е. Генерирование команд при распознавании конструкции 5 — операторов Милана — проще всего для оператора печати. Это просто команда вывода в выходной поток значения, помещенного при вычислении соответствующего выражения в верхушку стека.
Это делает процедура у7. Для оператора присваивания (у8) нужно сгенерировать команду, помещающую вычисленное значение Е из верхушки стека по адресу соответствующей переменной. Глава 5 Построение управления программой для организации цикла ~Ьйе В йо Е од требует специального рассмотрения. На схеме рис. 5.29 показано, что после команд, сгенерированных для вычисления условия В, требуется вставить команду условного перехода, организующую выход из цикла при ложном В, а также после команд, сгенерированных для тела цикла Е, следует вставить команду безусловного возврата на проверку условия В.
Именно это и делают семантические процедуры у9 — у11. Сначала запоминается адрес начала блока команд для вычисления В (адрес М вЂ” это текущее значение счетчика команд при входе в процедуру для распознавания Я), это делает процедура у9. Далее, процедура у10 запоминает адрес У вЂ” место, куда надо вставить команду безусловного возврата. Здесь же увеличением счетчика команд это место резервируется для помещения впоследствии этой команды. Процедура у11 имеет всю необходимую информацию, она и выполняет генерирование нужных команд. Рис.
5.29. Организация цикла при компиляции языка Милан Построение семантических процедур для организации цикла остается читателю в качестве упражнения. Рассмотрим, как будет работать построенный компилятор на программе для вычисления наибольшего общего делителя: Ьесп.п т: = хеас$; и: = хек чЫ.1е т <> и бо з.х п~>л О~еп, гп:= п~-и е1зе г.:= и-т ос1; мха:е (гп) епс1 Нисходящие методы синтаксического анализа 193 Компилятор сгенерирует следующую программу стековой машины (табл.
5.10) по этой программе (заметьтс, что число констант ~хс здесь О). 'Габлина 5.10. Программа стсковой машины Рис. 5.30. Транслирующий автомат для конструкции Я Рассмотрим теперь, как реализовать процсдуры трансляции по синтаксическим диаграммам. Построим по синтаксическим диаграммам рис. 5.25 распознающие автоматы, которые затем преобразуются в так называемые "транслирующие автоматы", у которых кроме символов на переходах определена также и семантика — те семантические процедуры, которые построены на рис. 5.28. Эти семантические действия выполняются при распознавании входной строки одновременно с распознаванием принадлежности ее языку, порождаемому данной грамматикой.
Для конструкции 5 грамматики Милана такой транслирующий автомат приведен на рис. 5.30. Глава 5 Построение транслирующих процедур по графам переходов транслирующих автоматов не представляет никаких трудностей. 5.8. ЩК)-грамматики Ы (1) грамматики — это наиболее общий класс грамматик, позволяющих выполнить нисходящий синтаксический анализ, просматривая входную цепочку слева (первый символ Ь в названии) при восстановлении левого канонического вывода (второй символ Ь в названии) данной терминальной цепочки, заглядывая вперед по входной цепочке на каждом шаге не более чем на 1 символов при принятии решения о том, какой из альтернативных правых частей заменить текущий — самый левый — нетерминал очередной сентенциальной формы.
На практике используются только ЬЬ(1)-грамматики. Рассмотрим построение распознавателя для них. Очевидно, что класс 1 Ь(1)-грамматик включает как автоматные (с детерминированным распознаванием), так и кграмматики, а также грамматики рекурсивного спуска. Для всех этих грамматик альтернативный выбор правил для каждого нетерминала делался на основании ключа — первого терминала, стоящего в начале альтернативы. В более общем случае, когда имеются продукции А-+а~ ~ а2 ~ ... ~ а„, и хотя бы одна из правых частей продукций начинается с нетерминала, следует рассматривать множества НАНЯТ(а,).
Эти множества должны быть непересекающимися. Если при этом среди альтернатив нетерминала А есть пустая цепочка, то каждое из множеств ЯКУТ(и,) должно не пересекаться с множеством Г01 Ь0%(А). В качестве примера рассмотрим грамматику: Й~л. 'Я-+АЬС ~ Ваа А-+СЯ~сВа  — +ас С-+Ь|ИС Пусть дан левый вывод цепочки: 5 =~ АЬС ==> СЯС ==> дСЯС ==> аЬВааЬС == аЬасааЬС =~ сйасааЬЬ Попробуем восстановить его, начиная с корня. Мы имеем начальный нетерминал и терминальную цепочку, т. е. начало и конец вывода: 5 ==> ? сйасааЬЬ. Очевидно, что перед нами стоит старая проблема: дан очередной нетерминал (в частном случае, начальный нетерминал 5) и остаток входной терминальной цепочки.
Можно ли сделать однозначный выбор того, какой из альтернативных правых частей правил грамматики следует заменить этот не- терминал для восстановления вывода этой цепочки? Нисходящие методы синтаксического анализа Для восстановления первого шага вывода в нашем случае надо принять решение. по какому из двух правил, Ь' — +АЬС или 5 — +Ваа, был заменен нетерминал Я.
Глядя на терминальную цепочку сйасиаЬЬ, выбрать один из двух возможных вариантов первого шага вывода, Я ==> АЬС =~ ... или 5 — > Ваа ==> непосредственно нельзя, поскольку правые части обоих правил для Я начинаются с нетерминалов (в з-грамматиках они начинались бы с различных терминалов, и проблема решилась бы тривиально).
Для решения этой проблемы используем функцию НККТ(а) для каждой альтернативы (правой части правил грамматики для нетерминала 5. Пусть А — +и~ ~ ... ~ а~ — все альтернативы нетерминала А. Объединение и, НКБТ(и;) определяет НКЗТ(А). Для нашей грамматики 6;з легче всего определить эту функцию для нетерминала В: НКЯТ(В) = НККТ(ас) = ~а~.
Далее, непосредственно по грамматике б~з видим, что Р1КЯ (С) = (Ь, И~; НКЯТ(А) = ЯКУТ(СЯ~ )Р1Й5Т(сВа) = = (Ь, сУ~~г~с~ = (Ь, с, Ы~. Далее, РИЯТ® = НК5Т(АЬС)~гНК5Т(Ваа) = (а, Ь, с, д~. Выбор первого шага Я == АЬС ==> ... или Я ==> Ваа =~ для нашего вывода 5==> ? =: МасааЬБ очень прост. Поскольку первый терминал входной цепочки д, а деНК5Т(А) и И~НК5Т(В), то первый шаг вывода мог быть только Я ==> АЬС.
Если первый терминал входной цепочки не принадлежит НК5Т(5), то мы с определенностью говорим об ошибке в первом же символе входной строки. Алгоритм синтаксического анализа ЬЦ1)-грамматик работает с магазином, как и алгоритм для я-грамматик. В магазин сначала помещается начальный нетерминал 5. По грамматике строится таблица решений, показывающая, какую цепочку следует записать в магазин вместо его верхнего символа для каждой пары <верхний символ магазина, очередной терминал входной иеиочки>. Для грамматики б5з такая таблица решений приведена на рис. 5.31. Если верхний символ магазина — нетерминал, и в таблице решений для соответствующего терминала входной цепочки — одна из альтернатив этого нетерминала в правилах грамматики„то алгоритм распознавания подставляет в магазин вместо нетерминала эту альтернативу, делая тем самым очередной шаг восстановления вывода.
Возможным результатом может быть также указание об ошибке. Если верхний символ магазина — терминал, то он должен совпадать с очередным терминалом цепочки. Алгоритм распознавания производит их взаимное уничтожение: верхний терминал магазина выталкивается (вместо него записывается пустая цепочка), а анализатор сдвигается по входной цепочке к следующему терминальному символу. Если же эта пара терминалов не совпадает, то это однозначно свидетельствует об ошибке во входной цепочке — она не принадлежит языку, порождаемому грамматикой.
Глава 5 Рис. 5.31. Управляющая таблица МП-автомата для распознавания языка, порождаемого 65з На рис. 5.32 представлена последователыюсть состояний магазина МП-автомата, распознающего цепочку сйасааЬЬ в грамматике С~; з. Рис. 5.32. Последовательность состояний магазина МП-автомата, распознающего входную цепочку бЬасааЬЬ в грамматике 8~ з Начинается распознавание с первого символа а входной цепочки, в магазине находится начальный символ грамматики 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
