Trình biên dịch

và không tất định đóng vai trò quan trọng trong môn học này.

Automat trả lời với tín hiệu YES hoặc NO được gọi là bộ chấp nhận (accepter).

Cho trước một chuỗi nhập, accepter có thể chấp nhận hay từ chối chuỗi nhập.

Input file

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

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

Control Unit

Storage

Output

Hình A.1 miêu tả cấu hình của thiết bị tự động nói chung.

Máy tự động giả định là hoạt động trên một khung thời gian rời rạc. Tại thời điểm bất kỳ, bộ điều khiển ở một trạng thái bên trong , và quét ký hiệu trên file nhập. Trạng thái bên trong của bộ điều khiển ở bước kế tiếp được xác định bởi trạng thái tiếp theo hoặc hàm chuyển dịch.

Hàm chuyển dịch này đưa ra trạng thái kế tiếp, ký hiệu nhập hiện hành và thông tin được ghi trong bộ lưu trữ tạm thời. Trong quá trình chuyển dịch từ một khoảng thời gian đến khoảng kế tiếp, Có thông tin được đưa ra hay bộ lưu trữ tạm bị thay đổi.

Dùng từ “cấu hình” để nói đến ba yếu tố: trạng thái hiện hành của bộ điều khiển, file nhập, và bộ lưu trữ tạm thời. Sự chuyển dịch của thiết bị tự động từ cấu hình này đến cấu hình khác gọi là một dịch chuyển (move).

Chúng ta cần phân biệt giữa automat tất định và không tất định. Thiết bị tự động hay automat tất định xác định cấu hình hiện tại duy nhất. Nếu chúng ta biết được trạng thái bên trong và nội dung của bộ lưu trữ tạm thời, ta có thể đoán trạng thái tiếp theo của automata một cách chính xác. Điều này không đúng vơí automaton không tất định. Tại mỗi thời điểm, automaton không tất định có nhiều sự di chuyển hơn. Vì thế ta chỉ có thể đoán được một tập các trạng thái xảy ra tiếp theo. Mối quan hệ giữa automat tất định và không tất định đóng vai trò quan trọng trong môn học này.

Automat trả lời với tín hiệu YES hoặc NO được gọi là bộ chấp nhận (accepter).

Cho trước một chuỗi nhập, accepter có thể chấp nhận hay từ chối chuỗi nhập.

A.2. Ứng dụng automat trong ngôn ngữ lập trình

Mặc dù chúng ta nhấn mạnh đến tính trừu tượng và tính chính xác của ngôn ngữ hình thức và automat. Nhưng cần phải thấy rằng các khái niệm này có nhiều ứng dụng phổ biến trong khoa học máy tính và thật sự là một chủ đề chung để kết nối nhiều lĩnh vực chuyên môn với nhau. Trong phần này, chúng ta đưa ra những ví dụ để thấy rằng những gì chúng ta tìm hiểu ở đây không chỉ là tập hợp các khái niệm trừu tượng, nhưng là điều gì đó mà nó giúp chúng ta hiểu nhiều điều quan trọng được ứng dụng trong thực tế.

Ngôn ngữ hình thức và văn phạm được dùng một cách rộng rãi trong ngôn ngữ lập trình. Việc mô tả cú pháp của ngôn ngữ thường thấy trong hầu hết các tài liệu về lập trình, nếu viết một trình biên dịch, hoặc nếu muốn giải thích về tính chính xác của một chương trình thì một mô tả cụ thể về chương trình là cần thiết . Ví dụ, chúng ta hãy tạo ra một ngôn ngữ nhỏ gần như ngôn ngữ Pascal.

Ví dụ

Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. Văn phạm sau mô tả các định danh của nó theo giả thiết này.

<id>

	<letter><rest>,
<rest>		<letter><rest>\|<digit><rest>\|
<letter>		a\|b\|…
<digit>		0\|1…

<id>, <letter>, <digit>, và <rest> là các biến a, b, …, 0, 1, … là những ký tự kết thúc

Một dẫn xuất cho định danh a0 l

=> a <rest>

=> a <digit> <rest>

=> a0 <rest>

=> a0

