Мартыненко Б.К. Языки и трансляции

Подождите немного. Документ загружается.

150

Рассмотрим два левосторонних вывода, в которых роль нетерминала

A игра-

ет символ

Имеем

(1) S aBS aaS и (2) S aBS abSBS . Тогда w = a, α = S , β = a,

γ = bSB. Ясно, что любая цепочка x, выводимая из βα = aS , начинается на a, а

цепочка

y, выводимая из γα = bSBS, начинается на b. Поэтому если первый сим-

вол цепочки, следующей за закрытой частью сентенциальной формы (

w = a),

есть

a, то для замены нетерминала B следует использовать первую альтернати-

ву. Если она начинается на

b, то вторую.

В обоих случаях

LL(1)-условие выполнено: по первому символу цепочки,

следующей за закрытой частью сентенциальной формы, однозначно определя-

ется то правило, которое следует применить к соответствующему нетерминалу,

чтобы в конце концов получить анализируемую цепочку. Очевидно, что любые

два левосторонних вывода в данной грамматике, подпадающие под вышеприве-

денный образец, удовлетворяют

LL(k)-условию.

Данная грамматика служит примером

простой LL(1)-грамматики.

Определение 2.5. Говорят, что контекстно-свободная грамматика G является

простой LL(1)-грамматикой, если в ней нет ε-правил, и все альтернативы для

каждого нетерминала начинаются с терминалов и притом различных.

Таким образом, в простой

LL(1)-грамматике для данной пары (A, a), где

A ∈V

и a ∈V

, существует самое большее — одна альтернатива вида A →aα.

§ 2.2. Свойства LL(k)-грамматик

Теорема 2.1. Чтобы контекстно-свободная грамматика G =(V

, V

, P, S) бы-

ла LL(k)-грамматикой, необходимо и достаточно, чтобы

FIRST

(βα) ∩

FIRST

(γα)=∅

для всех α, β, γ, таких, что существуют правила A →β, A →γ∈P, β≠γ и

существует вывод S

wAα.

Доказательство. Будем предполагать, что грамматика

G не содержит бес-

полезных нетерминалов. Это предположение не умаляет общности рассужде-

ний, так как бесполезные нетерминалы не влияют на

LL(k)-условие, фигури-

рующее в определении

LL(k)-грамматик. Обе части доказательства проведем

методом “от противного”.

Необходимость. Пусть G — LL(k)-грамматика, но условие не выполнено,

т.е. нашлись такие цепочки

α, β, γ, что существуют A →β, A→γ∈P, β≠γ и

существует вывод

wAα, для которых

FIRST

(βα) ∩

FIRST

(γα) ≠∅.

Пусть некоторая цепочка

z ∈

FIRST

(βα) ∩

FIRST

(γα). Мы можем про-

должить имеющийся вывод

wAα двумя способами, используя упомянутые

два правила и учитывая определение функции

FIRST

151

wAα

wβα

wzu,

wAα

wγα

wzv

для некоторых u,v ∈V

. При построении этих выводов была использована тео-

рема о том, что всякий вывод терминальной цепочки может быть перестроен в

левосторонний.

Остается сопоставить эти два левосторонних вывода с теми, которые участ-

вуют в определении

LL(k)-грамматик. Здесь в роли цепочки x используется zu, а

в роли цепочки

y — zv. Очевидно,

FIRST

(x)=

FIRST

( y)=z, но β≠γ, что

противоречит предположению о том, что

G — LL(k)-грамматика.

В частности, если

|z| <k и u = v = ε, то имеем два разных левосторонних вы-

вода одной и той же терминальной цепочки

wz. Это означает, что G — не одно-

значная грамматика и, естественно, не

LL(k) ни при каком k. Необходимость

доказана.

II.

Достаточность. Пусть условие теоремы выполнено, но G — не LL(k)-

грамматика. Это значит, что существуют два левосторонних вывода:

S wAα wβα wx,

S wAα wγα wy,

в которых

FIRST

(x)=

FIRST

