В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 20
Текст из файла (страница 20)
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 , $].Центральная идея метода заключается в том, что по грамматике строитсядетерминированный конечный автомат, распознающий активные префиксы.Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечногоавтомата из недетерминированного.Анализатор, работающий слева-направо по типу сдвиг-свертка, долженуметь распознавать основы на верхушке магазина. Состояние автомата послепрочтения содержимого магазина и текущий входной символ определяюточередное действие автомата.
Функцией переходов этого конечного автомата является функция переходов LR-анализатора. Чтобы не просматриватьмагазин на каждом шаге анализа, на верхушке магазина всегда хранитсято состояние, в котором должен оказаться этот конечный автомат после того,как он прочитал символы грамматики в магазине от дна к верхушке.Рассмотрим ситуацию вида [A → α.Bβ , a] из множества ситуаций, допустимых для некоторого активного префикса δ . Тогда существует правосторонний вывод S$ ⇒ ∗r γAax ⇒ r γαBβax, где δ = γα, а это значит, что ситуация[A → αB.β , a] допустима для δB , B ∈ N ∪ T . Если B ∈ N и B → ξ ∈ R,то S$ ⇒ ∗r γαBβax ⇒ ∗r δBbw ⇒ r δξbw.
Таким образом, [B → .ξ , b] также допустима для δ . Здесь b может быть первым терминалом, выводимым из β ,либо из β выводится e в выводе βax ⇒ ∗r bw и тогда b равно a. Значит, либоb ∈ F IRST (βax), либо β ⇒ ∗r e и a = $.Рассмотрим теперь недерминированный конечный автомат, состояниямикоторого являются LR(1)-ситуации, а переходы определены в соответствиисо сказанным выше: если автомат находится в состоянии [A → α.Bβ , a],то определен переход в состояние [A → αB.β , a] по символу B .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
