Lý thuyết automata và ngôn ngữ hình thức

Khái niệm: Chương trình dịch (compiler) là một chương trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language - SL) - rồi dịch nó thành một chương trình tương đương ở một ngôn ngữ khác - ngôn ngữ đích (target languague - TL).
Nội dung trích xuất từ tài liệu:
Lý thuyết automata và ngôn ngữ hình thức Principles of compilers GIẢNG VIÊN: TS. HÀ CHÍ TRUNG BỘ MÔN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 1 25-04-12 Giới thiệu chung  Cơ sở môn Chương trình dịch:  Lý thuyết automata và ngôn ngữ hình thức;  Cấu trúc dữ liệu và giải thuật;  Lập trình (C, C#...)  Tiêu chuẩn đánh giá sinh viên:  Báo cáo đề tài;  Chuyên cần, thường xuyên, thi hết môn;©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 2 25-04-12 Giới thiệu chung  Tài liệu tham khảo: 1. Bài giảng của giảng viên; 2. A.V. Aho, M. Lam, R. Sethi, J.D.Ullman. Compilers: Principles, Technique and Tools, 2nd Edition – Addison-Wesley, 2007. 3. A.W. Appel. Modern Compiler Implementation in C – Cambrige University Press, 2004. 4. S. Muchnick. Advanced Compiler Design and Implementation. Morgan-Kaufmann Publishers, 2007. 5. K. Cooper, L. Torczon. Engineering a Compiler. - Morgan- Kaufman Publishers, 2005. 6. Phạm Hồng Nguyên. Giáo trình chương trình dịch 2nd Edition, NXB ĐHQG Hà Nội, 2009.©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 3 25-04-12 Bài 1. Giới thiệu về chương trình dịch 1.1. Khái niệm về compiler 1.2. Vị trí của compiler trong LPS 1.3. Các giai đoạn làm việc của 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©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 4 25-04-12 Bài 1. Giới thiệu về chương trình dịch 1.1. Khái niệm về compiler 1.2. Vị trí của compiler trong LPS 1.3. Các giai đoạn làm việc của 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©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 5 25-04-12 1.1. Khái niệm về compiler  Khái niệm: Chương trình dịch (compiler) là một chương trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language - SL) - rồi dịch nó thành một chương trình tương đương ở một ngôn ngữ khác - ngôn ngữ đích (target languague - TL). Chương Ngôn ngữ trình nguồn Compiler đích (HLL)  Chương trình dịch là một dạng của bộ xử lý ngôn ngữ (languague proccessor)©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 6 25-04-12 1.1. Khái niệm về compiler  Quy ước viết tắt:  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);  ...©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 7 25-04-12 1.1. Khái niệm về compiler  Vấn đề trọng tâm:  Nguyên lý làm việc của cá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 và dịch tự động);  Chuyển đổi từ ngôn ngữ lập trình này sang ngôn ngữ khác.  Ứng dụng:  Hiểu từng ngôn ngữ, điểm mạnh điểm yếu của nó;  Lựa chọn ngôn ngữ và chương trình dịch thích hợp;  Phân biệt được công việc do CTD thực hiện và do CT ứng dụng thực hiện;  Thực hiện cá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ác câu lệnh  Áp dụng trong NLP, dịch tự động, tóm tắt văn bản…©TS. Hà Chí Trung, ...