(y), но β≠γ.

Пусть

FIRST

(x)=

FIRST

(y)=z. Имеем βα

x и γα

y. Согласно опре-

делению функции

FIRST

из существования этих двух выводов заключаем, что

z =

FIRST

(x) ∈

FIRST

(βα),

z =

FIRST

(y) ∈

FIRST

(γα)

и, следовательно,

z∈

FIRST

(βα) ∩

FIRST

(γα) ≠∅,

что входит в противоречие с первоначальным предположением о том, что

условие

теоремы выполняется. Достаточность доказана, а вместе с ней и вся тео-

рема.

Определение 2.6. Пусть G =(V

, V

, P, S) — контекстно-свободная граммати-

ка, и

β∈V

. Определим функцию

(β)={w ∈V

| S

γβα и w∈

FIRST

(α)}. Здесь k ≥0 — целое.

Теорема 2.2. Чтобы контекстно-свободная грамматика G = (V

, V

, P, S)

была LL(1)-грамматикой, необходимо и достаточно, чтобы

FIRST

(β

(A)) ∩

FIRST

(γ

(A)) = ∅

для всех A∈V

, β,γ∈(V

∪V

)

, таких, что существуют правила A →β, A →γ∈P,

β≠γ.

Доказательство.

Требуется пояснить, что в формулировке условия теоремы

аргумент функции

FIRST

— не цепочка, как было определено ранее, а множе-

152

ство

цепочек. Расширение области определения этой функции на множества про-

изводится естественным образом:

FIRST

(W )=

()

FIRST

∈

∪

где

W ⊆ V

Обе части теоремы доказываются методом “от противного”. Как и ранее, не

нарушая общности рассуждений, будем считать грамматику

G приведенной.

Необходимость. Пусть G — LL(1)-грамматика, но условие не выполнено,

т.е. существуют правила

A →β, A →γ∈P, β≠γ, c ∈(V

∪ {ε}), такие, что

c ∈

FIRST

(β

(A)) и c ∈

FIRST

(γ

(A)).

Это

означает, что существуют a, b ∈

(A), такие, что c ∈

FIRST

(βa) и

c ∈

FIRST

(γb), и согласно определению функции

FIRST

существуют выводы:

βa cu и γv cv, если c ∈V

или

βa ε и γb ε, если c = ε.

Случай 1

: c ∈V

, βa cu

a = cu, β cu

, u

∈V

; γb cv

b, γ cv

, v

∈V

Так

как грамматика G — приведенная, то существует вывод, в частности левосто-

ронний, который порождает сентенциальную форму, содержащую

A: S wAα,

который может быть продолжен двумя способами:

S wAα wβα wcu

α wcu

S wAα wγα wcv

α wcv

z ,

где

вывод α z, z ∈V

, существует также в силу приведенности грамматики G.

Итак, имеем два левосторонних вывода (1 и 2), фигурирующие в определе-

нии

LL(k)-грамматик, в которых в роли цепочки x используется cu

z, в роли це-

почки

y — cv

z, причем

FIRST

(x)=

FIRST

(cu

z)=c ,

FIRST

(y)=

FIRST

(cv

z)=c,

но

β≠γ. Следовательно, грамматика G — не LL(1), что противоречит

первоначальному предположению.

Случай 2

: c ∈V

, β

ε, a = с, a ∈

(A); γb

b, γ

, v

∈V

Согласно определению

с ∈

(A) означает, что существует вывод, в

частности левосторонний, вида

wAα, такой, что с ∈

FIRST

(α) или, что то

же самое, существует вывод

сz при некотором z ∈V

. Продолжим

левосторонним образом вывод

wAα двумя способами:

153

wAα

wβα

wα

wсz,

wAα

wγα

wсv

сz.

Получили

два вывода (1 и 2), фигурирующие в определении LL(k)-грамматик, с cz

в роли цепочки

x и cv

cz в роли цепочки y. Имеем

FIRST

(x)=

FIRST

(сz)=c,

FIRST

(y)=

FIRST

