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

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

157
Тогда
w = a, α = S , β = a, γ = bSB. Ясно, что любая цепочка x, выводимая из
βα = aS, начинается на a, а цепочка y, выводимая из γα = bSBS, начинается на b.
Поэтому если первый символ цепочки, следующей за закрытой частью
сентенциальной формы (
w = a), есть a, то для замены нетерминала B следует
использовать первую альтернативу. Если она начинается на
b, то вторую.
В обоих случаях
LL(1)-условие выполнено: по первому символу цепочки,
следующей за закрытой частью сентенциальной формы, однозначно опреде-
ляется то правило, которое следует применить к соответствующему нетер-
миналу, чтобы в конце концов получить анализируемую цепочку. Очевидно, что
любые два левосторонних вывода в данной грамматике, подпадающие под
вышеприведённый образец, удовлетворяют
LL(k)-условию.
Данная грамматика служит примером
простой LL(1)-грамматики.
Определение 2.6. Говорят, что контекстно-свободная грамматика G
является простой LL(1)-грамматикой, если в ней нет ε-правил, и все
альтернативы для каждого нетерминала начинаются с терминалов и притом
различных.
Таким образом, в простой
LL(1)-грамматике для данной пары (A, a), где
A ∈ V
N
и a ∈ V
T
, существует, самое большее, одна альтернатива вида A → aα.
§ 2.2. Свойства LL(k)-грамматик
Теорема 2.1. Чтобы контекстно-свободная грамматика G =(V
N
,V
T
,P,S)
была LL(k)-грамматикой, необходимо и достаточно, чтобы
для всех α, β, γ, таких, что существуют правила A →β, A →γ∈ P, β≠γ и
существует вывод S wAα.
Доказательство. Будем предполагать, что грамматика
G не содержит
бесполезных нетерминалов. Это предположение не умаляет общности рассуж-
дений, так как бесполезные нетерминалы не влияют на
LL(k)-условие,
фигурирующее в определении
LL(k)-грамматик. Обе части доказательства
проведем методом “от противного”.
I.
Необходимость. Пусть G — LL(k)-грамматика, но условие не выполнено,
т.е. нашлись такие цепочки
α, β, γ, что существуют A →β, A →γ∈P, β≠γ и
существует вывод
S wAα, для которых
Пусть некоторая цепочка Мы можем продол-
жить имеющийся вывод
S wAα двумя способами, используя упомянутые два
правила и учитывая определение функции
FIRST
G
k
:
1)
S
wAα
wβα
wzu,
2)
S
wAα
wγα
wzv
для некоторых u,v ∈V
T
*
. При построении этих выводов была использована
теорема о том, что всякий вывод терминальной цепочки может быть
перестроен в левосторонний.
l m
*
⇒
l m
*
⇒
l m
*
⇒
lm
⇒
l m
*
⇒
l m
*
⇒
lm
⇒
l m
*
⇒
FIRST ( ) FIRST ( )
GG
kk
βα ∩ γα = ∅
l m
*
⇒
FIRST ( ) FIRST ( ) .
GG
kk
β
α∩ γα≠∅
FIRST ( ) FIRST ( ).
GG
kk
z
∈
βα ∩ γα

Страницы