Bài giảng Chương trình dịch (Phần 1)
Môc lôc
LỜI NÓI ĐẦU............................................................................................................ 7
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.3. Phân tích chƣơng trình nguồn ...................................................................... 14
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.1. Từ vựng.................................................................................................. 22
1.6.3. Ngữ nghĩa............................................................................................... 23
Chƣơng 2. PHÂN TÍCH TỪ VỰNG........................................................................ 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.1.6. Automat hữu hạn đơn định .................................................................... 31
Automata) ........................................................................................................ 31
2.2. Giai đoạn phân tích từ vựng......................................................................... 34
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.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
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.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.2. Biến Ðổi văn phạm phi ngữ cảnh ................................................................ 79
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
2
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
TÀI LIỆU THAM KHẢO...................................................................................... 218
3
DANH MỤC HÌNH VẼ
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.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
Hình 3.3. Minh họa một cây phân tích cú pháp ....................................................... 81
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.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.13. Mô hình phân tích đẩy - thu ................................................................. 121
Hình 3.14. Mô hình bộ phân tích cú pháp LR........................................................ 128
Hình 3.15. Sơ đồ chuyển ........................................................................................ 142
5
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.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.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.13. Bảng phân tích cú pháp LR(1)............................................................. 144
6
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
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
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
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 Assembly
trong Pascal
Hình 1.1. Mô tả việc dịch các chương trình sang Assembly
10
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
nguồn
Chƣơng
trình dịch
Chƣơng trình
đí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
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
Tổng hợp
Chƣơng trình
nguồn
Đặc
tả trung gian
Chƣơng trình
đích
Phân tí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
operator
expr
+
id
number
initial
*
rate
60
Hình 1.4. Cây phân tích cú pháp
12
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
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
tin đối tƣợng
định vị lại đƣợc
Trình tải / Liên kết
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
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 + exprexpr - exprexpr /exprexpr expridnumber
*
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
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 + exprexpr - exprexpr /exprexpr expridnumber
*
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
expr
id
assign
expr
operator
expr
position
:=
id
expr
expr
operator
+
id
number
initial
*
rate
60
Hình 1.6. Một cây phân tích cú pháp
16
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
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ữ
Quản lý bảng ký
hiệu
Xử lý lỗi
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
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
2
3
4
position
initial
rate
...
...
...
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
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
Tải về để xem bản đầy đủ
75 trang
22120
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Chương trình dịch (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_chuong_trinh_dich_phan_1.pdf
