Giáo trình Lý thuyết ngôn ngữ lập trình (Nghề Lập trình máy tính): Phần 2 - Tổng cục dạy nghề

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

28
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Lý thuyết ngôn ngữ lập trình (Nghề Lập trình máy tính): Phần 2 giúp bạn nắm được các khái niệm cơ bản của ngôn ngữ lập trình chung, hiểu được các thành phần của một ngôn ngữ lập trình, biết phân biệt các đặc trưng khác nhau của các ngôn ngữ lập trình. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Lý thuyết ngôn ngữ lập trình (Nghề Lập trình máy tính): Phần 2 - Tổng cục dạy nghề

Bài 3 TÊN BÀI:HÀM THỦ TỤC MÃ BÀI:: ITPRG3-06.3 Giới thiệu Khái niệm chương trình con (sub-program hay sub-routine) ra đời từ rất sớm vào những năm 1950. Mà sau đó chương trình con dạng hàm hay thủ tục đã được sử dụng rộng rãi trong các ngôn ngữ lập trình, đặc biệt là các ngôn ngữ lập trình mệnh lệnh. Cho đến ngày nay, khi mà các ngôn ngữ lập trình rất pgong phú đa dạng thì khái niệm này vẫn tồn dưới nhiều hình thức khác nhau. Mục tiêu thực hiện - Hiểu rõ cơ chế thực hiện của chương trình con dạng hàm và thủ tục - Phân biệt và sử dụng đúng các dạng tham số - Nắm cấu trúc chuẩn của một chương trình con - Hiểu được tính ưu việt của các chương trình con - Nắm được cách xây dựng và sử dụng chương trình con trong ngôn ngữ lập trình Pascal - Nắm được khái niệm đệ quy Nội dung chính Trình bày hai khái niệm hàm và thủ tục. Nêu bật ưu điểm của hàm và thủ tục. Trình bày cách xây dựng hàm và thủ tục trong ngôn ngữ lập trình Pascal. Khái niệm chương trình con Khái niệm chương trình con (sub-program hay sub-routine) được ra đời từ rất sớm vào những năm 1950, khi mà ngôn ngữ để lập trình mới chỉ là ngôn ngữ máy. Do việc, viết chương trình bằng các bit nhị phân là rất phức tạp, khó khăn, người ta đã nghĩ đến việc xây dựng sẵn các đoạn chương trình thường hay sử dụng. Các đoạn chương trình này chính là tiền thân cho khái niệm chương trình con. Chương trình con thực ra là những đoạn chương trình (dãy các câu lệnh) thường được hay sử dụng lặp đi lặp lại trong khi lập trình. Để giảm bớt thời gian lập trình, người ta xây dựng sẵn các thư viện chứa các chương trình con mà sau đó các chương trình con này có thể được sử dụng nhiều lần. Ví dụ, tính cos hay sin là các công việc thường hay gặp trong toán học. Thế thì thay vì mỗi lần cần đến ta phải thực hiện tính toán, ta có thể xây dựng sẵn các chương trình con cho phép thực hiện công việc tính toán này và sau đó chỉ việc sử dụng. Trong thực tế, trong hầu hết tất cả các ngôn ngữ lập trình các công việc thường được lặp đi lặp lại như thế này đều được xây dựng sẵn thành các chương trình con chứa trong các thư viện dành cho người sử dụng. Ngoài ra trong quá trình lập trình, người lập trình có thể tự xây dựng cho mình các chương trình con được sử dụng nhiều lần trong một chương trình. Khái niệm chương trình con có hầu hết trong các ngôn ngữ lập trình, mà có thể tên gọi của nó bị thay đổi đi chút ít, như: hàm, thủ tục, thao tác, phương thức, ... Đặc biệt trong các 66
ngôn ngữ lập trình mệnh lệnh (như Pascal) thì chương trình con được chia làm hai loại: hàm (function) và thủ tục (procedure). Trong bài học này chúng ta sẽ tìm hiểu về hai loại chương trình con này thông qua ngôn ngữ lập trình Pascal, là một ngôn ngữ mang tính sư phạm cao và thể hiện rất rõ hai khái niệm này. Xây dựng hàm và thủ tục Trước hết hàm hay thủ tục đều là những đoạn chương trình thường được sử dụng lặp đi lặp lại. Thế sự khác nhau giữa hai khái niệm này là gì? Hàm sau khi thực hiện xong công việc thì tra về một giá trị thông qua tên hàm, trong khi thủ tục không trả về giá trị nào cả. Ví dụ, hàm binhphương tính giá trị bình phương của một số nguyên sẽ trả về giá trị đó qua tên hàm. Trong khi thủ tục xuatmanhinh thực hiện việc in ra màn hình một kết quả tính toán nào đó thì nó không trả về một giá trị nào cả. Trong ngôn ngữ Pascal, các chương trình con phải được khai báo và viết bên trên thân chương trình, sau đó được sử dụng trong thân chương trình. Cú pháp tổng quát để viết một hàm trong Pascal như sau: Function tên_hàm (khai báo các tham số hình thức) : kiểu_trả_về_của_hàm; (* Các khai báo hằng, biến cục bộ *) Begin (*thân hàm*) tên_hàm := biểu_thức; (* gán giá trị trả về *) End; Khi khai báo một hàm, nếu hàm đó có sử dụng các hằng hay biến cục bộ thì phải khai báo sau khi khai báo hàm. Ở đây chúng ta thấy xuất hiện khái niệm biến cục bộ (local variable) là các biến được khai báo bên trong một hàm (hay thủ tục). Trong thân hàm luôn phải có phép gán giá trị trả về cho tên hàm. Ví dụ, viết hàm tính tổng của 3 số thực: Function tong3so (x, y, z : real) : real; Begin tong3so := x + y + z; End; Đây là hàm rất đơn giản, nhận 3 giá trị số thực và trả về tổng của chúng. Đối với hàm này không có các khai báo thêm hằng, biến cục bộ. Hàm được bắt đầu bởi từ khóa Function, sau đó là tên hàm tong3so. Hàm nhận 3 tham số hình thức là x, y, z có kiểu real và trả về giá trị kiểu real. Thân hàm gồm các câu lệnh được đặt giữa hai từ khóa Begin và End. Giá trị tổng 3 số thực được gán trực tiếp cho tên hàm trong thân hàm. Dưới đây là một ví dụ khác, chương trình có chứa hàm tính giá trị lớn nhất của hai số thực. Hàm được sử dụng trong thân chương trình để tính giá trị lớn nhất của các biểu thức a+b và a-b. Program vi_du_max; Var 67
a, b, s : real; (*Khai báo hàm max2so*) Function max2so(x, y : real) : real; Var r : real; (* khai báo biến cục bộ *) Begin if x > y then r := x else r := y; max2so = r; End; (*Thân chương trình chính*) Begin a := 11.45 b := -42.7 s := max2so(a+b, a-b); (* gọi chương trình hàm *) Writeln(‘Max = ’, s:5:1); End. Như thế, chúng ta nhận thấy hàm luôn trả về một giá trị trong tên hàm. Trong khi định nghĩa hàm thì phải gán tên hàm cho giá trị trả về. Ngược lại, thủ tục không trả về giá trị. Cú pháp tổng quát để viết một thủ tục trong Pascal là như sau: Procedure tên_thủ_tục (khai báo các tham số hình thức); (* Các khai báo hằng, biến cục bộ*) 1. Begin (*thân thủ tục*) End; Bây giờ chúng ta viết lại chương trình tính giá trị lớn nhất hai số thực sử dụng chương trình con là thủ tục như sau: Program vi_du_max; Var a, b : real; (*Khai báo thủ tục max2so*) Procedure max2so(x, y : real); Var r : real; (* khai báo biến cục bộ *) Begin if x > y then r := x else r := y; Writeln(‘Max = ’, r:5:1); End; 68
(*Thân chương trình chính*) Begin a := 11.45 b := -42.7 max2so(a+b, a-b); (* gọi chương trình thủ tục *) End. Trong ngôn ngữ Pascal, còn cho phép viết các chương trình con bên trong thân một chương trình con khác. Chẳng hạn, chúng ta xem xét ví dụ thủ tục M sau: (* khai báo thủ tục M*) Procedure M (x, y : real); Var s : real; (* biến cục bộ của thủ tục M*) (* khai báo hàm M1 bên trong thân thủ thủ tục M*) Function M1 (m, n : real) : real; Var r : real; (* biến cục bộ của thủ tục M1*) Begin if m > n then r := m else r := n; M1 := r; End; (* khai báo thủ tục M2 bên trong thân thủ tục M*) Procedure M2 (a : real); Begin Writeln(‘In ket qua : ’, a:5:1); End; (* thân của thủ tục M *) Begin s := M1(x, y); (* gọi hàm M1*) M2(s); (* gọi thủ tục M2*) End; Trong ví dụ này, bên trong thân của thủ tục M chứa hai chương trình con khác là hàm M1 và thủ tục M2. Sau đó, trong thân của thủ tục M sử dụng hai chương trình con này. Lưu ý là không phải ngôn ngữ lập trình nào cũng cho phép khai báo các chương trình con bên trong chương trình con khác, chẳng hạn như ngôn ngữ C không cho phép điều này. Cơ chế hoạt động của chương trình con Liên quan đến chương trình con (hàm và thủ tục ở trên), chúng ta có một số khái niệm sau: - Biến cục bộ: là biến được khai báo và chỉ sử dụng bên trong thân một chương trình con, là biến r trong ví dụ trên. - Biến toàn cục: là biến được khai báo ở đầu chương trình và có thể được sử dụng bất cứ đâu trong chương trình, là các biến a và b trong ví dụ trên. 69
- Tham số hình thức (hay còn được gọi là đối): là các biến được khai báo sau tên của chương trình con (chúng ta sẽ được giới thiệu chi tiết hơn về tham số hình thức trong các phần tiếp theo), là các tham số x và y trong ví dụ trên. - Tham số thực: là các giá trị truyền cho các tham số hình thức tương ứng khi gọi các chương trình con. Chẳng hạn, trong ví dụ trên là các giá trị của biểu thức a+b và a- b. Cơ chế hoạt động của một chương trình con là như sau: chương trình được batứ đầu từ câu lệnh đầu tiên và kết thúc khi thực hiện xong câu lệnh cuối cùng trong thân chương trình, nếu chương trình gặp một lời gọi chương trình con (thủ tục hay hàm) thì máy sẽ thực hiện: - cấp phát bộ nhớ cho các biến cục bộ của chương trình con, - truyền giá trị của các tham số thực cho các tham số hình thức tương ứng, - thực hiện lần lượt các câu lệnh trong thân chương trình con, - giải phóng các biến cục bộ và trở về nơi gọi nó, nếu chương trình con là hàm thì khi trở về mang theo một giá trị. Quay trở lại chương trình chứa thủ tục max2so trên, hoạt động của nó là như sau: - gán giá trị 11.45 cho biến a và –42.7 cho biến b, - gặp lời gọi thủ tục max2so, thực hiện thủ tục max2so: o cấp phát bộ nhớ cho biến cục bộ r và các tham số hình thức x và y, o giá trị của biểu thức a+b và a-b được truyền cho các tham số hình thức x và y, o thực hiện các câu lệnh trong thân thủ tục để tính giá trị lớn nhất chứa trong biến r, o gọi thủ tục Writeln để in ra kết quả, o giải phóng các biến cục bộ r và tham số hình thức x, y, o máy thoát ra khỏi thủ tục để trở về chương trình chính, - kết thúc chương trình chính. Biến toàn cục và biến cục bộ Ở trên chúng ta đã nhắc đến hai khái niệm biến cục bộ và biến toàn cục, trong phần này chúng ta sẽ xem xét một cách chi tiết hơn. Biến toàn cục (global variable) là những biến được khai báo ở đầu chương trình, chúng tồn tại trong suốt thời gian làm việc của chương trình. Biến toàn cục được sử dụng bất kì đâu ở trong chuơnưg trình, nghĩa là trong thân chương trình chính hoặc trong các thân chương trình con. Biến cục bộ (local variable) là biến được khai báo ở đầu một chương trình con. Biến cục bộ được cấp phát bộ nhớ khi chương trình con được gọi tới và bị giải phóng khỏi bộ nhớ khi máy ra khỏi chương trình con. Biến cục bộ chỉ được sử dụng bên trong thân của chương trình con khai báo nó cũng như các chương trình con khác nằm bên trong thân của chương trình con khai báo nó. Để phân biệt rỏ sự khác nhau của biến cục bộ và biến toàn cục, chúng ta quan sát ví dụ sau: 70
Program cac_loai_bien; Var x : integer; (* x là biến toàn cục *) (* Khai báo thủ tục M *) Procedure M; Var a, b : integer; (* a và b là biến cục bộ trong M *) (* Khai báo thủ tục M1 *) Procedure M1; Var n : inetger; (* n là biến cục bộ trong M1 *) Begin x := x + 1; (* sử dụng biến toàn cục x *) n := a + b; Writeln(‘n = ’, n); a := a + 1; b := b + 1; End; (* Thân thủ tục M *) Begin a := 1; b := 5; Writeln(‘a = ’, a); Writeln(‘b = ’, b); M1; (* gọi thủ tục M1 *) Writeln(‘a = ’, a); Writeln(‘b = ’, b); End; (* Thân chương trình chính *) Begin x := 10; Writeln(‘x = ’, x); M; (* gọi thủ tục M *) Writeln(‘x = ’, x); End. Trong ví dụ này, chương trình chính chứa thủ tục M, thủ tục M lại chứa thủ tục M1. x là biến toàn cục được khai báo ở đầu chương trình chính, x có thể được sử dụng bất kỳ đâu trong chương trình. a và b là các biến cục bộ khai báo đầu thủ tục M, nên a và b chỉ có thể được sử dụng trong thân thủ tục M và thủ tục M1. n là biến cục bộ khái báo trong thủ tục M1, nên m chỉ có thể được sử dụng trong thân thủ tục M1. Hoạt động của chương trình này là như sau: - bắt đầu chương trình chính, biến x được gán giá trị 10, 71
- in x ra màn hình, - gọi thủ tục M, thực hiện các câu lệnh trong thân thủ tục M, o gán biến a bằng 1 và biến b bằng 5, o in ra màn hình giá trị các biến a và b, o gọi thủ tục M1, thực hiện các câu lệnh trong thân thủ tục M1,  biến toàn cục x được tăng lên một đơn vị,  gán biến cục bộ n bằng giá trị biểu thức a+b,  in n ra màn hình,  tăng mỗi biến cục bộ a và b của thủ tục M lên một đơn vị,  kết thúc thủ tục M1, quay trở về thủ tục M, o in ra giá trị của các biến cục bộ a và b, o kết thúc thủ tục M, quay trở về chương trình chính, - in ra giá trị của biến cục bộ x và kết thúc chương trình. Kết quả của chương trình trên là: x = 10 a=1 b=5 n=6 a=2 b=6 x = 11 Nhận xét: - Biến cục bộ và tham số hình thức có cơ chế hoạt động giống nhau, chúng chỉ tồn tại trong thời gian chương trình con hoạt động. - Biến toàn cục có thể bị thay đổi giá trị bất cứ đâu trong chương trình, điều này dẫn đến việc sử dung tùy tiện các biến toàn cục sẽ làm cho chương trình rất phức tạp, khó gỡ rối khi có lỗi xảy ra. Vì vậy, nên hạn chế sử dụng biến toàn cục. Cơ chế truyền tham số Ở trong các phần trên, chúng ta đã được giới thiệu cách xây dựng các chương trình con. Sau đó, chúng ta có thể sử dụng (lời gọi chương trình con) chương trình con. Mỗi khi sử dụng chương trình con, thông thường đều phải truyền dữ liệu cho nó. Có các cách truyền dữ liệu cho chương trình con khác nhau sau: - truyền tham số dạng biến toàn cục, - truyền tham số dạng tham trị, - truyền tham số dạng tham biến. D. Truyền tham số dạng biến toàn cục Do phạm vi sử dụng của biến toàn cục là bất kỳ mọi nơi trong chương trình nen ta có thể sử dụng chúng đẻ truyền dữ liệu cho các chương trình con cũng như nhận kết quả tính được từ các chương trình con. 72
Ví dụ chương trình giải phương trình bậc hai (ax2 + bx + c = 0) dưới đây truyền tham số bằng biến toàn cục. Trong ví dụ này, để giảm bớt phức tạp, chúng ta không xét đến các trường hợp suy biến của phương trình bậc 2. Program Phuong_trinh_bac_2; Var a, b, c, x1, x2, delta : real; Procedure gptb2; Var r : real; Begin delta := b*b – 4*a*c; if delta >= 0 then Begin r := sqrt(delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); End; End; (* Thân chương trình *) Begin Write(‘a = ’); readln(a); Write(‘b = ’); readln(b); Write(‘c = ’); readln(c); gptb2; (* gọi thủ tục gptb2 *) if (delta < 0) then Writeln(‘Phương trình vô nghiệm’); if (delta = 0) then Writeln(‘Phương trình có nghiệm kép: ’, x1:5:2); if (delta > 0) then Writeln(‘Phương trình có hai nghiệm: x1 = ’, x1:5:2, ‘x2 = ’, x2:5:2); End. Trong ví dụ trên, thủ tục gptb2 sử dụng 6 biến toàn cục của chương trình chính , các biến a, b, c truyền dữ liệu cho thủ tục, còn các biến x1, x2, delta nhận giá trị từ thủ tục. Nhận xét: Cách truyền tham số dùng biến toàn cục rất là đơn giản, tuy nhiên phương pháp này có nhược điểm rất lớn: vì chương trình con sử dụng biến toàn cục nên khi viết chương trình con phải luôn luôn nhớ toiư các biến này, nếu có sự thay đổi biến toàn cục trong chương trình chính thì phải thay đổi tương ứng trong chương trình con. Ngoài ra, cách sử dụng biến toàn cục như thế này rất khó để kiểm soát giá trị của chúng nên điều này thường dẫn đến sai sót. Do những nhược điểm như vây, nên người ta khuyến khích người lập trình không sử dụng phương pháp truyền tham số bằng biến toàn cục. Phương pháp dưới đây sẽ khắc phục nhược điểm trên. 73
E. Truyền tham số dạng tham trị Chúng ta cần nhắc lại rằng, đối với chương trình con có hai loại tham số. Tham số hình thức là các biến khai báo sau tên chương trình con, tham số thực là các giá trị hay biến truyền cho các tham số hình thức tương ứng khi gọi chương trình con. Tham số hình thức được chia làm hai dạng: tham trị và tham biến. Trước hết chúng ta sẽ xét đến dạng tham trị. Các tham số hình thức dạng tham trị được khai báo sau tên chương trình con giữa hai dấu ngoặc theo mẫu sau: danh_sách_tham_số : kiểu; danh_sách_tham_số : kiểu; ... Ví dụ: Function ham (x, y : real; a, b : real) : real; Procedure thutuc (x : real; a, b, c : real); Khi có lời gọi chương trình con, các tham số thực sẽ được truyền cho các tham số hình thức. Các tham số thực phải là một biểu thức cùng kiểu với tham số hình thức tương ứng. Chẳng hạn, nếu tham số hình thức có kiểu nguyên thì tham số thực phải là một biểu thức kiểu nguyên. Bây giờ chúng ta viết lại chương trình giải phương trình bậc 2 sử dụng tham số dạng tham trị như sau: Program Phuong_trinh_bac_2; Var x, y, z : real; Procedure gptb2(a, b, c : real); Var x1, x2, delta, r : real; Begin delta := b*b – 4*a*c; if delta < 0 then Writeln(”Phương trình vô nghiệm”); else Begin r := sqrt(delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); if (delta = 0) then Writeln(‘PT có nghiệm kép: ’, x1:5:2); if (delta > 0) then Writeln(‘PT có hai nghiệm: x1 = ’, x1:5:2, ‘x2 = ’, x2:5:2); End; End; (* Thân chương trình chính *) Begin Write(‘x = ’); readln(x); 74
Write(‘y = ’); readln(y); Write(‘z = ’); readln(z); gptb2(x, y, z); (* gọi thủ tục gptb2 *) End. Cơ chế hoạt động của một chương trình sử dụng tham số dạng tham trị là như sau: khi chương trình gặp một lời gọi tới chương trình con, máy sẽ: - cấp phát bộ nhớ cho biến cục bộ và các tham số hình thức dạng tham trị của chương trình con, trong ví dụ trên là cấp phát cho các biến x1, x2, delta, r và các tham số hình thức a, b, c, - truyền giá trị của các tham số thực cho các tham số dạng tham trị tương ứng, các giá trị x, y, z, được truyền vào tương ứng cho a, b, c, - thực hiện các câu lệnh trong chương trình con, - kết thúc chương trình con, máy sẽ giải phóng các biến cục bộ và các tham số hình thức, như thế các giá trị đặt trong các biến cục bộ và các tham số hình thức không thể đưa về để sử dụng trong một chương trình khác. Nhận xét: các tham số hình thức dạng tham trị chỉ được sử dụng trong chương trình con khai báo chúng. F. Truyền tham số dạng tham biến Trong ví dụ trên, các nghiệm của phương trình được in ra ngay trong thủ tục. Tuy nhiên, nếu chúng ta muốn chương trình phải trả về nghiệm của phương trình và việc in sẽ được thực hiện trong chương trình chính thì cách sử dụng tham số dạng tham trị không giải quyết được. Trong trường hợp này, chúng ta sử dụng tham số dạng tham biến, tức là giá trị của tham số vẫn được sử dụng sau khi ra khỏi chương trình con. Các tham số dạng tham biến được khai báo sau tên chương trình con giữa hai dấu ngoặc theo mẫu sau (với từ khóa Var): Var danh_sách_tham_số : kiểu; Var danh_sách_tham_số : kiểu; ... Ví dụ: Function (x,y : real; Var a : real; Var p,q : real) : real; Khi có lời gọi chương trình con, các tham số thực sẽ được truyền cho các tham số hình thức. Các tham số thực phải là một biến hay phần tử mảng có cùng kiểu với tham số hình thức tương ứng. Chẳng hạn, nếu tham số hình thức có kiểu nguyên thì tham số thực phải là một biến kiểu nguyên. Chúng ta viết lại chương trình giải phương trình bậc 2, trong đó thủ tục gptb2 nhận 3 tham số dạng tham trị là a, b, c, trả về ba giá trị bởi tham biến là delta, x1, x2. Program Phuong_trinh_bac_2; Var x, y, z, d, n1, n2 : real; Procedure gptb2(a, b, c : real; Var delta, x1, x2 : real); Var r : real; Begin delta := b*b – 4*a*c; if delta >= 0 then 75
Begin r := sqrt(delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); End; End; (* Thân chương trình chính *) Begin Write(‘x = ’); readln(x); Write(‘y = ’); readln(y); Write(‘z = ’); readln(z); gptb2(x, y, z, d, n1, n2); (* gọi thủ tục gptb2 *) if (d < 0) then Writeln(‘Phương trình vô nghiệm’); if (d = 0) then Writeln(‘Phương trình có nghiệm kép: ’, n1:5:2); if (d > 0) then Writeln(‘Phương trình có hai nghiệm: x1 = ’, n1:5:2, ‘x2 = ’, n2:5:2); End. Đối với chương trình con sử dụng tham số dạng tham biến, thì khi gặp lời gọi chương trình con, máy sẽ: - cấp phát bộ nhớ cho các biến cục bộ và các tham số dạng tham trị và tham biến, - truyền giá trị của tham số thực cho các tham số dạng tham trị tương ứng, - truyền địa chỉ của các biến tham số thực cho các tham số dạng tham biến, - thực hiện các câu lệnh trong thâm chương trình con Như thế, đối với các tham số dạng tham biến, thay vì truyền giá trị của tham số thực thì phải truyền địa chỉ của biến tham số thực. Vì vậy, mọi sự thay đổi giá trị của tham biến trong chương trình con sẽ kéo theo sự thay đổi của biến tham số thực. Trong ví dụ trên, mọi thay đổi giá trị trên các biến d, n1, n2 trong chuơng trình con cũng sẽ có hiệu lực sau khi đã thoát ra khỏi chương trình con. Đệ quy Một chương trình con được gọi là đệ quy (recursivity) nếu trong thân chương trình con đó có lời gọi đến chính nó. Nhiều ngôn ngữ lập trình cho phép xây dựng các chương trình con đệ quy. Chúng ta lấy ví dụ tính giai thừa của một số nguyên n. Giai thừa n được định nghĩa như sau: n! = 1.2.3...(n-1).n hoặc 1 nếu n = 0 n! = n.(n-1)!nếu n1 76
Trong cách định nghĩa sau, cách tính n! phụ thuộc vào (n-1)!. Với định nghĩa này chúng ta xây dựng hàm đệ quy tính n! bằng ngôn ngữ Pascal như sau: Function giai_thua1(n : longint) : longint; Begin if n = 0 then giai_thua1 := 1; else giai_thua1 := n * giai_thua1(n-1); End; Như thế, chúng ta nhận thấy hàm giai_thua1 được gọi trong khi định nghĩa chính nó. Mỗi lời gọi đệ quy cũng như lời gọi chương trình con, máy phải cấp phát bộ nhớ cho các biến cục bộ, và sau khi kết thúc thì phải giải phóng chúng. Với một chương trình con đệ quy thì có thể có nhiều lần gọi, vì vậy có bao nhiêu lần gọi thì cũng có bấy nhiêu lần cấp phát và giải phóng các biến cục bộ. Quá trình giải phóng các biến cục bộ được thực hiện theo thứ tự ngược lại quá trình cấp phát chúng: các biến cục bộ được tạo ra trước sẽ được giải phóng sau. Như thế, đối với một chương trình con đệ quy thì sẽ cần rất nhiều bộ nhớ cho các biến cục bộ. Thậm chí nếu chương trình con đệ quy thực hiện lời gọi đệ quy không dừng thì sẽ dẫn đến tình trạng tràn bộ nhớ. Chẳng hạn, nếu người sử dụng gọi hàm giai_thua1 trên như sau: n = giai_thua1(-1); thì sẽ bị lỗi tràn bộ nhớ. Tuy nhiên, chúng ta có thể dễ dàng nhận thấy rằng để tính n! chúng ta có thể sử dụng vòng lặp thay vì đệ quy như sau: Function giai_thua2(n : longint) : longint; Var i, gt : longint; Begin gt := 1; if n > 0 then for i : = 1 to n do gt := gt * i; giai_thua2 := gt; End; Bây giờ nếu, chúng ta phân tích hai lời gọi chương trình con sau: n = giai_thua1(100); n = giai_thua2(100); Với lời gọi thứ nhất, hàm giai_thua1 được gọi đệ quy đến 100 lần, và mỗi lần gọi cần cấp phát 4 byte cho tham số n kiểu longint, như thế cần 400 byte bộ nhớ. Trong khi với lời gọi thứ hai, hàm giai_thua2 chỉ được gọi 1 lần, chỉ cần cấp phát 12 byte bộ nhớ cho tham số n và hai biến cục bộ i, gt kiểu longint. Một ví dụ thứ hai minh họa chương trình con đệ quy. Ước số chung lớn nhất của hai số nguyên a và b được xác định theo công thức: - nếu x = y thì usc(x, y) = x - nếu x > y thì usc(x, y) = usc(x-y, y) - nếu x < y thì usc(x, y) = usc(x, y-x) Hàm đệ quy usc được viết như sau: 77
Function usc(a, b : int) : int; Begin if x = y then usc := x; else if x > y then usc := usc(x – y, y); else usc := usc(x, y - x); End; Nhận xét: Phương pháp đệ quy cho phép viết chương trình ngắn gọn đơn giản, nhưng lại không hiệu quả về mặt sử dụng tài nguyên bộ nhớ. Tính ưu việt của chương trình con Hầu hết tất cả các ngôn ngữ lập trình đều sử dụng khái niệm chương trình con. Chương trình con chỉ định nghĩa một lần nhưng sao đó được sử dụng nhiều lần. Việc viết chương trình sử dụng chương trình con chúng ta nhận thấy có các ưu điểm sau: - giảm bớt số dòng lệnh của một chương trình, - giảm thời gian lập trình, - giảm độ phức tạp của chương trình, - chương trình được tổ chức theo dạng tập hợp các chương trình con, nên dễ quản lý hơn, - dễ sữa đổi chương trình khi cần thiết, - dễ kiểm tra lỗi. Bài tập 1. Hai khái niệm hàm và thủ tục khác nhau chổ nào? 2. Tại sao không nên sử dụng biến toàn cục? 3. Viết thủ tục giải phương trình trùng phương ax4 + bx2 + c = 0. 4. Viết hàm tính giá trị lớn nhất (nhỏ nhất) của một dãy số. 5. Viết hàm hay thủ tục giải hệ phương trình bậc nhất: ax + by = p cx + dy = q 6. Viết hàm đệ quy tính: P(n) = 1 + 22 + 32 + ... + n2 7. Viết chương trình sử dụng hàm đệ quy đẻ tạo ra dãy số Fibonacci F1, F2, ... Fn được định nghĩa như sau: F1 = 1, F2 = 1 Fn = Fn-1 + Fn-2 Ví dụ: 1, 1, 2, 3, 5, 8, 13, 21, ... 8. Hãy viết lại hàm tính ước số chung lớn nhất của hai số nguyên sử dụng vòng lặp. 78
BÀI 4 ĐẶC TRƯNG CÚ PHÁP VÀ NGỮ NGHĨA CHƯƠNG TRÌNH Mã bài:ITPRG3-06.4 Giới thiệu Bài học sẽ trình bày tổng quan các vấn đề liên quan đến ngôn ngữ lập trình. Chẳng hạn, một ngôn ngữ lập trình được xây dựng như thế nào, làm sao để máy tính có thể hiểu được một chương trình nào đó, … Như thế, việc hiểu được bản chất của ngôn ngữ lập trình sẽ giúp cho người lập trình viết các chương trình hữu hiệu hơn. Mục tiêu thực hiện - Hiểu được cú pháp của các ngôn ngữ - Nắm các đặc trưng mang tính ngữ nghĩa của chương trình - Nắm các tiền đề cho sự phát triển của chương trình qua ngữ pháp và ngữ nghĩa - Viết chương trình có khả năng thân thiện hơn Nội dung chính Trình bày ngắn gọn cách định nghĩa, xây dựng một ngôn ngữ lập trình, cách phân tích một chương trình, các thành phần cần thiết để phân tích một chương trình. Khái niệm ngôn ngữ Một ngôn ngữ dù là ngôn ngữ tự nhiên như tiếng Việt hay là ngôn ngữ lập trình như Pascal, cũng đều có thể xem là một tập hợp các câu có cấu trúc quy định nào đó. Cấu trúc câu được quy định ra sao thì đó là vấn đề cách biểu diễn ngôn ngữ. Chúng ta có thể nhận xét thấy rằng, một câu của ngôn ngữ, dù là câu tiếng Việt “bạn đi học” hay cả một văb bản chương trình từ chữ “Program” cho đến dấu chấm “.” kết thúc chương trình, thì cũng đều chẳng qua là một dãy các xâu/từ có sẵn như “bạn”, “đi”, “học”, hay “Program”, … được liệt kê trong một bảng chữ nào đó, mà ta có thể xem là các kí hiệu cơ bản của ngôn ngữ. Từ nhận xét trên đây, chúng ta đi đến một số khái niệm hình thức về ngôn ngữ như dưới đây. Bảng chữ (alphabet) là một tập hợp các kí hiệu. Ví dụ: {a, b, c, .., z} : bảng chữ cái Latin {0,1, 2, .., 9} : bảng chữ số thập phân {0,1} : bảng chữ số nhị phân Xâu (string) là một dãy hữu hạn các kí hiệu từ bảng chữ cái. Ví dụ, với bảng chữ {0, 1} thì các xâu là 0, 1, 00, 01, 11, 001, 000, … Một cách không hình thức, ngôn ngữ (language) là một tập hợp các xâu trên một bảng chữ cái. Ví dụ, với bảng chữ {0, 1} thì ngôn ngữ trên bảng chữ này là tập hợp {0, 1, 00, 01, 11, 001, 000, …}. Cụ thể, ngôn ngữ lập trình là một hệ thống gồm các kí hiệu và các quy tắc kết hợp các kí hiệu thành một cấu trúc có ý nghĩa. Phần cú pháp (syntax) qui định sự kết hợp các kí hiệu, còn phần ngữ nghĩa qui định ý nghĩa của mỗi sự kết hợp đó. Sau đây là một ví dụ về các khía cạnh cú pháp và ngữ nghĩa trong ngôn ngữ lập trình. Chúng ta có các biểu thức sau: 79
bt1 = 2 bt2 = 1 + 1 bt3 = 1 * 2 Cả ba biểu thức trên có cùng giá trị, tức giống nhau về mặt ngữ nghĩa, tuy nhiên chúng khác nhau về mặt cú pháp. 1. Định nghĩa cú pháp Trước hết, phần này sẽ trình bày chi tiết hơn về khai niệm cú pháp, văn phạm là cơ chế để mô tả ngôn ngữ. G. Văn phạm phi ngữ cảnh Ðể xác định cú pháp của một ngôn ngữ, người ta dùng văn phạm phi ngữ cảnh CFG (Context Free Grammar). Văn phạm phi ngữ cảnh bao gồm bốn thành phần: 1. Một tập hợp các token , gọi là các ký hiệu kết thúc (terminal symbols). Ví dụ: Các từ khóa, các chuỗi, dấu ngoặc đơn, ... 2. Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols), còn gọi là các biến (variables) Ví dụ: Câu lệnh, biểu thức, ... 3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một ký hiệu chưa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token và / hoặc các ký hiệu chưa kết thúc gọi là vế phải. 4. Một trong các ký hiệu chưa kết thúc được dùng làm ký hiệu bắt đầu của văn phạm. Chúng ta qui ước: - Mô tả văn phạm bằng cách liệt kê các luật sinh. - Luật sinh chứa ký hiệu bắt đầu sẽ được liệt kê đầu tiên. - Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy nhất, trong đó các vế phải cách nhau bởi ký hiệu “ | “ đọc là “hoặc”. Ví dụ 4.1: Xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu -. Ta có, văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức. list  list + digit list  list – digit list  digit digit  0 | 1 | 2 | ...| 9 Như vậy văn phạm phi ngữ cảnh ở đây là: - Tập hợp các ký hiệu kết thúc: 0, 1, 2, ..., 9, +, - - Tập hợp các ký hiệu chưa kết thúc: list, digit. - Các luật sinh đã nêu trên. - Ký hiệu chưa kết thúc bắt đầu: list. Ví dụ 4.2 Từ ví dụ 2.1 ta thấy: 9 - 5 + 2 là một list vì: 9 là một list vì nó là một digit. 9 - 5 là một list vì 9 là một list và 5 là một digit. 80
9 - 5 + 2 là một list vì 9 - 5 là một list và 2 là một digit. Ví dụ 4.3: Một list là một chuỗi các lệnh, phân cách bởi dấu ; của khối begin - end trong Pascal. Một danh sách rỗng các lệnh có thể có giữa begin và end. Chúng ta xây dựng văn phạm bởi các luật sinh sau: block  begin opt_stmts end opt_stmts  stmt_list |  stmt_list  stmt_list ; stmt | stmt Trong đó opt_stmts (optional statements) là một danh sách các lệnh hoặc không có lệnh nào (). Luật sinh cho stmt_list giống như luật sinh cho list trong ví dụ 2.1, bằng cách thay thế +, - bởi ; và stmt thay cho digit. H. Cây phân tích cú pháp (parsing tree) Cây phân tích cú pháp minh họa ký hiệu ban đầu của một văn phạm dẫn đến một chuỗi trong ngôn ngữ. Nếu ký hiệu chưa kết thúc A có luật sinh A  XYZ thì cây phân tích cú pháp có thể có một nút trong có nhãn A và có 3 nút con có nhãn tương ứng từ trái qua phải là X, Y, Z. Hình 4.1 Cây phân tích cú pháp nhãn A Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp là một cây có các tính chất sau đây: 1. Nút gốc có nhãn là ký hiệu bắt đầu. 2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc một . 3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc. 4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong nào đó và X1 ... Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì A  X1X2 ... Xn là một luật sinh. Ở đây X1, ..., Xn có thể là ký hiệu kết thúc hoặc chưa kết thúc. Ðặc biệt, nếu A   thì nút có nhãn A có thể có một con có nhãn . 1. Các vấn đề cú pháp Sự nhập nhằng của văn phạm Một văn phạm có thể sinh ra nhiều hơn một cây phân tích cú pháp cho cùng một chuỗi nhập thì gọi là văn phạm nhập nhằng. Ví dụ 4.4: Giả sử chúng ta không phân biệt một list với một digit, xem chúng đều là một string ta có văn phạm: string  string + string | string - string | 0 | 1 | ... | 9. Với văn phạm này thì chuỗi biểu thức 9 - 5 + 2 có đến hai cây phân tích cú pháp như 81
sau : Hình 4.2 Hai cây phân tích cú pháp Tương tự với cách đặt dấu ngoặc vào biểu thức như sau : (9 - 5) + 2 9 - ( 5 + 2) Bởi vì một chuỗi với nhiều cây phân tích cú pháp thường sẽ có nhiều nghĩa, do đó khi biên dịch các chương trình ứng dụng, chúng ta cần thiết kế các văn phạm không có sự nhập nhằng hoặc cần bổ sung thêm các qui tắc cần thiết để giải quyết sự nhập nhằng cho văn phạm. Sự kết hợp của các toán tử Thông thường, theo quy ước ta có biểu thức 9 + 5 + 2 tương đương (9 + 5) + 2 và 9 - 5 - 2 tương đương với (9 - 5) - 2. Khi một toán hạng như 5 có hai toán tử ở trái và phải thì nó phải chọn một trong hai để xử lý trước. Nếu toán tử bên trái được thực hiện trước ta gọi là kết hợp trái. Ngược lại là kết hợp phải. Thường thì bốn phép toán số học: +, -, *, / có tính kết hợp trái. Các phép toán như số mũ, phép gán bằng (=) có tính kết hợp phải. Ví dụ 4.5 : Trong ngôn ngữ C, biểu thức a = b = c tương đương a = ( b = c) vì chuỗi a = b = c với toán tử kết hợp phải được sinh ra bởi văn phạm: right  letter = right | letter letter  a | b | ... | z Ta có cây phân tích cú pháp có dạng như sau (chú ý hướng của cây nghiêng về bên phải trong khi cây cho các phép toán có kết hợp trái thường nghiêng về trái): 82
Thứ tự ưu tiên của các toán tử Xét biểu thức 9 + 5 * 2. Có 2 cách để diễn giải biểu thức này, đó là 9 + (5 * 2) hoặc ( 9 + 5) * 2. Tính kết hợp của phép + và * không giải quyết được sự mơ hồ này, vì vậy cần phải quy định một thứ tự ưu tiên giữa các loại toán tử khác nhau. Thông thường trong toán học, các toán tử * và / có độ ưu tiên cao hơn + và -. Cú pháp cho biểu thức Văn phạm cho các biểu thức số học có thể xây dựng từ bảng kết hợp và ưu tiên của các toán tử. Chúng ta có thể bắt đầu với bốn phép tính số học theo thứ bậc sau : Kết hợp trái +, - Thứ tự ưu tiên Kết hợp trái *, / từ thấp đến cao Chúng ta tạo hai ký hiệu chưa kết thúc expr và term cho hai mức ưu tiên và một ký hiệu chưa kết thúc factor làm đơn vị phát sinh cơ sở của biểu thức. Ta có đơn vị cơ bản trong biểu thức là số hoặc biểu thức trong dấu ngoặc. factor  digit | (expr) Phép nhân và chia có thứ tự ưu tiên cao hơn đồng thời chúng kết hợp trái nên luật sinh cho term tương tự như cho list : term  term * factor | term / factor | factor Tương tự, ta có luật sinh cho expr : expr  expr + term | expr - term | term Vậy, cuối cùng ta thu được văn phạm cho biểu thức như sau : expr  expr + term | expr - term | term term  term * factor | term / factor | factor factor  digit | (expr) Như vậy: Văn phạm này xem biểu thức như là một danh sách các term được phân cách nhau bởi dấu + hoặc -. Term là một list các factor phân cách nhau bởi * hoặc /. Chú ý rằng bất kỳ một biểu thức nào trong ngoặc đều là factor, vì thế với các dấu ngoặc chúng ta có thể xây dựng các biểu thức lồng sâu nhiều cấp tuỳ ý. Cú pháp các câu lệnh Từ khóa (keyword) cho phép chúng ta nhận ra câu lệnh trong hầu hết các ngôn ngữ. Ví dụ trong Pascal, hầu hết các lệnh đều bắt đầu bởi một từ khóa ngoại trừ lệnh gán. Một số lệnh Pascal được định nghĩa bởi văn phạm (nhập nhằng) sau, trong đó id chỉ một danh biểu (tên biến). stmt  id := expr 83
| if expr then stmt | if expr then stmt else stmt | while expr do stmt | begin opt_stmts end Ký hiệu chưa kết thúc opt_stmts sinh ra một danh sách có thể rỗng các lệnh, phân cách nhau bởi dấu chấm phẩy (;). Dạng chuẩn Backus-Naur Thông thường để mô tả cú pháp của các ngôn ngữ lập trình người ta sử dụng dạng chuẩn Backus-Naur (Backus-Naur Form, viết tắt là BNF). Một văn phạm được định nghĩa bởi BNF gồm một dãy các quy tắc. Mỗi quy tắc gồm vế trái, dấu định nghĩa ::= (đọc được định nghĩa bởi) và vế phải. Vế trái là một kí hiệu phải được định nghĩa, còn vế phải là một dãy các kí hiệu, hợac được thừa nhận hoặc đã được định nghĩa từ trước đó, tuân theo một quy ước nào đó. BNF dùng các kí tự quy ước như sau: Kí hiệu Ý nghĩa ::=, hoặc , hoặc = được định nghĩa là {} chuỗi của 0 hoặc nhiều mục liệt kê tùy chọn [] hoặc 0 hoặc 1 mục liệt kê tùy chọn mục liệt kê phải được thay thế | hoặc (theo nghĩa loịa trừ) Các quy tắc BNF định nghĩa tên trong Pascal: ::= { | } ::= ‘A’ | … | ‘Z’ | ‘a’ | … | ‘z’ ::= ‘)’ | … | ‘9’ Ví dụ văn phạm của một ngôn ngữ lập trình đơn giản dang BNF như sau: ::= program end ::= := ; ::= while do done ::= | + |
end 1. Phân tích cú pháp Một ngôn ngữ lập trình, như trình bày ở phần trên, được thường định nghĩa bởi cú pháp hay văn phạm của nó bởi dạng chuẩn BNF. Sau đó, khi người lập trình sử dụng ngôn ngữ để viết chương trình, người lập trình phải tuân theo văn phạm đã được định nghĩa. Để kiểm tra xem một chương trình có đúng cú pháp hay không thì cần phải thực hiện phân tích cú pháp. Phân tích cú pháp là quá trình xác định xem một xâu/câu có thể được sinh ra từ một văn phạm cho trước không. Cụ thể, phân tích cú pháp của một chương trình là xác định xem từng câu lệnh của chương trình có được sinh ra bởi cú pháp của ngôn ngữ lập trình đó không. Trong phần này, chúng ta chỉ giới thiệu sơ bộ về quá trình phân tích cú pháp. Vấn đề này sẽ được trình bày đầy đủ hơn trong bài cuối cùng của môn học. Có nhiều phương pháp phân tích cú pháp khác nhau. Tuy nhiên, các phương pháp này đều nằm trong hai lớp: từ trên xuống (top down) và từ dưới lên (bttom-up). Để xác định xem một chương trình nguồn có được sinh ra từ một văn phạm hay không, các phương pháp phân tích cú pháp thường xây dựng cây phân tích của chương trình nguồn dựa trên văn phạm. Nếu tồn tại cây phân tích thì ta nói chương trình được sinh ra bởi văn phạm hay chương trình đúng cú pháp, ngược lại thì chương trình nguồn là không đúng cú pháp. Để xây dựng cây phân tích cho một chương trình nguồn, chúng ta có thể tiến hành hai cách cơ bản tương ứng với hai lớp các phương pháp phân tích cú pháp. Phương pháp phân tích từ trên xuống sẽ bắt đầu xây dựng cây phân tích từ các lá đi đến đỉnh của một câu hay chương trình cho trước. Ngược lại, phương pháp phân tích từ dưới lên sẽ bắt đầu xây dựng cây phân tích từ đỉnh đến các lá của một câu hay chương trình cho trước. Đối với mỗi lớp phương pháp phân tích cú pháp, có nhiều phương pháp khác nhau: - Phân tích cú pháp từ trên xuống gồm: o Phân tích đệ quy đi xuống: phương pháp này thực hiện việc xây dựng cây phân tích từ gốc đến lá và có khả năng quay lui (backtracking). o Phân tích cú pháp đoán nhận trước: phương này phân tích từ trên xuống nhưng không bị quay lui. o Phân tích cú pháp đoán nhận trước không đệ quy: phương này sử dụng ngăn xếp (stack) thay vì quay lui. - Phân tích cú pháp từ dưới lên gồm: o Phân tích cú pháp thứ tự yếu o Phân tích cú pháp LR Dưới đây là một ví dụ đơn giản minh họa phân tích cú pháp. Chúng có văn phạm G định nghĩa ngôn ngữ sau:  +  -   0 85