1. Trang Chủ
  2. Kỹ thuật lập trình
  3. Tập bài giảng Chương trình dịch

Tập bài giảng Chương trình dịch

Tập bài giảng “Chương trình dịch” được biên soạn theo chương trình chi tiết môn học “Chương trình dịch” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về chương trình dịch. Giúp sinh viên hiểu được các kiến thức cơ bản, tổng quan về chương trình dịch nói chung và các kỹ thuật cơ bản trong xây dựng các bộ phân tích từ vựng và phân tích cú pháp của các chương trình dịch của các ngôn ngữ lập trình bậc cao. Mời các bạn

Thể loại Tài liệu miễn phí Kỹ thuật lập trình

Số trang 218

Ngày tạo 4/3/2023 10:02:56 AM +00:00

Loại tệp PDF

Kích thước 1.53 M

Tên tệp

Tải Tập bài giảng Chương trình dịch (.pdf)

Xem mẫu

  1. Môc lôc LỜI NÓI ĐẦU ............................................................................................................ 7 Chƣơng 1. TỔNG QUAN VỀ CHƢƠNG TRÌNH DỊCH .......................................... 9 1.1. Mở đầu ............................................................................................................ 9 1.2. Chƣơng trình dịch ......................................................................................... 11 1.2.1. Các khái niệm ........................................................................................ 11 1.2.2. Mô hình phân tích - tổng hợp của một chƣơng trình dịch ..................... 12 1.2.3. Môi trƣờng của chƣơng trình dịch ......................................................... 13 1.3. Phân tích chƣơng trình nguồn ...................................................................... 14 1.3.1. Phân tích từ vựng (Lexical Analysis) .................................................... 14 1.3.2. Phân tích cú pháp (Syntax Analysis) ..................................................... 16 1.3.3. Phân tích ngữ nghĩa (Semantic Analysis) .............................................. 17 1.4. Các giai đoạn của chƣơng trình dịch ............................................................. 18 1.4.1. Quản lý bảng ký hiệu ............................................................................. 19 1.4.2. Xử lý lỗi ................................................................................................. 19 1.4.3. Các giai đoạn phân tích .......................................................................... 20 1.4.4. Sinh mã trung gian ................................................................................. 20 1.4.5. Tối ƣu mã ............................................................................................... 21 1.4.6. Sinh mã đích .......................................................................................... 21 1.5. Nhóm các giai đoạn ....................................................................................... 21 1.5.1. Kỳ đầu (Front End) ................................................................................ 22 1.5.2. Kỳ sau (Back End) ................................................................................. 22 1.6. Các đặc trƣng của ngôn ngữ lập trình bậc cao .............................................. 22 1.6.1. Từ vựng .................................................................................................. 22 1.6.2. Cú pháp .................................................................................................. 23 1.6.3. Ngữ nghĩa ............................................................................................... 23 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 ..................................................................... 24 Chƣơng 2. PHÂN TÍCH TỪ VỰNG ........................................................................ 25 2.1. Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat.................... 25 2.1.1. Một số khái niệm cơ sở .......................................................................... 25 2.1.2. Biểu diễn ngôn ngữ ................................................................................ 26 2.1.3. Văn phạm ............................................................................................... 27 2.1.4. Văn phạm phi ngữ cảnh ......................................................................... 28 1
  2. 2.1.5. Biểu thức chính quy (Regular Expression)............................................ 29 2.1.6. Automat hữu hạn đơn định .................................................................... 31 2.1.7. Automat hữu hạn không đơn định - NFA (Nondeterministic Finite Automata) ........................................................................................................ 31 2.1.8. Automat hữu hạn không đơn định với ε-dịch chuyển (NFAε) .............. 32 2.2. Giai đoạn phân tích từ vựng ......................................................................... 34 2.2.1. Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị)............................................. 35 2.2.2. Nhận biết thẻ từ (token) ......................................................................... 40 2.3. Kỹ thuật đọc chƣơng trình nguồn ................................................................. 43 2.3.1. Cặp bộ đệm (Buffer Pairs) ..................................................................... 43 2.3.2. Khóa cầm canh (Sentinel) ..................................................................... 44 2.4. Kỹ thuật sử dụng Automat để phân tích từ vựng .......................................... 45 2.4.1. Giải thuật sử dụng DFA ......................................................................... 45 2.4.2. Giải thuật sử dụng NFA ......................................................................... 48 2.4.3. Giải thuật sử dụng NFA ....................................................................... 49 2.5. Kỹ thuật biến đổi Automat ............................................................................ 50 2.6. Giải thuật Thomson ....................................................................................... 61 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 ..................................................................... 66 Chƣơng 3. PHÂN TÍCH CÚ PHÁP ......................................................................... 76 3.1. Giai đoạn phân tích cú pháp .......................................................................... 76 3.1.1. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích cú pháp ............... 76 3.1.2. Xử lý lỗi cú pháp ................................................................................... 77 3.1.3. Các chiến lƣợc phục hồi lỗi ................................................................... 77 3.1.4. Các phƣơng pháp phân tích cú pháp ...................................................... 78 3.2. Biến Ðổi văn phạm phi ngữ cảnh ................................................................ 79 3.2.1. Cây phân tích cú pháp (Parsing tree) và dẫn xuất ................................. 79 3.2.2. Ngôn ngữ nhập nhằng (Ambiguity) ....................................................... 82 3.2.3. Kỹ thuật khử nhập nhằng ....................................................................... 83 3.2.4. Kỹ thuật khử đệ quy trái ........................................................................ 84 3.2.5. Kỹ thuật thừa số hoá bên trái ................................................................. 88 3.3. Phân tích cú pháp từ trên xuống................................................................... 93 3.3.1. Phân tích cú pháp đệ quy xuống ............................................................ 93 3.3.2. Phân tích cú pháp dự đoán (phân tích LL(1)) ........................................ 96 2
  3. 3.4. Phân tích cú pháp từ dƣới lên (Bottom - up parsing) .................................. 117 3.4.1. Phân tích đẩy thu ( Shift – Reduce parsing) ........................................ 118 3.4.2. Phân tích cú pháp thứ bậc toán tử ........................................................ 124 3.4.3. Phân tích LR(K) ................................................................................... 127 3.4.4. Giải thuật phân tích LR ........................................................................ 128 3.4.5. Xây dựng bảng phân tích cú pháp ....................................................... 133 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 ................................................................... 146 LỜI GIẢI TÓM TẮT HOẶC HƢỚNG DẪN ........................................................ 155 TÀI LIỆU THAM KHẢO ...................................................................................... 218 3
  4. DANH MỤC HÌNH VẼ Hình 1.1. Mô tả việc dịch các chƣơng trình sang Assembly ................................... 10 Hình 1.2. Sơ đồ một chƣơng trình dịch .................................................................... 11 Hình 1.3. Mô hình phân tích - tổng hợp ................................................................... 12 Hình 1.4. Cây phân tích cú pháp .............................................................................. 12 Hình 1.5. Cấu trúc môi trƣờng của chƣơng trình dịch ............................................. 14 Hình 1.6. Một cây phân tích cú pháp ....................................................................... 16 Hình 1.7. Sơ đồ cấu trúc của một chƣơng trình dịch .............................................. 18 Hình 2.1. NFA với ε - dịch chuyển .......................................................................... 35 Hình 2.2. Vị trí của giai đoạn phân tích từ vựng ...................................................... 35 Hình 2.3. Sơ đồ chuyển nhận dạng token relop ....................................................... 42 Hình 2.4. Mô phỏng cặp bộ đệm .............................................................................. 44 Hình 2.5. Sơ đồ mô tả Automat đoán nhận biểu thức b*a+bb .................................. 46 Hình 2.6. Biểu diễn automat bằng đồ thị.................................................................. 47 Hình 2.7. Đồ thị biểu diễn Automat ......................................................................... 48 Hình 2.8. NFA với ε - dịch chuyển .......................................................................... 49 Hình 2.9. Sơ đồ giải thuật......................................................................................... 52 Hình 2.10. Biểu diễn automat bằng đồ thị................................................................ 52 Hình 2.11. Biểu diễn automat bằng đồ thị................................................................ 54 Hình 2.12. Biểu diễn automat bằng đồ thị................................................................ 55 Hình 2.13. Biểu diễn automat bằng đồ thị................................................................ 56 Hình 2.14. Sơ đồ giải thuật....................................................................................... 57 Hình 2.15. Biểu diễn automat bằng đồ thị................................................................ 57 Hình 2.16. Biểu diễn automat bằng đồ thị................................................................ 60 Hình 2.17. Automat đoán nhận biểu thức r=  ......................................................... 61 Hình 2.18. Automat đoán nhận biểu thức r = a ........................................................ 61 Hình 2.19. Automat đoán nhận biểu thức r = s+t ..................................................... 61 Hình 2.20. Automat đoán nhận biểu thức r=st ......................................................... 62 Hình 2.21a. Automat đoán nhận biểu thức r = s* ..................................................... 62 Hình 2.21b. Automat đoán nhận biểu thức r = s+ ..................................................... 62 Hình 2.22. Các automat đoán nhận a, b ................................................................... 64 Hình 2.23. Automat đoán nhận r7 = a+b ................................................................. 64 Hình 2.24. Automat đoán nhận r5 = (a+b)* .............................................................. 65 Hình 2.25. Automat đoán nhận r=(a b)*abb ............................................................ 65 Hình 3.1. Vị trí của bộ phân tích cú pháp ................................................................ 77 Hình 3.2. Minh họa một cây phân tích cú pháp ....................................................... 80 4
  5. Hình 3.3. Minh họa một cây phân tích cú pháp ....................................................... 81 Hình 3.4. Xây dựng cây phân tích cú pháp từ dẫn xuất ........................................... 82 Hình 3.5. Hai cây phân tích cú pháp của xâu id + id * id ........................................ 83 Hình 3.6. Hai cây phân tích cú pháp của cùng một xâu ........................................... 84 Hình 3.7 a, b, c. Mô tả quá trình phân tích xâu w = cad ......................................... 94 Hình 3.8. Sơ đồ chuyển của một biến....................................................................... 97 Hình 3.9. Sơ đồ chuyển cho các biến ....................................................................... 99 Hình 3.10. Sơ đồ chuyển rút gọn ............................................................................ 100 Hình 3.11. Mô tả hình tổ chức dữ liệu của kỹ thuật dự đoán ................................. 104 Hình 3.12. Cây phân tích cú pháp cho xâu vào id + id * id ................................... 107 Hình 3.13. Mô hình phân tích đẩy - thu ................................................................. 121 Hình 3.13a. Cây phân tích cú pháp cho xâu vào id * id +id theo đẩy – thu ......... 121 Hình 3.14. Mô hình bộ phân tích cú pháp LR ........................................................ 128 Hình 3.14a. Cây phân tích cú pháp cho xâu vào id * id + id theo LR .................. 128 Hình 3.15. Sơ đồ chuyển ........................................................................................ 142 5
  6. DANH MỤC BẢNG Bảng 2.1. Các ví dụ về token ................................................................................... 38 Bảng 2.2. Biểu thức chính quy cho một số token ................................................... 41 Bảng 2.3. Mô phỏng automat đoán nhận từ bbaaabb ............................................... 46 Bảng 2.4. Mô phỏng automat đoán nhận từ aaabba ................................................. 47 Bảng 2.5. Mô tả quá trình đoán nhận xâu ................................................................ 49 Bảng 2.6. Mô tả quá trình đoán nhận xâu ................................................................ 50 Bảng 2.7. Mô phỏng giải thuật ................................................................................. 54 Bảng 2.8. Mô phỏng giải thuật ................................................................................. 55 Bảng 2.9. Mô phỏng giải thuật ................................................................................. 60 Bảng 3.1. Bảng phân tích cú pháp ......................................................................... 107 Bảng 3.2. Phân tích cú pháp cho xâu vào id + id * id ............................................ 107 Bảng 3.3. Bảng phân tích cú pháp .......................................................................... 113 Bảng 3.4. Bảng phân tích cú pháp .......................................................................... 114 Bảng 3.5. Bảng phân tích cú pháp M phục hồi lỗi ................................................. 116 Bảng 3.6. Phân tích cú pháp cho xâu vào + id * + id phục hồi lỗi ........................ 117 Bảng 3.7. Quá trình phân tích đẩy thu xâu id1 + id2* id3 ....................................... 123 Bảng 3.8. Các quan hệ thứ bậc toán tử ................................................................... 125 Bảng 3.9. Bảng quan hệ thứ bậc các toán tử .......................................................... 125 Bảng 3.10. Bảng phân tích cú pháp ........................................................................ 131 Bảng 3.11. Quá trình phân tích xâu id*id+id ......................................................... 132 Bảng 3.12. Mô phỏng giải thuật đoán nhận xâu id1 + id2* id3 ............................... 135 Bảng 3.13. Bảng phân tích cú pháp LR(1) ............................................................. 144 6
  7. LỜI NÓI ĐẦU LỜI NÓI ĐẦU Chương trình dịch (compiler) là bộ môn khoa học quan trọng của khoa học máy tính. Ở nhiều nước trên thế giới, môn học “Chương trình dịch” đã trở thành môn học bắt buộc và là cơ sở của các ngành thuộc lĩnh vực công nghệ thông tin. Ở nước ta, hiện nay nhiều trường đại học cũng đang giảng dạy môn học này cho sinh viên các ngành khoa học máy tính và công nghệ thông tin. ... Tuy nhiên tài liệu phục vụ giảng dạy cho môn học ở nước ta còn ít, thời lượng dành cho môn học cũng còn rất khác nhau ở mỗi trường. §Ó cã mét néi dung thèng nhÊt cho c¸c ngµnh thuộc lÜnh vùc c«ng nghÖ th«ng tin cña Tr-êng, tr-êng §¹i häc S- ph¹m Kü thuËt Nam §Þnh, Trường ®· ban hµnh ch-¬ng tr×nh chi tiÕt cho m«n häc. Việc xuất bản tập đề cương bài giảng nhằm đáp ứng nhu cầu cung cấp tài liệu môn học cho việc giảng dạy của giảng viên và học tập của sinh viên các ngành thuộc khoa Công nghệ Thông tin trường Đại học Sư phạm Kỹ thuật Nam Định nói riêng và làm tại liệu tham khảo cho sinh viên và cán bộ giảng dạy các trường nói chung. Tập đề cương bài giảng “Chương trình dịch” được biên soạn theo chương trình chi tiết môn học “Chương trình dịch” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về chương trình dịch. Giúp sinh viên hiểu được các kiến thức cơ bản, tổng quan về chương trình dịch nói chung và các kỹ thuật cơ bản trong xây dựng các bộ phân tích từ vựng và phân tích cú pháp của các chương trình dịch của các ngôn ngữ lập trình bậc cao. Đây là các kiến thức nền tảng, làm cơ sở cho việc xây dựng ra các ngôn ngữ lập trình bậc cao và các chương trình dịch. Về nội dung, tập đề cương bài giảng được chia thành 3 chương: Chương 1. Tổng quan về chương trình dịch Chương này trình bày: Các khái niệm, kiển thức cơ bản về chương trình dịch. Môi trường của chương trình dịch. Các giai đoạn của chương trình dịch. Nhóm các giai đoạn của chương trình dịch. Các đặc trưng cơ bản của ngôn ngữ lập trình bậc cao. Chương 2. Phân tích từ vựng Chương này nhắc lại một số kiến thức về văn phạm, ngôn ngữ, Automat. Trình bày các kiến thức về thẻ từ, mẫu từ vựng và trị từ vựng; vị trí, nhiệm vụ của giai đoạn phân tích từ vựng; một số kỹ thuật đọc chương trình nguồn; kỹ thuật sử dụng Automat để phân tích từ vựng và kỹ thuật biến đổi automat. Chương 3. Phân tích cú pháp 7
  8. LỜI NÓI ĐẦU Chươngnày trình bày các kiến thức cơ bản về: Vị trí, nhiệm vụ của giai đoạn phân tích cú pháp và các phương pháp phân tích cú pháp. Các kỹ thuật biến đổi văn phạm: khử đệ quy trái, thừa số hoá bên trái, khử nhập nhằng. Phương pháp phân tích top – down: phân tích cú pháp đệ quy xuống, phân tích cú pháp dự đoán. Phương pháp phân tích bottom – up: phân tích cú pháp đẩy thu, phân tích cú pháp LR(k). Đặc biệt cuối mỗi chương còn đưa ra hệ thống câu hỏi, bài tập nhằm củng cố, khắc sâu, nâng cao và vận dụng các kiến thức vào giải các bài tập và cuối cùng là phần lời giải tóm tắt hoặc hướng dẫn cho các bài tập nhằm giúp sinh viên tự rèn luyện kỹ năng và kiểm tra kiến thức. Trong quá trình biên soạn, tập đề cương bài giảng không tránh khỏi những sai sót, rất mong đồng nghiệp và các sinh viên đóng góp ý kiến để tập đề cương bài giảng ngày càng được hoàn thiện hơn. Người biên soạn Phạm Hùng Phú 8
  9. Chƣơng 1. Tổng quan về chƣơng trình dịch Chƣơng 1 TỔNG QUAN VỀ CHƢƠNG TRÌNH DỊCH Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc các khái niệm cơ bản: Chƣơng trình dịch, hệ thống thông dịch, biên dịch. - Hiểu đƣợc môi trƣờng của một chƣơng trình dịch. - Hiểu đƣợc cấu trúc của một chƣơng trình dịch - Hiểu đƣợc các giai đoạn của chƣơng trình dịch: vị trí, nhiệm vụ. - Biết đƣợc các đặc trƣng cơ bản của ngôn ngữ lập trình bậc cao. Nội dung chính: - Khái niệm chƣơng trình dịch. - Môi trƣờng của chƣơng trình dịch. - Các giai đoạn của chƣơng trình dịch. - Nhóm các giai đoạn của chƣơng trình dịch. - Các đặc trƣng cơ bản của ngôn ngữ lập trình bậc cao. 1.1. Mở đầu Các ngôn ngữ lập chƣơng trình thực chất là các ngôn ngữ dùng để biểu diễn giải thuật thực hiện một bài toán nào đó. Để thuận tiện và đơn giản cho quá trình viết chƣơng trình ngƣời ta xây dựng các ngôn ngữ lập trình bậc cao nhƣ Algol, Pascal, C, C++, Visual Fox, Visual Basic, … Hiện nay có rất nhiều ngôn ngữ lập trình bậc cao. Những ngôn ngữ lập trình bậc cao có chung đặc tính là không phụ thuộc vào máy tính, gần gũi với toán học và các lĩnh vực hoạt động của con ngƣời. Chẳng hạn Visual Fox là ngôn ngữ vừa gần gũi, thích hợp với công việc quản lý sản xuất, kinh doanh vừa đủ chặt chẽ để diễn đạt các công thức toán học và mang tính logic cao. Viết chƣơng trình bằng ngôn ngữ máy có ƣu điểm cơ bản là chƣơng trình thực hiện nhanh, vì khi nạp chƣơng trình vào máy tính nó chạy đƣợc ngay không cần giai đoạn dịch, song nó có những nhƣợc điểm cơ bản sau: - Ngôn ngữ máy rất xa lạ với ngôn ngữ toán học và ngôn ngữ tự nhiên của con ngƣời. - Dễ sinh ra lỗi, song lại khó phát hiện lỗi, mất nhiều thời gian hiệu chỉnh chƣơng trình. - Khó diễn đạt rõ ràng giải thuật. - Phụ thuộc vào máy tính, không thuận tiện cho việc giao lƣu phổ biến các chƣơng trình, các giải thuật toán tốt, dẫn đến sự lãng phí về lao động xã hội. 9
  10. Chƣơng 1. Tổng quan về chƣơng trình dịch Những lý do nêu trên là nguyên nhân thúc đẩy việc sản sinh ra nhiều ngôn ngữ lập trình bậc cao khác nhau. Trái ngƣợc với ngôn ngữ máy, ngôn ngữ lập trình bậc cao có các đặc điểm sau: - Gần gũi với ngôn ngữ toán học và ngôn ngữ tự nhiên của con ngƣời. - Không phụ thuộc vào máy cụ thể, do vậy dễ phổ biến, dễ giao lƣu trao đổi hợp tác giữa những ngƣời làm chƣơng trình, tăng hiệu quả lao động của xã hội. - Ít sinh ra lỗi, cho phép phát hiện lỗi nhanh và do vậy tiết kiệm thời gian hiệu chỉnh chƣơng trình. Về nguyên tắc, các máy tính chỉ có thể thực hiện đƣợc các chƣơng trình viết bằng ngôn ngữ máy. Vì vậy, các chƣơng trình viết bằng các ngôn ngữ lập trình bậc cao muốn máy tính thực hiện đƣợc phải trải qua giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy. Giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy đƣợc gọi là giai đoạn dịch chƣơng trình hay ngắn gọn là dịch. Chƣơng trình thực hiện giai đoạn dịch gọi là chƣơng trình dịch (Compiler). Đối với chƣơng trình dịch thì các chƣơng trình viết bằng ngôn ngữ lập trình bậc cao là dữ liệu đầu vào và đƣợc gọi là chƣơng trình nguồn; chƣơng trình là kết quả dịch (đầu ra) của chƣơng trình dịch đƣợc gọi là chƣơng trình đích. Ngôn ngữ dùng để viết chƣơng trình nguồn ta gọi là ngôn ngữ nguồn. Ngôn ngữ dùng để viết chƣơng trình đích ta gọi là ngôn ngữ đích. Trong thực tế với mục đích tận dụng các chƣơng trình tốt đã có, viết bằng các ngôn ngữ lập trình bậc cao khác nhau; ngƣời ta thƣờng dịch các chƣơng trình nguồn ra ngôn ngữ trung gian sau đó ghép chúng lại thành một chƣơng trình viết bằng cùng một ngôn ngữ sau đó mới chuyển sang ngôn ngữ máy. Thậm chí có những chƣơng trình đƣợc viết bằng nhiều ngôn ngữ lập trình khác nhau, ngƣời ta gọi là chƣơng trình viết ở dạng hợp ngữ. Hình 1.1 mô tả việc dịch các chƣơng trình viết bằng các ngôn ngữ khác nhau sang chƣơng trình viết bằng ngôn ngữ trung gian Assembly. Chƣơng trình Chƣơng trình Trong C Trong C++ Assembly Chƣơng trình Chƣơng trình trong Pascal Trong Assembly Hình 1.1. Mô tả việc dịch các chương trình sang Assembly 10
  11. Chƣơng 1. Tổng quan về chƣơng trình dịch - Về bản chất, mọi chƣơng trình viết bằng một ngôn ngữ lập trình bậc cao đều đƣợc coi là một dãy ký hiệu và đƣợc gọi là xâu vào hay văn bản vào. Do vậy, quá trình dịch có thể coi là quá trình biến đổi một xâu vào hay văn bản vào viết ở ngôn ngữ này thành một xâu ra hay văn bản ra viết bằng ngôn ngữ khác sao cho nó bảo toàn “ngữ nghĩa” (Semantic) của xâu vào (chƣơng trình tƣơng đƣơng). Vấn đề bảo toàn “ngữ nghĩa” của văn bản vào là vấn đề chƣa đƣợc xác định rõ ràng trong lý thuyết chƣơng trình dịch. Một số tác giả đã đƣa ra khái niệm bảo toàn “ngữ nghĩa” nhƣ sau: Hai xâu đƣợc gọi là bản dịch của nhau nếu khi dịch sang ngôn ngữ thứ ba thì chúng có kết quả nhƣ nhau. 1.2. Chƣơng trình dịch 1.2.1. Các khái niệm 1) Khái niệm chương trình dịch Chƣơng trình dịch là một chƣơng trình làm nhiệm vụ đọc một chƣơng trình đƣợc viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language), rồi dịch nó thành một chƣơng trình tƣơng đƣơng ở một ngôn ngữ khác - Ngôn ngữ đích (target languague). Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chƣơng trình nguồn để thông báo lại cho ngƣời viết chƣơng trình. Chƣơng trình Chƣơng Chƣơng trình nguồn trình dịch đích Báo lỗi Hình 1.2. Sơ đồ một chương trình dịch 2) Biên dịch và thông dịch Ngƣời ta chia chƣơng trình dịch thành hai dạng là trình biên dịch và trình thông dịch. a) Trình biên dịch (Compiler) Trong hệ thống biên dịch, chƣơng trình dịch đọc toàn bộ chƣơng trình nguồn và dịch toàn bộ chƣơng trình nguồn sang chƣơng trình đích. - Chƣơng trình nguồn viết bằng ngôn ngữ lập trình bậc cao. - Chƣơng trình đích viết bằng ngôn ngữ máy hoặc assembly hoặc ngôn ngữ trung gian. Chƣơng trình đích cần có khả năng chạy độc lập trên tất cả các máy mà không cần chƣơng trình dịch nữa. 11
  12. Chƣơng 1. Tổng quan về chƣơng trình dịch Ƣu điểm của chƣơng trình dịch là chƣơng trình chạy nhanh. Nhƣợc điểm của nó là việc thiết kế và cài đặt phức tạp. Ví dụ nhƣ chƣơng trình dịch của Turbo C hay Turbo Pascal. b) Trình thông dịch (Interpreter) Trong hệ thống thông dịch, chƣơng trình dịch đọc vào từng câu lệnh, dịch sang chƣơng trình đích rồi thực hiện ngay câu lệnh đó. Ví dụ nhƣ chƣơng trình dịch của hệ điều hành DOS khi thực hiện lệnh tại dấu nhắc lệnh hay chƣơng trình dịch của hệ quản trị cơ sở dữ liệu Visual Foxpro khi thực hiện lệnh tại cửa sổ lệnh. 1.2.2. Mô hình phân tích - tổng hợp của một chƣơng trình dịch Chƣơng trình dịch thƣờng bao gồm hai quá trình: phân tích và tổng hợp - Phân tích  đặc tả trung gian - Tổng hợp  chƣơng trình đích Chƣơng trình Phân tích Đặc Tổng hợp Chƣơng trình nguồn tả trung gian đích Hình 1.3. Mô hình phân tích - tổng hợp Trong quá trình phân tích chƣơng trình nguồn sẽ đƣợc phân rã thành một cấu trúc phân cấp, thƣờng là dạng cây - cây cú pháp (parsing tree). Ví dụ 1.1: Câu lệnh gán position := initial + rate * 60 có cây phân tích cú pháp hình 1.4. stmt expr id assign expr expr position operator := id expr expr + operator id number initial * rate 60 Hình 1.4. Cây phân tích cú pháp 12
  13. Chƣơng 1. Tổng quan về chƣơng trình dịch 1.2.3. Môi trƣờng của chƣơng trình dịch Ngoài chƣơng trình dịch, còn phải cần dùng nhiều chƣơng trình khác nữa để tạo ra một chƣơng trình đích có thể thực thi đƣợc (executable). Các chƣơng trình đó gồm: bộ soạn thảo, bộ tiền xử lý, trình dịch hợp ngữ, bộ tải và liên kết. Hệ thống các chƣơng trình này giúp cho ngƣời lập trình có đƣợc một môi trƣờng hoàn chỉnh để phát triển các ứng dụng. - Bộ soạn thảo: cho phép soạn thảo chƣơng trình nguồn. - Bộ tiền xử lý: Xử lý một số chức năng ban đầu để tạo ra một chƣơng trình nguồn hoàn chỉnh từ một chƣơng trình nguồn khung (nguyên thuỷ) ban đầu. Ví dụ, một chƣơng trình nguồn có thể đƣợc phân thành các module và đƣợc lƣu trong các tập tin riêng rẽ. Công việc tập hợp lại các tập tin này thƣờng đƣợc giao cho một chƣơng trình riêng biệt gọi là bộ tiền xử lý (preprocessor). Bộ tiền xử lý có thể "bung" các ký hiệu tắt đƣợc gọi là các macro thành các câu lệnh của ngôn ngữ nguồn. Ngoài ra, bộ tiền xử lý còn cho phép bỏ qua các chú thích. - Chƣơng trình dịch: cho phép kiểm lỗi chƣơng chƣơng trình, dịch ra ngôn ngữ đích. Dịch ra ngôn ngữ đích nhƣng đang ở dạng định vị lại đƣợc hay có thể ở dạng ngôn ngữ assembly. Ngoài ra, chƣơng trình đích đƣợc tạo ra bởi chƣơng trình dịch có thể cần phải đƣợc xử lý thêm trƣớc khi chúng có thể chạy đƣợc. Thông thƣờng, chƣơng trình dịch chỉ tạo ra mã lệnh hợp ngữ (assembly code) để trình dịch hợp ngữ (assembler) dịch thành dạng mã máy định vị lại đƣợc. - Tải/liên kết: Tải chƣơng trình vào bộ nhớ máy tính và liên kết với một số thủ tục trong thƣ viện hệ thống để tạo thành một chƣơng trình mã máy tuyệt đối và thực thi đƣợc trên máy tính. Hình sau trình bày sơ đồ cấu trúc môi trƣờng của một chƣơng trình dịch trong một hệ thống biên dịch điển hình. 13
  14. Chƣơng 1. Tổng quan về chƣơng trình dịch Chƣơng trình nguồn khung (nguyên thuỷ) Bộ tiền xử lý Chƣơng trình nguồn Trình biên dịch Chƣơng trình đích hợp ngữ Trình dịch hợp ngữ Mã máy khả tái định vị Thƣ viện, Tập Trình tải / Liên kết tin đối tƣợng định vị lại đƣợc Mã máy tuyệt đối Hình 1.5. Cấu trúc môi trường của chương trình dịch 1.3. Phân tích chƣơng trình nguồn Quá trình phân tích chƣơng trình nguồn, về mặt logic có thể chia thành ba giai đoạn phân tích: Phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa. 1.3.1. Phân tích từ vựng (Lexical Analysis) Trong một chƣơng trình dịch, giai đoạn phân tích từ vựng sẽ đọc chƣơng trình nguồn từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các từ vị (lexeme) và tìm ra các thẻ từ (token) tƣơng ứng cho các từ vị đó. Thẻ từ là dạng ngữ pháp của từ vị; hay nói một cách khác, thẻ từ là tập hợp xâu các ký tự kết thúc (từ vị) có chung nhau luật ngữ pháp sinh ra các từ vị đó và mỗi thẻ từ thƣờng đƣợc đặt bởi một tên để định danh (phân biệt các thẻ từ với nhau) . Mỗi thẻ từ sẽ có một mẫu từ vựng (pattern) để xác định một từ vị là thuộc thẻ từ nào; hay nói cách khác, mẫu từ vựng của thẻ từ là luật ngữ pháp sinh ra các từ vị của thẻ từ đó. 14
  15. Chƣơng 1. Tổng quan về chƣơng trình dịch Từ vị của một thẻ từ là một từ của thẻ từ và nó phải thỏa mãn mẫu từ vựng của thẻ từ đó. Nhờ vào mẫu của thẻ từ, chƣơng trình dịch trong giai đoạn phân tích từ vựng sẽ phân tích để xác định ra các thẻ từ trả về cho giai đoạn phân tích cú pháp hoặc báo lỗi. Ví dụ 1.2: a) Trong một văn phạm có các luật sinh: 1. digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì: + digit là thẻ từ (token); + 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern) của thẻ từ digit; + Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một từ vị (lexeme) của thẻ từ digit. 2. letter A | B | ...| Z | a | b |...| z Thì: + letter là thẻ từ (token); + A | B | ...| Z | a | b |...| z là mẫu từ vựng (pattern) của thẻ từ letter; + Mỗi chữ cái La tinh: A, B, C, …, Z, a, b, c, …, z là một từ vị (lexeme) của thẻ từ letter. * 3. id (letter | _ )(letter | digit | _ ) Thì: + id là thẻ từ (token); * + (letter | _ )(letter | digit | _ ) là mẫu từ vựng (pattern) của thẻ từ id; + A, X1B, max_1a23 là 3 từ vị (lexeme) của thẻ từ id. b) Trong một văn phạm có các luật sinh: 1. Stmt  id := expr 2. Expr  expr + exprexpr - exprexpr /exprexpr * expridnumber 3. Relop  +-*/ 4. Assign  := Quá trình phân tích từ vựng cho câu lệnh gán position:= initial + rate * 60 sẽ tách thành các từ vị (lexeme) và trả về các thẻ từ (token) nhƣ sau: 1. position là từ vị của thẻ từ tên id 2. := là từ vị của thẻ từ phép gán assign 3. initial là từ vị của thẻ từ tên id 4. + là từ vị của thẻ từ phép toán operator 15
  16. Chƣơng 1. Tổng quan về chƣơng trình dịch 5. rate là từ vị của thẻ từ tên id 6. * là là từ vị của thẻ từ phép toán operator 7. 60 từ vị của thẻ từ số nguyên number Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. 1.3.2. Phân tích cú pháp (Syntax Analysis) Giai đoạn phân tích cú pháp sẽ dựa vào bộ luật cú pháp để tìm cấu trúc cú pháp của chƣơng trình nguồn. Các cấu trúc cú pháp này sẽ tƣơng ứng với một biểu thức, một phép gán, một khai báo, câu lệnh điều kiện, câu lệnh lặp, … Trong nhiều phƣơng pháp phân tích thì kết quả trả về không nhất thiết phải là cây cú pháp. Giai đoạn phân tích cú pháp thực hiện công việc nhóm các thẻ từ của chƣơng trình nguồn thành các ngữ đoạn văn phạm (grammatical phrase), mà sau đó sẽ đƣợc chƣơng trình dịch tổng hợp ra thành phẩm. Thông thƣờng, các ngữ đoạn văn phạm này đƣợc biểu diễn bằng dạng cây phân tích cú pháp (parsing tree). Về bản chất thì phân tích cú pháp sẽ cho ta thông tin về cú pháp của chƣơng trình nguồn và đƣợc thể hiện dƣới dạng cây phân tích cú pháp. Với ngôn ngữ đƣợc đặc tả bởi các luật sinh thì giai đoạn phân tích cú pháp dựa vào các luật sinh để xây dựng cây phân tích cú pháp. Ví dụ 1.3: Với câu lệnh gán position:= initial + rate * 60, giả sử bộ luật cú pháp của ngôn ngữ để nhận biết câu lệnh gán đƣợc đặc tả bởi các luật sinh sau: Stmt  id := expr Expr  expr + exprexpr - exprexpr /exprexpr * expridnumber Operator  +-*/ Assign  := Thế thì cây phân tích cú pháp của ví dụ trên sẽ đƣợc xây dựng nhƣ sau: stmt id expr assign expr position expr operator := id expr expr + operator initial id number * rate 60 Hình 1.6. Một cây phân tích cú pháp 16
  17. Chƣơng 1. Tổng quan về chƣơng trình dịch Cấu trúc phân cấp của một chƣơng trình thƣờng đƣợc diễn tả bởi quy luật đệ quy. Ví dụ 1.4: 1. Định danh (tên hay danh biểu - identifier) là một biểu thức (expr). 2. Số (number) là một biểu thức. 3. Nếu expr1 và expr2 là các biểu thức thì: - expr1 + expr2; - expr1 * expr2; - (expr) cũng là những biểu thức. Câu lệnh (statement) cũng có thể định nghĩa đệ quy: 1. Nếu id1 là một Danh biểu (tên hay định danh) và expr2 là một biểu thức thì id1:= expr2 là một lệnh (stmt). 2. Nếu expr1 là một biểu thức và stmt2 là một lệnh thì: - while (expr1) do stmt2; - if (expr1) then stmt2 đều là các lệnh. Ngƣời ta dùng các quy tắc đệ quy nhƣ trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình phân tích từ vựng và phân tích cú pháp cũng tuỳ theo công việc thực hiện. 1.3.3. Phân tích ngữ nghĩa (Semantic Analysis) Giai đoạn phân tích ngữ nghĩa sẽ thực hiện công việc: - Kiểm tra các lỗi ngữ nghĩa của chƣơng trình nguồn: Kiểm tra kiểu, phạm vi của hằng, biến; kiểm tra việc sử dụng trùng tên trùng nhau, ... - Thu nhận thông tin thuộc tính cho các thẻ từ; chẳng hạn, thông tin về giá trị, thông tin về loại của hằng, biến hay hàm cho tên. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu (type checking) và ép chuyển đổi kiểu. Chƣơng trình dịch, trong giai đoạn phân tích ngữ nghĩa sẽ kiểm tra kiểu dựa vào các đặc tả của ngôn ngữ nguồn để xem các toán hạng của một toán tử có hợp lệ hay không và thông báo lỗi nếu thấy lỗi. Ví dụ 1.5: Xét câu lệnh gán position:= initial + rate * 60; Trong khai báo ta có: Var position, initial: integer; Rate: real; Khi phân tích ngữ nghĩa: - Khai báo thứ nhất cho biết position, initial có kiểu số nguyên. - Khai báo thứ hai cho biết rate có kiểu số thực. 17
  18. Chƣơng 1. Tổng quan về chƣơng trình dịch - Câu lệnh gán cho biết vế phải của nó là kết quả của phép nhân một số thực rate với một số nguyên rồi cộng với một số nguyên; vậy nó phải có kiểu thực. Cho nên position phải có kiểu thực. Tuy nhiên khi so sánh lại thì mâu thuẫn. Vì vậy, chƣơng trình dịch sẽ báo lỗi sai kiểu dữ liệu. Nhƣng nếu trong khai báo: Var position, initial, Rate: real; Các tên biến đƣợc khai báo là real, 60 là số integer vì vậy chƣơng trình dịch sẽ ép chuyển đổi số nguyên 60 thành số thực 60.0. Phân tích ngữ nghĩa phải dựa vào các luật ngữ nghĩa đi kèm với từng luật cú pháp để thực hiện chức năng sinh thuộc tính cho các thẻ từ (token) và kiểm tra lỗi ngữ nghĩa. 1.4. Các giai đoạn của chƣơng trình dịch Để dễ hình dung, một chƣơng trình dịch đƣợc chia thành các giai đoạn, mỗi giai đoạn chuyển chƣơng trình nguồn từ một dạng biểu diễn này sang một dạng biểu diễn khác. Một cách phân rã điển hình chƣơng trình dịch đƣợc trình bày trong hình sau: Chƣơng trình nguồn Phân tích từ vựng Phân tích cú pháp Phân tích ngữ nghĩa Quản lý bảng ký Xử lý lỗi hiệu Sinh mã trung gian Tối ƣu mã Sinh mã đích Chƣơng trình đích Hình 1.7. Sơ đồ cấu trúc của một chương trình dịch 18
  19. Chƣơng 1. Tổng quan về chƣơng trình dịch Việc quản lý bảng ký hiệu và xử lý lỗi đƣợc thực hiện xuyên suốt qua tất cả các giai đoạn. 1.4.1. Quản lý bảng ký hiệu Một nhiệm vụ quan trọng của chƣơng trình dịch là ghi lại các định danh (tên hay danh biểu) đƣợc sử dụng trong chƣơng trình nguồn và thu thập các thông tin về các thuộc tính khác nhau của mỗi định danh. Những thuộc tính này có thể cung cấp thông tin về vị trí lƣu trữ đƣợc cấp phát cho một định danh, kiểu và tầm hoạt động của định danh, và nếu định danh là tên của một thủ tục hoặc hàm thì thuộc tính là các thông tin về số lƣợng và kiểu của các đối số, phƣơng pháp truyền đối số và kiểu trả về của thủ tục hoặc hàm nếu có. Bảng ký hiệu (symbol table) là một cấu trúc dữ liệu mà mỗi phần tử là một bản ghi dùng để lƣu trữ một định danh, bao gồm các trƣờng lƣu giữ ký hiệu và các thuộc tính của nó. Cấu trúc này cho phép tìm kiếm, truy xuất các định danh (tên hay danh biểu) một cách nhanh chóng. Trong quá trình phân tích từ vựng, định danh (tên hay danh biểu ) đƣợc tìm thấy và nó đƣợc đƣa vào bảng ký hiệu nhƣng nói chung các thuộc tính của nó có thể chƣa xác định đƣợc trong giai đoạn này mà nó đƣợc bổ sung dần trong các giai đoạn phân tích cú pháp và phân tích ngữ nghĩa. 1 position ... 2 initial ... 3 rate ... 4 1.4.2. Xử lý lỗi Mỗi giai đoạn có thể gặp nhiều lỗi, tuy nhiên sau khi phát hiện ra lỗi, tùy thuộc vào chƣơng trình dịch mà có các cách xử lý lỗi khác nhau, chẳng hạn: - Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Turbo Pascal). - Ghi nhận lỗi và tiếp tục quá trình dịch (Turbo C). Giai đoạn phân tích từ vựng thƣờng gặp lỗi khi các ký tự không thể ghép thành một token. Giai đoạn phân tích cú pháp gặp lỗi khi các token không thể kết hợp với nhau theo đúng cấu trúc cú pháp của ngôn ngữ. Giai đoạn phân tích ngữ nghĩa báo lỗi khi các toán hạng có kiểu không đúng, sử dụng tên trùng nhau, yêu cầu của phép toán hay các cấu trúc không có nghĩa đối với thao tác thực hiện mặc dù chúng hoàn toàn đúng về mặt cú pháp. 19
  20. Chƣơng 1. Tổng quan về chƣơng trình dịch 1.4.3. Các giai đoạn phân tích Giai đoạn phân tích từ vựng: đọc từng ký tự rồi gộp lại thành các từ vị (lexeme), sau đó kiểm tra các mẫu để tìm ra các thẻ từ (token) tƣơng ứng, token có thể là tên( định danh hay danh biểu), từ khóa, phép toán, ...Chuỗi ký tự tạo thành một thỏa mãn mẫu của một token gọi là lexeme - trị từ vựng (từ vị) của token đó. Ví dụ 1.6: Từ vị rate là một tên có token là tên (id), trị từ vựng (từ vị) là rate và tên này sẽ đƣợc đƣa vào bảng ký hiệu nếu nó chƣa có trong đó. Giai đoạn phân tích cú pháp và phân tích ngữ nghĩa: Xây dựng cấu trúc phân cấp cho chuỗi các token, biểu diễn bởi cây cú pháp và kiểm tra ngôn ngữ theo cú pháp. 1.4.4. Sinh mã trung gian Sau khi phân tích ngữ nghĩa, một số chƣơng trình dịch sẽ tạo ra một dạng biểu diễn trung gian của chƣơng trình nguồn. Có thể xem dạng biểu diễn này nhƣ một chƣơng trình dành cho một máy trừu tƣợng. Chúng có 2 đặc tính quan trọng: dễ sinh và dễ dịch thành chƣơng trình đích. Dạng biểu diễn trung gian có rất nhiều loại. Thông thƣờng, ngƣời ta sử dụng dạng "mã máy 3 địa chỉ" (three-address code), tƣơng tự nhƣ dạng hợp ngữ cho một máy mà trong đó mỗi vị trí bộ nhớ có thể đóng vai trò nhƣ một thanh ghi. Mã máy 3 địa chỉ là một dãy các lệnh liên tiếp, mỗi lệnh có thể có tối đa 3 đối số. Ví dụ 1.7: Trong ví dụ trên, sau các giai đoạn phân tích thì mã trung gian sẽ đƣợc tạo ra nhƣ sau: t1:= inttoreal (60) t2:= id3 * t1 t3:= id2 + t2 id1:= t3 (Trong đó id1 là position; id2 là initial; id3 là rate ) Dạng trung gian này có một số tính chất: - Mỗi lệnh chỉ chứa nhiều nhất một toán tử. Do đó khi tạo ra lệnh này, chƣơng trình dịch phải xác định thứ tự các phép toán, ví dụ * thực hiện trƣớc +. - Chƣơng trình dịch phải tạo ra một biến tạm để lƣu trữ giá trị tính toán cho mỗi lệnh. - Một số lệnh có ít hơn 3 toán hạng. 20
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường