Chương trình dịch - 2

Mục tiêu:

Chương 1

TỔNG QUAN VỀ CHƯƠNG TRÌNH DỊCH

Giúp sinh viên có khả năng:

- Hiểu được các khái niệm cơ bản: Chương trình dịch, hệ thống thông dịch, biên dịch.

- Hiểu được môi trường của một chương trình dịch.

- Hiểu được cấu trúc của một chương trình dịch

- Hiểu được các giai đoạn của chương trình dịch: vị trí, nhiệm vụ.

Có thể bạn quan tâm!

• Chương trình dịch - 1
• Phân Tích Ngữ Nghĩa (Semantic Analysis)
• Nhắc Lại Một Số Kiến Thức Về Văn Phạm – Ngôn Ngữ - Automat
• Thẻ Từ, Mẫu Từ Vựng Và Trị Từ Vựng (Từ Vị)

Xem toàn bộ 224 trang tài liệu này.

- Biết được các đặc trưng cơ bản của ngôn ngữ lập trình bậc cao.

Nội dung chính:

- Khái niệm chương trình dịch.

- Môi trường của chương trình dịch.

- Các giai đoạn của chương trình dịch.

- Nhóm các giai đoạn của chương trình dịch.

- Các đặc trưng cơ bản của ngôn ngữ lập trình bậc cao.

1.1. Mở đầu

Các ngôn ngữ lập chương trình thực chất là các ngôn ngữ dùng để biểu diễn giải thuật thực hiện một bài toán nào đó. Để thuận tiện và đơn giản cho quá trình viết chương trình người ta xây dựng các ngôn ngữ lập trình bậc cao như Algol, Pascal, C, C++, Visual Fox, Visual Basic, … Hiện nay có rất nhiều ngôn ngữ lập trình bậc cao. Những ngôn ngữ lập trình bậc cao có chung đặc tính là không phụ thuộc vào máy tính, gần gũi với toán học và các lĩnh vực hoạt động của con người. Chẳng hạn Visual

Fox là ngôn ngữ vừa gần gũi, thích hợp với công việc quản lý sản xuất, kinh doanh vừa đủ chặt chẽ để diễn đạt các công thức toán học và mang tính logic cao.

Viết chương trình bằng ngôn ngữ máy có ưu điểm cơ bản là chương trình thực hiện nhanh, vì khi nạp chương trình vào máy tính nó chạy được ngay không cần giai đoạn dịch, song nó có những nhược điểm cơ bản sau:

- Ngôn ngữ máy rất xa lạ với ngôn ngữ toán học và ngôn ngữ tự nhiên của con người.

- Dễ sinh ra lỗi, song lại khó phát hiện lỗi, mất nhiều thời gian hiệu chỉnh chương trình.

- Khó diễn đạt rò ràng giải thuật.

- Phụ thuộc vào máy tính, không thuận tiện cho việc giao lưu phổ biến các chương trình, các giải thuật toán tốt, dẫn đến sự lãng phí về lao động xã hội.

Những lý do nêu trên là nguyên nhân thúc đẩy việc sản sinh ra nhiều ngôn ngữ lập trình bậc cao khác nhau. Trái ngược với ngôn ngữ máy, ngôn ngữ lập trình bậc cao có các đặc điểm sau:

- Gần gũi với ngôn ngữ toán học và ngôn ngữ tự nhiên của con người.

- Không phụ thuộc vào máy cụ thể, do vậy dễ phổ biến, dễ giao lưu trao đổi hợp tác giữa những người làm chương trình, tăng hiệu quả lao động của xã hội.

- Ít sinh ra lỗi, cho phép phát hiện lỗi nhanh và do vậy tiết kiệm thời gian hiệu chỉnh chương trình.

Về nguyên tắc, các máy tính chỉ có thể thực hiện được các chương trình viết bằng ngôn ngữ máy. Vì vậy, các chương trình viết bằng các ngôn ngữ lập trình bậc cao muốn máy tính thực hiện được phải trải qua giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy. Giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy được gọi là giai đoạn dịch chương trình hay ngắn gọn là dịch. Chương trình thực hiện giai đoạn dịch gọi là chương trình dịch (Compiler). Đối với chương trình dịch thì các chương trình viết bằng ngôn ngữ lập trình bậc cao là dữ liệu đầu vào và được gọi là chương trình nguồn; chương trình là kết quả dịch (đầu ra) của chương trình dịch được gọi là chương trình đích. Ngôn ngữ dùng để viết chương trình nguồn ta gọi là ngôn ngữ nguồn. Ngôn ngữ dùng để viết chương trình đích ta gọi là ngôn ngữ đích.

