Bài giảng Xây dựng chương trình dịch: Bài 3 - Văn phạm sản sinh

Bài giảng "Xây dựng chương trình dịch: Bài 3 - Văn phạm sản sinh" cung cấp cho người học các kiến thức: lý thuyết ngôn ngữ; vấn đề biểu diễn ngôn ngữ; phân cấp Chomsky; văn phạm xuất phát từ ngôn ngữ tự nhiên; văn phạm sản sinh các số thực; quá trình sản sinh xâu -3.14;... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Xây dựng chương trình dịch: Bài 3 - Văn phạm sản sinh Bài 3. Văn phạm sản sinh 1 Lý thuyết ngôn ngữ • Mô hình cho tất cả các ngôn ngữ • Ngôn ngữ là tập các xâu (sentence, string) trên một bảng chữ nào đó • Ví dụ về xâu • Dãy các bit • Số thực • Chương trình C • Câu tiếng Việt 2 Vấn đề biểu diễn ngôn ngữ • Thực chất là biểu diễn cú pháp của ngôn ngữ • Biểu diễn phải hữu hạn • Công cụ sản sinh: văn phạm • Công cụ đoán nhận: ôtômat 3 Phân cấp Chomsky Lớp ngôn ngữ Công cụ Công cụ Ghi chú sản sinh đoán nhận Đệ quy kể được Văn phạm loại 0 Máy Turing Các bài toán tổng (ngữ cấu) quát Cảm ngữ cảnh Văn phạm cảm ngữ Ôtômat tuyến tính Ngôn ngữ tự nhiên cảnh giới nội Phi ngữ cảnh Văn phạm phi ngữ Ôtômat đẩy xuống Ngôn ngữ lập cảnh trình, phần chính của ngôn ngữ tự nhiên Chính quy Văn phạm chính Ôtômat hữu hạn Từ vựng của ngôn quy ngữ tự nhiên, ngôn Công cụ biểu diễn: ngữ lập trình Biểu thức chính quy 4 Văn phạm xuất phát từ ngôn ngữ tự nhiên ::= < bổ ngữ>::= ::= ::= bắt ::= ::= mèo | chuột ::= ::= nhỏ 5 Văn phạm sản sinh các số thực ::=- | ::= | . ::= | ::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 6 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: X = Ký hiệu đầu While còn ký hiệu không kết thúc Y trong X do Áp dụng một trong các sản xuất của,văn phạm chẳng hạn Y -> w 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. 7 Ví dụ S -> -A |A A -> B.B | B B -> BC | C C -> 0 | 1 | 2 |. . . .| 9 8 Quá trình sản sinh xâu -3.14 Quá trình thay thế Sản xuất được sử dụng S -A S  -A -B.B A  B.B -B.BC B  BC -C.BC BC -C.CC BC -3.CC C3 -3.1C C1 -3.14 C4 Quá trình suy dẫn (derivation) 9 Suy dẫn (Derivations) • Mỗi lần thực hiện việc thay thế là một 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ể thay thế bất cứ ký hiệu không kết thúc nào 10 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 để thay thế, kết quả của nó là suy dẫn trái hoặc suy dẫn phải Ví dụ suy dẫn trái: S -A-B.B -C.B-3.B-3.BC -3.CC  -3.1C-3.14 Ví dụ suy dẫn phải: S -A-B.B -B.BC-B.B4-B.C4 -B.14  -C.14 -3.14 11 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) 3) Nút trong có nhãn là ký hiệu không kết thúc(nút lá có nhãn là ký hiệu kết thúc hoặc ) 4) Nút A có các nút con từ trái qua phải là X1, X2, ... , Xk thì có một sản xuất dạng A -> X1 X2 ... 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í dụ: Cây phân tích cú pháp của văn phạm G: S ->SS |(S)| w=(()()) 12 Văn phạm nhập nhằng Văn phạm E -> E + E E -> E * E E -> ( E ) E -> TK_IDENT Cho phép đưa ra hai suy dẫn khác nhau cho xâu TK_IDENT + TK_IDENT * TK_IDENT (chẳng hạn x + y * z) Văn phạm là nhập nhằng 13 Khử nhập nhằng (disambiguation) E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> TK_IDENT E: Expresion, T: Term, F: Factor (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) 14 Đệ 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 Đệ quy trái X => b | Xa. X => X a => X a a => X a a a =>b a a a a a ... Đệ quy phải X => b | a X. X => a X => a a X => a a a X =>... a a a a a b Đệ quy giữa X => b | ( X). X =>(X) =>((X)) =>(((X))) =>(((... (b)...))) Đệ quy gián tiếp X =>* ω1X ω2 15 Khử đệ quy trái E -> E + T | T T -> T * F | F F -> ( E ) | TK_IDENT Khử đệ quy trái bằng cách thêm ký hiệu không 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 ) | TK_IDENT 16 ...