lOMoARcPSD|39270540 TRƯỜNG ĐẠI HỌC PHENIKAA KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP LỚN TÊN HỌC PHẦN: CHƯƠNG TRÌNH DỊCH Đề số 05 HỌC KỲ II NĂM HỌC 2023 – 2024 Giảng Viên Hướng Dẫn : Phạm Văn Cảnh Họ Và Tên Mã Sinh Gmail Viên Hoàng Xuân Trường 21010646 21010646@st.vn Nguyễn Văn Tuấn 21010653 210106653@st.vn Lê Thanh Tùng 21010655 21010655@st.vn Đoàn Phan Tiến Dũng 21012861 21012861@st.vn 1 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Bảng Đánh Giá Phần Nhiệm Vụ Được Phân Công Đánh giá của STT Tên thành viên Công việc trưởng nhóm Hoàng Xuân 1 Trường 25% Tốt (100%) ( Trường Nhóm) 2 Nguyễn Văn Tuấn 25% Tốt (100%) 3 Lê Thanh Tùng 25% Tốt (100%) Đoàn Phan Tiến 4 25% Tốt (100%) Dũng 3 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Đề bài Bài 1. - Mô tả cách xây dựng một số biểu thức quan hệ hai ngôi trong ngôn ngữ lập trình C++? - Dựa vào mô tả trên, hãy xây dựng một bộ phân tích từ vựng nhận biết biểu thức quan hệ hai ngôi trong ngon ngu C++, gồm các thành phần: + Đồ thị chuyển. + Lấy một ví dụ minh họa. - Viết giả mã cho chương chương trình thực hiện yêu cầu trên? Bài 2.
- Phân loại các thuật toán phân tích cú pháp đã học? So sánh phương pháp tất định và quay lui trong phân tích cú pháp? - Trình bày thuật toán LL(1) trong phân tích cú pháp. 4 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 - Áp dụng thuật toán LL(1) xây dựng bảng phân tích cú pháp cho văn phạm sau: SXS' S'-> or X S'| & X->FX' X' -> and F X'| & F->(E)|id Phan tích day (a or a) and a and a? Bai 3. Cho luat sinh đoi voi lenh if. else như sau: S-> if E then T else F.
- Hãy viết luật ngữ nghĩa cho lệnh while ở trên? - Áp dụng sinh mã ba địa chỉ với câu lệnh sau: if a>b+2 then a=a-2 else a=a+1. - Áp dụng sinh mã ba địa chỉ với lệnh: if (a>b) or (x<y) then x=a+1 else x=b+x+a. 5 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Bài 1: I -Quan hệ hai ngôi trong ngôn ngữ lập trình C++ thường được sử dụng để so sánh giá trị của hai biểu thức. Quan hệ hai ngôi trả về một giá trị boolean (true hoặc false) dựa trên kết quả của phép so sánh.
-Để xây dựng một biểu thức quan hệ hai ngôi trong C++, ta cần sử dụng toán tử so sánh và các toán hạng tương ứng. Dưới đây là cách xây dựng một biểu thức quan hệ hai ngôi bằng cách sử dụng các toán tử so sánh: +Chọn toán tử so sánh: Bạn cần chọn một trong các toán tử so sánh (==, !=, >, <, >=, <=) tùy thuộc vào yêu cầu của bạn. +Chọn toán hạng: Sau đó, bạn chọn các toán hạng cần so sánh. Các toán hạng này có thể là biến, hằng số hoặc biểu thức khác.
+Kết hợp toán tử và toán hạng: Bạn sử dụng toán tử đã chọn để so sánh các toán hạng. Bạn có thể sử dụng nó 6 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 trực tiếp trong các điều kiện if/else hoặc gán kết quả vào biến boolean. II – Đồ thị tuyến Dưới đây là một phiên bản của đồ thị tuyến mô tả cấu trúc cú pháp của các biểu thức quan hệ trong ngôn ngữ lập trình C++: (relational) (logical) Start operator1operandoperator2operandend Trong đồ thị tuyến này: +Start: Trạng thái bắt đầu. +Operator: Đại diện cho toán tử trong biểu thức quan hệ.
Có thể là một toán tử so sánh hoặc toán tử logic. +Operand: Thể hiện toán hạng trong biểu thức quan hệ. +End: Trạng thái kết thúc. -Ô-tô-mát : Trong ô-tô-mát này: Start: Trạng thái bắt đầu.
Operator1: Trạng thái biểu diễn một phần của toán tử trong biểu thức quan hệ. 7 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Operand: Trạng thái biểu diễn một phần của toán hạng trong biểu thức quan hệ. Operator2: Trạng thái biểu diễn một phần còn lại của toán tử trong biểu thức quan hệ. End: Trạng thái kết thúc của biểu thức quan hệ.
-Ví dụ: ta có biểu thức a<b&&c==d +Ô-tô-mát: +Đồ thị tuyến: III Giả mã #include <iostream> 8 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 #include <string> using namespace std; class RelationalExpressionAnalyzer { private: string current_state; public: RelationalExpressionAnalyzer() { current_state = "Start"; } bool analyze(string expression) { for (char& c : expression) { if (current_state == "Start") { if (isalpha(c)) { current_state = "Operator"; } else { cout << "Syntax error: Expected operand at the beginning." << endl; return false; } } else if (current_state == "Operator") { if (c == '<' || c == '>' || c == '!' c == '=') { || 9 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 current_state = "Operand"; } else { cout << "Syntax error: Invalid operator '" << c << "'." << endl; return false; } } else if (current_state == "Operand") { if (isalpha(c)) { current_state = "Operator2"; } else { cout << "Syntax error: Expected operand after operator." << endl; return false; } } else if (current_state == "Operator2") { if (c == '&' || c == '|') { current_state = "End"; } else { cout << "Syntax error: Invalid operator '" << c << "'." << endl; return false; } } else if (current_state == "End") { cout << "Syntax error: Unexpected character after expression." << endl; return false; } 10 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 } if (current_state == "Start" || current_state == "Operator2") { cout << "Syntax error: Incomplete expression." << endl; return false; } else { return true; } } }; int main() { RelationalExpressionAnalyzer analyzer; string expression = "a < b && c == d"; if (analyzer.analyze(expression)) { cout << "Syntax analysis passed." << endl; } else { cout << "Syntax analysis failed." << endl; } return 0; } 11 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Trong mã trên: Chúng ta định nghĩa một lớp “RelationalExpressionAnalyzer” để thực hiện phân tích cú pháp cho biểu thức quan hệ. Phương thức “analyze” lặp qua từng ký tự trong biểu thức và di chuyển giữa các trạng thái dựa trên các quy tắc của biểu thức quan hệ. Nếu phân tích cú pháp thành công, phương thức “analyze” sẽ trả về “true”, ngược lại sẽ trả về “false” và in ra thông báo lỗi tương ứng. 12 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 I Phân loại các thuật toán phân tích cú pháp: 1.Phân tích cú pháp thuật toán Bottom-up a.Ý tưởng và thuật toán ❑ Cho văn phạm G với các luật sinh: 𝑆 → 𝐸 + 𝑆|𝐸 𝐸 → 1|2|3|4|5|(𝑆) ❑ Xâu vào: 𝑊 = (1 + 2 + (3 + 4)) + 5 ❑ Thu gọn W thành S: 1 + 2 + 3 + 4 +5←(𝐸 + 2 + (3 + 4)) + 5← ( 𝐸 + 𝐸 + (3 + 4)) + 5←(𝐸 + 𝐸 + (𝐸 + 4)) + 5← ( 𝐸 + 𝐸 + (𝐸 + 𝐸)) + 5←(𝐸 + 𝐸 + (𝐸 + 𝑆)) + 5← ( 𝐸 + 𝐸 + (𝑆)) + 5←(𝐸 + 𝐸 + 𝐸) + 5← ( 𝐸 + 𝐸 + 𝑆) + 5←(𝐸 + 𝑆) + 5← ( 𝑆 ) + 5←𝐸 + 5←𝐸 + 𝐸←𝐸 + 𝑆←S Ý tưởng: - Bottom-up bắt đầu từ các thành phần nhỏ (ví dụ: từ đơn) và xây dựng cây cú pháp từ dưới lên.
- Bottom-up bắt đầu từ các thành phần nhỏ (ví dụ: từ đơn) và xây dựng cây cú pháp từ dưới lên. 13 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 - Thử sai và quay lui bằng năng lực tính toán của máy tính - Dò ngược quá trình suy dẫn 𝑤 ← 𝑤𝑛−1 ← ⋯ ← 𝑤1 ← 𝑆bằng kĩ thuật thu gọn: tìm xem 𝑤𝑖 có chứa vế phải của luật hay không, nếu có thì thay thế phần vế phải đó bằng vế trái tương ứng + Nếu một 𝑤𝑖 ≠ 𝑆thì chắc chắn nó cần phải được thu-gọn, + Nếu 𝑤𝑖 không chứa vế phải của luật nào đó thì nhánh thử sai này cần quay lui, ngược lại thì thu-gọn và thử tiếp Thuật toán: Bước 1: A = w Bước 2: Với chuỗi A đạt được trong quá trình lần ngược: o Nếu A = “S”: - Kết luận: quá trình tìm kiếm thành công - Lưu lại kết quả (chuỗi biến đổi từ đầu để được A) - Kết thúc ngay lập tức quá trình tìm kiếm o Duyệt tất cả các luật sinh dạng 𝑥 → 𝛼, nếu 𝛼 là một chuỗi con trong A thì: 14 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 - Áp dụng thu-gọn: thế α trong A bằng x, ta được A’ - Thử bước 2 với chuỗi A = A’ o Nếu không có phương án thu gọn nào thì quay lui b.Cài đặt bottom-up đơn giản Hình 1 cấu trúc 1 luật 15 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Hình 2 các hàm hỗ trợ Hình 3 các hàm hỗ trợ 16 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Hình 4 các hàm hỗ trợ Hình 5 các hàm chính 17 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 Hình 6 các hàm chính Hình 7 các hàm chính c.Đánh giá về bottom-up - Đặc trưng: + Dễ hiểu: cài đặt đơn giản + Chậm: duyệt toàn bộ, không có các bước cắt nhánh 18 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 + Không vạn năng: không làm việc với văn phạm có suy dẫn rỗng (𝐴 →𝜖) hoặc đệ quy (𝐴 →+ 𝐴) + Không dễ loại bỏ những kết quả trùng lặp (trường hợp muốn tìm mọi phương án suy dẫn) - Ý tưởng cải tiến: + Quy hoạch động: sử dụng lại những kết quả duyệt cũ + Cắt nhánh sớm: dựa trên đặc trưng của một số luật để loại bỏ các phương án không có tương lai 2.Phân tích cú pháp thuật toán CYK a.Khắc phục hạn chế của các phương pháp thử sai Hai thuật toán thử-sai cơ bản top-down và bottom-up đều có những hạn chế về văn phạm đầu vào o Top-down: văn phạm không có đệ quy trái o Bottom-up: văn phạm không có suy dẫn rỗng và không có kí hiệu đệ quy (A ⇒+ A) Các thuật toán thử-sai có hạn chế về mặt tốc độ o Tốc độ chấp nhận được với một số văn phạm đơn giản và đơn nghĩa, đầu vào ngắn 19 Downloaded by sau xanh (saudinh2@gmail.com) lOMoARcPSD|39270540 o Trường hợp xấu có độ phức tạp tính toán hàm mũ Không có cơ chế hiệu quả loại bỏ sự trùng lặp về kết quả (chẳng hạn như nhiều suy dẫn tương đương) Nguyên nhân của những hạn chế này o Hạn chế do bản thân cơ chế hoạt động của thử-sai o Không có cơ chế loại bỏ các phương án chắc-chắn-sai b.