Trong thực tế với mục đích tận dụng các chương trình tốt đã có, viết bằng các ngôn ngữ lập trình bậc cao khác nhau; người ta thường dịch các chương trình nguồn ra ngôn ngữ trung gian sau đó ghép chúng lại thành một chương trình viết bằng cùng một ngôn ngữ sau đó mới chuyển sang ngôn ngữ máy. Thậm chí có những chương trình được viết bằng nhiều ngôn ngữ lập trình khác nhau, người ta gọi là chương trình viết ở dạng hợp ngữ. Hình 1.1 mô tả việc dịch các chương trình viết bằng các ngôn ngữ khác nhau sang chương trình viết bằng ngôn ngữ trung gian Assembly.

Assembly

Chương trình Trong C

Chương trình Trong C++

Chương trình Trong Assembly

Chương trình trong Pascal

Hình 1.1. Mô tả việc dịch các chương trình sang Assembly

- Về bản chất, mọi chương trình viết bằng một ngôn ngữ lập trình bậc cao đều được coi là một dãy ký hiệu và được gọi là xâu vào hay văn bản vào. Do vậy, quá trình dịch có thể coi là quá trình biến đổi một xâu vào hay văn bản vào viết ở ngôn ngữ này thành một xâu ra hay văn bản ra viết bằng ngôn ngữ khác sao cho nó bảo toàn “ngữ nghĩa” (Semantic) của xâu vào (chương trình tương đương).

Vấn đề bảo toàn “ngữ nghĩa” của văn bản vào là vấn đề chưa được xác định rò ràng trong lý thuyết chương trình dịch. Một số tác giả đã đưa ra khái niệm bảo toàn “ngữ nghĩa” như sau: Hai xâu được gọi là bản dịch của nhau nếu khi dịch sang ngôn ngữ thứ ba thì chúng có kết quả như nhau.

1.2. Chương trình dịch

1.2.1. Các khái niệm

1) Khái niệm chương trình dịch

Chương trình dịch 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), 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). Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chương trình nguồn để thông báo lại cho người viết chương trình.

Chương trình nguồn

Chương trình dịch

Chương trình đích

Báo lỗi

Hình 1.2. Sơ đồ một chương trình dịch

2) Biên dịch và thông dịch

Người ta chia chương trình dịch thành hai dạng là trình biên dịch và trình thông dịch.

a) Trình biên dịch (Compiler)

Trong hệ thống biên dịch, chương trình dịch đọc toàn bộ chương trình nguồn và dịch toàn bộ chương trình nguồn sang chương trình đích.

- Chương trình nguồn viết bằng ngôn ngữ lập trình bậc cao.

- Chương trình đích viết bằng ngôn ngữ máy hoặc assembly hoặc ngôn ngữ trung gian.

Chương trình đích cần có khả năng chạy độc lập trên tất cả các máy mà không cần chương trình dịch nữa.

Ưu điểm của chương trình dịch là chương trình chạy nhanh. Nhược điểm của nó là việc thiết kế và cài đặt phức tạp.

Ví dụ như chương trình dịch của Turbo C hay Turbo Pascal.

b) Trình thông dịch (Interpreter)

Trong hệ thống thông dịch, chương trình dịch đọc vào từng câu lệnh, dịch sang chương trình đích rồi thực hiện ngay câu lệnh đó.

Ví dụ như chương trình dịch của hệ điều hành DOS khi thực hiện lệnh tại dấu nhắc lệnh hay chương trình dịch của hệ quản trị cơ sở dữ liệu Visual Foxpro khi thực hiện lệnh tại cửa sổ lệnh.

1.2.2. Mô hình phân tích - tổng hợp của một chương trình dịch

Chương trình dịch thường bao gồm hai quá trình: phân tích và tổng hợp

- Phân tích  đặc tả trung gian