(cv

cz)=c, т.е.

FIRST

(x)=

FIRST

(y), но β≠γ. Следова-

тельно, грамматика

G — не LL(1), что противоречит первоначальному

предположению.

Случай 3

: c ∈V

, βa

a, β

, u

∈V

; γ

ε, b = c, b ∈

(A).

Он разбирается аналогично предыдущему.

Случай 4

: c ∈V

, β

ε, γ

ε, a = b = c, c∈

(A).

Согласно определению

c ∈

(A) означает существование вывода

вида

wAα, такого, что c∈

FIRST

(α) или, что то же самое, α

cz при

некотором

z∈V

Теперь вывод

wAα продолжим левосторонним образом двумя способа-

ми:

wAα

wβα

wα

wсz ,

wAα

wγα

wα

wсz,

Мы получили два левосторонних вывода (1 и 2), фигурирующих в определении

LL(k)-грамматик, в которых в роли цепочек x и y используются одинаковые

терминальные цепочки

сz, функция

FIRST

от них дает одинаковый результат,

равный

с, притом что β ≠ γ. Следовательно, грамматика G — не LL(1), что

противоречит первоначальному предположению

Случай 5

: β

ε, γ

ε, a = b = ε, ε ∈

(A).

Как

и в случае 4, ε∈

(A) означает существование вывода S

wAα,

такого, что

ε. Его можно продолжить левосторонним образом двумя спосо-

бами:

wAα

wβα

wα

wAα

wγα

wα

Противоречие можно видеть и в том, что существуют два разных левосторонних выво-

да для одной и той же терминальной цепочки az.

154

В роли цепочек

x и y здесь используется ε. Имеем

FIRST

(x) =

FIRST

(y) = ε,

хотя по-прежнему

β ≠ γ. Следовательно, грамматика G — не LL(1), что

противоречит первоначальному предположению

. Необходимость доказана.

II.

Достаточность. Пусть условие теоремы выполнено, но грамматика G —

не

LL(1). Тогда существуют два левосторонних вывода вида

wAα

wβα

wx,

wAα

wγα

wy,

в которых

FIRST

(x)=

FIRST

(y), но β≠γ. Поскольку βα

x и γα

y, то

FIRST

(x) ⊆

FIRST

(βα)

FIRST

(y) ⊆

FIRST

( γα)

и тогда заключаем, что

FIRST

(x) =

FIRST

(y) ⊆

FIRST

(βα) ∩

FIRST

(γα) ≠ ∅,

что противоречит

первоначальному предположению о том, что условие теоремы

выполнено. Достаточность и теорема доказаны.

Следствие 2.1. Теорему 2.2 можно переформулировать следующим образом:

КС-грамматика G является LL(1)-грамматикой тогда и только тогда, когда для

каждого множества A-правил: A

→α

|α

|… |α

— выполняются следующие

условия:

FIRST

(α

) ∩

FIRST

(α

)=∅ при i ≠ j, 1 ≤ i, j ≤ n;

если α

ε, то

FIRST

(α

) ∩

(A) = ∅ для всех j: 1 ≤j ≤n, j ≠i.

Определение 2.7. Контекстно-свободная грамматика G =(V

, V

, P, S) называ-

ется

сильной LL(k)-грамматикой, если она удовлетворяет условию теоремы 2.2:

FIRST

(β

(A)) ∩

FIRST

(γ

(A)) = ∅

для всех

A ∈V

, β, γ∈(V

∪ V

)

, таких, что существуют правила A →β,

A →γ∈P, β≠γ.

Следствие 2.2. Каждая LL(1)-грамматика является сильной. Однако сле-

дующий пример показывает, что для

k >1 не всякая LL(k)-грамматика является

сильной.

Пример 2.3. Рассмотрим cfg G =({S, A}, {a, b}, P, S), где

P = {S → aAaa | bAba, A → b | ε}.

Используя теорему 2.1, проверим, что грамматика

G — LL(2).

Противоречие можно видеть и в том, что существуют два разных левосторонних выво-

да для одной и той же терминальной цепочки w.

155

I. Проведем тестирование относительно нетерминала

FIRST

(aAaaα) = {aa, ab},

FIRST

(bAbaα) = {bb} независимо от α,

FIRST

(aAaaα) ∩

FIRST

(bAbaα) = {aa, ab} ∩ {bb} = ∅.

II. Проведем тестирование относительно нетерминала

A. При этом следует

учесть, что

S ⇒ aAaa и S ⇒ bAba, так что α∈{aa, ba}. Тогда при α = aa

FIRST

(baa)={baa},

FIRST

(aa)={aa},

FIRST

(baa) ∩

FIRST

(aa)={baa} ∩ {aa}=∅;

при

α = ba

FIRST

(bba) = {bb},

FIRST

(ba) = {ba},

FIRST

(bba) ∩

FIRST

(ba)={bb} ∩ {ba}=∅.

Так что

G — действительно LL(2)-грамматика.

Но поскольку, очевидно, что

(S)={ε}, то, учитывая существова-

ние выводов

S ⇒ aAaa и S ⇒ bAba, заключаем, что

(A)={aa, ba}.

Проверка условия сильной

LL(2)-грамматики показывает, что для S

FIRST

(aAaa{ε}) ∩

FIRST

(bAba{ε}) = {aa, ab} ∩ {bb}=∅,

а для

FIRST

(b{aa, ba}) ∩

FIRST

(ε{aa, ba}) = {ba, bb} ∩ {aa, ba}={ba} ≠∅.

Таким образом, грамматика

G — LL(2), но не сильная LL(2)-грамматика.

Теорема 2.3. Если G =(V

, V

, P, S) — контекстно-свободная грамматика, и

G — леворекурсивна, то G — не LL(k)-грамматика ни при каком k.

Доказательство будем проводить в предположении приведенности грам-

матики

G, поскольку, как отмечалось ранее, бесполезные нетерминалы не влия-

ют на выполнение

LL(k)-критерия.

Так как грамматика

G леворекурсивна, то существует вывод вида A

Aρ,

где

ρ ≠ ε, хотя и не исключается, что ρ

ε. Напомним, что A

Aρ означает,

что существует вывод вида

Aρ.

Отметим, что независимо от того,

β = Aρ или β≠Aρ, должно существовать

еще какое-то правило для

A, скажем, A →γ (γ≠β), ибо в противном случае ни-

156

чего, кроме

Aρ

, где i ≥ 0, вывести из нетерминала A было бы невозможно,

что противоречило бы приведенности грамматики G.

любом случае вывод A

Aρ в общем случае состоит из шагов вида

... A

m – 1

...α

= Aρ,

где

= A, ρ = α

...α

. Очевидно, что в этом выводе были использованы прави-

ла

A → A

, A

→ A

,…, A

m – 1

→ A

, где A

= A. Хотя бы одно из этих

правил должно иметь альтернативу, не начинающуюся ни на один из

нетерминалов

, A

,…, A

(иначе грамматика G была бы неприведенной).

Пусть, например, существует

→ A

j + 1

| γ , где γ≠A

j + 1

Так как грамматика

G — приведенная, существует сентенциальная форма, в

частности левостороннего вывода, в которой участвует нетерминал

A, например

wAα, который может быть продолжен следующим образом:

wAα

wAρ

…

…α

α.

Далее этот вывод можно продолжить двумя способами:

j +1

…α

α wA

…α

α = wAρ

i +1

…α

i+1

α wγα

…α

i +1

α wzx

…x

i +1

wγα

…α

wzx

… x

предполагая, что ввиду приведенности грамматики существуют выводы

z, α

,…, α

, ρ

r , α

t, где w,z,x

,…,x

,r,t∈V

Эти два вывода можно сопоставить с теми, которые фигурируют в определении

LL(k)-грамматик. Здесь x = zx

…x

i +1

t, а y = wzx

…x

Если

r ≠ε, то каким бы большим ни было k, всегда путем выбора i можно

