MỞ ĐẦU Từ ngàn xƣa con ngƣời muốn giao tiếp với nhau phải dùng ngôn ngữ, vậy ngƣời giao tiếp với máy tính tất nhiên cũng phải thông qua ngôn ngữ. Con ngƣời muốn máy tính thực hiện công việc, thì phải viết các yêu cầu đƣa cho máy bằng ngôn ngữ máy có thể hiểu đƣợc. Việc viết các yêu cầu gọi là lập trình. Ngôn ngữ dùng để lập trình đƣợc gọi là ngôn ngữ lập trình.
Việc viết chƣơng trình sẽ dễ dàng và tự nhiên hơn nếu ngôn ngữ lập trình gần với cách diễn đạt của vấn đề cần giải quyết. Có nghĩa là, ngôn ngữ phải chứa đựng các cấu trúc thuật ngữ - phần tử dùng để miêu tả vấn đề, và không phụ thuộc vào máy tính cụ thể. Những ngôn ngữ lập trình có tính chất nhƣ trên đƣợc gọi là ngôn ngữ bậc cao. Việc phân cấp ngôn ngữ lập trình đƣợc dựa trên cơ sở của tính độc lập với máy tính ngày càng cao của các ngôn ngữ, bao gồm: 1 – Ngôn ngữ máy (machine language) 2 – Hợp ngữ (assembly language) 3 – Ngôn ngữ bậc cao (high level language) Để giải quyết một vấn đề nào đó bằng tin học, lập trình viên phải tạo ra các chƣơng trình nguồn bằng một ngôn ngữ bậc cao – ngôn ngữ gần với ngôn ngữ nói.
Nhƣng máy tính chỉ hiểu, chỉ chấp nhận ngôn ngữ bậc thấp, riêng của mình, đó là chuỗi các số 0 và 1, tuy nhiên chuỗi số đó lại không gần gũi với con ngƣời chút nào. Bởi vì máy tính chỉ có thể hiểu ngôn ngữ máy cho nên một chƣơng trình viết trong ngôn ngữ bậc cao cuối cùng rồi cũng đƣợc dịch sang ngôn ngữ máy. Do đó cần phải có một công cụ để thực hiện việc chuyển đổi này, công cụ đó 8 TIEU LUAN MOI download : skknchat@gmail.com đƣợc gọi là chương trình dịch. Để đáp ứng các nhu cầu về phần mềm ngày càng gia tăng cả về số lƣợng và chất lƣợng, các thiết kế ngôn ngữ lập trình có nhiều thay đổi dẫn đến các ngôn ngữ lập trình trở nên phức tạp hơn.
Vì thế việc thiết kế chƣơng trình dịch cũng tiếp tục thay đổi. Thiết kế và cài đặt chƣơng trình dịch luôn là một chủ đề nghiên cứu và phát triển thiết thực. Do đó mục tiêu chính của đề tài là tìm hiểu về các bƣớc để thiết kế một chƣơng trình dịch và xây dựng một chƣơng trình dịch cho một ngôn ngữ cụ thể tự định nghĩa. Việc xây dựng thành công một chƣơng trình dịch hoàn chỉnh là rất phức tạp, tốn nhiều thời gian và cần nhiều kiến thức.
Luận văn đƣợc trình bày thành bốn chƣơng: + Chƣơng I: Giới thiệu về chƣơng trình dịch. + Chƣơng II: Phân tích từ vựng, cú pháp và phân tích ngữ nghĩa. + Chƣơng III: Các công cụ hỗ trợ xây dựng chƣơng trình dịch. + Chƣơng IV: Xây dựng chƣơng trình dịch cho ngôn ngữ Minipas.Trong quá trình nghiên cứu tác giả khó tránh khỏi những sai sót, rất mong nhận đƣợc nhiều ý kiến đóng góp từ các thầy giáo, cô giáo và các bạn đọc để luận văn đƣợc hoàn thiện hơn.
9 TIEU LUAN MOI download : skknchat@gmail.com Chƣơng 1 - GIỚI THIỆU VỀ CHƢƠNG TRÌNH DỊCH Chƣơng này trình bày kiến thức tổng quan về chƣơng trình dịch, đƣợc trích từ tài liệu tham khảo [2, 4, 5]. Chƣơng trình dịch Chƣơng trình dịch, còn gọi là phần mềm biên dịch, là một chƣơng trình máy tính làm công việc dịch một chuỗi các câu lệnh đƣợc viết bằng một ngôn ngữ lập trình (ngôn ngữ nguồn hay mã nguồn), thành một chƣơng trình tƣơng đƣơng nhƣng ở dƣới dạng một ngôn ngữ mới (gọi là ngôn ngữ đích hay mã đích) và thƣờng là ngôn ngữ ở cấp thấp hơn, nhƣ ngôn ngữ máy. Hầu hết các chƣơng trình dịch sẽ chuyển mã nguồn viết trong một ngôn ngữ bậc cao thành mã đối tƣợng hay ngôn ngữ máy mà có thể đƣợc thi hành trực tiếp bởi một máy tính hay bởi một máy ảo. Dù vậy, việc dịch từ một ngôn ngữ bậc thấp sang một ngôn ngữ bậc cao hơn cũng có thể xảy ra, quá trình này thƣờng đƣợc hiểu nhƣ là bộ biên dịch ngƣợc nếu nó có thể tái tạo lại một chƣơng trình trong ngôn ngữ bậc cao.
Cũng tồn tại các chƣơng trình dịch chuyển đổi từ ngôn ngữ bậc cao này sang ngôn ngữ bậc cao khác, hay là chuyển đổi sang một ngôn ngữ mà nó cần để tiếp tục xử lý về sau, những chƣơng trình dịch nhƣ vậy đƣợc biết đến nhƣ là bộ biên dịch phân tầng. Các bƣớc thiết kế chƣơng trình dịch Chƣơng trình nguồn trong ngôn ngữ lập trình chính là chuỗi các ký tự. Chƣơng trình dịch có nhiệm vụ chuyển chuỗi ký tự này sang chuỗi ký tự khác. Quá trình này bao gồm các quá trình nhỏ hơn và đƣợc đặt tên nhƣ sau: i) Phân tích từ vựng ii) Phân tích cú pháp 10 TIEU LUAN MOI download : skknchat@gmail.com iii) Tổ chức bảng ký hiệu iv) Phân tích ngữ nghĩa v) Sinh mã trung gian vi) Tối ƣu mã vii) Sinh mã đích viii) Phát hiện và thông báo lỗi Đối với một chƣơng trình dịch tồn tại trong thực tế, thứ tự các bƣớc có thể hơi khác so với thứ tự trên.
Có thể một số bƣớc nhỏ kết hợp với nhau tạo thành một bƣớc duy nhất. Phân tích từ vựng Là công việc đọc chƣơng trình nguồn từ trái sang phải (hay được gọi là quá trình quét nguyên liệu) để tách ra thành các thẻ từ (token). Nói cách khác, quá trình phân tích từ vựng là quá trình dịch mà đầu nhập của nó là chuỗi các ký tự, tƣợng trƣng cho chƣơng trình nguồn, đầu ra là các token. Dạng đầu ra này lại là đầu nhập của quá trình phân tích cú pháp về sau.
Các token đƣợc nhận biết bởi quá trình phân tích từ vựng và các thông tin (hay các thuộc tính) của từng token sẽ đƣợc lƣu trong bảng ký hiệu. Tổ chức bảng ký hiệu Bảng ký hiệu là một cấu trúc dữ liệu mà mỗi phần tử là một mẫu tin dùng để lƣu trữ một token đƣợc bộ phân tích từ vựng nhận biết và các thông tin của token đó, bao gồm các trƣờng lƣu giữ ký hiệu và các thuộc tính của nó. Cấu trúc này cho phép chúng ta tìm ra nhanh chóng mẫu tin của mỗi token và cũng có thể lƣu trữ và truy xuất token một cách nhanh chóng. 11 TIEU LUAN MOI download : skknchat@gmail.com Bảng ký hiệu thƣờng xuyên đƣợc truy xuất để thêm hoặc xuất các token, do đó phải thỏa mãn hai điều kiện: 1) Thực hiện nhanh các thao tác thêm token, hoặc các thông tin của token.
2) Có khả năng truy xuất nhanh các thông tin của một token. Bảng ký hiệu có thể đƣợc tổ chức dƣới dạng danh sách liên kết hoặc bảng băm. Phân tích cú pháp Các token đƣợc xuất ra từ quá trình phân tích từ vựng có dạng (loại token, thuộc tính), sẽ là chuỗi nhập vào của bộ phân tích cú pháp. Trong quá trình phân tích cú pháp, các token sẽ đƣợc kiểm tra xem có thể đƣợc biểu diễn bằng cấu trúc cú pháp của ngôn ngữ lập trình cho trƣớc hay không? Nhƣ vậy kết quả của quá trình phân tích cú pháp của một chuỗi nhập là cấu trúc cú pháp đƣợc biểu diễn bằng cấu trúc cây đƣợc gọi là cây cú pháp.
Với một chuỗi token là chuỗi nhập và một tập luật sinh cho trƣớc, bộ phân tích cú pháp sẽ tự động tìm ra cây cú pháp cho chuỗi nhập. Khi cây cú pháp đƣợc xây dựng xong thì quá trình phân tích cú pháp của chuỗi nhập cũng kết thúc thành công. Ngƣợc lại, nếu bộ phân tích cú pháp áp dụng tất cả các luật sinh hiện có, nhƣng không thể xây dựng đƣợc cây cú pháp của chuỗi nhập cho trƣớc thì bộ phân tích cú pháp sẽ ra thông báo rằng chuỗi nhập không đƣợc viết đúng cú pháp của ngôn ngữ lập trình. Phân tích ngữ nghĩa Bộ phân tích ngữ nghĩa sẽ kiểm tra lỗi ngữ nghĩa của chƣơng trình nguồn và thu nhận các thông tin về kiểu cho giai đoạn sau.
Giai đoạn này sử dụng cây 12 TIEU LUAN MOI download : skknchat@gmail.com cú pháp đƣợc xác định trong giai đoạn phân tích cú pháp với mỗi nút trên cây cú pháp kết hợp với một tập thuộc tính để xác định toán tử và toán hạng của các biểu thức và câu lệnh. Một nhiệm vụ quan trọng mà bộ phân tích ngữ nghĩa thực hiện là kiểm tra kiểu dữ liệu. Dựa trên cây cú pháp, bộ phân tích ngữ nghĩa sẽ xử lý từng phép toán. Với mỗi phép toán, nó sẽ xét các toán hạng xem kiểu dữ liệu của chúng có cho phép chúng tham gia vào phép toán đó không? 1.
Sinh mã trung gian Sau giai đoạn phân tích cú pháp và phân tích ngữ nghĩa, một số chƣơng trình dịch sẽ tạo ra một dạng biểu diễn trung gian của chƣơng trình nguồn. Dạng biểu diễn trung gian có rất nhiều loại. Thông thƣờng, ngƣời ta sử dụng dạng "mã máy ba địa chỉ" (three-address code), tƣơng tự nhƣ dạng hợp ngữ cho một máy mà trong đó mỗi vị trí bộ nhớ có thể đóng vai trò nhƣ một thanh ghi. Tối ƣu mã Giai đoạn tối ƣu mã cố gắng cải thiện mã trung gian bằng cách thu giảm một số bƣớc trong mã trung gian để có thể có mã máy thực hiện nhanh hơn.
Sinh mã đích Giai đoạn cuối của chƣơng trình dịch là sinh mã đích. Mã đích có thể là mã máy hay mã hợp ngữ. Các vị trí vùng nhớ đƣợc chọn lựa cho mỗi biến đƣợc chƣơng trình sử dụng. Sau đó, các chỉ thị trung gian sẽ đƣợc dịch lần lƣợt thành chuỗi các chỉ thị mã máy.
13 TIEU LUAN MOI download : skknchat@gmail. Phát hiện và thông báo lỗi Mỗi giai đoạn của quá trình dịch đều có thể gặp lỗi. Tuy nhiên sau khi phát hiện ra lỗi, mỗi giai đoạn phải có cách xử lý lỗi để có thể tiếp tục dịch chƣơng trình, và nhƣ thế cho phép phát hiện thêm nhiều lỗi khác trong chƣơng trình nguồn. Một chƣơng trình dịch cứ phải dừng lại khi phát hiện lỗi sẽ không đƣợc cho là hữu ích.
Mỗi chƣơng trình dịch cũng có cách xử lý lỗi khác nhau, chẳng hạn: - Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Pascal). - Ghi nhận lỗi và tiếp tục quá trình dịch (C). 14 TIEU LUAN MOI download : skknchat@gmail.com Chƣơng 2 - PHÂN TÍCH TỪ VỰNG , CÚ PHÁP VÀ NGỮ NGHĨA Nhƣ Chƣơng 1 đã trình bày, quá trình xây dựng một chƣơng trình dịch gồm tám bƣớc. Trong chƣơng này sẽ đề cập chuyên sâu các bƣớc phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa.
Trƣớc khi đi vào tìm hiểu ba bƣớc trên là nhắc lại kiến thức về ngôn ngữ và văn phạm đƣợc tham khảo từ [1]. Ngôn ngữ và văn phạm hình thức 2.