Bài giảng Xây dựng chương trình dịch: Bài 2 - Nguyễn Thị Thu Hương

Bài giảng "Xây dựng chương trình dịch - Bài 2: Các giai đoạn chính của chương trình dịch" cung cấp cho người học các kiến thức: Các giai đoạn của trình biên dịch, phân tích từ vựng, phân tích cú pháp, phân tích ngữ nghĩa, sinh mã trung gian, các vấn đề thiết kế bộ sinh mã đích. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Xây dựng chương trình dịch: Bài 2 - Nguyễn Thị Thu Hương 21/1/2010 Các giai đoạn của trình biên dịch Bài 2. Các giai đoạn chính của ủ chương trình dịch „ Phân tích từ vựng (Lexical Analysis Scanner) Lần lượt xem xét từng ký tự của chương trình nguồn, ồ phân hâ nhóm hó chúng hú thành hà h những hữ đơn đ vịị cú pháp gọi là từ tố (token) „ Phân tích cú pháp (Syntax Analysis) Dãy token do bộ phân tích từ vựng đưa ra được kiểm tra xem có đúng cú pháp không? 1 Các thành phần chính của trình biên dịch 3 Các giai đoạn của trình biên dịch Phân tích ngữ nghĩa (Semantic Analysis) phân tích ý nghĩa từng lệnh của ngôn ngữ nguồn. g „ Sinh mã trung gian (Intermediate Code Generation)thường là mã 3 địa chỉ. Mã trung gian không phụ thuộc máy nên dễ tối ưu. „ 2 4 1 21/1/2010 Các giai đoạn của trình biên dịch Pha 1:Phân tích từ vựng Sinh mã đích: Sinh ra các lệnh máy để thực hiện thao tác. „ Tối ưu mã: Thực hiện với mã trung gian và cả mã đích nhằm làm cho chương trình hiệu quả hơn. „ „ Bộ từ vựng:Chương trình làm nhiệm vụ phân tích từ vựng „ Các công g việc của bộ từ vựng g Nhóm các ký tự thành từ tố Từ tố :đơn vị cú pháp được xử lý trong quá trình dịch như một thực thể không thể chia nhỏ hơn nữa Nhóm các từ tố theo loại. 5 7 Một số loại từ tố Quá trình dịch một ộ câu lệnh 6 8 2 21/1/2010 Pha 2: Phân tích cú pháp Ví dụ: câu lệnh a = b + c Trình biên dịch kiểm tra xem những từ tố mà bộ từ vựng nhận biết được có kết hợp thành những g câu lệnh ệ đúng g cú p pháp p không „ Do bộ phân tích cú pháp đảm nhận „ 9 Pha 2: Phân tích cú pháp „ 11 Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp Đầu ra của bộ phân tích cú pháp: „ … Cây phân tích cú pháp (nếu có) … Thông báo lỗi nếu ngược lại „ Cú pháp … Cấu trúc văn phạm của một ngôn ngữ Bộ phân tích cú pháp cần đưa ra phân tích cho mỗi câu của ngôn ngữ (chương trình) „ BNF : Dạng chuẩn để mô tả văn phạm của ngôn ngữ „ Sơ đồ cú pháp:cách mô tả văn phạm trực quan dưới dạng đồ thị định hướng „ Việc xây dựng được cây phân tích cú pháp chứng tỏ chương trình đúng về cú pháp 10 12 3 21/1/2010 Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp Các luật của BNF cũng như văn phạm hình thức sử dụng 2 loại ký hiệu ở vế phải „ Ký hiệu kết thúc : „ … Từ tố ố của ủ ngôn ô ngữ ữ xuất hiện ở vế trái … Không „ Ký hiệu không kết thúc … Ký hiệu trung gian của văn phạm để mô tả cấu trúc ngôn ngữ … Cần xuất hiện ở vế trái của ít nhất một luật … Bao trong cặp Bằng cách áp dụng liên tục các luật mô tả văn phạm „ Nếu bộ PTCP chuyển thành công từ xâu vào thành ký hiệu đầu thì xâu vào đúng cú pháp „ Ngược lại, câu được xem xét không đúng cú pháp „ 13 Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp „ Khái niệm và kỹ thuật phân tích cú pháp Ký hiệu đầu : 15 Khái niệm và kỹ thuật phân tích cú pháp „ Vấn đề quan trọng nhất khi xây dựng trình biên dịch là xây dựng một văn phạm „ Bao gồm đầy đủ các cấu trúc của một chương trình „ Không thể tạo nên một luật nào khác … Ký hiệu không kết thúc ở mức cao nhất … Xuất hiện ở gốc cây cú pháp 14 16 4 21/1/2010 Khái niệm và kỹ thuật phân tích cú pháp Pha 4: Sinh mã trung gian „ Văn „ Chương trình với mã nguồn được chuyển sang chương trình tương đương g trong g ngôn g ngữ g trung gg gian bằng bộ sinh mã trung gian. „ Mã trung gian là mã máy độc lập tương tự với tập lệnh trong máy. phạm phải không nhập nhằng „ Nếu ế văn phạm nhập nhằng, ằ xây dựng được nhiều hơn 1 cây cho mỗi câu được đưa ra phân tích 17 19 Ưu điểm của mã trung gian Pha 3: Phân tích ngữ nghĩa „ Duyệt cây cú pháp của chương trình để xem mọi cấu trúc ngữ nghĩa hĩ có ó đú đúng khô không „ Chương trình đúng cả về cú pháp và ngữ nghĩa mới sinh mã được 18 1. Thuận lợi khi cần thay đổi cách biểu diễn chương trình đích. 2. Có thể tối ưu hóa mã độc ộ lập ập với máy đích cho dạng biểu ể diễn trung gian. 3. Giảm thời gian thực thi chương trình đích vì mã trung gian có thể được tối ưu 20 5