Định nghĩa ngôn ngữ lập trình thông qua văn phạm thì khá phổ biến và rất hữu dụng. Nhưng còn có cách khác để định nghĩa một ngôn ngữ lập trình mà thích hợp trong nhiều trường hợp. Ví dụ, ta mô tả một ngôn ngữ bằng một bộ chấp nhận (accepter), xem một chuỗi được chấp nhận là một phần của ngôn ngữ. Để hiểu rò ràng hơn về vấn đề này, cần có vài định nghĩa hình thức về một automat.

Một Automat có thể được biểu diễn bởi một đồ thị với các nút là các trạng thái nội, các cạnh là các chuyển dịch. Nhãn của các cạnh cho biết điều gì xảy ra (dưới dạng nhập hay xuất) trong khi chuyển dịch. Ví dụ, hình 1.3 trình bày sự chuyển dịch từ trạng thái 1 sang trạng thái 2 xảy ra khi ký hiệu nhập vào là a. Với hình minh họa trực quan này, ta có thể mô tả các định danh của ngôn ngữ theo cách khác.

Ví duï

Hình A.2

Letter

1 2

Digit

Letter or Digi

Letter or Digit

Hình A.3

Hình A.3 là một automat chấp nhận tất cả các định danh hợp lệ. Giả sử rằng khởi dầu Automat ở trạng thái 1: chúng ta quy ước ký hiệu là một mũi tên (không xuất phát từ bất kỳ một nút nào) vào trạng thái này. Chuỗi cần kiểm tra sẽ được đọc từ trái sang phải, mỗi lần một ký hiệu. Nếu ký hiệu đầu tiên là ký tự, automat sẽ chuyển sang trạng thái 2, sau đó các ký hiệu còn lại của chuỗi thì không quan trọng. Trạng thái 2

biểu diễn trạng thái “chấp nhận” của accepter. Ngược lại, nếu ký hiệu đầu tiên được đọc vào là ký số, automat sẽ chuyển sang trạng thái 3 là trạng thái “không chấp nhận” của accepter và sẽ giữ luôn ở trạng thái đó (định danh không hợp lệ). Ở đây chúng ta giả thiết rằng các ký hiệu nhập vào chỉ là ký tự hoặc ký số.

Trình biên dịch và các máy chuyển dịch một chương trình từ ngôn ngữ này tới ngôn ngữ khác cũng dùng các ý tưởng trình bày ở các ví dụ trên. Ngôn ngữ lập trình có thể được định nghĩa một cách chính xác thông qua văn phạm.

PHỤ LỤC B

NGÔN NGỮ LẬP TRÌNH VÀ CHƯƠNG TRÌNH DỊCH

B.1. Các mức khác nhau của ngôn ngữ lập trình

Để cho máy tính có thể thực hiện được thuật toán, cần phải viết thuật toán dưới dạng các dòng "lệnh" theo các quy ước nào đó mà máy tính có thể thực hiện được một cách trực tiếp hoặc viết dưới dạng nào đó để có thể sinh tự động dạng mà máy tính có thể thực hiện trực tiếp. Tập các kí hiệu và các quy tắc viết các lệnh để thể hiện thuật toán được gọi là một ngôn ngữ lập trình (programming language). Các quy tắc để viết chương trình được gọi là cú pháp (syntax) của ngôn ngữ lập trình. Mỗi chương trình sẽ mang một ý nghĩa nhất định mà ta gọi là ngữ nghĩa (semantic) của chương trình.

Có nhiều lớp ngôn ngữ lập trình khác nhau. Theo mức độ hình thức hoá, người ta chia các ngôn ngữ lập trình thành các lớp sau:

Ngôn ngữ máy. Chương trình trong ngôn ngữ máy là dãy các lệnh máy mà CPU có thể thực hiện trực tiếp. Đó là ngôn ngữ lập trình duy nhất mà máy tính "hiểu được". Trong thang bậc các ngôn ngữ giao tiếp với máy tính, đây là mức thấp nhất nhưng hiệu quả của chương trình sẽ là cao nhất vì ta có thể khai thác triệt để khả năng của máy. Tuỳ theo thiết kế về phần cứng, mỗi loại máy tính có một ngôn ngữ máy khác nhau. Các lệnh viết bằng ngôn ngữ máy nói chung ở dạng nhị phân hoặc biến thể của chúng trong hệ đếm 16.