- Tổng hợp  chương trình đích

Chương trình nguồn

Đặc

tả trung gian

Chương trình đích

Phân tích Tổng hợp

Hình 1.3. Mô hình phân tích - tổng hợp

Trong quá trình phân tích chương trình nguồn sẽ được phân rã thành một cấu trúc phân cấp, thường là dạng cây - cây cú pháp (parsing tree).

Ví dụ 1.1:

Câu lệnh gán position := initial + rate * 60 có cây phân tích cú pháp hình 1.4.

stmt

id

position

assign

:=

expr

expr

operator

expr

id expr

expr

+ operator

initial

id

*

rate

number

60

Hình 1.4. Cây phân tích cú pháp

1.2.3. Môi trường của chương trình dịch

Ngoài chương trình dịch, còn phải cần dùng nhiều chương trình khác nữa để tạo ra một chương trình đích có thể thực thi được (executable). Các chương trình đó gồm: bộ soạn thảo, bộ tiền xử lý, trình dịch hợp ngữ, bộ tải và liên kết. Hệ thống các chương trình này giúp cho người lập trình có được một môi trường hoàn chỉnh để phát triển các ứng dụng.

- Bộ soạn thảo: cho phép soạn thảo chương trình nguồn.

- Bộ tiền xử lý: Xử lý một số chức năng ban đầu để tạo ra một chương trình nguồn hoàn chỉnh từ một chương trình nguồn khung (nguyên thuỷ) ban đầu. Ví dụ, một chương trình nguồn có thể được phân thành các module và được lưu trong các tập tin riêng rẽ. Công việc tập hợp lại các tập tin này thường được giao cho một chương trình riêng biệt gọi là bộ tiền xử lý (preprocessor). Bộ tiền xử lý có thể "bung" các ký hiệu tắt được gọi là các macro thành các câu lệnh của ngôn ngữ nguồn. Ngoài ra, bộ tiền xử lý còn cho phép bỏ qua các chú thích.

- Chương trình dịch: cho phép kiểm lỗi chương chương trình, dịch ra ngôn ngữ đích. Dịch ra ngôn ngữ đích nhưng đang ở dạng định vị lại được hay có thể ở dạng ngôn ngữ assembly. Ngoài ra, chương trình đích được tạo ra bởi chương trình dịch có thể cần phải được xử lý thêm trước khi chúng có thể chạy được. Thông thường, chương trình dịch chỉ tạo ra mã lệnh hợp ngữ (assembly code) để trình dịch hợp ngữ (assembler) dịch thành dạng mã máy định vị lại được.

- Tải/liên kết: Tải chương trình vào bộ nhớ máy tính và liên kết với một số thủ tục trong thư viện hệ thống để tạo thành một chương trình mã máy tuyệt đối và thực thi được trên máy tính.

Hình sau trình bày sơ đồ cấu trúc môi trường của một chương trình dịch trong một hệ thống biên dịch điển hình.

Chương trình nguồn khung (nguyên thuỷ)

Bộ tiền xử lý

Chương trình nguồn

Trình biên dịch

Chương trình đích hợp ngữ

Trình dịch hợp ngữ

Mã máy khả tái định vị

Thư viện, Tập tin đối tượng định vị lại được

Trình tải / Liên kết

Mã máy tuyệt đối

Hình 1.5. Cấu trúc môi trường của chương trình dịch

1.3. Phân tích chương trình nguồn

Quá trình phân tích chương trình nguồn, về mặt logic có thể chia thành ba giai đoạn phân tích: Phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa.

1.3.1. Phân tích từ vựng (Lexical Analysis)

Trong một chương trình dịch, giai đoạn phân tích từ vựng sẽ đọc chương trình nguồn từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các từ vị (lexeme) và tìm ra các thẻ từ (token) tương ứng cho các từ vị đó.

Thẻ từ là dạng ngữ pháp của từ vị; hay nói một cách khác, thẻ từ là tập hợp xâu các ký tự kết thúc (từ vị) có chung nhau luật ngữ pháp sinh ra các từ vị đó và mỗi thẻ từ thường được đặt bởi một tên để định danh (phân biệt các thẻ từ với nhau) .

