zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: Le Van Vi | Ngày: | Loại File: PDF | Số trang:48

Báo xấu

80
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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, Khoa CNTT - HVKTQS 8 25-04-12
1.1. Khái niệm về compiler  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 số lần duyệt: Duyệt đơn, duyệt nhiều lần.  Theo mục đích: Tải và chạy, gỡ rối, tối ưu, chuyển đổi ngôn ngữ, chuyển đôỉ định dạng…  Theo độ phức tạp của chương trình nguồn và đích:  Asembler (chương trình hợp dịch): Dịch từ ngôn ngữ asembly ra ngôn ngữ máy;  Preproccessor (tiền xử lý): Dịch từ ngôn ngữ cấp cao sang ngôn ngữ cấp cao khác (thực chất là dịch một số cấu trúc mới sang cấu trúc cũ);  Compiler (biên dịch): dịch từ ngôn ngữ cấp cao sang ngôn ngữ cấp thấp. ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 9 25-04-12
1.1. Khái niệm về compiler  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 từng lệnh và phân tích rồi thực hiện nó (VD: cmd, HQTCSDL Foxpro), hoặc chuyển sang một IL + đọc CT ở IL này và thực hiện từng câu lệnh. IL được gọi là ngôn ngữ của một máy ảo (VM) - chương trình thông dịch thực hiện ngôn ngữ này;  Biên dịch (compiler): toàn bộ chương trình nguồn được trình biên dịch chuyển sang chương trình đích ở dạng ML. Chương trình đích này có thể chạy độc lập trên máy mà không cần hệ thống biên dịch nữa.  Theo lớp văn phạm: LL(1) (LL – Left to right, leftmost) LR(1) (LR – letf to right, right most) ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 10 25-04-12
1.1. Khái niệm về compiler  Thông dịch: Output (executable Chương trình nguồn Trình thông dịch machine-language (SP) (interpreter) program) Dữ liệu vào (input) Thông báo lỗi (Error messages )  Biên dịch: Chương trình nguồn Trình biên dịch Chương trình đích (SP on the SL) (Compiler) (TP on the TL) Thông báo lỗi (Error messages ) ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 11 25-04-12
1.1. Khái niệm về compiler  VD: Hệ thống dịch Java kết hợp cả thông dịch và biên dịch. Mã nguồn Java được dịch ra dạng Bytecode. File này được một trình thông dịch gọi là máy ảo Java thực hiện. Source Intermediate Compiler program program Input data JVM output ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 12 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 13 25-04-12
1.2. Vị trí của compiler trong LPS  Để tạo tra một chương Skeletal source program trình đích có khả năng thực Bộ tiền xử lí (Preprocessor) thi (excutable) thì ngoài trình biên dịch ta phải có Chương trình nguồn (Source program) thêm một số chương trình Trình biên dịch (Compiler) khác nữa. Ct hợp ngữ đích (Target assembly program)  Sơ đồ bên mô tả ngữ cảnh của một trình biên dịch Trình dịch hợp ngữ (Assembler) trong một hệ thống xử lí Relocatable machine code ngôn ngữ (LPS: language- (Library Trình tải/liên kết (Loader/link- processing system) hay môi editor) object files) trường biên dịch. Absolute machine code ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 14 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 15 25-04-12
1.3. Các giai đoạn làm việc của compiler  Các giai đoạn làm việc của compiler có thể phân chia theo tính logic của công việc hoặc theo thời gian làm việc.  Cấu trúc theo thời gian: lần lượt hay đồng thời.  Duyệt một lần: một số thành phần của chương trình được thực hiện đồng thời. Bộ phân tích cú pháp đóng vai trò trung tâm, điều khiển cả chương trình.  Duyệt nhiều lần: các thành phần trong chương trình được thực hiện lần lượt và độc lập với nhau. Qua mỗi một phần, kết quả sẽ được lưu vào thiết bị lưu trữ ngoài để lại được đọc vào cho bước tiếp theo.  Cấu trúc logic: 2 giai đoạn: analysis (front end) và synthesis (back end), chia làm nhiều pha làm việc. ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 16 25-04-12
1.3. Các giai đoạn làm việc của compiler Chương trình nguồn (Source program) analysis Phân tích từ vựng (Lexical analyzer) (front end) Phân tích cú pháp (Syntax analyzer) Phân tích ngữ nghĩa (Semantic analyzer) Quản lí bảng kí tự Quản lí lỗi (Symbol-table manager) Sinh mã trung gian (Error handler) (Intermediate code generator) Tối ưu mã (Code optimizer) synthesis Sinh mã (back end) (Code generator) Chương trình đích (Target program) ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 17 25-04-12
1.3. Các giai đoạn làm việc của compiler  Modern Compiler Implementation in C – A.W. Appel - Cambrige University Press. ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 18 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 19 25-04-12
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 ra thành các từ tố (token);  Cũng như NL, PL được xây dựng dựa trên bộ từ vựng;  Để xây dựng một CTD, hệ thống phải tìm hiểu tập từ vựng của SL và phân tích để biết được từng loại từ vựng và các thuộc tính của nó. ©TS. Hà Chí Trung, Khoa CNTT - HVKTQS 20 25-04-12

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.