Bài giảng Các vấn đề cơ sở của khoa học máy tính - Chương 4 Phần mềm

Chương 4: PHẦN MỀM Nội Dung 1. Các thệ hệ của ngôn ngữ lập trình. 2. Trình biên dịch và trình thông dịch. 3. Máy ảo. 4. Lập trình thủ tục. 5. Lập trình hướng đối tượng. 6. Ngôn ngữ kịch bản. 7. Ngôn ngữ lập trình hàm. 8. Cú pháp ngôn ngữ và ngữ nghĩa. 2 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình • Các nhà khoa học máy tính gọi chung các ngôn ngữ lập trình, các chương trình và các sản phẩm là phần mềm (software). • Một lệnh máy là một dãy các bit 0 và 1 được chứa trong bộ nhớ máy tính. • Khi máy tính đọc bộ nhớ, nó xác định xem dãy bit đã đọc có phải là lệnh máy không. Nếu đúng, máy tính thực thi lệnh đó, ngược lại máy tính sẽ dừng vì lệnh không hợp lệ. • Mỗi máy tính (một họ CPU) có một tập lệnh máy hữu hạn. Hầu hết các máy tính ngày nay có từ 75 đến 150 lệnh máy trong tập lệnh. • Mỗi kiến trúc máy tính được thể hiện trong 3 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình tập lệnh. Các tập lệnh của các kiển trúc khác nhau sẽ khác nhau. Ví dụ, tập lệnh của Intel Pentium khác với của Sun SPARC. Cả khi thực hiện cùng một tác vụ, một lệnh của kiến trúc này cũng sẽ khác với kiến trúc khác. • Trong các máy tính trước đây, việc lập trình được thực hiện trực tiếp bằng lệnh máy. Người lập trình làm việc với các bit 0 và 1 để viết mã cho mỗi lệnh. Ví dụ sau là ba lệnh của máy tính 16 bit để cộng hai giá trị được chứa trong bộ nhớ tại địa chỉ 64 và 65 và lưu kết quả vào địa chỉ 66: 4 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình 0110000001000000 Nạp giá trị tại 64 vào AX 0100000001000001 Cộng với giá trị tại 65. 0111000001000010 Chứa giá trị AX vào 66. • Khi tất cả lệnh máy được tạo, người lập trình lưu chúng vào bộ nhớ. Sau đó, thiết lập thanh ghi PC trỏ đến lệnh đầu tiên của chương trình và thực thi. • Các thao tác cơ bản của máy tính là đọc lệnh trong bộ nhớ được trỏ bởi thanh ghi PC, tăng thanh ghi PC, thực thi lệnh và lặp lại. • Một sự cải tiến trước đây để lập trình hiệu quả hơn là sử dụng hợp ngữ (assembly language). Trong hợp ngữ, chúng ta có thể 5 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình đọc mã lệnh bằng từ gợi nhớ (chữ và số - mnemonic) thay vì mã máy và mỗi từ gợi nhớ ứng với một lệnh máy. • Hợp ngữ được gọi là ngôn ngữ thế hệ thứ hai (second-generation language). Trong hợp ngữ, người lập trình viết mã lệnh gợi nhớ và nó sẽ được biên dịch (bằng trình hợp dịch – assembler) trực tiếp thành mã máy. Một số từ gợi nhớ tiêu biểu như sau: - LDA m: Nạp giá trị tại địa chỉ m vào thanh ghi AX. - ADA m: Cộng giá trị của AX với giá trị tại địa chỉ m, kết quả chứa trong AX. 6 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình - ALS: Dịch các bit trong AX sang trái 1 đơn vị. - SSA: Nếu bit msb của AX là 1, bỏ qua lệnh kế tiếp. Ngược lại, thực thi lệnh kế tiếp. - JMP m: Nhảy đến địa chỉ m. • Sau đây là mã hợp ngữ để viết lại 3 lệnh máy ở trên: LDA 100 // 100 octal = 64 ADA 101 // 101 octal = 65 STA 102 // 102 octal = 66 • Người lập trình thường sử dụng hợp ngữ để viết chương trình vì nó gần gũi với phần 7 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình cứng máy tính hoặc những chương trình tối ưu tốc độ hay bộ nhớ. • Như là một công cụ giáo dục, lập trình hợp ngữ rất quan trọng, bởi vì nó là cách tốt nhất để biết được máy tính làm gì và làm như thế nào. • Vào năm 1954, ngôn ngữ thế hệ thứ ba ra đời. Ngôn ngữ đó là FORTRAN, do John Backus của IBM phát minh. • FORTRAN là chữ viết tắt của FORmula TRANslation. Ngôn ngữ này giúp người lập trình làm việc ở mức trừu tượng cao hơn. • Thay vì bị hạn chế bởi tập lệnh máy, người 8 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình lập trình bây giờ sử dụng các câu lệnh giống như tiếng Anh và các biểu thức toán học. Ngôn ngữ cũng bao gồm các lệnh rẽ nhánh, lặp và nhập/xuất. • Sau đây là câu lệnh của FORTRAN. Các tên biến X, Y và Z trở thành tên đại diện cho các vị trí nhớ. Câu lệnh sẽ cộng nội dung của Y với Z và chứa tổng vào X: X = Y + Z • So sánh với hợp ngữ, câu lệnh của FORTRAN dễ đọc, dễ viết và ngắn gọn hơn. • FORTRAN là “ngôn ngữ thủ tục” (procedural language). Nghĩa là, người lập trình phải tổ 9 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình chức hợp lý một dãy các bước cần thiết để thực thi tác vụ nào đó. • Các ngôn ngữ thủ tục còn được gọi là các “ngôn ngữ mệnh lệnh” (imperative language), bởi vì các câu lệnh của ngôn ngữ là những mệnh lệnh cho máy tính – các bước của chương trình chỉ định mỗi hành động của máy tính. • Khác với các ngôn ngữ mệnh lệnh là các ngôn ngữ “hướng đối tượng” (object- oriented). Hầu hết, nhưng không phải là tất cả các chương trình ngày nay được viết bằng các ngôn ngữ mệnh lệnh. 10 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Các Thế Hệ của Ngôn Ngữ Lập Trình • Cho đến nay, các ngôn ngữ thế hệ thứ ba gồm: LISP (for LISt Processing), Cobol, PL/1, BASIC, ADA, C, Smalltalk, C++, Java. Trong đó, Smalltalk, C++ và Java là các ngôn ngữ lập trình hướng đối tượng. 11 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch • Với sự ra đời của FORTRAN, chương trình trở nên phức tạp hơn để tạo ra mã máy. Một chương trình khác được gọi là trình biên dịch (compiler) dùng để dịch ngôn ngữ lập trình cấp cao thành mã máy. • Đầu vào của trình biên dịch là mã nguồn được viết bằng ngôn ngữ cấp cao. Đầu ra của trình biên dịch là mã máy. • Ví dụ sau là đoạn mã của ngôn ngữ FORTRAN: DIMENSION X(1000) READ(*, 1) N, M FORMAT(2I5) WRITE(*, 2) M, N 12 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch FORMAT('AVERAGES ON ', I6, ' TESTS FOR EACH OF ', I6, 1’ SUBJECTS’) EM=M DO 5 J=1, N READ(*, 3) ID, (X(K), K=1, M) FORMAT(I5, 25F3.0/ (5X, 25F3.0)) SUM = 0.0 DO 4 K=1, M SUM = SUM + X(K) AV = SUM / EM WRITE(*, 6 ) J, ID, AV FORMAT(I6, 3X, 'SUBJECT ', I6, 3X, 'AV= ', F9.2) STOP END 13 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch • Trình biên dịch xử lý mã nguồn qua hàng loạt các bước: 1. Bước đầu tiên gọi là “quét” (scanning) hay “phân tích từ vựng” (lexical analysis) và xuất ra một chuỗi các “token” (từ tố/thẻ từ). Token là từ của ngôn ngữ, ví dụ “READ”, “FORMAT”, “AV”, “4” và “3X” là các token trong chương trình ví dụ. 2. Kế đến, trình biên dịch “phân tích từ loại” (parse) chuỗi token đó. Bước này được gọi là “phân tích cú pháp” (syntax analysis). Xem xét “văn phạm” hay các qui tắc của ngôn ngữ. Trình biên dịch sử dụng “cây 14 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch phân tích cú pháp” (parse tree) để thẩm tra các lệnh trong mã nguồn là những lệnh hợp lệ của ngôn ngữ. Tại bước này, trình biên dịch trả về thông báo lỗi, ví dụ thiếu dấu phẩy hay sai từ khoá. 3. Nếu tất cả câu lệnh đều hợp lệ, trình biên dịch tiếp tục “phân tích ngữ nghĩa” (semantic analysis). Trong giai đoạn này, ý nghĩa (meaning) của các lệnh được tạo, các lệnh sẽ được chuyển thành các mã thực thi (executable code). • Các trình biên dịch ngày nay thường biên dịch chương trình nguồn thành “ngôn ngữ 15 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch trung gian” (intermediate language) và sau đó sẽ chuyển thành mã máy. Trong khi các trình biên dịch trước đây hoặc là tạo mã hợp ngữ và sau đó sẽ hợp dịch (assemble) bằng trình hợp dịch (assembler) hoặc là tạo trực tiếp thành mã máy. • Ưu điểm của trình biên dịch ngày nay là có thể biên dịch nhiều ngôn ngữ khác nhau thành mã trung gian ở dạng tổng quát, không phụ thuộc vào môi trường/nền (platform) và sau đó có thể sinh ra mã máy tối ưu cho từng loại máy. • Kết quả của sự biên dịch chương trình là tập 16 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch tin mã đối tượng (object code). Nó là tập tin nhị phân của các lệnh máy và sẽ thực thi khi chương trình chạy. • Trình biên dịch thực hiện dịch mã nguồn thành mã thực thi chỉ 1 lần, khi chương trình chạy, các mã này sẽ thực thi ngay lập tức. • Đối với trình thông dịch (interpreter) thì khác. Trình thông dịch thực hiện dịch từng dòng mã nguồn thành mã máy ở mỗi thời điểm khi chương trình thực thi. Ví dụ, BASIC là ngôn ngữ sử dụng trình thông dịch. • Nói chung, một chương trình được thực thi bằng trình thông dịch sẽ chạy chậm hơn 17 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Trình Biên Dịch và Trình Thông Dịch chương trình đã được biên dịch thành mã máy. Bởi vì, ở mỗi thời điểm trình thông dịch phải phân tích từng dòng lệnh và chuyển nó thành mã máy khi chương trình chạy. • Trình thông dịch thường cung cấp thông báo chuẩn đoán tốt hơn vì nó làm việc trực tiếp với từng dòng lệnh. • Sự khác biệt giữa ngôn ngữ sử dụng trình biên dịch và thông dịch đôi khi cũng không rõ ràng. Có một số ngôn ngữ sử dụng cả trình thông dịch và biên dịch như BASIC, PERL, LISP, Java, 18 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Máy Ảo • Máy ảo (virtual machine) là máy tính được định nghĩa bởi phần mềm hơn là phần cứng. Máy ảo chạy các chương trình giống như máy tính thật, nhưng máy ảo thực sự được điều khiển bởi chương trình khác, một sự tạo dựng bởi phần mềm đó là lấy, giải mã và thực thi các lệnh của chương trình. • Thuật ngữ máy ảo mô tả một lớp trừu tượng được thêm vào giữa người dùng và phần cứng, vì thế các nhà khoa học máy tính cũng sử dụng thuật ngữ này để mô tả phần mềm tạo nên sự thể hiện ở các dạng khác nhau của máy tính. 19 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Theo nhiều người, lập trình thủ tục (procedural programming) là mô hình tự nhiên. Một chương trình được mô tả đơn giản chỉ là một danh sách các lệnh được thực thi theo trình tự, tức là một thủ tục. • Các ngôn ngữ lập trình thủ tục cũng được gọi là các ngôn ngữ mệnh lệnh (imperative language). • Trong lập trình thủ tục, mã lệnh cho một công việc cụ thể được chứa trong một thủ tục có tên. Thủ tục cũng còn được gọi là subroutine. Cho ví dụ, hãy tạo một thủ tục để tìm độ lệch chuẩn của một dãy số. 20 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Độ lệch chuẩn được định nghĩa như sau. Gọi σ là độ lệch chuẩn và 𝒙𝒙� là trung bình của các phần tử trong dãy số: 𝝈𝝈 = (�𝒙𝒙𝒊𝒊𝟐𝟐 − 𝒏𝒏𝒙𝒙�𝟐𝟐)𝒏𝒏 𝒊𝒊=𝟏𝟏 /𝒏𝒏 • Sau đây là thủ tục được viết bằng mã giả để tính độ lệch chuẩn: 21 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục SUM = 0.0, SUMSQUARES = 0.0 n = size of the array of scores Start with the first score and continue until all the scores have been processed SUM = SUM + score SUMSQUARES = SUMSQUARES + score2 End of loop MEAN = SUM / n Return SquareRoot((SUMSQUARES − n * MEAN2) / n) • Sau đây là đoạn mã lệnh được viết bằng Java với lớp Sd chứa phương thức stdDev(): 22 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục import java.lang.Math; class Sd { public static void main(String args[]) { float[] numbers = {3, 5, 7, 9}; System.out.println("Std. dev. = " + stdDev(numbers)); } public static float stdDev(float scores[]) { float sum = 0; float sumSquares = 0; int n = scores.length; 23 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục for(int i = 0; i < n; i++) { sum = sum + scores[i]; sumSquares = sumSquares + scores[i]*scores[i]; } float mean = sum / n; float variance = (sumSquares - n * mean * mean) / n; return (float)Math.sqrt(variance); } } 24 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Trong lập trình thủ tục, các mã lệnh có thể được viết trong một khối gọi là thủ tục (procedure)/hàm (function). Khối này được truy xuất thông qua tên của nó và có thể tái sử dụng. • Thủ tục nhận tập giá trị nhập và trả về tập kết quả. Lưu ý là các biến bên trong thủ tục như sum và sumSquares có tầm vực (scope) chỉ bên trong thủ tục đó. Điều này giúp tránh lẫn lộn các biến đang sử dụng với các biến cùng tên ở tầm vực/khối bao. • Một thủ tục có thể được truy xuất bởi chương trình khác. Chỉ đơn giản là chúng ta thêm thủ tục đó vào thư viện. 25 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục • Khái niệm lập trình cấu trúc (structured programming) được hiểu như là tập con của lập trình thủ tục. Phương pháp lập trình cấu trúc thường đi đôi với phương pháp phân tích trên xuống (top-down). Tác vụ của chương trình được chia thành nhiều thủ tục/hàm. Điều này rất quan trọng trong thiết kế chương trình, bởi vì chương trình được cục bộ hóa nên dễ đọc, dễ bảo trì, độ tin cậy cao, tái sử dụng và tạo thư viện . • Lập trình cấu trúc sử dụng các lệnh có cấu trúc như các lệnh rẽ nhánh, lặp để gọi các thủ tục/hàm đã được định nghĩa. Các ngôn ngữ 26 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Thủ Tục hỗ trợ lập trình cấu trúc như ALGOL, ADA, Pascal, C, • Nhược điểm: Trong lập trình cấu trúc, giải thuật luôn phụ thuộc chặt chẽ vào cấu trúc dữ liệu, do đó khi thay đổi cấu trúc dữ liệu, phải thay đổi giải thuật. Nghĩa là phải viết lại chương trình. • Khái niệm lập trình không cấu trúc (unstructured/non-structured programming) được hiểu là chương trình có sử dụng các lệnh GOTO hay JUMP. Kết quả sẽ làm cho chương trình khó đọc, khó tìm lỗi, khó tái sử dụng. • Các ngôn ngữ hỗ trợ lập trình không cấu trúc như Assembly, BASIC, 27 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng • Lập trình hướng đối tượng (Object-oriented programming – OOP) được phát triển sau này, nó cung cấp độ tin cậy và tái sử dụng phần mềm xa hơn nữa. • Thay vì lập trình thủ tục, lập trình hướng đối tượng dựa vào các đối tượng phần mềm như là các đơn vị của chương trình. • Một đối tượng là một thể hiện (instance) của một “lớp” (class). Để tạo ra một thể hiện, người ta sử dụng các đặc tả của lớp đó. Ví dụ MyCar là một thể hiện của lớp Automobile: có 4 bánh, có động cơ, có ghế ngồi, 28 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng • Một thể hiện của một lớp có “trạng thái” hay các nét đặc trưng (characteristic) của riêng nó. Ví dụ, màu của thể hiện MyCar là đỏ và của YourCar là xanh. Hoặc MyCar có 170 hp (mã lực) và YourCar có 200 hp, Tất cả các đặc trưng màu sắc, dung tích động cơ (và các đặc trưng khác) được gọi là thuộc tính (attribute) hay các biến thể hiện (instance variable). • Các đối tượng cũng có “hành vi” (behavior). Hành vi được xác định bởi các thủ tục của lớp đó, các thủ tục như thế được gọi là các phương thức (method). Ví dụ, lớp 29 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng Automobile có phương thức như changeSpeed() để thay đổi tốc độ xe nhanh hay chậm hơn, park() xác định kích thước của chỗ đậu xe. Phương thức còn được gọi là phương thức thể hiện (instance method) • Lập trình hướng đối tượng “đóng gói” (encapsulate) trạng thái và hành vi của đối tượng. Chương trình chỉ có thể truy xuất các thuộc tính public và phương thức public của đối tượng. • Một ý tưởng quan trọng trong lập trình hướng đối tượng là “sự thừa kế” (inheritance). Nghĩa là chúng ta có thể tạo một lớp mới “mạnh 30 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Lập Trình Hướng Đối Tượng hơn” bằng cách thừa kế từ lớp trước đó và thêm những tính năng mới của nó. Ví dụ, lớp Limousine thừa kế từ lớp Automobile. • Có liên quan đến thừa kế là khái niệm về “tính đa hình” (polymorphism) - tính chất thể hiện nhiều hình thái của đối tượng. Tính đa hình là sự thực thi của một phương thức có thể cho kết quả khác nhau phụ thuộc vào lớp của đối tượng mà phương thức đó được gọi. • Ví dụ, lớp Automobile và Limousine (xe ô tô hạng sang) đều có phương thức park(). Tuy nhiên, phương thức park() của Limousine yêu cầu chỗ đậu xe lớn hơn trong phương thức park() của Automobile. 31 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Kịch Bản • Ngày nay, có một số ngôn ngữ lập trình là ngôn ngữ kịch bản (scripting language). Ý tưởng ban đầu của “script” (kịch bản) là một tập các lệnh của hệ điều hành được đặt trong tập tin. Khi người sử dụng thực thi tập tin kịch bản (script file), tập lệnh trong đó được thực thi. Các kịch bản rất hữu dụng trong việc tự động hoá công việc thường ngày. • Do tính hữu dụng của ngôn ngữ kịch bản đã khơi dậy nhiều nhà phát minh phát triển ngôn ngữ mới với nhiều tính năng và tiện lợi hơn. Các ngôn ngữ như Perl, PHP, Python, JaVaScript, là những ngôn ngữ kịch bản. Tuy nhiên, ngôn ngữ kịch bản được thông dịch, vì thế tốc độ thực thi không phải là ưu điểm chính của nó. 32 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm • Các ngôn ngữ lập trình hàm (functional programming language) được phát minh từ rất sớm trong lịch sử máy tính. Năm 1958, John McCarthy đã cho ra đời ngôn ngữ LISP (LISt Processing). • Ngôn ngữ lập trình hàm thường dùng để xử lý các hàm toán học. Một hàm cần một hay nhiều đối số và trả về một trị. Cho ví dụ, phương trình của đường parabol là: f(x) = 2x2 + 5 Khi chúng ta cung cấp giá trị cho x (ví dụ x = 3), thì hàm trên sẽ trả về kết quả như sau: f(3) = 2(3)2 + 5 = 23 33 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm • Với ngôn ngữ lập trình hàm, việc tính toán được thực hiện bằng cách truyền các đối số đến một hàm và nhận kết quả trả về của hàm đó. • Trong các ví dụ, chúng ta sẽ sử dụng ngôn ngữ Scheme. Ngôn ngữ Scheme được gọi là ngôn ngữ thao tác ký hiệu (symbolic manipulation), ra đời năm 1975 và thuộc họ LISP. • Một biểu thức trong Scheme là một atom (nguyên tử) hay một list (danh sách). Một atom là một số, ký tự, tên hay hàm. Một list là một tập các biểu thức được chứa trong dấu 34 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm ngoặc (). Các phần tử trong list có thể là atom hay là một list khác. • Trong bất kỳ ngôn ngữ lập trình hàm nào, một số hàm cơ bản sẽ được tạo sẵn. Ngoài ra, người lập trình có thể tự định nghĩa hàm. Sau đây là một số ví dụ về Scheme: 1.(+ 3 5) → 8 2.(+ 3 5 7 4 2) → 21 3.(/ (+ 3 5) (- 7 5)) → 4 4.(list 1 5 6) →(1 5 6) 5.(car (list 1 5 6)) → 1 6. (cdr (list 1 5 6)) → (5 6) 35 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Scheme/ LISP Ngôn Ngữ Lập Trình Hàm 7.(define sum (lambda (n m) (+ n m))) > (sum 4 3) 7 Trong ví dụ trên, định nghĩa hàm sum sử dụng ký pháp lambda (lambda notation). Ưu điểm là không phân biệt định nghĩa hàm với định nghĩa giá trị. 8.(define factorial (lambda (n) (if (<= n 1) 1 (* n (factorial( - n 1)))))) 36 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm > (factorial 5) 120 • Lưu ý: Thay vì sử dụng các lệnh if lồng nhau, Scheme cho phép sử dụng lệnh cond. Ví dụ: cond((>= grade 8) “Gioi”) ((>= grade 7) “Kha”) ((>= grade 6) “TB kha”) ((>= grade 5) “Trung binh”) (else “Kem”))) 37 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Ngôn Ngữ Lập Trình Hàm 9.(define listSum (lambda (n) (cond ((null? n) 0) ((null? (cdr n)) (car n)) (else (+ (car n) (listSum( cdr n)))) ))) > (listSum (list 2 4 5)) 11 • Lập trình hàm thường được sử dụng trong trí tuệ nhân tạo (artificial intelligence) và hệ chuyên gia (expert system). 38 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Trước khi biên dịch chương trình ngôn ngữ cấp cao thành mã máy, bộ xử lý ngôn ngữ (chương trình dịch) phải thực hiện nhiều tác vụ như phân tích từ vựng (lexical analysis), phân tích cú pháp (syntax analysis) và sinh mã (phân tích ngữ nghĩa - semantic analysis). • Trong bước phân tích từ vựng, chương trình dịch đọc dãy ký tự từ tập tin mã nguồn và tạo các token của ngôn ngữ đó. Token là từ của ngôn ngữ và có nhiều dạng, có thể là từ khoá (key word) như String, một ký hiệu như ‘+’, một danh hiệu như myCount, một hằng như 3.14 hay một chuỗi ký tự như “Please enter your name:”. 39 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Sau khi các token được tạo, bộ phân tích cú pháp (parser) xây dựng cây phân tích cú pháp (parse tree) theo các qui tắc văn phạm của ngôn ngữ và tìm lỗi nếu có. • Cú pháp của ngôn ngữ mô tả các lệnh hợp lệ của ngôn ngữ đó. Cú pháp đúng, không đảm bảo là kết quả của chương trình đúng, nhưng một chương trình đúng phải có cú pháp đúng. • Ngày nay, các qui tắc cú pháp thường biểu diễn ở dạng Backus-Naur form (BNF) hay BNF mở rộng (EBNF). Từ “Backus-Naur” được 40 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa ghép từ tên John Backus là nhà phát minh ra ngôn ngữ FORTRAN và Peter Naur. • BNF sử dụng một tập các qui tắc hay luật sinh (production rule) để mô tả văn phạm hay cú pháp. • Bên trái của luật sinh, BNF cho thấy một khái niệm ngôn ngữ học được biết như là các “ký hiệu không kết thúc” (non-terminal). Ví dụ, ký hiệu không kết thúc trong tiếng Anh là “câu” (sentence) và “ngữ động từ” (verb phrase). Trong ngôn ngữ lập trình, ký hiệu không kết thúc có thể là “expression” hay “term”. 41 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Bên phải của luật sinh, BNF cho thấy sự kết hợp của ký hiệu không kết thúc và/hoặc ký hiệu kết thúc thay thế cho ký hiệu không kết thúc bên trái. • Ví dụ sau là văn phạm của các biểu thức toán học: 1.expression → term | expression addop term 2.term → factor | term multop factor 3.factor → identifier | number | -factor | (expression) 4.addop → + | - 5.multop → * | / 42 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Các vạch đứng “|” nghĩa là “hoặc”. Các luật sinh 3, 4, và 5 tạo các ký hiệu kết thúc. • Trong luật sinh 1, một biểu thức có thể là term hoặc là một biểu thức khác addop (+ | -) với term. • Trong luật sinh 2, term có thể là factor hoặc là một term khác multop(* | /) với factor. • Cho ví dụ, phân tích cú pháp biểu thức sau dựa vào văn phạm ở trên: X * 3 + 4 • Áp dụng luật sinh 1: X * 3 + 4 → (X * 3) addop term expr + 4 43 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Áp dụng luật sinh 2 và 3 cho term: term → factor → number 4 • Áp dụng luật sinh 1 và 2 cho (X * 3): (X * 3) → term → term multop factor (X * 3) X * 3 • Áp dụng luật sinh 3 cho factor: factor → number 4 • Áp dụng luật sinh 2 và 3 cho term: term → factor → identifier X X X 44 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Sự phân tích một biểu thức thành các ký hiệu kết thúc dựa vào các qui tắc văn phạm được gọi là dẫn xuất (derivation). Kết quả của sự dẫn xuất thành công là cây phân tích cú pháp hay cây cú pháp (syntax tree). Sau đây là cây phân tích cú pháp của dẫn xuất mà chúng ta vừa thực hiện: 45 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa 46 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng Cú Pháp Ngôn Ngữ và Ngữ Nghĩa • Để tính ý nghĩa của biểu thức, cây phân tích cú pháp được duyệt (traverse) từ dưới lên. Tính phép nhân trước rồi đến phép cộng. Lúc này, trình biên dịch sẽ tạo các lệnh máy tương ứng để thực thi biểu thức. Đây là giai đoạn cuối cùng được gọi là sinh mã (code generation). 47 Các Vấn Đề Cơ Sở của KHMT ThS. GVC Tô Oai Hùng