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
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
12 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2296 | Lượt tải: 1
Bạn đang xem nội dung 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, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
ĐẠ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 thự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
1
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 khoa 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.
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
2
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 THAM 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ý thuyế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
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
3
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ý thuyế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)
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
4
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
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
5
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 Parser 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
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
6
Hình 2 :Cấu trúc trình biên dịch
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
7
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
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
8
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
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
9
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á
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
10
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 tuyế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.
Phương pháp nghiên cứu khoa học Võ Ngọc Tân - 1212034
11
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]
ylt13477.html
[6]
cac-thoi-dai.html
[7]
cho-tuong-lai-1515314.html
Các file đính kèm theo tài liệu này:
- 1212034ppnckh_k22_vongoctan_8536.pdf