В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 20
Текст из файла (страница 20)
Так, если S ⇒ ∗r αAβ ⇒ r αγβ , то A → γ в позиции,следующей за α, — это основа цепочки αγβ . Подцепочка β справа от основысодержит только терминальные символы.Вообще говоря, грамматика может быть неоднозначной, поэтому правосторонний вывод αγβ и основа могут не быть единственными. Если грамматикаоднозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминаллевой части называется отсечением основы.
Обращение правостороннеговывода может быть получено с помощью повторного применения отсеченияосновы, начиная с исходной цепочки w. Если w — слово в рассматриваемойграмматике, то w = αn , где αn — n-я правая сентенциальная форма ещенеизвестного правого вывода S = α0 ⇒ r α1 ⇒ r . . . ⇒ r αn−1 ⇒ r αn = w.Чтобы восстановить этот вывод в обратном порядке, выделяем основу γnв αn и заменяем γn на левую часть некоторого правила вывода An → γn ,получая (n − 1)-ю правую сентенциальную форму αn−1 .
Затем повторяемэтот процесс, т. е. выделяем основу γn−1 в αn−1 и сворачиваем эту основу,получая правую сентенциальную форму αn−2 . Если, повторяя этот процесс,мы получаем правую сентенциальную форму, состоящую только из начального символа S , то останавливаемся и сообщаем об успешном завершении4.5. Разбор снизу-вверх типа сдвиг-свертка95разбора. Обращение последовательности правил, использованных в свертках,есть правый вывод входной строки.Таким образом, главная задача анализатора типа сдвиг-свертка — этовыделение и отсечение основы.4.5.2.
LR(1)-анализаторы. В названии LR(1) символ L указывает на то,что входная цепочка читается слева-направо; R — на то, что строится правыйвывод; наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.LR(1)-анализ привлекателен по нескольким причинам:– LR(1)-анализ — наиболее мощный метод анализа без возвратов типасдвиг-свертка;– LR(1)-анализ может быть реализован довольно эффективно;– LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;– класс грамматик, которые могут быть проанализированы LR(1)-методом,строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверху-вниз типа LL(1)).Схематически структура LR(1)-анализатора изображена на рис.
4.6. Анализатор состоит из входной ленты, выходной ленты, магазина, управляющейпрограммы и таблицы анализа (LR(1)-таблицы), которая имеет две части —функцию действий (Action) и функцию переходов (Goto). Управляющаяпрограмма одна и та же для всех LR(1)-анализаторов, разные анализаторыотличаются друг от друга только таблицами анализа.-Рис.
4.6Анализатор читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки видаI0 X1 I1 X2 I2 . . . Xm Im (Im — верхушка магазина). Каждый Xi — символ грамматики (терминальный или нетерминальный), а Ii — символ состояния.96Глава 4. Синтаксический анализЭлемент функции действий Action[Im , ai ] для символа состояния Im и входа ai ∈ T ∪ {$}, может иметь одно из четырех значений:1)2)3)4)shift I (сдвиг), где I — символ состояния;reduce A→γ (свертка по правилу грамматики A→γ );accept (допуск);error (ошибка).Элемент функции переходов Goto[Im , A] для символа состояния Im и входа A ∈ N может иметь одно из двух значений:1) I , где I — символ состояния;2) error (ошибка).Конфигурацией LR(1)-анализатора называется пара, первая компонентакоторой — содержимое магазина, а вторая — непросмотренный вход:(I0 X1 I1 X2 I2 .
. . Xm Im , ai ai+1 . . . an $).Эта конфигурация соответствует правой сентенциальной формеX1 X2 . . . Xm ai ai+1 . . . an .Если S ⇒ ∗r γAw ⇒ r γβw, то любой префикс δ цепочки γβ называетсяактивным префиксом. Основа сентенциальной формы всегда располагаетсяна верхушке магазина. Таким образом, активный префикс — это такой префикс правой сентенциальной формы, который не переходит правую границуосновы этой формы.Когда анализатор начинает работу, в магазине находится только символначального состояния I0 , на входной ленте — анализируемая цепочка с маркером конца.Каждый очередной шаг анализатора определяется текущим входным символом ai и символом состояния на верхушке магазина Im нижеследующимобразом.Пусть LR(1)-анализатор находится в конфигурации(I0 X1 I1 X2 I2 .
. . Xm Im , ai ai+1 . . . an $).Анализатор может проделать один из следующих шагов.1. Если Action[Im , ai ] = shift I , то анализатор выполняет сдвиг, переходяв конфигурацию(I0 X1 I1 X2 I2 . . . Xm Im ai I , ai+1 . . . an $).Таким образом, в магазин помещаются входной символ ai и символсостояния I , определяемый Action[Im , ai ]. Текущим входным символомстановится ai+1 .974.5.
Разбор снизу-вверх типа сдвиг-свертка2. Если Action[Im , ai ] = reduce A → γ , то анализатор выполняет свертку,переходя в конфигурацию(I0 X1 I1 X2 I2 . . . Xm−r Im−r AI , ai ai+1 . . . an $),где I = Goto[Im−r , A] и r — длина γ , правой части правила вывода.Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Im−r . Затем анализатор помещает в магазин A — левую часть правила вывода, и I — символ состояния, определяемыйGoto[Im−r , A].
На шаге свертки текущий входной символ не меняется. Для LR(1)-анализаторов последовательность символов грамматикиXm−r+1 . . . Xm , удаляемых из магазина, всегда соответствует γ — правойчасти правила вывода, по которому делается свертка.После осуществления шага свертки генерируется выход LR(1)-анализатора, т. е. исполняются семантические действия, связанные с правилом,по которому делается свертка, например, печатаются номера таких правил.Заметим, что функция Goto таблицы анализа, построенная по грамматике G, фактически представляет собой функцию переходов детерминированного конечного автомата, распознающего активные префиксы G.3. Если Action[Im , ai ] = accept, то разбор успешно завершен.4.
Если Action[Im , ai ] = error, то анализатор обнаружил ошибку, и выполняются действия по диагностике и восстановлению.Пример 4.12. Рассмотрим грамматику= ({E , T , F }, {id, +, ∗}, P , E) с правилами:1) E → E + T ;2) E → T ;3) T → T ∗ F ;4) T → F ;5) F → id.4 В.А. СеребряковарифметическихвыраженийG =98Глава 4.
Синтаксический анализВ табл. 4.3 представлены функции Action и Goto, образующие LR(1)-таблицудля этой грамматики. Элемент Si функции Action означает сдвиг и помещениев магазин состояния с номером i, Rj — свертку по правилу номер j , acc — допуск,пустая клетка — ошибку. Для функции Goto символ i означает помещение в магазинсостояния с номером i, пустая клетка — ошибку.Т а б л и ц а 4.3СостоянияActionid0+*Goto$1 2 3S61S42R2 S7 R23R4 R4 R44acc5 3S65R1 S7 R16R5 R5 R578E T F8S6R3 R3 R3В табл.
4.4 описана последовательность состояний магазина и входной лентына входе id + id ∗ id. Например, в первой строке LR-анализатор находится в нулевомсостоянии и «видит» первый входной символ id. Действие S6 в нулевой строкеи столбце id в поле Action (табл. 4.3) означает сдвиг и помещение символа состояния6 на верхушку магазина. Это и изображено во второй строке: первый символ idи символ состояния 6 помещаются в магазин, а id удаляется со входной ленты.Текущим входным символом становится +, а действием на вход + в состоянии 6является свертка по F → id.
Из магазина удаляются два символа (один символ состояния и один символ грамматики). Затем анализируется нулевое состояние. ПосколькуGoto в нулевом состоянии по символу F — это 3, F и 3 помещаются в магазин.Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шагиопределяются аналогично.Заметим, что в магазине не обязательно должны размещаться одновременно и символы грамматики, и символы состояний.
Возможно размещениетолько символов состояний или только символов грамматики. В этом случаетекущее состояние может быть определено путем последовательного чтениясимволов грамматики в магазине ото дна к вершине конечным автоматом,строящимся в следующем подразделе. Одновременное использование и символов грамматики, и символов состояний облегчает понимание поведенияLR-анализатора.4.5. Разбор снизу-вверх типа сдвиг-свертка99Т а б л и ц а 4.4АктивныйпрефиксМагазин0Вход Действиеid + id ∗ id$ сдвигid0 id 6+id ∗ id$ F → idF0F 3+id ∗ id$ T → FT0T 2+id ∗ id$ E → TE0E1+id ∗ id$ сдвигE+0E 1+4E + id0 E 1 + 4 id 6∗id$ F → idE+F0E 1+4F 3∗id$ T → FE+T0E 1+4T 5id$ сдвигE + T∗0E 1+4T 5∗7id$ сдвигE + T ∗ id0 E 1 + 4 T 5 ∗ 7 id 6$ F → idE+T ∗F0E 1+4T 5∗7F 8$ T →T ∗FE+T0E 1+4T 5$ E →E+TE0E1id ∗ id$ сдвигдопуск4.5.3.
Конструирование LR(1)-таблицы. Рассмотрим алгоритм конструирования таблицы, управляющей LR(1)-анализатором.Пусть G = (N , T , P , S) — КС-грамматика. Пополненной грамматикой дляданной грамматики G называется КС-грамматикаG′ = (N ∪ {S ′ }, T , P ∪ {S ′ → S}, S ′ ),т. е. эквивалентная грамматика, в которой введены новый начальный символS ′ и новое правило вывода S ′ → S .Это дополнительное правило вводится для того, чтобы определить, когдаанализатор должен остановить разбор и зафиксировать допуск входа. Такимобразом, допуск имеет место тогда и только тогда, когда анализатор готовосуществить свертку по правилу S ′ → S .LR(1)-ситуацией называется пара [A → α.β , a], где A → αβ — правилограмматики, a — терминал или правый концевой маркер $. Вторая компонентаситуации называется аванцепочкой.Будем говорить, что LR(1)-ситуация [A → α.β , a] допустима для активного префикса δ , если существует вывод S ⇒ ∗r γAw ⇒ r γαβw, где δ = γαи либо a — первый символ w, либо w = e и a = $.Будем говорить, что ситуация допустима, если она допустима для какоголибо активного префикса.4*100Глава 4.
Синтаксический анализПример 4.13. Дана грамматика G = ({S , B}, {a, b}, P , S) с правилами:S → BB ;B → aB | b.Существует правосторонний вывод S ⇒ ∗r aaBab ⇒ r aaaBab. Легко видеть, чтоситуация [B → a.B , a] допустима для активного префикса δ = aaa, если в определении выше положить γ = aa, A = B , w = ab, α = a, β = B . Существует такжеправосторонний вывод S ⇒ ∗r BaB ⇒ r BaaB . Поэтому для активного префикса Baaдопустима ситуация [B → a.B , $].Центральная идея метода заключается в том, что по грамматике строитсядетерминированный конечный автомат, распознающий активные префиксы.Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечногоавтомата из недетерминированного.Анализатор, работающий слева-направо по типу сдвиг-свертка, долженуметь распознавать основы на верхушке магазина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
