21/1/2010
1
Bài 8.
Vănphạm LL(k)
Văn
phạm
LL(k)
Phân cấp các ngôn ngữ phi ngữ cảnh
Ngôn ngữ LL(k)
Xem trước k ký hiệu trên xâu vào để quyết
định sản xuất được sử dụng
Đượcsinhranhờvănphạm LL(k)
Được
sinh
ra
nhờ
văn
phạm
LL(k)
FIRSTk(α)
Định nghĩa:Cho vănphạm G phi ngữcảnh, số
nguyên dươngk,alàmộtxâubaogồmký
hiệu
kết
thúc
và
không
kết
thúc
hiệu
kết
thúc
và
không
kết
thúc
FIRSTk(
α
)làtậpcácxâu xgồmkkýhiệukết
thúc trái nhấtcủacácxâusuydẫntừ
α
(Kểcả
trường hợpxkhôngcóđủ kký hiệunhưng
α
suy dẫn ra x , không còn ký hiệu nào sau x)
21/1/2010
2
FIRSTk(α)
Định nghĩa:Cho vănphạmG=(Σ, Δ,P,S),số
nguyên
dươn
k,α∈V*
FIRSTk(α)={x∈Σ*|αxβvà |x| = k hoặcαxvà
|x| < k}
(Tậpcácxâu x
∈Σ
*cókkýhiệutráinhấtsuydẫn
từ
α
(Kểcảtrường hợpxkhôngcóđủ kký hiệu
nhưng
α
x , không còn ký hiệu nào sau x))
FOLLOWk(α)
kkýhiệukết thúc đầu tiên tiếpsauxâuđược
suy dẫntừ
α
.
Đặcbiệt , khi A là ký hiệu không kếtthúc,S
suy dẫn ra bA thì FOLLOW1(A) ={ε}
FOLLOWk(α)
FOLLOWk(α)={x∈Σ*|S ⇒*βαδ và x∈FIRSTk(δ)}
Đặ
biệt
khi
A
Δ
*
S
*
β
A
thì
Đặ
c
biệt
,
khi
α=
A
∈
Δ
*
,
S
⇒
*
β
A
thì
FOLLOW1(A) ={ε}
Văn phạm LL(k)
Định nghĩavănphạm phi ngữcảnh G = (Σ,
Δ,P,S) làLL(k) vớikchotrướcnếuvới
m
ọ
ic
ặp
su
y
dẫntrái
ọ
ặp
y
S=>xAα=> xβ1α=> xZ1
S=>xAα=> xβ2α=> xZ2
NếuFIRST
k(Z1)=FIRST
k(Z2)thìβ1=β2
21/1/2010
3
Ví dụ
VănphạmGvớicácsảnxuất:
S→aAS | b
A
→
bSA
|
a
A
→
bSA
|
a
là LL(1)
Văn phạm LL(1) đơn giản
VănphạmG=(Σ, Δ, P, S) là LL(1) đơngiảnnếu
mọisảnxuấtcủavănphạmcódạng
A→a1α1|a
2α2|....a
nα, ai∈Σ1≤i≤n
Trong đóa
i≠ajvớii≠j
Điều kiện nhận biết văn phạm LL(1)
Định lý VănphạmG=(Σ, Δ, P, S) là LL(1) khi
và chỉkhi mọitậpA-sảnxuất trong P có dạng
A
→α
1
|
α
2
|
....
|
α
n
,
n≥2thoảmãn
1
|
2
|
|
n
,
FIRST1(αi)∩FIRST1(αj)=∅
Nếuαi⇒*εthì
FIRST1(αi)∩FOLLOW1(A) =∅,i≠j
Điều kiện LL(1) trên sơ đồ cú pháp
Ở mỗi lối rẽ, các nhánh phải bắt đầu bằng
các ký hiệu khác nhau
Nếubiểuđồ có chứamộtđường rỗng thì
Nếu
biểu
đồ
có
chứa
một
đường
rỗng
thì
mọi ký hiệu đứng sau ký hiệu được biểu
diễn bởi biểu đồ phải khác các ký hiệu
đứng đầu các nhánh của sơ đồ
21/1/2010
4
A FIRST(A) FOLLOW(A)
Block CONST, VAR,TYPE,
PROCEDURE,BEGIN
.,;
Unsignedconst ident, number,’
Constant +,-,’,ident,number
T
id t i t h
Văn phạm KPL là LL(1)
T
ype
id
en
t
,
i
n
t
eger, c
h
ar,arra
y
Statement ident, CALL, BEGIN,
WHILE,FOR
.,;, END
Expression +,-,(,ident,number .,;, END,TO,THEN,DO,),-
,.),<,<=,>,>=,=,!=
Term ident,number, ( .,;,END,TO,THEN,DO,),-
,<,<=,>,>=,=,!=
Factor ident, number, ( .,;,END,TO,THEN, DO, +, -,
*,/,) ,<,<=,>,>=,=,!=