добиться, чтобы

FIRST

(x)=

FIRST

(y) при том, что в точке, где эти два вывода

разошлись, были применены различные альтернативы для раскрытия нетермина-

ла

→ A

j + 1

| γ , γ≠A

j + 1

Если

r = ε, то имеем два разных левосторонних вывода одной и той же тер-

минальной цепочки

wzx

…x

t. То и другое означает, что грамматика G — не

LL(k) ни при каком k.

Следствие 2.3. Итак, мы имеем два достаточных признака для того, чтобы

считать КС-грамматику не

LL-грамматикой. Это — неоднозначность и

леворекурсивность.

157

§ 2.3. k-Предсказывающие алгоритмы анализа

Для класса LL(k)-грамматик существует адекватный класс анализаторов, на-

зываемых

k-предсказывающими алгоритмами анализа.

2.3.1. Неформальное описание

Это устройство (рис. 2.1) имеет разбитые на ячейки входную, выходную

ленты и ленту магазина. “Дно” магазина маркируется специальным символом,

например $, который постоянно находится на магазинной ленте. Конечное уст-

ройство управления руководствуется управляющей таблицей, создаваемой по

грамматике, в которой производится синтаксический анализ. Она определяет

действия в зависимости от

k символов, сканируемых единовременно читающей

головкой входной ленты — эта часть входной цепочки называется

аванцепоч-

кой, и верхнего символа магазина. Этими параметрами определяются движения

следующих двух типов:

1. Запись вместо верхнего символа магазина некоторой цепочки магазинных

символов и выдача на выходную ленту некоторой цепочки выходных символов.

Выходная головка при этом продвигается к ближайшей свободной ячейке. В

случае использования этого устройства для целей анализа на выходную ленту

записываются номера правил, образующих левосторонний анализ входной це-

почки, если она принимается. Этот тип движений не продвигает входную го-

ловку.

2. Сброс верхнего символа магазина и продвижение читающей головки

вправо к следующей ячейке входной ленты. Такие движения происходят только

тогда, когда первый символ аванцепочки — такой же, как верхний символ мага-

зина. При этих движениях на выходную ленту ничего не пишется.

Существует возможность сигнализации о приеме входной цепочки или об

ошибке в ней.

k-Предсказывающий алгоритм анализа напоминает детерминированный ма-

газинный преобразователь, но отличается от него тем, что “видит” сразу

k сим-

волов на входе и не имеет внутренних состояний управления. В начальный мо-

мент на входе находится анализируемая цепочка, в магазине — начальный сим-

Управляющая

таблица

Вход:

Выход:

Рис. 2.1.

158

вол магазина и маркер его “дна”, на выходе пусто. Читающая головка сканирует

начало входной ленты. На каждом такте работы алгоритм адресуется к своей

управляющей таблице с двумя входами: верхним символом магазина и текущей

аванцепочкой. Управляющий элемент диктует одно движение из двух, которое

и выполняется. Этот цикл повторяется до тех пор, пока управляющий элемент

не просигнализирует о приеме входной цепочки, и в этом случае на выходе об-

разуется ее левосторонний анализ, или управляющий элемент диагностирует

ошибку на входе, и тогда алгоритм останавливается, не принимая входной це-

почки.

На рис. 2.1 входная цепочка

представлена как wx, причем w обозначает

просмотренную, а

x — не просмотренную ее часть, которая начинается с аван-

цепочки

u и заканчивается цепочкой y. Магазинная цепочка представлена в ви-

де

Xα$, где X обозначает верхний символ магазина, α — символы магазина,

располагающиеся ниже его вершины, а $ — маркер “дна”. Выходная цепочка

представлена как

πi, где π обозначает часть цепочки, образованную перед по-

следним движением алгоритма, а

i — последнюю произведенную запись на вы-

ходную ленту.

2.3.2. Формальное определение.

Сначала дадим несколько определений.

Определение 2.8. k-Предсказывающим алгоритмом анализа называется фор-

мальная

