Tài liệu Các nguyên lý sáng tạo và áp dụng vào xây dựng trình biên dịch

ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH TR ƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA : CÔNG NGHỆ THÔNG TIN  CÁC NGUYÊN LÝ SÁNG TẠO VÀ ÁP DỤNG VÀO XÂY DỰNG TRÌNH BIÊN DỊCH Môn học:Phương phá p nghiên cứu khoa học Giảng viên hướng dẫn:GS.TSKH Hoàng Kiếm Học v iên t hực hiên:Võ Ngọc Tâ n – 1212034 Khóa:Cao học K22 – Hệ Thống Thông Tin TP.Hồ Chí Minh, ngày 14 tháng 12 năm 2012 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 Lời cám ơn Lời đầu tiên, em xin chân thành cám ơn thầy GS.TSKH Hoàng Kiếm đã nhiệt tình giảng dạy em và các bạn học viên cao học khóa 22 trong môn Phương pháp nghiên cứu k hoa học. Thầy đã giúp chúng em nắm rõ về các phương pháp luận sáng tạo trong khoa học nói chung và trong lĩnh vực công nghệ thông tin nói riêng. Môn học này tối cần thiết cho việc định hướng những công trình nghiên cứu khoa học, đồng thời hỗ trợ tốt trong việc nghiên cứu và hoàn thành luận văn tốt nghiệp thạc sĩ. Xin trân trọng cảm ơn thầy.Kính chúc thầy nhiều sức khỏe, nhiều niềm vui để đạt được nhiều thành tựu trong nghiên cứu khoa học cũng như công việc giảng dạy. 1 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 MỤC LỤC CÁC PHƯƠNG PHÁ P NGUY ÊN CỨU KHOA HỌC ỨNG DỤNG TRONG XÂY DỰNG TRÌNH BIÊN DỊCH ...................................................................................................................................2 1. NGUY ÊN TẮC PHÂ N NHỎ ..............................................................................................2 2. NGUY ÊN TẮC TÁCH KHỎI..............................................................................................4 3. NGUY ÊN TẮC VẠN NĂNG .............................................................................................4 4. NGUY ÊN TẮC CHỨA TRONG ........................................................................................4 5. NGUY ÊN TẮC KẾT HỢP .................................................................................................7 6. NGUY ÊN TẮC THỰC HIỆN SƠ BỘ ................................................................................7 7. NGUY ÊN TẮC PHẢ N ĐỐI XỨNG....................................................................................8 8. NGUY ÊN TẮC SỬ DỤNG ĐỐI TƯỢNG TRUNG GIAN..................................................8 9. NGUY ÊN TẮC SAO CHÉP...............................................................................................8 10. NGUY ÊN TẮC RẺ THAY ĐẮT......................................................................................8 11. NGUY ÊN TẮC TÁC ĐỘNG THEO CHU KỲ.................................................................9 12. NGUY ÊN TẮC DỰ PHÒNG..........................................................................................9 13. NGUY ÊN TẮC LINH ĐỘNG..........................................................................................9 14. NGUY ÊN TẮC ĐẢO NGƯỢC.......................................................................................9 15. NGUY ÊN TẮC CHUY ỂN SANG CHIỀU KHÁ C ......................................................... 10 KẾT LUẬN.................................................................................................................................. 10 TÀI LIỆU THA M KHẢO .............................................................................................................. 11 CÁC PHƯƠNG PHÁP NGUYÊN CỨU KHOA HỌC ỨNG DỤNG TRONG XÂY DỰNG TRÌNH BIÊN DỊCH 1. NGUYÊN TẮC PHÂN NHỎ  Về l ý thu yết ta có thể xâ y dựng một ngôn ngữ lập trình cấp cao thao tác trực tiếp với lõi phần cứng của máy tính tạo thành một khối thống nhất,nhưng khi đó ngôn ngữ lập trình này chỉ chạy được trên một hệ thống máy tính và hệ thông máy tích chỉ thực thi được một ngôn ngữ lập trình =>không khả chuyển  Để cho các ngôn ngữ lập trình có thể chạy trên một hệ thống các phần cứng khác nhau và các hệ thống phần cứng có thể thực thi các chương 2 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 trình được xâ y dựng trên các ngôn ngữ lập trình khác nhau,Ta có thể chia nhỏ hệ thống trình biên dịch thành nhiều phần khác nhau như sau: Hình 1:Cấu trúc hệ thống Máy Tính  Bare Mechine :lõi phần cứng của CPU  Macroinstruction Interpreter :Bộ thông dịch chỉ thị Macro(Mã máy)  Operating System :hệ điều hành  C++ compiler,ada Compiler… trình biên dịch(máy ảo)  Về l ý thu yết có thể xâ y dựng một ngôn ngữ lập trình cấp cao thao tác trực tiếp với lõi phần cứng của máy tính nhưng khi đó ngôn ngữ lập trình này chỉ chạy được trên một hệ thống máy tính và hệ thông máy tích chỉ thực thi được một ngôn ngữ lập trình =>không khả chuyển  Một chương trình được viết bằng một ngôn ngữ bất kỳ sẽ thông qua trình biên dịch của ngôn ngữ đó để chuyển thành mã máy mà hệ điều hành có thể thực thi,thông qua hệ điều hành sẻ giao tiếp với phần cứng máy tinh(ảo hóa máy tính:cho phép chạy trực tiếp ngôn ngữ lập trình cấp cao) 3 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 2. NGUYÊN TẮC TÁCH KHỎI  Việc xây dựng trình biên giúp người lập trình không xây dựng phần mềm thao tác trực tiếp đến lõi phần cứng mà giao tiếp với trình biên dịch,điều này giúp xây dựng được nhiều ngôn ngữ lập trình và người lập trình dễ dàng xây dựng các ứng dụng trên các ngôn ngữ lập trình khác nhau  Bộ phân tích cú pháp trong trình biên dịch được chia làm 2 phần :  Phần mức thấp gọi là bộ phân tích từ vựng(Scaner) là một automatch hữu hạn dựa vào văn phạm chính qui  Phần mức cao cao gọi là bộ phân tích cú pháp là một automatch đẩy xuống dựa vào ngôn ngữ phi ngữ cảnh hoặc BNF  Lý do chia bộ phân tích cú pháp thành 2 phần :  Đơn giản – phân tích từ vựng đơn giản hơn =>việc xây dựng bộ phân tích từ vựng đon giản hơn  Hiệu quả :việc phân chia thành 2 khối giúp tối ưu hóa  Tính khả chuyển :bộ phân tích từ vựng không khả chuyễn nhưng bô phân tích cú pháp có thể khả chuyễn(đẩu ra của bộ phân tích từ vựng là các token có thể đưa vào các máy phân tích cú pháp khác nhau ) 3. NGUYÊN TẮC VẠN N ĂNG  Một ứng dụng sau khi được trình biên dịch dịch ra mã máy ứng với một hệ thống phần cứng nào đó, thì ứng dụng này chỉ chạy được trên đúng hệ thống phần cứng này, quá trình này được gọi là quá trình biên dịch  Vấn đề đặt ra là một chương trình sau khi đã biên dịch có thể chạy được trên mọi hệ thống, để thực hiện đều này trình thông dịch ra đời với ngôn ngữ tiêu biểu là Java,chương trình nguồn được biên dịch thành mã trung gian, trong trình biên dịch của java có một hệ thống gọi là máy ảo,máy ảo này có nhiệm vụ biên dịch mã trung gian thành mã máy phù hợp với hệ thống mà nó sẽ thực thi,đều này giúp chương trình viết bằng Java có thể thực thi trên mọi hệ thống khác nhau 4. NGUYÊN TẮC CHỨA TRONG  Một trình biên dịch được chia thành nhiều phần  Bộ phận phân tích cú pháp :kiểm tra cú pháp của các lệnh được viết trong chương trình, bộ phân tích cú pháp được chia làm 2 phần 4 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034  Bộ phận phân tích từ vựng(Scanner) sẽ cho ra luồn đơn vị từ vựng như ID,các toán tử..  Chia chương trình thành những “tokens” là những đơn thể nhỏ nhất nhưng có đầy đủ ý nghĩa  Cơ sở lý thuyết của Scanner là ngôn ngữ chính quy DFA  Bộ phận phân tích cú pháp(Parser),Parser sẽ kiểm tra cú pháp và xâ y dựng cây phân tích cú pháp  Cơ sở lý thuyết của Pars er là ngôn ngữ phi ngữ cảnh PDA  Tìm ra cấu trúc phi ngữ cảnh của chương trình  Bộ phận phát sinh mã trung gian  Bộ phân chuyển mã lệnh sanh mã trung gian  Bộ phận tối ưu mã liên qua đến việc sử dụng tài nguyên phần cứng  Bộ phận chuyển Mã trung gian thành mã máy  Mã tối ưu này sẽ chuyển vào Bộ phận chuyễn mã và kết quả là mã máy, hay mã hợp ngữ hoặc một ngôn ngữ khác, định vị lại địa chỉ của các dòng mã lệnh  Kết quả sẽ chuyển vào giai đoạn tối ưu liện qua đến việc sử dụng tài nguyên phần cứng 5 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 Hình 2 :Cấu trúc trình biên dịch 6 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 5. NGUYÊN TẮC KẾT HỢP  Kết hợp biên dịch và thông dịch  Kết hợp các ưu điểm giữa thông dịch và biên dịch  Ngôn ngữ lập trình cấp cao sẽ được biên dịch sang ngôn ngữ trung gian (dịch một lần)để dễ dàng thông dịch  Nhanh hơn thông dịch truyền thông  Ví dụ : 1. NNLT Perl :sẽ biên dịch để kiểm tra lỗi trươc khi thông dịch 2. Java :ý tưởng ban đầu của java là biên dịch mã nguồn sang mã trung gian là Byte code và có thể thực hiện trên tất cả các hệ thống thông qua máy ảo JVM Hình 3:Hệ thống kết JMV 6. NGUYÊN TẮC THỰC HIỆN SƠ BỘ  Trong trình biên dịch kết hợp giữa biên dịch và thông dịch, việc thực thi một chương trình được chia làm 2 giai đoạn  Giai đoạn 1:Kiểm tra lổi chương trình,biên dịch mã nguồn thành mã trung gian  Giai đoạn 2 :thông dịch mã trung gian sang mã máy 7 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034  Việc chia quá trình thực thi thành hai giai đoạn như vậy giúp việc thực thi chương trình nhanh chóng hơn 7. NGUYÊN TẮC PHẢN ĐỐI XỨNG  Chương trình nguồn sẽ qua bộ phận phân tích từ vựng(Scanner) sẽ cho ra luồn đơn vị từ vựng như ID,các toán tử.. gọi là “tokens” , đây là một dãy các token có thứ thự  Dãy các token có thứ tự tiến tính sẽ được đưa vào bộ phận phân tích cú pháp(Parser),Parser sẽ kiểm tra cú pháp và xâ y dựng cây phân tích cú pháp(không theo thứ tự tuyến tính 8. NGUYÊN TẮC SỬ DỤNG ĐỐI TƯỢNG TRUNG GIAN  Trong chương trình dữ liệu được lưu trữ trong bộ nhớ,để truy xuất đến dữ liệu,chương trình phải truy xuất đến đúng địa chỉ vật lý của dữ liệu  Khi viết chương trình, để truy xuất đến dữ liệu về nguyên tắc người lập trình phải truy cập đúng vào địa chỉ vật lý,đều này gâ y khó khăn cho người lập trình  Các ngôn ngữ lập trình cho phép truy xuất đến ô nhớ thông qua đối tượng trung gian đó là biến, thông qua biến chương trình có thể truy xuất đến địa chỉ ô nhớ 9. NGUYÊN TẮC SAO CHÉP  Khi truyền giá trị cho tham số hình thức cho chương trình con, người lập trình có thể dùng phương pháp truyền theo trị,trong phương pháp này trình biên dịch sẽ sao chép dữ liệu từ tham số thực vào tham số hình thức và tiến hành xữ l ý 10. NGUYÊN TẮC RẺ THAY ĐẮT  Trong phương pháp truyền tham số cho chương trình con,phương pháp truyền theo trị sẽ sao chép dữ liệu từ tham số thực sang tham số hình thức =>hệ thống phải cấp pháp vùng nhớ cho tham số hình thức đúng bằng vùng nhớ của tham số thực và phải tốn thời gian thực hiện thao tác sao chép dữ liệu  Để không tiêu tốn thời gian và bộ nhớ,trình biên dịch cung cấp phương pháp truyền tham biến.truyền tham biến là cách truyến địa chỉ của ô nhớ chứa dữ liệu cho chương trình con 8 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 11. NGUYÊN TẮC TÁC ĐỘNG THEO CHU KỲ  Trong các trình biên dịch luôn có một chương trình chuyên “dọn rác” của hệ thống, chương trình này sẽ thực hiện theo một chu kỳ,khi tới chu kỳ chương trình sẽ kiểm tra trong vùng nhớ Head xem những vùng nhớ nào không còn được dùng sẽ giải phóng và đưa về những vùng nhớ có thể dùng 12. NGUYÊN TẮC DỰ PHÒNG  Khi chương trình thực thi,chương trình sẽ yêu cầu hệ thống cung cấp vùng nhớ để chứa dữ liệu của chương trình  Tại một thời điểm có nhiều chương trình cùng thực thi, nên yêu cầu vùng nhớ lớn nhưng kích thước của bộ nhớ thì hữu hạn=>có thể xảy ra tình trạng hết bộ nhớ do những bộ nhớ đã được cấp phát nhưng chưa thu hồi  Để đề phòng trường hợp này, trình biên dịch luôn có chương trình “dọn rác” để thu hồi lại những ô nhớ đã được cấp phát cho biến trong chương trình con sau khi chương trình này thực thi xong 13. NGUYÊN TẮC LINH ĐỘNG  Từ chương trình để chuyển thành mã máy chạy được trên một hệ thống phần cứng, trước tiên chương trình phải được kiểm tra có đúng cú pháp không?việc kiểm tra trực tiếp từ mã nguồn sẽ gặp khó khăn.  Để đơn giản quá trình này , trước khi chuyển qua giai đoạn phân tích cú pháp, chương trình nguồn sẽ được đưa vào bộ phận phân tích từ vựng,chương trình nguồn sẽ được tách thành danh sách các từ vựng.sau đó danh sách từ vựng này sẽ chuyển cho bộ phận phân tích để tiến hành phân tích cú pháp của chương trình nguồn 14. NGUYÊN TẮC ĐẢO NGƯỢC  Sau khi phân tích cú pháp của chương trình nguồn, trình biên dịch sẽ tạo cây phân tích cú pháp  Thông thường Cây sẽ được tạo từ gốc đến lá  Nhưng trong phân tích cú pháp có phương pháp Buttom-Up :Xây dựng cây phân tích cú pháp đi từ nút lá 9 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 15. NGUYÊN TẮC CHUYỂN SANG CHIỀU KHÁC  Khi định nghĩa mảng 2 chiều trong ngôn ngữ lập trình,người lập trình tưởng tượng mảng 2 chiều là một bảng và bảng này được lưu vào trong bộ nhớ  Bộ nhớ máy tính là một dãy tu yến tính các ô nhớ nên để lưu trữ mảng nhiều chiều, trình biên dịch sẽ chuyển mảng nhiều chiều thành mảng một chiều, và vị trí lưu trữ của các phần tử trên mảng tùy thuộc vào ngôn ngữ hỗ trợ lưu trữ mảng theo thứ tự dòng hay thứ tự cột  Để truy xuất đến các phần tử trong mảng nhiều chiều, trình biên dịch xâ y dựng hàm truy xuất đến vị trí lưu trữ dựa vào chỉ số các chiều của phần tử KẾT LUẬN Qua đó ta thấy việc vận dụng các nguyên tắc sáng tạo trongquá trình nghiên cứu khoa học, giải quyết các vấn đề trong lĩnh vực công nghệ thông tin và mọi lĩnh vực khác trong cuộc sống là điều tối cần thiết, cực kì quan trọng. Nó giúp cho chúng ta có được những hướng đi mới, cách nghĩ mới để giải quyết vấn đề. Điều mấu chốt là cấp kỳ thay đổi cách tư duy để sáng tạo mới tiếp cận được đến thành công. Hiện nay ở Việt Nam số bằng sáng chế một năm là rất ít so với các nước trên thế giới. Nguyên nhân là do sự tư duy theo lối mòn, s ự dạy học thụ động, sự vận động, khuyến khích sáng tạo đổi mới của các giảng viên đến sinh viên là không nhiều. Do đó phần đông các sinh viên khi ra trường chỉ có thể làm theo những gì mà doanh nghiệp yêu cầu, ít có khả năng tựsáng tạo. Vì vậ y việc đưa môn họcPhương pháp nghi ên cứu khoa học vào chương trình đại học là cần thiết, để các sinh viên có dịp tiếp cận các phương pháp luận sáng tạo và đặc biệt là 40 nguyên lý sáng tạo của giáo sư Atlshuller. Có như vậy Việt Nam mới có thể cạnh tranh cùng bạn bè thế giới trong tương lai không xa. 10 Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034 TÀI LIỆU THAM KHẢO [1] Slides bài giảng môn PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC, GS.TSKH. Hoàng Kiếm. [2] GS.TS. Phan Dũng, 40 thủ thuật (nguyên tắc) sáng tạo cơ bản, Trung tâm sáng tạo khoa học kỹ thuật thuộc ĐH Khoa học tự nhiên TP Hồ Chí Minh, 1994. [3] Tham khảo các bài khoá trước [4] www.wikipedia.org [5] http://www.techz.vn/Lich-su-Laptop---Nhung-buoc-di-manh-meylt13477.html [6] http://www.lethanglaptop.com/Tin-tuc/2468224/44808/Lich-su-laptop-quacac-thoi-dai.html [7] http://sohoa.vnexpress.net/tin-tuc/doi-song-so/8-y-tuong-laptop-doc-daocho-tuong-lai-1515314.html 11