А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 64
Текст из файла (страница 64)
На рис. 4.34 показаны действия синтаксического анализатора методом "перенос!свертка'* для входной строки !и * Ы с использованием 1.К(0)- автомата из рис. 4.31. Стек используется для хранения состояний; для ясности в столбце "Символы" приведены символы грамматики, соответствующие состо- 317 4.6, Введение в 1.а-анализ; простой 1,К яниям. В строке (1) в стеке находится стартовое состояние 0 автомата; соответствующий ему символ — маркер дна стека 3. Рис.
4.34. Синтаксический анализ строки Ы * И Очередной входной символ — Ы, а состояние 0 имеет переход по Ы в состояние 5. Таким образом, выбирается перенос. В строке (2) состояние 5 (символ Ы) вносится в стек. Переходов из состояния 5 для входного символа * нет, так что выбирается свертка. Пункт [Š— Ы.] в состоянии 5 указывает, что свертка выполняется с использованием продукции Р— Ы. Что касается символов, то свертка выполняется путем снятия тела продукции со стека (в строке (2) тело продукции — Ы) и размещения в нем заголовка продукции (в данном случае — Г).
В стеке мы снимаем состояние 5 для символа Ы, что приводит к поднятию состояния 0 на вершину стека, и ишем переходы для Г, заголовка использованной для свертки продукции. На рис. 4.31 состояние 0 имеет переход по г в состояние 3, так что в стек помещается состояние 3 с соответствующим символом Г (см. строку (3)). В качестве еше одного примера рассмотрим строку (5) с состоянием 7 (символ *) на вершине стека. Это состояние имеет переход в состояние 5 лля входного символа Ы, так что мы помещаем в стек состояние 5 (символ Ы).
У состояния 5 нет переходов, поэтому выполняется свертка в соответствии с продукцией à — Ы. Когда со стека снимается состояние 5, соответствующее телу продукции Ы, на вершине стека оказывается состояние 7. Поскольку состояние 7 имеет переход по символу Г в состояние 10, мы вносим в стек состояние 10 (символ Е). а 4.6.3 Алгоритм ЕК-анализа Схематически 1.К-анализатор показан на рис. 4.35.
Он состоит из входного буфера, выхода, стека, программы-драйвера и таблицы синтаксического анализа, 318 Глава 4. Синтаксический анализ состоящей из двух частей (лст1О19 и бото). Программа-драйвер одинакова для всех 1.К-анализаторов; от одного анализатора к другому меняются таблицы синтаксического анализа. Программа синтаксического анализа по одному считывает символы из входного буфера. Там, где ПС-анализатор должен перенести символ, 1 К-анализатор переносит состояние. Каждое состояние подытоживает информацию, содержащуюся в стеке ниже него.
Вхо Стек -к Выход Рис. 4.35.Модель 1.К-анализатора Стек хранит последовательность состояний волг ... в„„ где а находится на вершине стека. В случае метода Я.К стек хранит состояния 1.К (0)-автомата; канонический метод (.К и ЬА(.К-метод аналогичны. В соответствии с построением каждое состояние имеет соответствующий грамматический символ. Вспомним, что состояния соответствуют множествам пунктов и что существует переход из состояния т в состояние у, если бото(Ум Х) = 1 .
Все переходы в состояние з должны соответствовать одному и тому же символу грамматики Х. Таким образом, каждое состояние, за исключением стартового состояния О, имеет единственный грамматический символ, связанный с ним.т Структура таблицы Ей-анализа Таблица синтаксического анализа состоит из двух частей: функции действий синтаксического анализа Аст1О19 и функции переходов бото. 1. Функция лст1О19 принимает в качестве аргумента состояние 1 и терминал а (или 3, маркер конца входной строки).
Значение АОТ1О19 [т', а] может быть одного из следующих видов. 'Обратное не обязательно, т.е. один и тот же грамматический символ могут иметь несколько состояний. В качестве примера можно привести состояния 1 и е в ьй (О)-автомате на рис. 4.31, вход в которые осушествляется персхолом по и, или состояния 2 и 9, вход в которые асушествляется переходом по Т. 319 4.б. Введение в ЬК-анализ: простой ЬК а) Перенос 1, где з — состояние. Действие, предпринимаемое синтаксическим анализатором, эффективно переносит входной символ а в стек, но для представления а использует состояние ). б) Свертка А — )3.
Действие синтаксического анализатора состоит в эффективной свертке,9 на вершине стека в заголовок А. в) Принятие. Синтаксический анализатор принимает входную строку и завершает анализ. г) Ошибка. Синтаксический анализатор обнаруживает ошибку во входной строке и предпринимает некоторое корректирующее действие. Более подробно о таких подпрограммах восстановления после ошибки будет говориться в разделах 4.8.3 и 4.9,4. 2. Функция сото, определенная на множествах пунктов, распространяется на состояния: если сото~1;, А~ = 1,, то ното отображает также состояние ) и нетерминал А на состояние з.
Конфигурации ЕК-анализатора Описать поведение ЬК-анализатора можно с помощью обозначений, представляющих полное состояние синтаксического анализатора: его стек и оставшуюся непроанализированной часть входной строки. Колфигуриция ЬК-анализатора представляет собой пару (воз1... з, а,а,Н... а„$) Здесь первый компонент -- содержимое стека (вершина стека справа), а второй компонент — оставшаяся непроанализированной часть входной строки. Эта конфигурация представляет правосентенциальную форму Х1Хз...
Х а,а;~1...а„ по сути, тем же способом, что и ПС-аналнзатор; единственное отличие заключается в том, что вместо символов грамматики в стеке хранятся состояния, нз которых могут быть восстановлены грамматические символы. Иначе говоря, Х, является грамматическим символом, представленным состоянием а,. Заметим, что стартовое состояние синтаксического анализатора яо не представляет символ грамматики, а служит маркером дна стека и играет важную роль в процессе анализа. Поведение ЬК-анализатора Очередной шаг синтаксического анализатора из приведенной выше конфигурации определяется считанным текущим входным символом а, и состоянием на вершине стека я путем обращения к записи Аст[ом)я, а;1 в таблице действий 32О Глава 4.
Синтаксический анализ синтаксического анализа. В результате выполнения указанного в записи действия (одного из четырех возможных типов) получаются следующие конфигурации. 1. Если лст[ом 1а, а,~ = перенос в, синтаксический анализатор выполняет перенос в стек очередного состояния а и его конфигурацией становится (воз~...а а,а,.Н...а„Э) Символ вч хранить в стеке не нужно, поскольку при необходимости (что на практике никогда не требуется) он может быть восстановлен из а.
Текущим входным символом становится а; ~~. 2. Если Астюм 1а,„, а, = свертка А — Д, синтаксический анализатор выполняет свертку и его конфигурацией становится (аоа~... я, „а, а,а,+~... а„8) Здесь г — длина ~3, а а == сото ~в„, „А]. Синтаксический анализатор вначале снимает т символов состояний с вершины стека, что переносит на вершину стека состояние а„, „, после чего на вершину стека помещается а, запись нз сото ~а„.... А~1 При свертке текущий входной символ не изменяется.
В 1.К-анализаторах, которые мы будем строить, последовательность символов грамматики Х„,,~~... Х всегда соответствует 1), правой части продукции свертки. 3. Если лст~ом ~в,в, а,) = принятие, синтаксический анализ завершается. 4. Если лет~он [в, а,) = ошибка, синтаксический анализатор обнаруживает ошибку и вызывает подпрограмму восстановления после ошибки. Алгоритм 1.К-анализа приведен ниже. Все ЕК-анализаторы ведут себя подобным образом„единственное отличие одного ЕК-анализатора ог другого заключается в информации в записях полей АСТ1ОХ и ООТО таблицы синтаксического анализа.
Алгоритм 4.30. Алгоритм 1.К-анализа Вход: входная строка ш и таблица 1.К-анализа с функциями лет!ом и сото для грамматики С. Вьи0д: если ю е Ь (С), шаги сверток восходящего синтаксического анализа ш; в противном случае — указание о происшедшей ошибке. Мвтод: изначально в стеке синтаксического анализатора находится начальное состояние ао, а во входном буфорс — ц$. Затем синтаксический анализатор выполняет программу, приведенную на рис. 4.36.
и 321 4.6. Введение в 1.К-анализ: простой ВК Пусть а — первый символ го5. зтЫ!е(1) ( /е Бесконечный цикл */ Пусть в — состояние на вершине стека. И( лстюм[в,а] = перенос г) ( Внести 1 в стек. Присвоить а очередной входной символ. ) еЬе !Г ( лстюн [в, а] = свертка А - )3 ) ( Снять ])з'] символов со стека. Пусть теперь на вершине стека находится состояние г. Внести в стек сото [г, А].
Вывести продукцию А — )3. ) еЬе !1 ( лстюн[в,а] = принятие ) ( Ьгеа)с; /* Синтаксический анализ завершен *! ) еЬе Вызов подпрограммы восстановления после ошибки. Рис. 4.36. Программа БК-анализа (1) Š— Е+ Т (2) Š— Т (3) Т- ТеГ (4) Т вЂ” Е (5) à — (Е) (6) Š— Ы Коды действий следующие. 1. в! означает перенос и размещение в стеке состояния !. 2. гз' означает свертку в соответствии с продукцией с номером 7'.
3. асс означает принятие. 4. Пустое поле означает ошибку. Заметим, что значение Пото [в, а] для терминала а находится в поле АСт1ОМ, связанном с переносом для входного символа а и состояния в. Поле гютО дает значения ВОтО [в, а] для нетерминалов А. Кроме того, следует иметь в виду, что мы пока что не пояснили, каким образом выбираются записи на рис. 4.37 (об этом поговорим немного позже). Для входной строки Ы * Ы+ Ы последовательность содержимого стека и входной строки показана на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