Ví dụ sau đây là một đoạn chương trình viết bằng ngôn ngữ máy của một máy tính dùng bộ vi xử lý Intel 8086.

Bảng B.1. Ngôn ngữ máy

Mã trên hệ nhị phân

Mã hệ 16	Ý nghĩa
1001 0001 0110 0100 0001 0000	A1 64 10	Nạp số 2 byte từ 1064 lên AX
0000 0011 0110 0110 0001 0000	03 65 10	Cộng AX với số 2 byte ở 1066 kết quả để trên AX
1010 0011 0000 0000 0010 1011	A3 00 2B	Chuyển kết quả từ AX về hai byte bắt đầu từ 2B00

Đoạn chương trình này cộng hai số nguyên hai byte ở trong các địa chỉ 1064 và 1066. Kết quả để ở hai byte bắt đầu từ địa chỉ 2B00. Cột đầu là dòng lệnh trong hệ 16, cột giữa là dòng lệnh tương đương trong hệ nhị phân (chính là hình ảnh thực sự của chương trình trong bộ nhớ) và cột bên phải là giải thích. AX là tên một thanh ghi 16 bít trong bộ vi xử lý 8086 .

Qua ví dụ trên, ta thấy ngôn ngữ máy không thật thích hợp cho số đông người sử dụng máy tính vì để viết hoặc hiểu chương trình, người ta phải nhớ rất máy móc các mã số của lệnh mà các dòng số này không có hàm ý rò ràng. Mặt khác do tập lệnh của các bộ xử lý có thể khác nhau nên không thể dùng chương trình viết trên bộ xử lý này chạy trên máy tính dùng bộ xử lý khác loại.

Hợp ngữ (Assembly). Để khắc phục nhược điểm trên của ngôn ngữ máy, người ta đề xuất một ngôn ngữ giao tiếp với máy ở mức độ hình thức hơn gọi là hợp ngữ. Về cơ bản, hợp ngữ có các cấu trúc rất giống với ngôn ngữ máy. Điều khác là trong hợp ngữ có thể viết lệnh dưới dạng mã chữ. Mã chữ thể hiện mã lệnh hoặc các đối tượng trong lệnh (trong ngôn ngữ máy nó là mã lệnh và địa chỉ của đối tượng). Mã lệnh ở dạng chữ thường chính là những từ trong tiếng Anh có ý nghĩa rò ràng, còn đối tượng do ta tự đặt tên phù hợp với ý niệm về đối tượng đó. Ví dụ nếu đoạn chương trình trên dùng để cộng chiều dài và chiều rộng của hình chữ nhật để tính nửa chu vi thì trong hợp ngữ ASM ta chỉ cần viết

Bảng B.2. Chương trình viết trên Assembly

MOV AX CHIEU_DAI

ADD AX CHIEU_RONG

MOV NUA_CHU_VI AX

Từ MOV có gốc từ từ MOVE trong tiếng Anh, có nghĩa là chuyển, còn từ ADD có nghĩa là cộng. Lệnh thứ nhất có nghĩa là nạp số liệu mà ta đặt tên là CHIEU_DAI lên thanh ghi AX, lệnh thứ hai có nghĩa là cộng số trong thanh ghi AX với số liệu mà ta đặt tên là CHIEU_RONG. Ta thấy mặc dù còn cồng kềnh và còn phụ thuộc vào một loại máy tính cụ thể, hợp ngữ dễ dùng hơn rất nhiều so với ngôn ngữ máy.

Để một chương trình viết bằng hợp ngữ chạy được trên máy tính, nó cần phải được dịch ra ngôn ngữ máy. Rò ràng là, mỗi hợp ngữ dùng cho một loại máy nào đó đều cần có trình dịch phù hợp. Khi dịch, hai đối tượng CHIEU_DAI và CHIEU_RONG nói trên sẽ được tự động thay bằng hai địa chỉ cụ thể nào đó không nhất thiết là 1064 và 1066 như ở ví dụ trên. Vì vậy ta cũng không cần phải quan tâm đến sắp xếp địa chỉ cụ thể sau khi dịch xong và chạy chương trình. Chương trình dịch đối với hợp ngữ được gọi là hợp dịch (assembler).

