BỘ MƠN DUYỆT Chủ nhiệm Bộ mơn Ngơ Hữu Phúc ĐỀ CƯƠNG CHI TIẾT BÀI GIẢNG (Dùng cho tiết giảng) Học phần: CHƯƠNG TRÌNH DỊCH Nhóm mơn học: Bộ mơn: Khoa học máy tính Khoa (Viện): CNTT Thơng tin nhóm mơn học TT Họ tên giáo viên Hà Chí Trung Võ Minh Phổ Nguyễn Trung Tín Thay mặt nhóm mơn học Học hàm GVC GVC TG Hà Chí Trung Học vị TS TS TS Địa điểm làm việc: Giờ hành chính, Bộ mơn Khoa học máy tính – Tầng 13 nhà S4 – Học viện Kỹ thuật Quân Địa liên hệ: Bộ mơn Khoa học máy tính – Khoa Cơng nghệ thông tin – Học viện Kỹ thuật Quân 236 Hoàng Quốc Việt Điện thoại, email: hct2009@yahoo.com; vominhpho@yahoo.com Bài giảng 01: Nhập mơn Chương trình dịch Chương I, mục: Tiết thứ: 1-3 Tuần thứ: - Mục đích yêu cầu Mục đích: Cung cấp thơng tin mơn học, giáo trình tài liệu liên quan, mục đích phạm vi lý thuyết môn học, lich sử đời thành phần chương trình dịch điển hình Cơ chế pha làm việc chương trình dịch Yêu cầu: sinh viên phải hệ thống lại kiến thức sở lý thuyết ngôn ngữ lập trình, kiến thức lập trình, tự nghiên cứu ôn tập lại vấn đề lý thuyết khác có liên quan đến môn học lý thuyết automata ngơn ngữ hình thức, tốn rời rạc - Hình thức tổ chức dạy học: Lý thuyết, thảo luận, tự học, tự nghiên cứu - Thời gian: Giáo viên giảng: tiết; Thảo luận làm tập lớp: tiết; Sinh viên tự học: tiết - Địa điểm: Giảng đường P2 phân cơng - Nội dung chính: 1.1 Khái niệm compiler 1.2 Vị trí compiler LPS 1.3 Các giai đoạn làm việc compiler 1.3.1 Phân tích từ vựng (lexical analysis) 1.3.2 Phân tích cú pháp (syntax analysis) 1.3.3 Phân tích ngữ nghĩa (semantic analysis) 1.3.4 Sinh mã trung gian (ICG) 1.3.5 Tối ưu mã (code optimition) 1.3.6 Sinh mã đích (code generation) 1.4 Vấn đề quản lý bảng ký tự 1.5 Xử lý lỗi biên dịch 1.1 Khái niệm compiler  Khái niệm: Chương trình dịch (compiler) chương trình làm nhiệm vụ đọc chương trình viết ngôn ngữ - ngôn ngữ nguồn (source language - SL) - dịch thành chương trình tương đương ngơn ngữ khác - ngơn ngữ đích (target languague - TL)  Chương trình dịch dạng xử lý ngôn ngữ (languague proccessor) Một số khái niệm:  CTD: chương trình dịch (compiler);  CT: chương trình (program);  SP: chương trình nguồn (source program);  TP: chương trình ngơn ngữ đích (target program);  SL: ngôn ngữ nguồn (source languague);  TL: ngơn ngữ đích (target languague);  PL: ngơn ngữ lập trình (programming languague);  HLL: ngơn ngữ bậc cao (high level languague);  IL: ngôn ngữ trung gian (intermediate languague);  NL: ngôn ngữ tự nhiên (natural languague);  MC: mã máy (machine code);  ML: ngôn ngữ máy (machine languague);  Vấn đề trọng tâm:  Nguyên lý làm việc chương trình dịch;  Lý thuyết thiết kế ngơn ngữ lập trình (ngơn ngữ người – máy dịch tự động);  Chuyển đổi từ ngôn ngữ lập trình sang ngơn ngữ khác  Ứng dụng:  Hiểu ngôn ngữ, điểm mạnh điểm yếu nó;  Lựa chọn ngơn ngữ chương trình dịch thích hợp;  Phân biệt cơng việc CTD thực CT ứng dụng thực hiện;  Thực dự án xây dựng chương trình dịch;  Trong giao tiếp người máy thông qua câu lệnh  Áp dụng NLP, dịch tự động, tóm tắt văn bản…  Phân loại Compilers: Có nhiều cách phân loại khác nhau, tùy theo tiêu chí phân loại Theo phương pháp dịch chạy:  Thông dịch: (diễn giải - interpreter) đọc SP theo lệnh phân tích thực (VD: cmd, HQTCSDL Foxpro), chuyển sang IL + đọc CT IL thực câu lệnh IL gọi ngơn ngữ máy ảo (VM) - chương trình thông dịch thực ngôn ngữ này;  Biên dịch (compiler): tồn chương trình nguồn trình biên dịch chuyển sang chương trình đích dạng ML Chương trình đích chạy độc lập máy mà không cần hệ thống biên dịch  Theo lớp văn phạm: LL(1) (LL – Left to right, leftmost) LR(1) (LR – letf to right, right most)  VD: Hệ thống dịch Java kết hợp thông dịch biên dịch Mã nguồn Java dịch dạng Bytecode File trình thơng dịch gọi máy ảo Java thực 1.2 Vị trí compiler LPS Để tạo tra chương trình đích có khả thực thi (excutable) ngồi trình biên dịch ta phải có thêm số chương trình khác Sơ đồ sau mơ tả ngữ cảnh trình biên dịch hệ thống xử lí ngơn ngữ (LPS: language- processing system) hay môi trường biên dịch 1.3 Các giai đoạn làm việc compiler Các giai đoạn làm việc compiler phân chia theo tính logic công việc theo thời gian làm việc Cấu trúc theo thời gian: hay đồng thời Duyệt lần: số thành phần chương trình thực đồng thời Bộ phân tích cú pháp đóng vai trị trung tâm, điều khiển chương trình Duyệt nhiều lần: thành phần chương trình thực độc lập với Qua phần, kết lưu vào thiết bị lưu trữ để lại đọc vào cho bước Cấu trúc logic: giai đoạn: analysis (front end) synthesis (back end), chia làm nhiều pha làm việc 1.3.1 Phân tích từ vựng (lexical analysis) Lexical analysis: đọc chương trình nguồn từ trái sang phải (linear analysis/scanning) để tách thành từ tố (token); Cũng NL, PL xây dựng dựa từ vựng; Để xây dựng CTD, hệ thống phải tìm hiểu tập từ vựng SL phân tích để biết loại từ vựng thuộc tính  Từ vựng ngơn ngữ lập trình thường xây dựng dựa chữ gồm có:  chữ cái: A Z, a z  chữ số:  ký hiệu toán học: +, - , *, /, (, ), =, , !, %, /  ký hiệu khác: [, ],  Các từ vựng ngôn ngữ hiểu bao gồm từ khóa, tên hàm, tên hằng, tên biến, phép toán,  Các từ vựng có qui định định  VD: Câu lệnh chương trình nguồn viết ngơn ngữ C: a = b + c * 60; Chương trình phân tích từ vựng trả về:  a tên (tên (định danh))  = toán tử gán  b tên (định danh)  + toán tử cộng  c định danh  * toán tử nhân  60 số;  Kết phân tích từ vựng là: (tên, a), phép gán, (tên, b) phép cộng (tên, c) phép nhân, (số, 60) 1.3.2 Phân tích cú pháp (syntax analysis)  Syntax: Thành phần quan trọng ngôn ngữ Trong FL ngơn ngữ tập câu thỏa mãn văn phạm (grammar) ngơn ngữ  Syntax analysis: Phân tích cấu trúc ngữ pháp chương trình Các từ tố (token) chương trình nguồn thành cụm từ văn phạm (grammatical phrase) theo cấu trúc phân cấp (syntax tree):  Ngôn ngữ định nghĩa luật sinh (production);  Phân tích cú pháp dựa vào luật sinh để xây dựng phân tích cú pháp (parse tree)  Trong PL, cú pháp thể luật cú pháp Bộ luật dùng để mơ tả cấu trúc chương trình, câu lệnh , bao gồm:  khai báo  biểu thức số học, biểu thức logic  lệnh: lệnh gán, lệnh gọi hàm, lệnh vào ra,  câu lệnh điều kiện if  câu lệnh lặp: for, while  chương trình (hàm thủ tục)  Với chuỗi từ tố tập luật cú pháp SL, phân tích cú pháp có nhiệm vụ tự động đưa cú pháp cho chuỗi nhập; Khi cú pháp xây dựng xong q trình phân tích cú pháp chuỗi nhập kết thúc thành công Ngược lại áp dụng tất luật xây dựng cú pháp chuỗi nhập không cú pháp (Syntax error)  Phân tích tồn SP thành cấu trúc cú pháp ngơn ngữ, từ để kiểm tra tính đắn mặt ngữ pháp SP  Ví dụ: Ngơn ngữ đặc tả luật sau: Stmt ten := expr Expr expr + expr | expr * expr | ten | so  Với chuỗi nhập: a= b+c*60 ta có dẫn xuất hình vẽ sau: 1.3.3 Phân tích ngữ nghĩa (semantic analysis) Ngữ nghĩa: Trong phạm vi PL liên quan đến:  Kiểu, phạm vi biến (type checking)  Phân biệt sử dụng tên hằng, tên biến, tên hàm Phân tích ngữ nghĩa: Sử dụng cấu trúc phân cấp giai đoạn parser để xác định toán tử, toán hạng biểu thức câu lệnh, Phân tích đặc tính khác chương trình mà khơng phải đặc tính cú pháp Kiểm tra chương trình nguồn để tìm lỗi cú pháp hợp kiểu CTD phải kiểm tra tính đắn sử dụng đại lượng Ví dụ: khơng cho gán giá trị cho hằng, kiểm tra tính đắn gán kiểu, kiểm tra phạm vi, kiểm tra sử dụng tên (tên không khai báo trùng, dùng cho gọi hàm phải tên có thuộc tính hàm) VD: Giả sử biến rate, initial position khai báo real, 60 số integer trình biên dịch đổi số nguyên 60 thành số thực 60.0 hàm inttoreal 1.3.4 Sinh mã trung gian (ICG)  Sinh mã trung gian (intermediate code generation): Sinh chương trình IL nhằm mục đích:  dễ sinh tối ưu mã;  dễ chuyển đổi mã máy  Sau phân tích cấu trúc ngữ nghĩa, số trình biên dịch tạo dạng biểu diễn trung gian chương trình nguồn  IC thông thường biểu diễn dạng "mã máy địa chỉ" (threeaddress code), tương tự dạng hợp ngữ cho máy mà vị trí nhớ đóng vai trị ghi  VD: Với chuỗi nhập: a= b+c*60 sau giai đoạn phân tích IC sinh có dạng sau: temp1 := 60 temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 1.3.5 Tối ưu mã (code optimition) Tối ưu mã: Sửa đổi chương trình IL nhằm cải tiến chương trình đích hiệu VD: với IC trên, rút gọn: temp1 := id3 * 60 id1 := id2 + temp1 1.3.6 Sinh mã đích (code generation) Sinh mã: tạo TP từ chương trình IL tối ưu Thông thường sinh MC hay mã hợp ngữ, vấn đề định việc gán biến cho ghi VD: Chẳng hạn CTD sử dụng ghi R1 R2, thị lệnh MOVF, MULF, ADDF, mã đích cho đoạn code sinh sau: MOVF id3, R2 MULF #60, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 1.4 Vấn đề quản lý bảng ký tự Quản lý bảng ký tự: Để ghi lại kí hiệu, tên … sử dụng chương trình nguồn thuộc tính kèm theo kiểu, phạm vi, giá trị Cho việc sử dụng chúng suốt trình dịch Từ tố (token) + thuộc tính (kiểu, phạm vi…) = bảng kí hiệu (symbol table) Trong q trình phân tích từ vựng, tên lưu vào bảng ký hiệu, từ giai đoạn phân tích ngữ nghĩa thơng tin khác thuộc tính tên (tên hằng, tên biến, tên hàm) bổ sung giai đoạn sau Trong giai đoạn lại: lưu trữ thuộc tính từ vựng truy xuất thơng tin thuộc tính cho giai đoạn Bảng kí hiệu tổ chức cấu trúc liệu với phần tử mẩu tin dùng để lưu trữ trị từ vựng thuộc tính Trị từ vựng: tên từ tố Các thuộc tính: tầm hoạt động, số đối số, kiểu đối số 1.5 Xử lý lỗi biên dịch Xử lý lỗi: Khi phát lỗi q trình dịch ghi lại vị trí gặp lỗi, loại lỗi, lỗi khác có liên quan đến lỗi để thơng báo cho người lập trình Mỗi giai đoạn có nhiều lỗi, tùy thuộc vào trình biên dịch mà là: Dừng thông báo lỗi gặp lỗi dầu tiên (Pascal) Ghi nhận lỗi tiếp tục trình dịch (C) Giai đoạn phân tích từ vựng: có lỗi ký tự ghép thành token (ví dụ: 15a, a@b, ) Giai đoạn phân tích cú pháp: Có lỗi token khơng thể kết hợp với theo cấu trúc ngơn ngữ (ví dụ: if stmt then expr) Giai đoạn phân tích ngữ nghĩa báo lỗi tốn hạng có kiểu khơng yêu cầu phép toán Đối với SL, ta quan tâm đến việc sinh IC mà không cần biết mã máy đích (khơng phụ thuộc vào máy đích) IL thường gần với mã máy - Nội dung thảo luận Kinh nghiệm trình biên dịch debug lập trình môi trường Turbo C Visual C++ Sự giống, khác ngơn ngữ lập trình ngơn ngữ tự nhiên Sự giống, khác trình biên dịch người biên dịch - Yêu cầu SV chuẩn bị Ôn tập lại kiến thức liên quan đến lý thuyết ngơn ngữ hình thức, automata hữu hạn biểu thức quy - Bài tập Tìm hiểu từ tố cú pháp ngơn ngữ Pascal Tìm hiểu từ tố cú pháp ngôn ngữ C Tìm hiểu từ tố cú pháp ngơn ngữ HTML, XML Tìm hiểu vấn đề biên dịch modul thực chức biên dịch mơi trường Visual Studio.net Tìm hiểu vấn đề biên dịch modul thực chức biên dịch môi trường Java NetBeans Tìm hiểu cấu trúc file văn RTF, HTML, TEX Sự giống khác cấu trúc văn với cấu trúc chương trình C, Pascal? - Tài liệu tham khảo Compilers : Principles, Technique and Tools A.V Aho, M Lam, R Sethi, J.D.Ullman - Addison -Wesley 2nd Edition, 2007 Chương Advanced Compiler Design and Implementation S Muchnick Morgan-Kaufmann Publishers, 2007 Chương Giáo trình chương trình dịch 2nd Edition Phạm Hồng Nguyên NXB ĐHQG Hà Nội, 2009 Chương - Câu hỏi ôn tập Khái niệm ngôn ngữ, từ (chuỗi, xâu) Một số phép tốn từ ngơn ngữ Các hình thức biểu diễn ngơn ngữ Cho ví dụ minh họa Chương trình dịch gì? Các pha làm việc trình biên dịch So sánh hệ thống biên dịch thông dịch So sánh thiết kế duyệt lượt nhiều lượt Ưu điểm kiến trúc kỳ trước kỳ sau Tạo cần sử dụng ngôn ngữ nhân tạo? So sánh chương trình dịch duyệt lần nhiều lần 10 Lấy ví dụ chương trình biên dịch chương trình thơng dịch - Ghi chú: Các mơn học tiên : tốn rời rạc, cấu trúc liệu giải thuật, lập trình Bài giảng 02: Lý thuyết Automata ngôn ngữ hình thức Chương 2, mục: Tiết thứ: 4-15 Tuần thứ: 2, 3, - Mục đích yêu cầu Mục đích: Sau chương này, sinh viên cần nắm vững khái niệm sau:  Cấu trúc ngôn ngữ tự nhiên ngơn ngữ lập trình;  Các phép tốn chuỗi, ngôn ngữ;  Cách thức biểu diễn ngôn ngữ; 10 E -> - E1 E -> ( E1 ) E -> id E.place := newtemp; E.code := E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place) E.place := E1.place E.code := E1.code E.place := id.place E.code := ‘’ 6.3 Sinh mã trung gian cho biểu thức boole, logic số học Sinh mã đích cho biểu thức boole Đối với biểu thức Boole E, ta dịch E thành dãy câu lệnh ba địa chỉ, phép toán logic sinh lệnh nhảy có điều kiện khơng có điều kiện đến hai vị trí: E.true, nơi quyền điều khiển chuyển tới E đúng, E.false, nơi quyền điều khiển chuyển tới E sai Sinh mã trung gian cho biểu thức logic số học Xét văn phạm E → E+ E | E and E | E relop E | id Trong đó, E and E đòi hỏi hai đối số phải logic Trong + relop có đối số biểu thức logic hoặc/và số học Ðể sinh mã lệnh trường hợp này, dùng thuộc tính tổng hợp E.type arith bool E có thuộc tính kế thừa E.true E.false biểu thức số học 6.4 Sinh mã trung gian cho số lệnh điều khiển Để sinh nhãn mới, ta dùng thủ tục newlable Với biểu thức logic E, kết hợp với nhãn E.true : Nhãn dòng điều khiển E true E.false : Nhãn dòng điều khiển E false S.code : Mã lệnh địa sinh S S.next : Là nhãn mà lệnh địa thực sau mã lệnh S S.begin : Nhãn định lệnh sinh cho S * Dịch biểu thức logic lệnh điều khiển Nếu E có dạng a