21/1/2010
1
Bài 3.
Vănphạmsảnsinh
1
Văn
phạm
sản
sinh
Làm thế nào để sản sinh ra các
xâu ?
Văn phạm phi ngữ cảnh có thể dùng để
sản sinh ra các xâu thuộc ngôn ngữ như
sau:
2
X = Ký hiệu đầu
WhileWhile còn ký hiệu không kết thúc Y trong X dodo
Áp dụng một trong các sản xuất của,văn
phạm chẳng hạn Y -> w
Ví dụ
S -> +A | -A |A
A -> B.B | B
3
B -> BC | C
C -> 0 | 1 | 2 |. . . .|9
Khi X chỉ chứa ký hiệu kết thúc, nó là xâu được
sản sinh bởi văn phạm.
Suy dẫn (Derivations)
Mỗi lần thực hiện việc thay thế là một
bướcsuydẫn
4
bước
suy
dẫn
.
Nếu mỗi dạng câu có nhiều ký hiệu không
kết thúc để thay thế có thể sử dụng bất cứ
sản xuất nào.
21/1/2010
2
Suy dẫn trái và suy dẫn phải
Nếu giải thuật phân tích cú pháp chọn ký
hiệu không kết thúc cực trái hay cực phải
để tha
y
thế
,
kết
q
uả của nó lad su
y
dẫn
5
y , q y
trái hoặc suy dẫn phải
Cây suy dẫn(Cây phân tích cú pháp)
Cây suy dẫn có những đặc điểm sau
1) Mỗi nút của cây có nhãn là ký
hiệu kết thúc, ký hiệu không kết
thúc hoặc ε(xâu rỗng)
2) Nhãn của nút gốc là S (ký hiệu
đầu)
6
3) Nút trong có nhãn là ký hiệu
không kết thúc
4) Nút A có các nút con từ trái qua
phải là X1, X2, ... , Xkthì có một
sản xuất dạng A -> X1X2... Xk
5)Nút lá có thể có nhãn εchỉ khi tồn
tại sản xuất A -> εvà nút cha của
nút lá chỉ có một nút con duy nhất
Văn phạm nhập nhằng
Văn phạm
E -> E + E
E -> E * E
7
E -> ( E )
E -> ident
Cho phép đưa ra hai suy dẫn khác nhau cho
xâu ident + ident * ident (chẳng hạn x + y * z)
Văn phạm là nhập nhằng
Khử nhập nhằng
E -> E + T
E -> T
T
>T
*
F
8
T
-
>
T
F
T -> F
F -> ( E )
F -> ident
(Bằng cách thêm các ký hiệu không kết thúc và các sản xuất để
đảm bảo thứ tự ưu tiên)
21/1/2010
3
Đệ quy
Một sản xuất là đệ qui nếu X =>* ω1X ω2
Có thể dùng để biểu diễn các quá trình lặp hay cấu trúc
lồng nhau
Đệ quy trực tiếp X =>ω1X ω2
9
Đệ quy trái X => b | Xa. X => X a => X a a => X a a a =>b a a a a a ...
Đệ quy phảiX => b | a X. X => a X => a a X => a a a X =>... a a a a a b
Đệ quy giữaX => b | "(" X")". X =>(X) =>((X)) =>(((X))) =>(((... (b)...)))
Đệ quy gián tiếp X =>* ω1X ω2
Khử đệ quy trái
E -> E + T | T
T -> T * F | F
F -> ( E ) | ident
Khử đ
ệ
q
u
y
trái bằn
g
cách thêm k
ý
hi
ệ
u khôn
g
1 0
ệqy gýệg
kết thúc và sản xuất mới
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | ident