Chương 3
Văn phạm phi ngữ cảnh
1
Nội dung
Suy dẫn phi ngữ cảnh
Cây suy dẫn và sự nhập nhằng
Giản lược văn phạm phi ngữ cảnh
Dạng chuẩn Chomsky
2
Suy dẫn phi ngữ cảnh
Văn phạm phi ngữ cảnh: là văn phạm trong đó
các sản xuất có dạng:
A với A ; ( )*
Suy dẫn phi ngữ cảnh: tại mỗi bước chỉ áp
dụng sản xuất phi ngữ cảnh
3
Một số ví dụ về suy dẫn phi ngữ cảnh
Ví dụ 1: Trong ngôn ngữ lập trình
<định danh><chữ cái>|<định danh><chữ cái>|<định
danh><chữ số>
<chữ cái> A|B|C|…|Z
<chữ số>0|1|2|3|4|5|6|7|8|9
Kí hiệu không kết thúc: <định danh>, <chữ cái>, <chữ số>
Kí hiệu kết thúc: A, B, C, …, Z, 0, 1, 2, …, 9
4
Một số ví dụ về suy dẫn phi ngữ cảnh
Ví dụ 2: Trong văn phạm tiếng Việt có các quy tắc:
<câu><chủ ngữ><vị ngữ>
<chủ ngữ><danh từ>|<đại từ>
<vị ngữ><động từ>
<danh từ>bò|mèo|…
<đại từ>tôi|nó|…
<động từ>ăn|nằm|…
Kí hiệu không kết thúc: <câu>, <chủ ngữ>, <vị ngữ>, <danh
từ>, <đại từ>, <động từ>
Kí hiệu kết thúc: “bò”, “mèo”, “tôi”, “nó”, “ăn”, “nằm”… là các
từ tiếng Việt
5