Bài giảng Ngôn ngữ lập trình - Nguyễn Văn Linh

Nguyễn Văn Linh - Programing Language - Chapter 1 1 NGÔN NGỮ LẬP TRÌNH  45 tiết = 3 đơn vị học trình  Giảng viên: Nguyễn Văn Linh  E-mail: nvlinh@ctu.edu.vn  Tel: (84) (71) 831301 Nguyễn Văn Linh - Programing Language - Chapter 1 2 TÀI LIỆU THAM KHẢO 1.-Terrence W.Part - Programming languages: Design and Implementation (second edition) - Prentice-Hall Iternational Editions 2.- Trung Việt, Ngô - Các khái niệm cơ bản của lập trình - Trung tâm khoa học tự nhiên và công nghệ quốc gia, Hà nội - 1993 3.- Jacques LONCHAMP - Les langages de programmation: concetps essentiels évolution et classification - Masson, Pais - 1989 4.- Ngôn ngữ lập trình - Ðại học mở-Bán công thành phố Hồ Chí Minh - 1994 Nguyễn Văn Linh - Programing Language - Chapter 1 3 NỘI DUNG • Mở đầu • Kiểu dữ liệu • Kiểu dữ liệu sơ cấp • Kiểu dữ liệu có cấu trúc • Kiểu do người dùng định nghĩa • Chương trình con • Ðiều khiển tuần tự • Lập trình hàm • Lập trình logic Nguyễn Văn Linh - Programing Language - Chapter 1 4 TỔNG QUAN - Cung cấp cho sinh viên những kiến thức cơ bản của ngôn ngữ lập trình, qua đó người sinh viên có thể hiểu rõ hơn về các ngôn ngữ lập trình cụ thể, sử dụng chúng một cách tốt hơn và trên cơ sở kết hợp với lý thuyết chương trình dịch để tạo ra một ngôn ngữ mới. - Cung cấp các xu hướng lập trình để sinh viên có thể tiếp cận nhanh với chúng và có được sự lựa chọn một ngôn ngữ lập trình phù hợp khi cần giải quyết các đề án tin học trong thực tế. Nguyễn Văn Linh - Programing Language - Chapter 1 5 CHƯƠNG 1: MỞ ÐẦU • Khái niệm về ngôn ngữ lập trình • Vai trò của ngôn ngữ lập trình • Lợi ích của việc nghiên cứu NNLT • Các tiêu chuẩn đánh giá một ngôn ngữ tốt Nguyễn Văn Linh - Programing Language - Chapter 1 6 KHÁI NIỆM VỀ NGÔN NGỮ LẬP TRÌNH • Là ngôn ngữ dùng để viết các chương trình cho máy tính. • NNLT cũng có từ vựng, cú pháp và ngữ nghĩa. • Ngôn ngữ máy. • Hợp ngữ. • Ngôn ngữ cấp cao. Nguyễn Văn Linh - Programing Language - Chapter 1 7 VAI TRÒ CỦA NGÔN NGỮ LẬP TRÌNH • NNLT đóng vai trò là một công cụ giúp con người thực hiện bước cài đặt trong kỹ nghệ phần mềm. • Công cụ đó ngày càng được cải tiến hoàn thiện và có thể nói mọi tiến bộ trong tin học đều thể hiện ra trong NNLT. • NNLT vừa là công cụ vừa là đối tượng nghiên cứu. Nguyễn Văn Linh - Programing Language - Chapter 1 8 LỢI ÍCH CỦA VIỆC NGHIÊN CỨU NNLT • Cho phép lựa chọn một NNLT phù hợp với dự án thực tế. • Sử dụng một cách có hiệu quả các công cụ của ngôn ngữ. • Làm tăng vốn kinh nghiệm khi xây dựng các chương trình. • Tạo sự dễ dàng để học một ngôn ngữ mới. • Tạo tiền đề để thiết kế một ngôn ngữ mới. Nguyễn Văn Linh - Programing Language - Chapter 1 9 CÁC TIÊU CHUẨN ÐÁNH GIÁ MỘT NGÔN NGỮ TỐT Tính dễ đọc. • Sự giản dị • Cấu trúc điều khiển • Kiểu dữ liệu và cấu trúc dữ liệu • Cú pháp Tính dễ viết. • Sự giản dị • Hỗ trợ cho trừu tượng • Khả năng diễn đạt Ðộ tin cậy. Chi phí Nguyễn Văn Linh - Programing Language - Chapter 1 10 CÁC TIÊU CHUẨN ÐÁNH GIÁ MỘT NGÔN NGỮ TỐT Ðộ tin cậy. • Kiểm tra kiểu • Xử lý ngoại lệ • Sự lắm tên Chi phí • Đào tạo, cài đặt chương trình • Dịch chương trình, thực hiện chương trình • Bảo trì chương trình. • Mua trình biên dịch Nguyễn Văn Linh - Programming Languages - Chapter 2 11 CHƯƠNG 2: KIỂU DỮ LIỆU Đối tượng dữ liệu. Biến và hằng. Kiểu dữ liệu. Sự khai báo. Kiểm tra kiểu. Chuyển đổi kiểu. Gán và khởi tạo. Nguyễn Văn Linh - Programming Languages - Chapter 2 12 ĐỐI TƯỢNG DỮ LIỆU Khái niệm đối tượng dữ liệu. Phân loại ĐTDL. Thuộc tính của ĐTDL. Giá trị dữ liệu. Thời gian tồn tại. Các mối liên kết. Biến và hằng. Nguyễn Văn Linh - Programming Languages - Chapter 2 13 BIẾN VÀ HẰNG Biến: – ĐTDL do lập trình viên định nghĩa và đặt tên. – Giá trị dữ liệu có thể thay đổi. Hằng: – ĐTDL có tên. – Giá trị dữ liệu không thay đổi. – Hằng trực kiện. Nguyễn Văn Linh - Programming Languages - Chapter 2 14 KIỂU DỮ LIỆU Định nghĩa kiểu dữ liệu. Đặc tả kiểu dữ liệu: – Các thuộc tính. – Các giá trị. – Các phép toán. Cài đặt kiểu dữ liệu: – Tổ chức lưu trữ trong bộ nhớ. – Giải thuật thực hiện các phép toán. Nguyễn Văn Linh - Programming Languages - Chapter 2 15 SỰ KHAI BÁO Khái niệm khai báo. Mục đích của sự khai báo: – Chọn tổ chức lưu trữ tốt nhất. – Quản lý bộ nhớ. – Các phép toán chung. – Kiểm tra kiểu. Nguyễn Văn Linh - Programming Languages - Chapter 2 16 KIỂM TRA KIỂU Kiểm tra kiểu tĩnh: Trong khi dịch. Ngôn ngữ khai báo. Thông tin về kiểu được cung cấp cho bộ dịch. Thực hiện nhanh, không bỏ sót lỗi. Không mềm dẻo. Kiểm tra kiểu động: Trong khi thực hiện. Ngôn ngữ không khai báo. Thông tin về kiểu lưu trong ĐTDL. Chậm, bỏ sót. Mềm dẻo. Nguyễn Văn Linh - Programming Languages - Chapter 2 17 CHUYỂN ĐỔI KIỂU Khi có sự không tương thích kiểu. Sử dụng hàm biến đổi kiểu.  Biến đổi kiểu tự động. Tránh lạm dụng biến đổi kiểu tự động. Nguyễn Văn Linh - Programming Languages - Chapter 2 18 PHÉP GÁN Cú pháp khác nhau. Bản chất khác nhau: – Phép gán: Kiểu X Kiểu  (Không có trị trả về). – Phép gán: Kiểu X Kiểu Kiểu (Có trị trả về). Thực hiện khác nhau: Sao chép giá tri, sao chép địa chỉ Nguyễn Văn Linh - Programming Languages - Chapter 2 19 SỰ KHỞI TẠO Khai báo và khởi tạo. Tác hại của biến chưa khởi tạo: Sự dụng nhầm giá trị rác. Biến có giá trị đầu. Nguyễn Văn Linh - Programming Languages - Chapter 3 20 CHƯƠNG 3: KIỂU DỮ LIỆU SƠ CẤP Định nghĩa. Đặc tả. Cài đặt. Kiểu dữ liệu số. Kiểu liệt kê. Kiểu logic. Kiểu ký tự. Nguyễn Văn Linh - Programming Languages - Chapter 3 21 ĐỊNH NGHĨA Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà các ÐTDL là sơ cấp. Như vậy kiểu dữ liệu sơ cấp là một tập các ÐTDL sơ cấp và tập các phép toán trên các ÐTDL đó. Các kiểu dữ liệu sơ cấp thông dụng: Nguyên, Thực, Ký tự, Logic, Liệt kê. Nguyễn Văn Linh - Programming Languages - Chapter 3 22 SỰ ĐẶC TẢ Thuộc tính: Kiểu dữ liệu. Giá trị: Tập hợp có thứ tự, có giá trị lớn nhất và giá trị nhỏ nhất. Nguyễn Văn Linh - Programming Languages - Chapter 3 23 SỰ CÀI ĐẶT Tổ chức dữ liệu trong bộ nhớ: Biểu diễn bởi phần cứng. Cài đặt các phép toán: Sử dụng phép toán phần cứng; Tạo các thủ tục hoặc hàm; Chuỗi các dòng mã lệnh. Nguyễn Văn Linh - Programming Languages - Chapter 3 24 KIỂU DỮ LIỆU SỐ Số nguyên. Miền con của số nguyên (Subranges). Số thực dấu chấm động (Floating-point real numers). Nguyễn Văn Linh - Programming Languages - Chapter 3 25 SỐ NGUYÊN Sự đặc tả các thuộc tính: Kiểu dữ liệu nguyên. Ðặc tả các phép toán: • Các phép toán số học. • Các phép toán quan hệ. • Phép gán trị. Cài đặt: Sử dụng phần cứng. Nguyễn Văn Linh - Programming Languages - Chapter 3 26 KIỂU MIỀN CON CỦA SỐ NGUYÊN Sự đặc tả: • Một dãy các số nguyên trong một khoảng đã định. • Các phép toán tương tự như kiểu số nguyên. Cài đặt: • Tốn ít bộ nhớ hơn. • Kiểm tra kiểu tốt hơn. Nguyễn Văn Linh - Programming Languages - Chapter 3 27 SỐ THỰC Đặc tả: • Một dãy có thứ tự từ một số âm nhỏ nhất đến một số dương lớn nhất có thể lưu trữ được bởi phần cứng. • Các phép toán: Tương tự số nguyên + Các hàm Cài đặt: • Sử dụng biểu diễn của phần cứng: Phần định trị và phần mũ. Nguyễn Văn Linh - Programming Languages - Chapter 3 28 KIỂU LIỆT KÊ Đặc tả: • Liệt kê danh sách các hằng trực kiện có thứ tự. • Các phép toán: quan hệ, gán, xác định phần tử đứng trước/sau một phần tử. Cài đặt: • Mỗi trực kiện được biểu diễn bởi một số nguyên không âm, chỉ cần một số bit để biểu diễn cho một giá trị. • Cài đặt các phép toán dựa vào các phép toán trên số nguyên. Nguyễn Văn Linh - Programming Languages - Chapter 3 29 KIỂU LOGIC Đặc tả: • Có thể xem như là một kiểu liệt kê: (FALSE, TRUE). • Các phép toán: NOT, AND, OR. Cài đặt: • Sử dụng một đơn vị nhớ (bite/word) để lưu trữ một giá trị logic. • Sử dụng một bit trong đơn vị nhớ để lưu 0 và 1. • Sử dụng cả đơn vị nhớ để lưu 0 và khác 0. Nguyễn Văn Linh - Programming Languages - Chapter 3 30 KIỂU KÝ TỰ (1) Sự cần thiết phải có kiểu ký tự: • Tất cả dữ liệu từ thiết bị nhập, xuất đều là ký tự, chuỗi ký tự. • Có một sự chuyển đổi tự động từ ký tự (chuỗi ký tự) thành số khi nhập hay xuất. • Ngôn ngữ vẫn cần xử lý ký tự một cách trực tiếp (văn bản). • Dựa vào kiểu ký tự để xây dựng kiểu chuỗi ký tự. Nguyễn Văn Linh - Programming Languages - Chapter 3 31 KIỂU KÝ TỰ (2) Đặc tả: • Một liệt kê các ký tự được định nghĩa bởi ngôn ngữ, tương ứng với các ký tự chuẩn của phần cứng và hệ điều hành. • Các phép toán: Quan hệ, phép gán. Cài đặt: • Sử dụng phần cứng và hệ điều hành. Nguyễn Văn Linh - Programming Languages - Chapter 4 32 CHƯƠNG 4: KIỂU DỮ LIỆU CÓ CẤU TRÚC  Định nghĩa kiểu dữ liệu có cấu trúc.  Sự đặc tả kiểu dữ liệu có cấu trúc.  Sự cài đặt các cấu trúc dữ liệu.  Vectơ (mảng một chiều).  Mảng nhiều chiều.  Mẩu tin và mẩu tin có cấu trúc thay đổi.  Chuỗi ký tự.  Cấu trúc dữ liệu có kích thước thay đổi (Danh sách, Con trỏ, Tập hợp, Tập tin). Nguyễn Văn Linh - Programming Languages - Chapter 4 33 ĐỊNH NGHĨA Kiểu dữ liệu có cấu trúc hay còn gọi là CTDL là kiểu dữ liệu mà các ÐTDL có cấu trúc. Như vậy CTDL là một tập các ÐTDL có cấu trúc và tập các phép toán trên các ÐTDL đó. Các CTDL thông dụng: Mảng, chuỗi ký tự, mẩu tin, ngăn xếp, con trỏ, tập tin... Nguyễn Văn Linh - Programming Languages - Chapter 4 34 SỰ ĐẶC TẢ Thuộc tính: • Số lượng phần tử. • Kiểu của các phần tử. • Tên của phần tử. • Kích thước tối đa. • Tổ chức phần tử. Phép toán: • Lựa chọn phần tử. • Phép toán trên toàn cấu trúc. • Thêm/bớt phần tử, tạo/hủy cấu trúc. Nguyễn Văn Linh - Programming Languages - Chapter 4 35 ĐẶC TẢ THUỘC TÍNH Số lượng phần tử: Kích thước cố định, kích thước thay đổi. Kiểu phần tử: Đồng nhất và không đồng nhất. Tên của phần tử: Chỉ số, tên trường. Kích thước tối đa: Số lượng lớn nhất các phần tử. Tổ chức phần tử: Một dãy các phần tử. Nguyễn Văn Linh - Programming Languages - Chapter 4 36 ĐẶC TẢ PHÉP TOÁN Phép toán lựa chọn một phần tử: Chọn trực tiếp và chọn tuần tự. Phép toán trên toàn cấu trúc: Gán. Thêm / Bớt phần tử: Làm thay đổi kích thước. Tạo / Hủy cấu trúc. Nguyễn Văn Linh - Programming Languages - Chapter 4 37 SỰ CÀI ĐẶT Biểu diễn bộ nhớ: • Biểu diễn tuần tự. • Biểu diễn liên kết. Cài đặp phép toán chọn một phần tử: • Chọn trực tiếp trong biểu diễn tuần tự. • Chọn tuần tự trong biểu diễn tuần tự . • Chọn trực tiếp trong biểu diễn liên kết. • Chọn tuần tự trong biểu diễn liên kết. Nguyễn Văn Linh - Programming Languages - Chapter 4 38 BIỂU DIỄN BỘ NHỚ  Biểu diễn tuần tự Biểu diễn liên kết Bộ mô tả Phần tử Phần tử Bộ mô tả Phần tử Nguyễn Văn Linh - Programming Languages - Chapter 4 39 CÀI ĐẶT PHÉP TOÁN Chọn trực tiếp trong biểu diễn tuần tự: Vị trí phần tử = địa chỉ cơ sở + độ dời. Chọn tuần tự trong biểu diễn tuần tự: Xác định vị trí phần tử đầu tiên. Vị trí phần tử tiếp theo = Vị trí phần tử hiện hành + Kích thước phần tử hiện hành. Lựa chọn trong biểu diễn liên kết: Duyệt từ đầu danh sách. Nguyễn Văn Linh - Programming Languages - Chapter 4 40 VÉCTƠ (MẢNG MỘT CHIỀU) Định nghĩa: Là CTDL có kích thước cố định và đồng nhất. Đặc tả: – Số lượng phần tử: Tập chỉ số. – Kiểu của tất cả các phần tử. – Tên phần tử: Chỉ số của phần tử. – Phép tóan lựa chọn một phần tử: Chọn trực tiếp bằng cách chỉ ra chỉ số của phần tử. Chỉ số là giá trị của biểu thức. – Phép toán gán. – Ví dụ: V : ARRAY[1..10] OF REAL 41 CÀI ĐẶT VÉCTƠ (1) Tổ chức lưu trữ: Biểu diễn tuần tự. Véc tơ A LB UB Kiểu phần tử Địa chỉ cơ sởBộ mô tả Các phần tử Kiểu dữ liệuCận dưới tập chỉ số Cận trên tập chỉ sốKích thước mỗi PT Nguyễn Văn Linh - Programming Languages - Chapter 4 42 CÀI ĐẶT VÉCTƠ (2) Phép toán lựa chọn 1 phần tử: Vị trí phần tử thứ i =  + D + (i – LB)* E –  là địa chỉ cơ sở. – D là kích thước bộ mô tả. Phép toán gán: Copy khối ô nhớ. Nguyễn Văn Linh - Programming Languages - Chapter 4 43 MẢNG NHIỀU CHIỀU Đặc tả: Mỗi chiều có một tập chỉ số. Cài đặt: Biểu diễn bộ nhớ tuần tự, các phần tử được lưu trũ kế tiếp nhau, nhưng có 2 cách lưu: – Các phần tử được lưu theo trật tự dòng: Hết dòng này đến dòng khác. – Các phần tử được lưu theo trật tự cột: Hết cột này đến cột khác. 44 BIỂU DIỄN MA TRẬN M[1..3,-1..2] OF INTEGER Cận trên tập chỉ số 1Cận dưới tập chỉ số 2Cận trên tập chỉ số 2 Ma trận M LB1 (=1) UB1 (=3) LB2 (=-1) Địa chỉ cơ sởBộ mô tả Các phần tử Kiểu dữ liệuCận dưới tập chỉ số 1 Nguyễn Văn Linh - Programming Languages - Chapter 4 45 CHỌN MỘT PHẦN TỬ CỦA MA TRẬN Vị trí của phần tử M[i,j] được tính theo công thức: Vị trí M[i,j] =  + D + (i-LB1)*S + (j-LB2)*E  là địa chỉ cơ sở. D là kích thước bộ mô tả. S là kích thước 1 dòng = (UB2-LB2+1)*E. E là kích thước một phần tử. Nguyễn Văn Linh - Programming Languages - Chapter 4 46 MẨU TIN  Định nghĩa: Là CTDL có kích thước cố định và không đồng nhất.  Đặc tả: – Số lượng phần tử (trường). – Tên của mỗi phần tử. – Kiểu của mỗi phần tử. – Phép toán chọn phần tử: Sử dụng tên PT. – Phép gán. Ví dụ: Nhan_vien: Record Ma: Integer; Ho_ten: string[25]; Tuoi: Integer; Luong: Real; End. 47 CÀI ĐẶT MẨU TIN Bộ nhớ tuần tự: Một khối ô nhớ liên tục để lưu trữ cả mẩu tin. Mỗi trường được lưu trong một khối. Mỗi khối có thể có bộ mô tả riêng. Ví dụ: Nhan_vien 22901 Nguyễn Văn A 20 2.18 Vị trí phần tử =  + Tổng kích thước các phần tử trước đó. Ví dụ: Vị trí Tuoi =  + Kích thước Ma + Kích thước Ho_ten Ma Ho_t enTuoi Luon g Nguyễn Văn Linh - Programming Languages - Chapter 4 48 MẨU TIN CÓ CẤU TRÚC THAY ĐỔI Bài toán. Định nghĩa. Cài đặt. Nguyễn Văn Linh - Programming Languages - Chapter 4 49 MẨU TIN CÓ CẤU TRÚC THAY ĐỔI (BÀI TOÁN) Ví dụ: Một xí nghiệp có hai loại công nhân: Biên chế và hợp đồng. Lương công nhân biên chế = Số ngày công * múc lương tối thiểu * Hệ số /20. Những ngày nghỉ bảo hiểm xã hội, họ được trả lương bảo hiểm. Lương công nhân hợp đồng = Số ngày công * đơn giá công nhật. Nguyễn Văn Linh - Programming Languages - Chapter 4 50 ĐỊNH NGHĨA MẨU TIN CÓ CẤU TRÚC THAY ĐỔI Mỗi mẩu tin bao gồm hai phần: Phần tĩnh và phần động. Phần tĩnh gồm các trường mà tất cả các thể hiện đều có. Phần động sẽ có các trường khác nhau tùy theo từng thể hiện. Trong phần tĩnh phải có một trường dùng để phân biệt các thể hiện. Phép toán lựa chọn một phần tử tương tự như mẩu tin bình thường. 51 VÍ DỤ TYPE Loai_Cong_Nhan = (bien_che,hop_dong); VAR Cong_Nhan : RECORD Ho_Ten: String[20]; Ngay_Cong: Real; Luong: Real; CASE loai: Loai_Cong_Nhan OF bien_che: (He_So: Real; Nghi_bhxh:Real); hop_dong: (Gia_Cong_Nhat: Real); END; Nguyễn Văn Linh - Programming Languages - Chapter 4 52 CÀI ĐẶT MẨU TIN CÓ CẤU TRÚC THAY ĐỔI Ho_Ten Ngay_C ong Luong Loai Gia_Co Ho_Ten Ngay_C ong Luong Loai He_So Nguyễn Văn Linh - Programming Languages - Chapter 4 53 CHUỖI KÝ TỰ Đặc tả thuộc tính. Đặc tả phép tóan. Cài đặt chuỗi ký tự. Nguyễn Văn Linh - Programming Languages - Chapter 4 54 ĐẶC TẢ THUỘC TÍNH CHUỖI KÝ TỰ Đặc tả thuộc tính: Có ba phương pháp: – Độ dài khai báo cố định. – Độ dài thay đổi trong một giới hạn đã được khai báo. – Độ dài không giới hạn. Nguyễn Văn Linh - Programming Languages - Chapter 4 55 ĐẶC TẢ PHÉP TOÁN CHUỖI KÝ TỰ Đặc tả phép toán: – Phép ghép chuỗi. – Các phép toán quan hệ. – Lấy chuỗi con của một chuỗi bằng cách chỉ ra ký tự đầu tiên và ký tự cuối cùng. – Định dạng nhập - xuất. – Chọn chuỗi con bằng cách so mẫu. Nguyễn Văn Linh - Programming Languages - Chapter 4 56 CÀI ĐẶT CHUỖI KÝ TỰ (1) Độ dài khai báo cố định: Sử dụng một véctơ của các ký tự để lưu trữ một chuỗi Ví dụ chuỗi được khai báo có độ dài 12 nhưng chuỗi thực là “EINSTEIN”. Thì phải thêm vào 4 ký tự trắng để có độ dài 12. E I N S T E I N Nguyễn Văn Linh - Programming Languages - Chapter 4 57 CÀI ĐẶT CHUỖI KÝ TỰ (2) Độ dài thay đổi trong giới hạn đã khai báo: Sử dụng một véctơ để lưu trữ một chuỗi và có bộ mô tả lưu cả độ dài được khai báo và độ dài thực. Ví dụ chuỗi được khai báo có độ dài 12 nhưng chuỗi thực là “EINSTEIN”. Sẽ có 4 ô không sử dụng. 12 8 E I N S T E I N Nguyễn Văn Linh - Programming Languages - Chapter 4 58 CÀI ĐẶT CHUỖI KÝ TỰ (3) Độ dài không cố định: Sử dụng biểu diễn liên kết có bộ mô tả lưu trữ độ dài thực của chuỗi. Ví dụ chuỗi cần lưu trữ là “EINSTEIN”. 8 E I N S E I NT Nguyễn Văn Linh - Programming Languages - Chapter 4 59 CẤU TRÚC DỮ LIỆU CÓ KÍCH THƯỚC THAY ĐỔI Định nghĩa: Là CTDL có số phần tử thay đổi một cách động trong quá trình thực hiện chương trình. Một số cấu trúc điển hình: – Danh sách. – Ngăn xếp. – Hàng đợi. Nguyễn Văn Linh - Programming Languages - Chapter 4 60 CON TRỎ Cấp phát tĩnh, cấp phát động và con trỏ. Đặc tả. Ví dụ. Cài đặt. Nguyễn Văn Linh - Programming Languages - Chapter 4 61 CON TRỎ (Cấp phát ...) Cấp phát tĩnh: Trong khi dịch. Nhờ khai báo biến, bộ dịch sẽ dành sẵn ô nhớ đủ để lưu trữ. Tự động giải phóng. Sử dụng nhờ tên biến Không tối ưu. Cấp phát động: Trong khi thực hiện. Người lập trình chủ động cấp phát và giải phóng. Sử dụng thông qua địa chỉ. Cần có biến con trỏ để lưu trữ địa chỉ. Nguyễn Văn Linh - Programming Languages - Chapter 4 62 ĐẶC TẢ CON TRỎ Con trỏ tham chiếu đến các ĐTDL có kiểu cụ thể. Con trỏ tham chiếu đến các ĐTDL có kiểu bất kỳ. Phép toán cấp phát ô nhớ động và trả địa chỉ về cho con trỏ. Phép toán truy xuất tới ĐTDL được cấp phát động. Phép toán giải phóng ô nhớ. Nguyễn Văn Linh - Programming Languages - Chapter 4 63 VÍ DỤ VỀ CON TRỎ (1) Con trỏ tham chiếu đến các ĐTDL có kiểu cụ thể Type Sinh_vien = Record Ho_ten : String[25]; Tuoi : Byte; End; Var p : ^Sinh_vien; q : ^Integer; Nguyễn Văn Linh - Programming Languages - Chapter 4 64 VÍ DỤ VỀ CON TRỎ (2) Begin New(p); p^.Ho_ten:= ‘Nguyen Van A’; p^.tuoi := 20; Writeln(p^.Ho_ten, ‘ ‘, p^.tuoi); Dispose(p); New(q); q^ := 3547; End. Nguyễn Văn Linh - Programming Languages - Chapter 4 65 VÍ DỤ VỀ CON TRỎ (3) Con trỏ tham chiếu đến các ĐTDL có kiểu bất kỳ Type Sinh_vien = Record Ho_ten : String[25]; Tuoi : Byte; End; Var p : pointer ; Nguyễn Văn Linh - Programming Languages - Chapter 4 66 VÍ DỤ VỀ CON TRỎ (4) Begin GetMem(p, SizeOf(Sinh_vien)); {................ } FreeMem(p, SizeOf(Sinh_Vien)); GetMem(p, SizeOf(Integer)); {................. } FreeMem(p, SizeOf(Integer)); End. Nguyễn Văn Linh - Programming Languages - Chapter 4 67 CÀI ĐẶT CON TRỎ Địa chỉ tuyệt đối: Giá trị con trỏ là địa chỉ thực của khối ô nhớ cấp phát động. Phương pháp này thường dùng cho con trỏ tham chiếu đến một ĐTDL có kiểu cụ thể. Địa chỉ tương đối: Giá trị con trỏ là độ dời của khối ô nhớ cấp phát động. Địa chỉ của khối ô nhớ = địa chỉ cơ sở + giá trị con trỏ (độ dời). Nguyễn Văn Linh - Programming Languages - Chapter 4 68 TẬP HỢP Đặc tả. Cài đặt tập hợp bằng véctơ bit. Cài đặt tập hợp bằng bảng băm. Nguyễn Văn Linh - Programming Languages - Chapter 4 69 ĐẶC TẢ TẬP HỢP CTDL đồng nhất và có kích thước thay đổi; Không quan tâm đến thứ tự các phần tử; Giá trị các phần tử khác nhau. Phép toán kiểm tra một giá trị có thuộc một tập hợp? Thêm, Bớt phần tử. Hợp, giao và hiệu của hai tập hợp. Nguyễn Văn Linh - Programming Languages - Chapter 4 70 CÀI ĐẶT TẬP HỢP BẰNG VECTO BIT Một tập hợp được biểu diễn bởi một véctơ các bit 0 hoặc 1. Phép kiểm tra. Phép Thêm và Bớt. Phép Hợp, Giao và Hiệu Ưu điểm: dễ dàng cài đặt. Nhược điểm: Không gian nhỏ. Nguyễn Văn Linh - Programming Languages - Chapter 4 71 CÀI ĐẶT TẬP HỢP BẰNG BẢNG BĂM Tập hợp là một bảng băm mở. Phép kiểm tra. Phép Thêm và Bớt. Phép Hợp, Giao và Hiệu Ưu điểm: cài đặt cho tập hợp bất kỳ, các phép kiểm tra, thêm, bớt dễ thực hiện. Nhược điểm: khó thực hiện các phép hợp, giao, hiệu. Nguyễn Văn Linh - Programming Languages - Chapter 4 72 TẬP TIN Tập tin tuần tự Tập tin văn bản. Tập tin truy xuất trực tiếp Nguyễn Văn Linh - Programming Languages - Chapter 4 73 TẬP TIN TUẦN TỰ Đặc tả: một dãy tuyến tính các phần tử có cùng kiểu. Ðộ dài của tập tin là không giới hạn. Kiểu phần tử có thể là kiểu sơ cấp hoặc kiểu cấu trúc có kích thước cố định như mảng hoặc mẩu tin Mode read, mode write, con trỏ tập tin. Phép toán: open, read, write, EOF, close Nguyễn Văn Linh - Programming Languages - Chapter 4 74 CÀI ĐẶT TẬP TIN TUẦN TỰ Hệ điều hành. Giao tiếp giữa bộ nhớ trong và bộ nhớ ngoài thông qua buffer. Nguyễn Văn Linh - Programming Languages - Chapter 4 75 CÁC LOẠI TẬP TIN KHÁC Tập tin văn bản: Tập tin tuần tự đặc biệt, các phần tử là kí tự. Tập tin truy xuất trực tiếp: Có thể nhẩy đến truy xuất phần tử bất kỳ. Nguyễn Văn Linh - Programming Languages - Chapter 7 76 CHƯƠNG 5: ĐIỀU KHIỂN TUẦN TỰ Khái niệm về điều khiển tuần tự (ĐKTT). ĐKTT trong biểu thức. ĐKTT tự giữa các lệnh. Ngoại lệ và xử lý ngoại lệ. Nguyễn Văn Linh - Programming Languages - Chapter 7 77 KHÁI NIỆM ĐIỀU KHIỂN TUẦN TỰ Tập hợp các quy tắc xác định thứ tự thực hiện trong chương trình. ĐKTT trong biểu thức. ĐKTT giữa các lệnh. ĐKTT chương trình con. ĐKTT ẩn. ĐKTT tường minh. Nguyễn Văn Linh - Programming Languages - Chapter 7 78 ĐIỀU KHIỂN TRONG BIỂU THỨC Đặt vấn đề. Biểu diễn biểu thức theo cấu trúc cây. Cú pháp của biểu thức: Tiền tố, hậu tố và trung tố. Trong biểu thức trung tố: Phải sử dụng tiền tố, nguyên tắc kết hợp, độ ưu tiên. Dịch biểu thức thành biểu diễn cây. Biểu diễn trong thời gian thực hiện. Nguyễn Văn Linh - Programming Languages - Chapter 7 79 ĐIỀU KHIỂN TUẦN TỰ GIỮA CÁC LỆNH Các lệnh cơ bản. ĐKTT dùng nhãn lệnh và GOTO: – GOTO không điều kiện. – GOTO có điều kiện. – Sử dụng GOTO để thực hiện các lệnh khác. Các lệnh cấu trúc. 80 SỬ DỤNG GOTO ĐỂ THỰC HIỆN CÁC LỆNH Hợp thành Lựa chọn Lặp S0 S0 S0 GOTO L1 IF a=0 GOTO L1 L1: IF a=0 GOTO L2 L2: S2 S1 S1 GOTO L3 GOTO L2 GOTO L1 L1: S1 L1: S2 L2: S2 GOTO L2 L2: S3 L3: S3 Chuỗi lệnh thực hiện Chuỗi lệnh thực hiện Chuỗi lệnh thực hiện S0 S1 S2 S3 S0 S2 S3 Hoặc S0 S2 hoặc S0 S1 S3 S0 S1 S2 hoặc S0 S1 S1 S2 hoặc S0 S1 S1 S2 .... Nguyễn Văn Linh - Programming Languages - Chapter 7 81 CÁC LỆNH CẤU TRÚC Lệnh hợp thành. Lệnh điều kiện: IF, CASE. Lệnh lặp: WHILE, FOR, LOOP... Nguyễn Văn Linh - Programming Languages - Chapter 7 82 NGOẠI LỆ VÀ XỬ LÝ NGOẠI LỆ Một số khái niệm. Xử lý ngoại lệ. Đề xuất một ngoại lệ. Lan truyền ngoại lệ. Sau khi một ngoại lệ được xử lý. Nguyễn Văn Linh - Programming Languages - Chapter 7 83 MỘT SỐ KHÁI NIỆM Ngoại lệ (exceptions): Sự cố đặc biệt. Xử lý ngoại lệ: Gọi một chương trình con đặc biệt để xử lý các sự cố đó. Đề xuất một ngoại lệ: Phát hiện sự kiện, ngắt sự thực hiện chương trình và chuyển điều khiển đến chương trình con xử lý ngoại lệ. Nguyễn Văn Linh - Programming Languages - Chapter 7 84 XỬ LÝ NGOẠI LỆ (1) Các ngoại lệ được định nghĩa trước bởi ngôn ngữ: ZERO_DIVIDE, OVERFLOW,... Ví dụ: Nguyễn Văn Linh - Programming Languages - Chapter 7 85 XỬ LÝ NGOẠI LỆ (2) Ví dụ: Public void Read_a_file () { ....... try { RandomAccessFile file = new RandomAccessFile(pathname. “r”); while (file.getFilePointer() < file.length()) { .... } } Catch (Exception e) {system.out.println(“Error...”+e.toString()); } ..... } Nguyễn Văn Linh - Programming Languages - Chapter 7 86 ĐỀ XUẤT MỘT NGOẠI LỆ Đề xuất ẩn. Đề xuất bởi người lập trình. Nguyễn Văn Linh - Programming Languages - Chapter 7 87 LAN TRUYỀN NGOẠI LỆ Một ngoại lệ có thể được đề xuất từ một chỗ và được xử lý tại một chỗ khác. Lan truyền ngoại lệ từ điểm được đề xuất đến điểm được xử lý. Giả sử có một ngoại lệ P được đề xuất trong chương trình con C. Nếu trong C không có một xử lý cho P thì C kết thúc và truyền ngoại lệ đến B (chương trình gọi C). Nếu trong B không có một xử lý.... Cuối cùng một xử lý của ngôn ngữ sé được gọi tới. Nguyen Van Linh - Programing Language - Chapter 8 88 CHƯƠNG 6: LẬP TRÌNH HÀM Ngôn ngữ lập trình hàm • Giới thiệu. • Hàm toán học. • Dạng hàm. • Bản chất của lập trình hàm. Ngôn ngữ LISP Nguyen Van Linh - Programing Language - Chapter 8 89 NGÔN NGỮ LISP Giới thiệu. Các khái niệm cơ bản. Các hàm. Đệ quy. Biến toàn cục và biến cục bộ. Các hàm nhập xuất. Hướng dẫn sử dụng Lisp. Nguyen Van Linh - Programing Language - Chapter 8 90 LISP: GIỚI THIỆU Được J. MAC CARTHY viết năm 1958. Phát triển mạnh vào đầu những năm 80. Cú pháp đơn gỉan. Là một ngôn ngữ mạnh. Mềm dẻo và dễ phát triển. Áp dụng trong lĩnh vực trí tuệ nhân tạo. Nguyen Van Linh - Programing Language - Chapter 8 91 CÁC KHÁI NIỆM CƠ BẢN Nguyên tử (Atom): Số, kí hiệu. Danh sách: Dã̃y có thứ tự các nguyên tử hoặc danh sách, nằm trong cặp dấu ngoặc đơn (). Biểu thức và nguyên tắc lượng giá: • Số. • Ký hiệu. • Danh sách. Nguyen Van Linh - Programing Language - Chapter 8 92 HÀM ĐỊNH NGHĨA TRƯỚC • Các hàm số học: +, -, *, /, 1+, 1- • Các hàm so sánh: , =, =, eq. • Các hàm thao tác trên danh sách: CAR, CDR, CONS và LIST. • Các vị từ kiểm tra: (atom a), (numberp n), (listp l), (symbol s),... • Các hàm logic AND, OR, NOT. • Các hàm điều khiển IF, COND, PROGN, PROG1 Nguyen Van Linh - Programing Language - Chapter 8 93 HÀM DO NGƯỜI DÙNG ĐỊNH NGHĨA Cú pháp: (defun (Các tham số hình thức) ) Ví dụ: (defun binh_phuong (n) (* n n) ) (defun lap_phuong (n) (* n (binh_phuong n)) ) Nguyen Van Linh - Programing Language - Chapter 8 94 ĐỆ QUY Một trường hợp “nguyên tố” để kết thúc việc gọi đệ quy. Lời gọi đệ quy phải bao hàm yếu tố dẫn đến trường hợp “nguyên tố”. Ví du: Tính n giai thừa (defun giai_thua (n) (if (= n 0) 1 ; Trường hợp “nguyên tố” (* n (giai_thua (1- n))) ) ) Nguyen Van Linh - Programing Language - Chapter 8 95 BIẾN TOÀN CỤC & BIẾN CỤC BỘ (SETQ ). (LET ((var1 E1) (var2 E2) ... (vark Ek)) Ek+1 ... En) Hạn chế sử dụng biến toàn cục. Nguyen Van Linh - Programing Language - Chapter 8 96 CÁC HÀM NHẬP XUẤT • LOAD( ). • (READ) • (PRINT e) • (PRINC e) • (TERPRI) Nguyen Van Linh - Programing Language - Chapter 8 97 HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH Soạn thảo chương trình: • Sử dụng bất kỳ editor nào. • Phầ̀̀n mở rộng .LSP. • Trong một tập tin, có thể định nghĩa nhiều hàm. Gọi thực hiện XLISP: • Trong Windows 3.x. • Trong Windows 9x. • Sử dụng menu File-Open/Load để mở tập tin chương trình. Nguyễn Văn Linh - Programing Language - Chapter 2 98 CHƯƠNG 7: LẬP TRÌNH LOGIC GIỚI THIỆU. • Bài toán được mô tả dưới dạng biểu thức logic các vị từ. • Để giải được bài toán, cần có một cơ sở tri thức. • Khi có một yêu cầu, hệ thống sẽ dựa vào cơ sở tri thúc để suy diễn. NGÔN NGỮ PROLOG. Nguyễn Văn Linh - Programing Language - Chapter 2 99 NGÔN NGỮ PROLOG Giới thiệu. • Được Philippe Roussel, Alian Calmerour phát triển vào đầu thập niên 70. Cấu trúc chương trình. Nguyễn Văn Linh - Programing Language - Chapter 2 100 SỰ CÀI ĐẶT Tổ chức dữ liệu trong bộ nhớ: Biểu diễn bởi phần cứng. Cài đặt các phép toán: Sử dụng phép toán phần cứng; Tạo các thủ tục hoặc hàm; Chuỗi các dòng mã lệnh. Nguyễn Văn Linh - Programing Language - Chapter 2 101 KIỂU DỮ LIỆU SỐ Số nguyên. Miền con của số nguyên (Subranges). Số thực dấu chấm động (Floating-point real numers). Nguyễn Văn Linh - Programing Language - Chapter 2 102 SỐ NGUYÊN Sự đặc tả các thuộc tính: Kiểu dữ liệu nguyên. Ðặc tả các phép toán: • Các phép toán số học. • Các phép toán quan hệ. • Phép gán trị. Cài đặt: Sử dụng phần cứng. Nguyễn Văn Linh - Programing Language - Chapter 2 103 MIỀN CON CỦA SỐ NGUYÊN Sự đặc tả: • Một dãy các số nguyên trong một khoảng đã định. • Các phép toán tương tự như kiểu số nguyên. Cài đặt: • Tốn ít bộ nhớ hơn. • Kiểm tra kiểu tốt hơn. Nguyễn Văn Linh - Programing Language - Chapter 2 104 SỐ THỰC DẤU CHẤM ĐỘNG Đặc tả: • Một dãy có thứ tự từ một số âm nhỏ nhất đến một số dương lớn nhất có thể lưu trữ được bởi phần cứng. • Các phép toán: Tương tự số nguyên + Các hàm Cài đặt: • Sử dụng biểu diễn của phần cứng: Phần định trị và phần mũ. Nguyễn Văn Linh - Programing Language - Chapter 2 105 KIỂU LIỆT KÊ Đặc tả: • Liệt kê danh sách các hằng trực kiện có thứ tự. • Các phép toán: quan hệ, gán, xác định phần tử đứng trước/sau một phần tử. Cài đặt: • Mỗi trực kiện được biểu diễn bởi một số nguyên không âm, chỉ cần một số bit để biểu diễn cho một giá trị. • Cài đặt các phép toán dựa vào các phép toán trên số nguyên. Nguyễn Văn Linh - Programing Language - Chapter 2 106 KIỂU LOGIC Đặc tả: • Có thể xem như là một kiểu liệt kê: (FALSE, TRUE). • Các phép toán: NOT, AND, OR. Cài đặt: • Sử dụng một đơn vị nhớ (bite/word) để lưu trữ một giá trị logic. • Sử dụng một bit trong đơn vị nhớ để lưu 0 và 1. • Sử dụng cả đơn vị nhớ để lưu 0 và khác 0. Nguyễn Văn Linh - Programing Language - Chapter 2 107 KIỂU KÝ TỰ Sự cần thiết phải có kiểu ký tự: • Tất cả dữ liệu từ thiết bị nhập, xuất đều là ký tự, chuỗi ký tự. • Có một sự chuyển đổi tự động từ ký tự (chuỗi ký tự) thành số khi nhập hay xuất. • Ngôn ngữ vẫn cần xử lý ký tự một cách trực tiếp (văn bản). • Dựa vào kiểu ký tự để xây dựng kiểu chuỗi ký tự. Nguyễn Văn Linh - Programing Language - Chapter 2 108 KIỂU KÝ TỰ Đặc tả: • Một liệt kê các ký tự được định nghĩa bởi ngôn ngữ, tương ứng với các ký tự chuẩn của phần cứng và hệ điều hành. • Các phép toán: Quan hệ, phép gán. Cài đặt: • Sử dụng phần cứng và hệ điều hành. Nguyễn Văn Linh - Programing Language - Chapter 1 109