Карпов - Основы построения трансляторов (2005), страница 36

То, что 1 К(0)-грамматики являются собственным подмножеством Я й.(1)- грамматик, а множество Я.К(1)-грамматик является собственным подмножеством 1.А1 К(1)-грамматик, показано примерами построения распознавателей для грамматик б~з, 664 и 665. Покажем, что существуют 1.К(1)-грамматики, не являющиеся 1.А1.К(1)-грамматиками. Построим одну из самых простых таких грамматик.

Для того чтобы грамматика была 1 К(1), но не была бы грамматикой 1 А1.К(1), достаточно, чтобы существовали два одинаковых ситуационных множества с конфликтами типа редукггия/редукция, но с разными контекстами для разрешения этих конфликтов. Пусть соответствующие состояния 1.К(1)-распознавателя следующие (рис. 6.8). Рис. 6.8. Состояния Щ1)-распознавателя Построим теперь другие состояния 1.К(1)-распознавателя (рис.

б.9). Таким образом, искомая грамматика может иметь следующий вид: б6.7. Л'-+аАа ~ аВЬ | ЬАЬ ~ ЬВа А — и  — и' Очевидно, что это 1 К(1)-грамматика, поскольку в состояниях 03 и о4 конфликты типа редукция/редукция однозначно разрешаются с помощью контек- Глава б 234 Рис. 6.9. Другие состояния ~й(1)-распознавателя Рис.

6.10. Построение ЬЧ й(1)-распознавателя ста длиной 1. Однако это не 1 А1.К(1)-грамматика, поскольку при построении ЕЛОК(1)-распознавателя состояния ~~3 и 04 будут совмещены в одно состоя- ние с объединением контекста у ситуаций (рис. 6.10). Восходящие алгоритмы синтаксического анализа 235 При попадании управления в это объединенное состояние распознавателя разрешить конфликт с помощью контекста длиной 1 невозможно. Отметим, что язык, порождаемый грамматикой б~,7, конечный, он содержит всего четыре цепочки 167 = ~а~а, ай, Ага, Ьгб~. Этот язык порождается и другими грамматиками, в частности простейшей КС-грамматикой Я вЂ” +а~а ~ ай ~ Ь|а ~ Ь~Ь и даже автоматной грамматикой, и проблема синтаксического анализа для них решается элементарно.