Mỗi thẻ từ sẽ có một mẫu từ vựng (pattern) để xác định một từ vị là thuộc thẻ từ nào; hay nói cách khác, mẫu từ vựng của thẻ từ là luật ngữ pháp sinh ra các từ vị của thẻ từ đó.

Từ vị của một thẻ từ là một từ của thẻ từ và nó phải thỏa mãn mẫu từ vựng của thẻ từ đó.

Nhờ vào mẫu của thẻ từ, chương trình dịch trong giai đoạn phân tích từ vựng sẽ phân tích để xác định ra các thẻ từ trả về cho giai đoạn phân tích cú pháp hoặc báo lỗi.

Ví dụ 1.2:

a) Trong một văn phạm có các luật sinh: 1. digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Thì:

+ digit là thẻ từ (token);

+ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern) của thẻ từ digit;

+ Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một từ vị (lexeme) của thẻ từ digit.

2. letter  A | B | ...| Z | a | b |...| z Thì:

+ letter là thẻ từ (token);

+ A | B | ...| Z | a | b |...| z là mẫu từ vựng (pattern) của thẻ từ letter;

+ Mỗi chữ cái La tinh: A, B, C, …, Z, a, b, c, …, z là một từ vị (lexeme) của thẻ từ letter.

3. id  (letter | _ )(letter | digit | _ )* Thì:

+ id là thẻ từ (token);

+ (letter | _ )(letter | digit | _ )* là mẫu từ vựng (pattern) của thẻ từ id;

+ A, X1B, max_1a23 là 3 từ vị (lexeme) của thẻ từ id.

b) Trong một văn phạm có các luật sinh:

1. Stmt  id := expr

2. Expr  expr + exprexpr - exprexpr /exprexpr * expridnumber 3. Relop  +-*/

4. Assign  :=

Quá trình phân tích từ vựng cho câu lệnh gán position:= initial + rate * 60 sẽ tách thành các từ vị (lexeme) và trả về các thẻ từ (token) như sau:

1. position là từ vị của thẻ từ tên id

2. := là từ vị của thẻ từ phép gán assign

3. initial là từ vị của thẻ từ tên id

4. + là từ vị của thẻ từ phép toán operator

5. rate là từ vị của thẻ từ tên id

6. * là là từ vị của thẻ từ phép toán operator

7. 60 từ vị của thẻ từ số nguyên number

Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua.

1.3.2. Phân tích cú pháp (Syntax Analysis)

Giai đoạn phân tích cú pháp sẽ dựa vào bộ luật cú pháp để tìm cấu trúc cú pháp của chương trình nguồn. Các cấu trúc cú pháp này sẽ tương ứng với một biểu thức, một phép gán, một khai báo, câu lệnh điều kiện, câu lệnh lặp, … Trong nhiều phương pháp phân tích thì kết quả trả về không nhất thiết phải là cây cú pháp.

Giai đoạn phân tích cú pháp thực hiện công việc nhóm các thẻ từ của chương trình nguồn thành các ngữ đoạn văn phạm (grammatical phrase), mà sau đó sẽ được chương trình dịch tổng hợp ra thành phẩm. Thông thường, các ngữ đoạn văn phạm này được biểu diễn bằng dạng cây phân tích cú pháp (parsing tree).

Về bản chất thì phân tích cú pháp sẽ cho ta thông tin về cú pháp của chương trình nguồn và được thể hiện dưới dạng cây phân tích cú pháp. Với ngôn ngữ được đặc tả bởi các luật sinh thì giai đoạn phân tích cú pháp dựa vào các luật sinh để xây dựng cây phân tích cú pháp.

Ví dụ 1.3:

Với câu lệnh gán position:= initial + rate * 60, giả sử bộ luật cú pháp của ngôn ngữ để nhận biết câu lệnh gán được đặc tả bởi các luật sinh sau:

Stmt  id := expr

Expr  expr + exprexpr - exprexpr /exprexpr * expridnumber Operator  +-*/

Assign  :=

Thế thì cây phân tích cú pháp của ví dụ trên sẽ được xây dựng như sau: stmt

id position

assign

:=

expr

expr

expr

expr

operator

id

expr

+ operator

initial

id

*

rate

number

60

Hình 1.6. Một cây phân tích cú pháp