система A =(Σ, Γ∪{$}, ∆, M, X

, $), где Σ — входной алфавит,

Γ∪{$} — магазинный алфавит, $ ∉Γ— маркер “дна” магазина, ∆ — выходной

алфавит, X

∈Γ— начальный символ магазина, M: (Γ∪{$}) ×Σ

→ {(β, i), pop,

accept, error} —

управляющая таблица, β∈Γ

, i∈∆ — номер правила грамматики.

Работу

k-предсказывающего алгоритма анализа проще всего описать в тер-

минах отношения

на множестве конфигураций.

Определение 2.9. Под конфигурацией k-предсказывающего алгоритма анали-

за будем подразумевать тройку (

x, α, π), где x ∈Σ

— непросмотренная часть

входной цепочки, причем

u =

FIRST

(x) ∈Σ

— аванцепочка, α∈Γ

{$} — мага-

зинная цепочка,

π∈∆

— выходная цепочка.

Начальная конфигурация есть (w, X

$, ε), где w ∈Σ

— вся входная цепочка.

Пусть (

x, Xα, π) — текущая конфигурация, где x ∈Σ

— непросмотренная

часть входной цепочки,

X ∈Γ∪{ε} — верхний символ магазина или пустая це-

почка,

α∈Γ

{$} — остальная часть магазинной цепочки.

Определим следующую конфигурацию в зависимости от значения элемента

управляющей таблицы

M(X, u).

1. Если

M(X, u)=(β, i), то (x, Xα, π) (x, βα, πi).

2. Если

M(X, u) = pop и в этом случае всегда X = a, a ∈Σ, x = ax

’,

’

∈Σ

, то

(

x, Xα, π)=(ax

’

, aα, π) (x

’

, α, π).

159

3. Если

M(X, u) = accept, что бывает только по достижении конечной или при-

нимающей конфигурации (ε, $ , π), то анализатор останавливается, принимая

входную цепочку.

4. Если M(X,

u) = error, то анализатор сообщает об ошибке на входе и оста-

навливается, не принимая входной цепочки.

Как обычно, определяется степень (

), транзитивное замыкание ( ) и реф-

лексивно-транзитивное замыкание (

) этого отношения на конфигурациях.

Если (

w, X

$, ε) (ε, $ , π), то мы пишем A(w)=π и называем π выходом A

для

входа w.

Если из начальной конфигурации (

w, X

$, ε) алгоритм A не достигает при-

нимающей конфигурации, то говорят, что значение A(w) не определено.

Трансляция, определяемая k-предсказывающим алгоритмом анализа A, есть

τ(A)={(w, π) | A(w)=π}.

Говорят, что

A есть правильный k-предсказывающий алгоритм анализа для

cfg

G, если (1) L(G)={w | A(w) — определен} и (2) если A(w)=π, то S

Если

k-предсказывающий алгоритм анализа A, использующий управляю-

щую таблицу

M, является правильным для cfg G, то говорят, что M — правиль-

ная управляющая таблица для грамматики G.

Пример 2.4. Построим 1-предсказывающий алгоритм анализа для простой

LL(1)-грамматики, приведенной в примере 2.2. Пронумеруем ее правила:

S → aBS, 2) S → b, 3) B → a, 4) B → bSB.

С учетом свойств этой грамматики, выявленных в примере 2.2, нетрудно

построить управляющую таблицу анализатора (табл. 2.1).

Табл. 2.1

Аванцепочки

X∈Γ

a b

S aBS, 1 b, 2 error

B a, 3 bSB, 4 error

A pop error error

B error pop error

$ error error accept

Используя эту таблицу, алгоритм A анализировал бы входную цепочку

abbab следующим образом:

(

abbab, S$, ε) (abbab, aBS$, 1) (bbab, BS$, 1) (bbab, bSBS$,14)

bab, SBS$,14) (bab, bBS$, 142) (ab, BS$, 142)

(ab, aS$, 1423) (b, S$, 1423) (b, b$, 14232) (ε, $, 14232).