Bài giảng Ngôn ngữ học máy tính - Nguyễn Tuấn Đăng - Văn phạm phi ngữ cảnh

VĂN PHẠM PHI NGỮ CẢNH
(CONTEXT-FREE GRAMMARS - CFG)
1
Văn phạm phi ngữ cảnh
2
 Một dẫn xuất của một chuỗi là một dãy các luật sinh.
Ví dụ: Chuỗi “a flight” có dẫn xuất như sau.
NP => Det Nominal => a Nominal => a Noun => a flight
Dẫn xuất (Derivation)
S  NP VP
NP  Det Nominal
Nominal  Noun
VP  V
Det  the
Det  a
Noun  flight
V  left
Dẫn xuất(Derivation)
Dẫn xuất có thể được hình dung như một cây phân
tích cú pháp (PARSE TREE).
Ngôn ngữ được định nghĩa bởi văn phạm phi
ngữ cảnh là tập các chuỗi dẫn xuất được bắt
đầu bởi S (Sentence).
3
Dẫn xuất (Derivations) 
và cây phân tích cú pháp (Parse trees)
4
Định nghĩa văn phạm phi ngữ cảnh
Một văn phạm phi ngữ cảnh (CFG) là một hệ
thống gồm bốn thành phần trong
đó:
– N là một tập hữu hạn các biến, hay các ký tự
không kết thúc.
–  là một tập hữu hạn các ký tự kết thúc.
5
Định nghĩa văn phạm phi ngữ cảnh
– P là một tập hợp các luật sinh (productions),
mỗi luật sinh có dạng:
A → α
–Với A là biến (non-terminal)
–α là chuỗi các ký hiệu tạo bởi biến và các ký
tự kết thúc ( υ N)*.
– S là biến đặc biệt thuộc N, gọi là biến khởi
đầu văn phạm.
6
Phi ngữ cảnh (context free)
• Ví dụ:
A  B C
Trong qui tắc trên, có thể viết A như BC, mà
không phụ thuộc vào ngữ cảnh mà ta tìm thấy
A.
7
Dẫn xuất và ngôn ngữ
• Nếu như S =>* w với w chỉ gồm các ký hiệu
kết thúc, ta nói w là một từ của văn phạm G.
• Tập hợp tất cả các từ như vậy tạo thành
một ngôn ngữ tương ứng với CFG G, ký
hiệu là L(G).
• Ngôn ngữ này thuộc loại văn phạm phi ngữ
cảnh context-free language.
– L(G)={w| w chỉ gồm các chốt | S =>* w}
8
Dẫn xuất và ngôn ngữ
• Chuỗi phù hợp với LG được gọi là hợp ngữ
pháp (GRAMMATICAL)
• Chuỗi không phù hợp với LG được gọi là
không hợp ngữ pháp (UNGRAMMATICAL)
9
Xây dựng văn phạm
• Một trong những kỷ năng cơ bản nhất trong
NLE là khả năng viết một CFG cho những phần
nhỏ của một ngôn ngữ (Ví dụ: cấu trúc ngày,
tháng, năm…).
10
Ví dụ về bộ từ vựng
11
Ví dụ về văn phạm
12
Một cây phân tích cú pháp đơn giản
13
Đệ qui (Recursion)
• Nominal  Nominal PP (PP) (PP)
– Đây là một ví dụ cho qui tắc đệ qui
• Những ví dụ khác:
– NP  NP PP
– VP  VP PP
• Đệ qui là một công cụ mạnh mẽ, nhưng có thể 
có kết quả không tốt.
14