Đề cương Chương trình dịch

Nội dung text: Đề cương Chương trình dịch

1. 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
2. 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. Email: thoanntt@hpu.edu.vn - 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: huong_ntxh@hpu.edu.vn - 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:
3. 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.
4. [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
5. 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
6. 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 à nhi c ục đích v ệm vụ ủ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ú - Gi ên gi CHƯƠNG 1 : TỔNG ảng vi ả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
7. 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ả
8. 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. Ôn t 3.1. Văn phạm phi ngữ ập lại văn phạm - Giảng viên đặt câu hỏi cho sinh phi ng à cảnh và ôtomat đẩy xuống ữ cảnh v 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 xuống Đọc trước nội dung - 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.
9. 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.
10. 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 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.2. Chiến lược phân các vấn đề có liên quan. Đọc trước nội dung 12. tích BOTTOM – UP và - Gọi các sinh viên khác trả lời, từ mục 3.5.2, chuẩn LR (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 đặt câu hỏi cho sinh viên CHƯƠNG 4 : PHÂN - Yêu cầu sinh viên đặt câu hỏi cho Nắm chắc các khái TÍCH NGỮ NGHĨA các vấn đề có liên quan. niệm liên quan đến kiểu dữ liệu, biểu 4.1. Mục đích và nhiệm - Gọi các sinh viên khác trả lời, 13. thức. vụ của phân tích ngữ nhận xét, bổ sung ý (nếu cần). Đọc trước nội dung - Gọi sinh viên lên bảng làm bài tập. nghĩa các mục 4.1, 4.2, 4.2. Các hệ thống kiểu - Gọi sinh viên khác nhận xét, bổ chuẩn bị câu hỏi. sung - Giảng viên kết luận 4.3. Bảng ký hiệu (cây Giảng viên giảng định danh) - Giảng viên đặt câu hỏi cho sinh Nắm chắc các khái 4.3.1. Mục đích, nhiệm viên niệm liên quan đến vụ - Yêu cầu sinh viên đặt câu hỏi cho kiểu dữ liệu, biểu các vấn đề có liên quan. 14. 4.3.2. Các yêu cầu đối thức. với bảng ký hiệu - 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). 4.3.3. Cấu trúc dữ liệu mục 4.3, chuẩn bị của bảng ký hiệu - Gọi sinh viên lên bảng làm bài tập. câu hỏi. 4.3.4. Quy tắc sử dụng - Gọi sinh viên khác nhận xét, bổ bảng ký hiệu sung
11. 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ú - Giảng viên kết luận CHƯƠNG 5: VẤN ĐỀ - Gi ên gi SINH MÃ ảng vi ảng - Gi 5.1. Mục đích nhiệm ảng viên đặt câu hỏi cho sinh viên vụ - Yêu c 5.2. Mã ba địa chỉ ầu sinh viên đặt câu hỏi cho (three address code) các vấn đề có liên quan. Chuẩn bị các nội - Gọi các sinh viên khác trả lời, 5.3. Các vấn đề thiết kế dung chương 8 15. nh bộ sinh mã ận xét, bổ sung ý (nếu cần). Chuẩn bị câu hỏi. - Gi ên t 5.3.1. Đầu vào ảng vi ổng kết. - G ên lên b àm bài t 5.3.2. Đầu ra ọi sinh vi ảng l ập. - G ên khác nh xét, b 5.3.3. Quản lý bộ nhớ ọi sinh vi ận ổ sung 5.3.4. Chọn chỉ thị lệnh - Giảng viên kết luận 5.3.5. Máy đích 7.Tiêu chí đánh giá nhiệm vụ giảng viên giao cho sinh viên: - Sinh viên phải nắm được nguyên lý xây dựng các ngôn ngữ lập trình, biết cách phân tích các điểm mạnh, điểm yếu của từng ngôn ngữ. - Sinh viên biết cách chọn ngôn ngữ lập trính thích hợp cho dự án của m ình. - Sinh viên có thể tự xây dựng một chương trình dịch đơn giản để chuyển đổi một chương trình được viết từ ngôn ngữ lập trình này thành một chương trình được viết bằng ngôn ngữ lập trình khác. - Sinh viên cài đặt được một số thuật toán phân tích đ ã học. 8.Hình thức kiểm tra, đánh giá môn học: - Hoàn thành 2 bài kiểm tra định kỳ của phần lý thuyết (điểm quá tr ình) - Hoàn thành 1 bài kiểm tra định kỳ của phần thực hành (điểm quá trình) - Thi kết thúc học phần 9.Các loại điểm kiểm tra và trọng số của từng loại điểm: - Kiểm tra trong năm học: Thông qua b ài tập, trả lời câu hỏi. - Kiểm tra giữa kỳ (tư cách): 30% - Thi hết môn: 70% 10.Yêu cầu của giảng viên đối với môn học:
12. Yêu cầu về điều kiện để tổ chức giảng dạy môn học (giảng đ ường, phòng máy, ): Giảng đường, máy chiếu, máy tính, phòng thực hành. Sử dụng phần mềm TC Yêu cầu đối với sinh viên (sự tham gia học tập trên lớp, quy định về thời hạn, chất lượng các bài tập về nhà, ): Tham gia học tập trên lớp từ 70% số tiết trở lên, hoàn thành các bài kiểm tra định kỳ, dự buổi thảo luận tr ên lớp. Sinh viên phải chuẩn bị tài liệu môn học theo yêu cầu của Giảng viên. Hải Phòng, ngày 12 tháng 06 năm 2011 Chủ nhiệm Bộ môn Người viết đề cương chi tiết Ths. Vũ Anh Hùng Ths. Nguyễn Thị Thanh Thoan