Ngôn ngữ thuật toán (còn gọi là ngôn ngữ thuật toán) . Ta đã thấy ngôn ngữ máy và cả hợp ngữ đều phụ thuộc vào hệ thống lệnh của một loại máy cụ thể. Chúng chưa thật thích hợp cho đông đảo người sử dụng máy tính. Người ta muốn thể hiện thuật toán bằng những lệnh với ý nghĩa thực tế và độc lập với bất cứ loại máy cụ thể nào. Chẳng hạn trong ví dụ trên chỉ cần viết NUA_CHU_VI = CHIEU_DAI + CHIEU_RONG là đủ. Từ đầu những năm 50, người ta đã xây dựng những ngôn ngữ lập trình vạn năng có các lệnh gần với ngôn ngữ tự nhiên và ngôn ngữ toán học. Các ngôn ngữ lập trình này được gọi là các ngôn ngữ lập trình bậc cao (high level programming language). Vì chúng chỉ nhằm vào thể hiện thuật toán độc lập với các máy tính cụ thể nên người ta còn gọi nó là các ngôn ngữ thuật toán (algorithmic language). Cũng như đối với hợp ngữ, mỗi ngôn ngữ lập trình bậc cao trên một loại máy cụ thể đều cần có chương trình dịch để dịch các chương trình sang sang ngôn ngữ máy của máy đó mới có thể thực hiện được.

Chú ý rằng mỗi lệnh của hợp ngữ nói chung được dịch thành một lệnh trong ngôn ngữ máy còn mỗi lệnh của ngôn ngữ bậc cao thường tương đương với nhiều lệnh máy. Ví dụ lệnh NUA_CHU_VI = CHIEU_DAI + CHIEU_RONG sẽ dịch thành 3 lệnh máy.

Có hai kiểu dịch: thông dịch (Interpeter) là kiểu dịch từng lệnh để hiểu công việc phải làm và thực hiện luôn nhưng không nhất thiết phải tạo ra những đoạn mã tương ứng trong ngôn ngữ máy. Nếu một lệnh cần thực hiện nhiều lần thì cũng phải dịch nhiều lần.

Ngôn ngữ BASIC thịnh hành vào những năm 80 thường đi theo chế độ thông dịch. Còn các trình biên dịch (compiler) sẽ dịch toàn bộ chương trình ban đầu (gọi là chương trình nguồn) thành một chương trình tương ứng trong ngôn ngữ máy (gọi là chương trình đích), sau đó nạp chương trình đích vào máy tính để thực hiện. Sở dĩ trong tiếng Việt chúng ta gọi hai kiểu dịch này là "thông dịch' và "biên dịch" vì tính chất dịch có phần nào giống với dịch tiếng nước ngoài. Thông dịch giống như công việc của người phiên dịch (thông ngôn), nói tới đâu dịch tới đó. Còn biên dịch là công việc của người biên dịch, căn cứ trên tài liệu đầy đủ, ta viết ra một lần bản dịch đầy đủ.

Ngôn ngữ bậc cao đầu tiên được xây dựng vào năm 1957 là ngôn ngữ FORTRAN (FORmula TRANslator - Bộ dịch các công thức). Ngày nay có rất nhiều các ngôn ngữ lập trình bậc cao như PASCAL hay C. Sau đây là một đoạn chương trình giải phương trình bậc 2 viết trên PASCAL và FORTRAN. Bạn đọc dù chưa có một chút ý niệm gì về các ngôn ngữ này cũng có thể hiểu được các đoạn chương trình sau nói gì

Bảng B.3. Chương trình viết trên Pascal

(*Đoạn chương trình trên PASCAL*)

DELTA := B*B - 4*A*C;

IF DELTA > 0 THEN

BEGIN

X1 := (- B + SQRT(DELTA))/(2*A);

X2 := (- B - SQRT(DELTA))/(2*A);

WRITE (X1,X2);

END

WRITE('Vo nghiem');

.....

Xem toàn bộ nội dung bài viết ᛨ