Таким образом, мы еще раз убеждаемся, что при построении транслятора мы можем задать язык разными грамматиками, и выбор неподходящей грамматики может привести к существенным проблемам на этапе синтаксического анализа нашего транслятора. 6.6. Синтаксический анализ ~Й(К)-языков Рассмотрим, как строятся (Я, 1 А~ЬК.-анализаторы на практике.

Для грамма- тики Стб.4' 66.4' О. У +Ф М 1. Я-+аЛс повторим граф переходов распознающего Я К(1)-автомата (см. рис. 6.11) и рассмотрим его функционирование при распознавании цепочки ФааасссФ. Распознающий автомат переводится префиксом хааа входной цепочки в состояние оЗ, в котором по очередному входному символу с требуется выполнить редукцию Л' ~ е, т. е.

до символа с нужно вставить символ 5 вместо пустой цепочки с получением предыдущей сентенциальной формы ФаааЛсссФ. Однако это можно сделать только заглянув на один шаг вперед, т. е. проверив, является ли следующий символ одним из символов ~с, Ф~. Таким образом, состояние уЗ не является "заключительным" с точки зрения теории конечных автоматов. В этом состоянии выполняются два разных типа действий в зависимости от того, какой символ будет следующим в обрабатываемой строке. Если это очередной символ Я, то анализатор читает его и переходит в следующее состояние 05, если очередной символ — Ф или с. то анализатор, НЕ ЧИТАЯ СЛЕДУЮЩИЙ СИМВОЛ, производит редукцию в соответствии с продукцией 5-+е.

Для однообразия удобно и все другие состояния, в которых нет конфликтов при определении редукции, тоже представлять не заключительными, а "промежуточными", считая, что редукция производится после анализа следующего за связкой символа. Так, например, редукцию О после того, как мы оказались в состоянии о4, можно выполнить, если следующий символ — это ограничивающий входную цепочку символ %. Глава б Рис. 6.11. Распознающий ~й-автомат для грамматики 8~4 Пусть выполнен первый шаг распознавания этим анализатором входной цепочки ФааасссФ. Следующий шаг распознавания — подача на вход автомата построенной на предыдущем шаге сентенциальной формы ФаааЛсссФ.

Префикс ФаааЛс этой цепочки приводит к состоянию дб„в котором очередной символ с входной строки требует редукции Я:== а5с, т. е. хвост а5с этого префикса должен быть заменен символом Я. Итак, на этом втором шаге цепочка Фиаа5сссФ будет свернута к сентенциальной форме ФааЯссФ. Очевидно, что построенный 1 К.-автомат (рис. б.11) по любой сентенциальной форме на каждом шаге строит предыдущую сентенциальную форму канонического правого вывода.

Поскольку задачей синтаксического анализа является восстановление всего правого вывода, эту операцию нужно повторять многократно до тех пор, пока последняя редукция не будет выполнена, и входная цепочка языка не свернется к начальному нетерминалу. Конечно, бессмысленно повторять для очередной сентенциальной формы весь тот путь из начального состояния, который распознающим автоматом был проделан до границы свернутой связки в предыдущей сентенциальной форме: последовательность пройденных состояний будет повторяться. Разумно этот путь запомнить в стеке подобно тому, как для грамматик предшествования в стеке сохраняется начальный префикс сентенциальной формы со вставленными между символами отношениями предшествования.

Пройден- Глава б Таблица 6.3 (окончание) Стек Действия, выполняемые в этом состоянии распознавателем ~ цЫц,а~;ацЯ, „Фд~5д. -~-суоаЧ! 592 6с/4 Редукция О. Ь" с== ~5'Й: цепочка принята Из этого примера видно, как правый вывод восстанавливается в 1.К-грам- матике этим анализатором. Традиционно в алгоритмах синтаксического анализа для 1.К-грамматик авто- мат-распознаватель представляется в виде таблицы переходов и выходов в следующей форме (табл. б.4). Таблица 6.4.

Таблица переходов и выходов Таблица состоит из строк, помеченных состояниями автомата, и столбцов, помеченных терминалами (включая символ конца строки 3) и нетерминалами грамматики. Таблица заполняется следующим образом: Г3 Если ситуационное множество, соответствующее состоянию д, включает ситуацию <А — +ива~3>, где а — терминальный символ, и в распознающем автомате из д под воздействием а есть переход в г, то определить Дейс~лвие ~д, а~ = "сдви". ~.", Очередной символ входной цепочки Остаток входной цепочки Переход из состояния о5 в состояние об после чтения с; запись шага в стек Переход из состояния 02 в состояние о4 под воздействием 4; запись шага в стек Глава 6 240 Унравляющая программа ЕК-анализатора выглядит следующим образом: // // // Пусть асГ сп(,1 — управляющая таблица анализатора; 77ереход [с(,Х) — состояние, в которое переходит анализатор из состояния я при чтении символа Х; // Установить указатель 1р на первый символ входной цепочки, // в стек поместить начальное состояние анализатора; ыЬ~1е (цепочка не закончилась) // Пусть с.," — состояние на вершине стека, /./ а — символ входной цепочки, на который указывает з.р з.й' (ас':акоп (с".„а1 =-= .~п~~~ ц') // Переход из состояния ~( в состояние с(' при чтении а; рцв)~ (а); // рцвп (с~' ); // 1.р+ +; // Втолкнуть в стек очередной символ входной цепочки; в стек состояние 77ереход (с1,а) следующему символу входной цепочки Втолкнуть Перейти к (с~, а) тезисе ): Л с== )З) // Обнаружена связка Л "= )З е1ве Ы ! ас( 1оп Жеп Гот (1=-1; 1<=-~ ~ ~, 1++) // Для всех символов связки выполнить сто рср (); // Вытолкнуть очередной символ связки; рор (); // Вытолкнуть соответствующее состояние; // Пусть о' — состояние на вершине стека после выталкивания связки; р Бь (л)р // Втолкнуть в стек левую часть обнаруженной связки; рцзЬ (77"реход (а', Л1); // Втолкнуть в стек состояние, в которое // переходит анализатор из состояния о' при чтении символа А Вывод правила (Л-.Р); е18е ~ Г (ас 1сп (а, а) == эссер~) Жел хе~итп Бцссевв; е1зе Е11ог(); // Если в таблице клетка не заполнена, то обнаружена // ошибка во входной строке Все незаполненные клетки таблицы соответствуют синтаксическим ошиб- кам.

Восходящие алгоритмы синтаксического анализа 6.7. Семантические вычисления при восходящем распознавании. ~-атрибутная семантика При восходящем синтаксическом анализе ~например, для грамматик предшествования или 1 К-грамматик) семантические атрибуты могут находиться в стеке разбора вместе с символами грамматики и состояниями. Когда применяется правило свертки связки к подходящему нетерминалу, семантические атрибуты иногда могут вычисляться одновременно с выполнением свертки, тем самым позволяя избежать необходимости хранения синтаксического дерева или его части для последующего семантического анализа. Например, рассмотрим грамматику, порождающую описания переменных вида г, г, г: геа! или г, г, ю, ю: т1ецег. О.

 — и'Л 1. Л вЂ” ~, ю'Е 2. Е-+: Т 3. Т вЂ” н~г1едег 4. Т-и"его Атрибутная грамматика этого языка представлена в табл. 6.6. Табл ица б.б. Атрибутная грамматика 068 Аннотированное дерево вывода цепочки г, г, г: иИеуег в грамматике 66~ рас- смотрена на рис. 6.12. На дереве рис. 6.12 ясно видно, что каждый раз при свертке очередной связки к нетерминалу в случае синтезированных атрибутов семантические вычисления могут выполниться на том же шаге без проблем: все ссмал~лические апг- Глава б рибупгы получают свои значения до того, как они используюпгся для вычисления других атрибутов при выполнении каждого шага свертки.

Это означает, что этап генерации (вычисление семантических атрибутов) выполняется одновременно с этапом синтаксического анализа. Рис. 6.12. Аннотированное дерево вывода с синтезированныыи сеыантическими атрибутами Очевидно, что это утверждение всегда верно в случае синтезированных атрибутов при восходящем синтаксическом анализе.

В то же время, наличие унаследованных атрибутов может вызвать проблемы при выполнении семантических вычислений одновременно с синтаксическим анализом. Действительно, рассмотрим другую грамматику того же языка, порождающего описания переменных вида г, г, г: ген или с, г, г, г: айеуег: О. Х)-+Л: Т 1. г-~;г 2. Х,— и 3. Т вЂ” ни~еуег 4. Т вЂ” +ген Атрибутная грамматика этого языка включает унаследованные атрибуты, т. е. атрибуты символов правой части продукции, определяемые по значениям атрибутов других символов, входящих в продукцию (табл. б.7). Построим аннотированное дерево вывода той же цепочки г, с, г: ю~еуег в этой грамматике (рис.