CHƯƠNG TRÌNH DỊCH - CHƯƠNG 4

CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Văn phạm ưu tiên toán tử Văn phạm phi ngữ cảnh thỏa mãn các ĐK: - Không có 2 sản xuất có cùng vế phải - Không có vế phải là ε - Không có 2 ký hiệu chưa kết thúc đứng liền nhauGiáo trình Kiến trúc máy tính và Hệ điều hành 97
Nội dung trích xuất từ tài liệu:
CHƯƠNG TRÌNH DỊCH - CHƯƠNG 4 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Văn phạm ưu tiên toán tử Văn phạm phi ngữ cảnh thỏa mãn các ĐK:- Không có 2 sản xuất có cùng vế phải- Không có vế phải là ε- Không có 2 ký hiệu chưa kết thúc đứng liền nhau Giáo trình Kiến trúc máy tính và Hệ 97 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Mối quan hệ ưu tiên giữa các ký hiệu Với a, b ∈Σ có:- a b: a ưu tiên hơn b Giáo trình Kiến trúc máy tính và Hệ 98 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Qui tắc xác định mối quan hệ(1) ∃ Sx mà vế phải có dạng αabβ . a=b hay αaCbβ(2) ∃ Sx mà vế phải có dạng αaBβ . ab mà A⇒+ Kia trúc máy tính⇒+ γaC Giáo trình γ ến hay A và Hệ 99 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Qui tắc xác định mối quan hệ S⇒+γa hay S⇒+γaC(4) a. >$ hay S⇒+ aγ hay S⇒+Caγ Với a, b∈Σ; A,B,C∈∆; α, β, γ ∈ (Σ∪∆)* Giáo trình Kiến trúc máy tính và Hệ 100 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Thuật toánSử dụng: 1 stack và 1 BufferKhởi tạo: - stack: $ - Buffer: x$Lặp: If (Stack là $S) và (Buffer là $) Then - x đúng cú pháp của vp G Giáo trình Kiến trúc máy tính và Hệ 101 điều hành - Dừng vòng lặp TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Thuật toán Else {giả sử k/h kết thúc gần đỉnh stack nhất là a và buffer là b} If (a>b). Then - Tìm cán β ở đỉnh stack - Lấy cán β ra khỏi stack Giáo trình Kiến trúc máy tính và Hệ 102 - Đẩy A vào stack với A β điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Thuật toán Else . . If (a TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Ví dụ: S if DK then L ; DK true | false L write(ID) | read(ID) ID a|b Xâu x: if true then read(a); có đúng cú pháp vp trên? Giáo trình Kiến trúc máy tính và Hệ 104 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.1. Phương pháp ưu tiên toán tử Ví dụ- Xác định tất cả các mối quan hệ- Phân tích Giáo trình Kiến trúc máy tính và Hệ 105 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.2. Phương pháp thứ tự yếu Giáo trình Kiến trúc máy tính và Hệ 106 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp SLR (LR(0)) Giáo trình Kiến trúc máy tính và Hệ 107 điều hành TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGCHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH ...