BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PH ÒNG ISO 9001:2008 ĐỀ CƯƠNG CHI TIẾT Môn học CHƯƠNG TRÌNH DỊCH Mã môn : COM33021 Dùng cho ngành CÔNG NGHỆ THÔNG TIN Bộ môn phụ trách CÔNG NGHỆ PHẦN MỀM THÔNG TIN VỀ CÁC GIẢNG VIÊN CÓ THỂ THAM GIA GIẢNG DẠY MÔN HỌC 1.ThS. Nguyễn Thị Thanh Thoan - Giảng viên cơ hữu - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Công nghệ phần mềm, khoa: Công nghệ thông tin - Địa chỉ liên hệ: Bộ môn Công nghệ phần mềm, khoa: Công nghệ thông tin - Điện thoại: 031.3739878. E mail: [email protected] - Các hướng nghiên cứu chính: Phân tích thiết kế hệ thống thông tin, Ch ương trình dịch, Data mining .... 2.ThS. Nguyễn Thị Xuân Hương - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Công nghệ phần mềm, khoa: Công nghệ thông tin - Địa chỉ liên hệ: Bộ môn Công nghệ phần mềm, khoa: Công nghệ thông tin - Điện thoại: 031.3739878. Email: [email protected] - Các hướng nghiên cứu chính: Khai phá dữ liệu, Ch ương trình dịch, Cấu trúc dữ liệu và giải thuật , Lập trình C/C++. 3.Thông tin về trợ giảng (nếu có): Họ và tên: ................................ ................................ ................................ ................................ .. - Chức danh, học hàm, học vị: ................................ ................................ ............................. - Thuộc bộ môn/lớp: ................................ ................................ ................................ ............ - Địa chỉ liên hệ: ................................ ................................ ................................ .................. - Điện thoại: ................................ .......... Email: ................................ ................................ - Các hướng nghiên cứu chính: ................................ ................................ ............................ THÔNG TIN VỀ MÔN HỌC 1. Thông tin chung: - Số đơn vị học trình/ tín chỉ: 2 tín chỉ - Các môn học tiên quyết: Otomat và ngôn ngữ hình thức, Vi xử lý và ngôn ngữ máy,Lập trình C/C++, Cấu trúc dữ liệu và Giải thuật,.. - Các môn học kế tiếp: - Các yêu cầu đối với môn học: Bài giảng chi tiết, máy chiếu, thực hành. - Thời gian phân bổ đối với các hoạt động: + Nghe giảng lý thuyết: 14 tiết + Làm bài tập trên lớp: 10 tiết + Thảo luận: 8 tiết + Thực hành, thực tập (ở PTN, nhà máy, điền dã,...): 10 tiết + Hoạt động theo nhóm: Không + Tự học: 95 tiết + Kiểm tra: 3 tiết 2. Mục tiêu của môn học: - Kiến thức: Giúp sinh viên nắm vững nguyên lý ngôn ngữ lập trình; Hiểu sâu từng ngôn ngữ lập trình, nắm được các điểm mạnh, điểm yếu của từng ngôn ngữ. Từ đó biết cách lựa chọn các ngôn ngữ lập tr ình thích hợp cho dự án của mình.. - Kỹ năng : nâng cao trình độ hiểu biết và tay nghề, giúp sinh viên nhanh chóng cải thiện hiểu biết và kỹ năng lập trình của mình, biết cách áp dụng vào thực tế - Thái độ: Tạo cho sinh viên tinh thần phấn khởi, tin tưởng và yêu thích môn học, ngành học. 3.Tóm tắt nội dung môn học: - Nghiên cứu cấu trúc tổng quát của một ch ương trình dịch (cấu trúc tĩnh và cấu trúc động) - Nghiên cứu chức năng nhiệm vụ vủa từng bộ phân tích trong một ch ương trình dịch - Tìm hiểu một số ngôn ngữ lập tr ình bậc cao như SLANG, PL/0, PASCAL,C/C++ ... - Tìm hiểu quá trình sinh mã và tối ưu mã - Biết cách xây dựng một chương trình dịch cho một ngôn ngữ đ ơn giản như PL/0 hoặc SLANG 4.Học liệu: Bắt buộc [1]. Phạm Hồng Nguyên, Giáo trình lý thuyết và thực hành môn học chương trình dịch, Khoa Công nghệ ĐHQG Hà nội. 1998. [2]. Trần Đức Quang, Trình biên dịch: nguyên lý, kỹ thuật và công cụ, NXB KHKT, 2000 [3]. Nguyễn Văn Ba, Ngôn ngữ hình thức, NXB ĐHBK Hà nội, 1994 Tham khảo [4]. Alfred V.Aho, Monica S.Lan, Ravi Sethi, Jeffrey D.Uman, Compilers, Principles techniques and tools,Addison Wesley,1986. [5]. Alfred V.Aho, Jeffrey D.Uman, The theory ò passing, translation, and Compiling,Prentice – Hall, inc, 1980. 5.Nội dung và hình thức dạy - học: Hình thức dạy – học Nội dung Tự Tổng Lý Bài Thảo TH, TN, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) học, (tiết) thuyết tập luận điền dã tra tự NC CHƯƠNG 1 : TỔNG QUAN VỀ CHƯƠNG TRÌNH DỊCH 1.1. Giới thiệu môn học chương trình dịch 1.1.1. Giới thiệu môn học 1.1.2. Định nghĩa CTD 1.5 0 0.5 0 6 0 8 1.1.3. Phân loại 1.1.4. Nhiệm vụ của CT D 1.1.5. Yêu cầu về kiến thức 1.1.6. Mục đích của môn học 1.2. Cấu trúc một chương trình dịch 1.2.1 Cấu trúc tĩnh 1.2.2 Cấu trúc động 1.2.3 Vị trí của CTD trong hệ thống dịch thực 2 0 1 0 7.5 0 10.5 sự 1.2.4 Các đặc trưng của ngôn ngữ lập trình bậc cao CHƯƠNG 2: PHÂN TÍCH T Ừ VỰNG 2.1. Văn phạm chính quy và ôtmat hữu hạn 1 0.5 0.5 0 6 0 8 2.1.1 Văn phạm chính quy 2.1.2 Otomat hữu hạn Hình thức dạy – học Nội dung Tự Tổng Lý Bài Thảo TH, TN, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) học, (tiết) thuyết tập luận điền dã tra tự NC 2.2. Mục đích nhiệm vụ của phân tích từ vựng 2.2.1. Mục đích 2.2.2. Nhiệm vụ 1 0 0 0 3 0 4 2.2.3. Từ tố (Token), từ vị (lexeme) và mẫu (pattem) 2.3. Biểu diễn từ tố 2.3.1 Phương pháp dùng biểu thức chính quy 2.3.2 Phương pháp dựng đồ thị chuyển 1 1 1 2 10 0 15 2.4.Các bước để xây dựng một bộ phân tích từ vựng CHƯƠNG 3: PHÂN TÍCH CÚ PHÁP 3.1. Văn phạm phi ngữ cảnh và ôtomat đẩy xuống 3.1.1. Văn phạm phi ngữ cảnh 0.5 1 0.5 0 7.5 0 9.5 3.1.2. Otomat đẩy xuống 3.2. Vai trò của phân tích cú pháp 3.3. Phát hiện lỗi và xử lý lỗi cú pháp 3.4. Các chiến lược phục hồi lỗi 3.5. Các phương pháp phân tích cú pháp 3.5.1. Chiến lược phân tích TOP_DOWN v à 1 3 1 3 16 0 24 LL(1) 3.5.2. Chiến lược phân tích BOTTOM – UP 1 3 1 3 16 2 26 và LR Hình thức dạy – học Nội dung Tự Tổng Lý Bài Thảo TH, TN, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) học, (tiết) thuyết tập luận điền dã tra tự NC CHƯƠNG 4 : PHÂN TÍCH NGỮ NGHĨA 4.1. Mục đích và nhiệm vụ của phân tích ngữ 2 0.5 1 2 11 0 16.5 nghĩa 4.2. Các hệ thống kiểu 4.3. Bảng ký hiệu (cây định danh) 4.3.1. Mục đích, nhiệm vụ 4.3.2. Các yêu cầu đối với bảng ký hiệu 1 0.5 1 0 6 0 8.5 4.3.3. Cấu trúc dữ liệu của bảng ký hiệu 4.3.4. Quy tắc sử dụng bảng ký hiệu CHƯƠNG 5: VẤN ĐỀ SINH MÃ 5.1. Mục đích nhiệm vụ 5.2. Mã ba địa chỉ (three address code) 5.3. Các vấn đề thiết kế bộ sinh mã 5.3.1. Đầu vào 2 0.5 0.5 0 6 1 10 5.3.2. Đầu ra 5.3.3. Quản lý bộ nhớ 5.3.4. Chọn chỉ thị lệnh 5.3.5. Máy đích Tổng (tiết) 14 10 8 10 95 3 140 6.Lịch trình tổ chức dạy – học cụ thể: Chi tiết về hình thức tổ chức dạy - Nội dung yêu cầu sv Ghi Tuần Nội dung học phải chuẩn bị trước chú CHƯƠNG 1 : TỔNG - Giảng viên giảng QUAN VỀ CHƯƠNG - Đặt câu hỏi cho sinh viên TRÌNH DỊCH - Yêu cầu sinh viên đưa ra các câu 1. 1.1. Giới thiệu môn hỏi, vấn đề thắc mắc học chương trình dịch - Mời sinh viên khác trả lời câu hỏi 1.1.1. Giới thiệu môn - Giáo viên bổ sung cho câu trả lời học của sinh viên Chi tiết về hình thức tổ chức dạy - Nội dung yêu cầu sv Ghi Tuần Nội dung học phải chuẩn bị trước chú 1.1.2. Định nghĩa CTD - Giáo viên tổng kết lại nội dung 1.1.3. Phân loại 1.1.4. Nhiệm vụ của CT D 2. 1.1.5. Yêu cầu về kiến thức 1.1.6. Mục đích của môn học 1.2. Cấu trúc một chương trình dịch 1.2.1 Cấu trúc tĩnh - Giảng viên giảng 1.2.2 Cấu trúc động - Yêu cầu sinh viên đặt câu hỏi. Gọi các sinh viên khác trả lời. Sau đó Chuẩn bị trước các 3. 1.2.3 Vị trí của CTD trong hệ thống dịch thực giảng viên bổ sung cho câu trả lời nội dung từ mục 1.2 sự nếu cần 1.2.4 Các đặc trưng - Giảng viên tổng kết lại nội dung. của ngôn ngữ lập trình bậc cao - Giảng viên yêu cầu sinh viên ôn lại các kiến thức. Nắm vững ngôn ngữ CHƯƠNG 2: PHÂN - Gọi sinh viên đặt các câu hỏi và lập trình C, hoặc TÍCH TỪ VỰNG gọi các sinh viên khác trả lời; sau đó Pascal 2.1. Văn phạm chính giảng viên có thể bổ sung câu trả lời Ôn tập các kiến thức 4. quy và ôtmat hữu hạn (nếu cần) cơ bản về văn phạm 2.1.1 Văn phạm chính - Gọi sinh viên lên bảng làm bài tập chính quy và Otomat quy - Gọi sinh viên khác nhận xét, bổ hữu hạn. 2.1.2 Otomat hữu hạn sung (nếu cần) Xem lại các bài tập. - Giảng viên kết luận 2.2. Mục đích nhiệm vụ - Đặt câu hỏi cho sinh viên của phân tích từ vựng - Yêu cầu sinh viên đưa ra các câu Ôn tập lại các khái 2.2.4. Mục đích hỏi, vấn đề thắc mắc niệm cơ bản trong 5. ngôn ngữ lập trình C 2.2.5. Nhiệm vụ - Gọi sinh viên trả lời, nhận xét, bổ 2.2.6. Từ tố (Token), từ sung ý (nếu cần). vị (lexeme) và mẫu - Giảng viên bổ sung cho các câu trả Chi tiết về hình thức tổ chức dạy - Nội dung yêu cầu sv Ghi Tuần Nội dung học phải chuẩn bị trước chú (pattem) lời (nếu cần) - Giảng viên kết luận - Giảng viên giảng bài - Giảng viên đặt câu hỏi cho sinh 2.3. Biểu diễn từ tố viên Nắm được các cách 2.3.1 Phương pháp - Yêu cầu sinh viên đạt câu hỏi. biểu diễn biểu thức dùng biểu thức chính quy - Gọi các sinh viên khác trả lời, chính quy và 6. 2.3.2 Phương pháp nhận xét, bổ sung ý (nếu cần). Otomat. dựng đồ thị chuyển - Giảng viên giảng Đọc nội dung 2.4.Các bước để xây - -Gọi sinh viên lên bảng làm bài tập chương 2, chuẩn bị dựng một bộ phân tích câu hỏi. từ vựng - Gọi sinh viên khác nhận xét, bổ sung - Giảng viên kết luận - Giảng viên yêu cầu sinh viên nhắc CHƯƠNG 3: PHÂN lại các kiến thức đã học. TÍCH CÚ PHÁP - Giảng viên tổng hợp lại nội dung. 3.1. Văn phạm phi ngữ Ôn tập lại văn phạm - Giảng viên đặt câu hỏi cho sinh phi ngữ cảnh và cảnh và ôtomat đẩy xuống viên Otomat đẩy xuống. 3.1.1. Văn phạm phi - Gọi các sinh viên khác trả lời, Xem lại một số bài 7. ngữ cảnh nhận xét, bổ sung ý (nếu cần). tập 3.1.2. Otomat đẩy - Giảng viên giảng Đọc trước nội dung xuống - Gọi sinh viên lên bảng làm bài tập mục 3.1, 3.2, chuẩn 3.2. Vai trò của phân bị câu hỏi. tích cú pháp - Gọi sinh viên khác nhận xét, bổ sung - Giảng viên kết luận - Giảng viên yêu cầu sinh viên nhắc Ôn tập lại văn phạm lại các kiến thức đã học. phi ngữ cảnh và 3.3. Phát hiện lỗi và xử - Giảng viên tổng hợp lại nội dung. Otomat đẩy xuống. lý lỗi cú pháp - Giảng viên đặt câu hỏi cho sinh Xem lại một số bài 8. 3.4. Các chiến lược viên tập phục hồi lỗi - Gọi các sinh viên khác trả lời, Đọc trước nội dung nhận xét, bổ sung ý (nếu cần). mục 3.3, 3.4, chuẩn - Giảng viên giảng bị câu hỏi. Chi tiết về hình thức tổ chức dạy - Nội dung yêu cầu sv Ghi Tuần Nội dung học phải chuẩn bị trước chú - Gọi sinh viên lên bảng làm bài tập - Gọi sinh viên khác nhận xét, bổ sung - Giảng viên kết luận - Giảng viên giảng - Giảng viên đặt câu hỏi cho sinh viên 3.5. Các phương pháp - Yêu cầu sinh viên đặt câu hỏi cho phân tích cú pháp các vấn đề có liên quan. Đọc trước nội dung 9. 3.5.1. Chiến lược phân - Gọi các sinh viên khác trả lời, từ mục 3.5.1, chuẩn tích TOP_DOWN và nhận xét, bổ sung ý (nếu cần). bị câu hỏi. LL(1) - Gọi sinh viên lên bảng làm bài tập.Gọi sinh viên khác nhận xét, bổ sung - Giảng viên kết luận - Giảng viên giảng - Giảng viên đặt câu hỏi cho sinh viên - Yêu cầu sinh viên đặt câu hỏi cho 3.5.1. Chiến lược phân các vấn đề có liên quan. Đọc trước nội dung 10. tích TOP_DOWN và - Gọi các sinh viên khác trả lời, từ mục 3.5.1, chuẩn LL(1) (tiếp) nhận xét, bổ sung ý (nếu cần). bị câu hỏi. - Gọi sinh viên lên bảng làm bài tập. - Gọi sinh viên khác nhận xét, bổ sung - Giảng viên kết luận Giảng viên giảng - Giảng viên đặt câu hỏi cho sinh viên 3.5.2. Chiến lược phân Đọc trước nội dung - Yêu cầu sinh viên đặt câu hỏi cho 11. tích BOTTOM – UP và từ mục 3.5.2, chuẩn các vấn đề có liên quan. LR bị câu hỏi. - Gọi các sinh viên khác trả lời, nhận xét, bổ sung ý (nếu cần). - Gọi sinh viên lên bảng làm bài tập.