- Nghiên cứu tổng quan về chương trình dịch. - Chương 1: Giới thiệu về chương trình dịch. - Chương 2: Phân tích từ vựng, cú pháp và ngữ nghĩa (ngôn ngữ và văn phạm hình thức. - phân tích từ vựng. - phân tích cú pháp. - phân tích ngữ nghĩa). - Chương 3: Các công cụ hỗ trợ xây dựng chương trình dịch (bộ sinh trình phân tích từ vựng FLEX, bộ sinh trình phân tích cú pháp BISON). - Chương 4: Xây dựng chương trình dịch cho ngôn ngữ Minipas.. - Ngôn ngữ lập trình. - Ngôn ngữ máy tính. - Chương trình dịch. - 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. - 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. - 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. - 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 đó 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. - 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 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.. - 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ự. - Phân tích từ vựng. - 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.. - 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?. - 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. - 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.. - Giai đoạn cuối của chương trình dịch là sinh mã đích. - 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.1.1. - Ngôn ngữ. - Ta gọi ngôn ngữ là một tập hợp các chuỗi trên một bảng chữ cái nào đó. - là các ngôn ngữ trên mọi bộ chữ. - cũng là một ngôn ngữ. - Mỗi ngôn ngữ trên bảng chữ cái là một tập con của. - Ngôn ngữ sinh bởi văn phạm: Với văn phạm G có ký hiệu bắt đầu S . - để định nghĩa L (G ) là ngôn ngữ được sinh ra bởi G . - Trong luận văn, sẽ chỉ đề cập đến hai lớp văn phạm là văn phạm chính quy được sử dụng trong bước phân tích từ vựng và văn phạm phi ngữ cảnh được sử dụng trong bước phân tích cú pháp.. - Văn phạm G. - Vai trò của bộ phân tích từ vựng. - Phân tích từ vựng là giai đoạn đầu tiên của mọi chương trình dịch. - Vai trò của bộ phân tích cú pháp. - Bộ phân tích cú pháp nhận chuỗi các token được xuất ra từ bộ phân tích từ vựng và xác nhận rằng chuỗi này có thể được sinh ra từ văn phạm của ngôn ngữ nguồn hay không bằng cách tạo ra cây cú pháp cho chuỗi.. - Mỗi ngôn ngữ lập trình đều có các quy tắc diễn tả cấu trúc cú pháp của các chương trình định dạng đúng. - Các chiến lƣợc phân tích cú pháp. - Có hai chiến lược để thực hiện việc phân tích cú pháp:. - Chiến lược phân tích cú pháp từ trên xuống (top – down),. - Chiến lược phân tích cú pháp từ dưới lên (bottom – up).. - Chiến lƣợc phân tích từ trên xuống. - P , S ) và một câu cần phân tích w . - Một trong số các thuật toán sử dụng chiến lược phân tích từ trên xuống là thuật toán phân tích cú pháp Earley 1. - Earley là một thuật toán thuộc loại phân tích cú pháp từ trên xuống và xây dựng các dẫn xuất trái nhất của chuỗi ký tự nhập. - Thuật toán phân tích cú pháp Earley. - Chiến lƣợc phân tích dƣới lên. - Một trong số các thuật toán sử dụng chiến lược phân tích từ trên xuống là thuật toán phân tích cú pháp CYK 2 . - Đây là một thuật toán phân tích cú pháp trên văn phạm phi ngữ cảnh tổng quát. - Thuật toán CYK sẽ đi xây dựng một bảng phân tích cú pháp ij (có hình một tam giác), mỗi phần tử ij với 1 i n và 1 j n i 1 có các giá trị là một tập con của N. - Chuỗi nhập w thuộc ngôn ngữ L (G ) nếu S t 1 n . - Thuật toán phân tích cú pháp CYK. - Khi viết một chương trình bằng một ngôn ngữ lập trình nào đó, ngoài việc quan tâm đến cấu trúc cú pháp của chương trình, ta còn phải chú ý đến ý nghĩa của chương trình. - Trên thực tế, đã có rất nhiều công cụ có khả năng sinh ra bộ phân tích từ vựng và bộ phân tích cú pháp. - Johnson được ra đời sớm hơn, có nhiệm vụ sinh ra trình phân tích cú pháp.. - Bộ sinh trình phân tích từ vựng Flex 3.2.1. - Cấu trúc của một chương trình được viết bằng ngôn ngữ Flex gồm ba phần:. - Việc tạo ra bộ phân tích từ vựng được thực hiện trong ba bước. - Bước đầu là tạo ra chương trình flex.l trong ngôn ngữ Flex. - Các hành vi có liên quan đến các biểu thức chính quy trong flex.l là các chương trình con trong ngôn ngữ C và chúng được chuyển thẳng sang chương trình flex-yy.c. - Nó chính là bộ phân tích từ vựng, có khả năng chuyển các dòng nhập thành các token của ngôn ngữ, được xác định bởi các biểu thức chính quy, đã được đặc tả trong ngôn ngữ Flex.. - Bộ sinh trình phân tích cú pháp Bison 3.3.1. - Tương tự như Flex, Bison nhận đầu vào là một tệp bao gồm các đặc tả của một ngôn ngữ. - Từ đó, Bison biên dịch ra bộ phân tích cú pháp bằng mã C để chạy cùng với chương trình. - Cấu trúc của tệp đặc tả ngôn ngữ gồm ba phần:. - Chƣơng 4 - XÂY DỰNG CHƢƠNG TRÌNH DỊCH CHO NGÔN NGỮ MINIPAS Trong chương này, luận văn sẽ định nghĩa một ngôn ngữ tựa Pascal có tên gọi là Minipas và sau đó sử dụng các công cụ đã được giới thiệu trong chương ba để xây dựng bộ phân tích từ vựng và bộ phân tích cú pháp cho ngôn ngữ Minipas.. - Minipas được xây dựng dựa trên ngôn ngữ Pascal. - Đủ dùng để diễn tả một số thuật toán đơn giản cho người mới làm quen với ngôn ngữ lập trình.. - Ngôn ngữ Minipas. - Ngôn ngữ xây dựng được đặt tên là Minipas có một số đặc điểm:. - Có kiểu chương trình con là hàm. - Ngôn ngữ Minipas có phân biệt chữ hoa và chữ thường.. - Xây dựng trình phân tích từ vựng cho Minipas. - Bảng sau liệt kê danh sách các token của ngôn ngữ Minipas và biểu thức chính quy xác định các token đó:. - Xây dựng trình phân tích cú pháp cho Minipas Văn phạm phi ngữ cảnh sinh ngôn ngữ Minipas:. - Xử lý ngữ nghĩa cho ngôn ngữ Minipas. - Khi bộ phân tích cú pháp nhận dạng ra một luật sinh (khai báo, biểu thức, câu lệnh. - Đi sâu vào tìm hiểu ba bước chính là phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa.. - Tìm hiểu về hai thuật toán để phân tích cú pháp là thuật toán Earley và thuật toán CYK.. - Tìm hiểu về các công cụ để xây dựng chương trình dịch là công cụ xây dựng trình phân tích từ vựng Flex và công cụ xây dựng trình phân tích cú pháp Bison.. - Sử dụng các công cụ để viết được một chương trình dịch ở mức độ vừa phải cho một ngôn ngữ tựa Pascal là Minipas. - Chương trình dịch có thể sử dụng làm công cụ lập trình ở mức đơn giản cho người mới làm quen với ngôn ngữ lập trình.. - Cải tiến ngôn ngữ: thêm các hàm chuẩn xử lí các kiểu dữ liệu cơ bản. - Hỗ trợ tham biến cho chương trình con. - [1] Nguyễn Văn Ba (2002), Ngôn ngữ hình thức, Nhà xuất bản Khoa học và kỹ thuật.. - [3] Thái Thuần Thạch (2000), Xây dựng bộ công cụ thực hiện một số thuật toán trong lý thuyết ngôn ngữ hình thức và automat, Luận văn tốt nghiệp, Đại học Bách khoa Đà Nẵng.