Chương 3
Văn phạm phi ngữ cảnh
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
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
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
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