Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 5

GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 5.1. NGÔN NGỮ LẬP TRÌNH. 5.1.1. 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 thông qua ngôn ngữ. Con người muốn máy tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được.
Nội dung trích xuất từ tài liệu:
Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 5 CHƯƠNG V: GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 5.1. NGÔN NGỮ LẬP TRÌNH. 5.1.1. 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 thông qua ngôn ngữ. Con người muốn máy tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được. Việc viết các yêu cầu, ta gọi là lập trình (programming). Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình (programming language). Viết chương trình để giải quyết vấn đề sẽ dễ dàng và tự nhiên hơn nếu ngôn ngữ lập trình gần với 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ể. Các ngôn ngữ lập trình có tính chất như trên được gọi là ngôn ngữ cấp cao. Nhưng máy tính chỉ hiểu, chỉ chấp nhận ngôn ngữ cấp thấp riêng của mình, đó là chuỗi các số 0 và 1, chuỗi số đó lại không gần gũi chút nào đối với con người. Việc phân cấp ngôn ngữ lập trình được dựa trên cơ sở của tính không phụ thuộc với máy tính ngày càng cao của các ngôn ngữ. Phân loại: 1) Ngôn ngữ máy (machine language), 2) Hợp ngữ (assembly language), 3) Ngôn ngữ cấp cao (higher-level language). 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ữ cấp cao cuối cùng rồi cũng được dịch sang ngôn ngữ máy. Công cụ thực hiện việc dịch đó được gọi là chương trình dịch (translator). Chương trình dịch được chia làm hai loại: trình biên dịch (compiler) và trình thông dịch (interpreter). − Trình biên dịch: chuyển một chương trình viết trong ngôn ngữ cấp cao − chương trình nguồn sang chương trình trong ngôn ngữ cấp cao khác hoặc ngôn ngữ máy − chương trình đích. + Thời gian chuyển một chương trình nguồn sang chương trình đích được gọi là thời gian dịch (compile time). + Thời gian mà chương trình đích được thực thi được gọi là thời gian thực Dữ liệu thi (run time). Chương trình Chương trình Máy tính Trình Kết quả nguồn đích thực thi biên dịch Thời gian dịch Thời gian thực thi 76 Như vậy, đối với trình biên dịch, chương trình nguồn và dữ liệu được xử lý trong thời gian khác nhau, đó là thời gian dịch và thời gian thực thi. − Trình thông dịch: quá trình xử lý dạng bên trong của chương trình nguồn và dữ liệu cùng một thời gian. Chương trình Trình Kết quả nguồn thông dịch Dữ liệu Một số trình thông dịch làm việc như sau: phân tích từng phát biểu và thực thi luôn. Hiện nay trình thông dịch đa phần áp dụng kỹ thuật của trình biên dịch là biên dịch chương trình nguồn sang dạng mã trung gian. Từ mã trung gian sẽ được thực thi bằng trình thông dịch. Đặc tả ngôn ngữ lập trình: để đặc tả ngôn ngữ lập trình, tối thiểu ta cần định nghĩa: 1. Tập các ký hiệu cần dùng trong các chương trình hợp lệ. 2. Tập các chương trình hợp lệ. 3. Nghĩa của từng chương trình hợp lệ. Việc định nghĩa tập các ký hiệu của một ngôn ngữ thật dễ dàng, ta chỉ cần liệt kê chúng. Song định nghĩa tập chương trình, gọi là hợp lệ thì quả là một công việc khó khăn hơn nhiều. Bởi vì thật là khó để xác định thế nào là một chương trình hợp lệ. Khi đặc tả ngôn ngữ lập trình, ta thường định nghĩa lớp các chương trình bằng tập các luật văn phạm, ta có thể tạo nên cả những chương trình còn nghi vấn về tính hợp lệ. Chẳng hạn, trong Fortran cho phép phát biểu sau: L GOTO L là hợp lệ. Mặc dù nếu phát biểu này mà được thực hiện thì sẽ là vòng lặp vô tận, không giải quyết được gì cả. Vì thế chương trình mà ta coi là hợp lệ phải được hiểu trong nghĩa hẹp. Khó khăn thứ ba cũng là vấn đề khó nhất của đặc tả ngôn ngữ là việc định nghĩa ý nghĩa của một chương trình hợp lệ. Có ba phương pháp để xác định nghĩa của chương trình hợp lệ. Phương pháp thứ nhất là định nghĩa bằng phép ánh xạ: ánh xạ mỗi chương trình vào một câu trong ngôn ngữ mà nghĩa của nó ta hiểu được. Phương pháp thứ hai, xác định ý nghĩa của chương trình bằng một máy lý tưởng (idealized machine). Nghĩa của chương trình có thể được đặc tả trong ngôn 77 từ của máy lý tưởng này. Như vậy máy lý tưởng trở thành bộ thông dịch cho ngôn ngữ. Phương pháp thứ ba, nghĩa của một chương trình nguồn chính là sản phẩm xuất ra của trình biên dịch, khi nó dịch chương trình nguồn. Trình biên dịch được dặc tả như là tập các cặp (x, y), với x là chương trình nguồn và y là chương trình đích, là chương trình mà x sẽ được dịch sang y. Giả sử cặp (x, y) đã có trước, bây giờ ta quan tâm đến cấu trúc của thiết bị để khi nhận x là đầu vào thì sinh ra y ở đầu ra. Ta coi tập (x, y) là sự biên dịch. Nếu mỗi chuỗi x được định nghĩa trên bảng chữ Σ và chuỗi y được định nghĩa trên bảng chữ ∆ thì biên dịch là phép ánh xạ từ Σ* đến ∆*. 5.1.2. Cú pháp và ngữ nghĩa: Để tiện lợi hơn trong đặc tả và hiện thực sự biên dịch, ta coi sự biên dịch bao gồm hai phép chiếu đơn giản hơn. Thứ nhất là phép ánh xạ cú pháp (syntactic mapping), nó ánh xạ một chương trình viết trong ngôn ngữ nguồn sang cấu trúc là đối số của phép ánh xạ tiếp theo, đó là phép ánh xạ ngữ nghĩa (semantic mapping). Cấu trúc của phép ánh xạ cú pháp là cây cú pháp (syntactic tree). Sau đây là thí dụ cây cú pháp được xây dựng như thế nào trên chuỗi nhập vào là một câu tiếng Anh. Mỗi câu tiếng Anh được bẻ ra thành những ký hiệu cú pháp nhờ vào các luật văn phạ ...