Chương 1 ĐẬT VÁN ĐÈ Lý thuyết môn học ChưmĩiỊ trình dịch là một trong những lý thuyêt chuyên ngành khó cùa công nghệ thông tin. Để nắm vừng và đi sâu vào lý thuyết này thì khônu cách nào hơn là tự minh xây dựng lấy một chương trinh dịch hoàn chinh, qua đó ta có thể vỡ ra nhiều vấn đè về lý thuyết và thực hành. Các kĩ thuật cùa chương trình dịch có nhiều điều bổ ích và rất lý thú. Nó có thể áp dụng rất tốt sang các bài toán khác.
Nhằm giúp các bạn thực hành môn học, chúng tôi biên soạn phần thực hành nảy. Nhiệm vụ thực hành cùa chúng ta như sau: Viết một chương trình biên dịch hoàn chinh. Chương trình này sẽ dịch các chinmg trình nguồn viết trong một ngôn ngữ lập trình bậc cao và cho ra chương trình đích trong một ngôn ngừ lộp trình bậc thấp, chạy được trên một loại máy lính nào đó. Chương trình dịch loại biên dịch (sau này sẽ gọi dơn giản là chương trình dịch nếu khône sợ hiểu lầm) sẽ dịch toàn bộ chương trinh nguồn thành cliưcrng trinh đích rồi mới chạy.
Nó khác với loại thông dịch là dịch rồi cho chạy làn lượt từng câu lệnh. Đa số các chương trình dịch ngày nay là loại bicn dịch. Như phân lý thuyết đà cho thấy, chương trình dịch có nhiều giai đoạn, mỗi giai đoạn phái áp dụng những lý thuyết và những kĩ thuật khác nhau. Đông thời, các chương trình dịch cho cùng cặp ngôn ngừ vào /ra có thể có nhièu mức độ phức tạp và hoàn chinh khác nhau.
Do đó, vấn đề đặt ra với chúng ta là biết chọn độ phức tạp và hoàn chinh vừa đù đề thực hành và hoàn thành được nó. 167 Chương trình nguồn viết trong Chương trình nguồn viết một ngôĩ^ngừ nguồn trorm SLAN(J Phân tích i Phân tích từ vựng lừ vựnc Z E Z c Phân tích <35 JcZ. Phân tích cú pháp e '< Í C cú pháp k ĩ Ỷ I/ Phân tích \\ Phân tích _________ .1/ / ngừ nghĩa V V / ngữ nghĩa ^ Quản lý ị/ ------------ '1 V - “Mng~kịr -------- x r - ~ ~ - ^ “ X ĩĩiriồ ĩ' hl^u KN v Sinh mà / i *Ị \\ trung gian // ^ Sinh mà V* JZ 1 Tối ưu mà 0ã1 '<■pw Chưcmg trinh đích i I c '« ữ cho máy tính VI.VI sz Sinh mã CL t Chương trình đích viết cho một ngôn ngừ Hình 1. Sơ đồ khối cùa một chương trinh dịch đầy đủ và chương trình ta sẽ thực hành.
Chúng ta sẽ không thực hiện mọi khối chức năng của chương trinh dịch mà chỉ các chức năng cơ bản và bò đi hai khối (bạn c ó thê tự phát triển chúng): sinh mã trung gian và tối ưu mã. Ta cũng bò đi một số dường nổi ít dùng giữa các khối: trong các chương trình dịch bình thường thì khối phân tích cú pháp không cần làm việc với bàng ký hiệu và bộ sinh mã không tạo lỗi nên có thề bò các đường nối giữa chúng. Sơ đo khối cùa một chương trình dịch đây đủ và chương trình dịch ta sẽ thục hành được trình bày ở hình 1.1 đê bạn đọc tiện so sánh. Đầu tiên, ta sẽ nghiên cứu về một ngôn ngữ lập trình bậc cao (tên là SLANG) nhưng nhỏ và vừa đủ phức tạp mà ta sẽ viết chương trình dich cho nó (chương 2, phần A).
Căn cứ vào định nghĩa của ngôn ngữ lập trình này, ta sẽ thiết kế và lập trình cho ba khối đầu: phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa. Các kĩ thuật dùng trong phần phân tích từ vựng (chương 3) là kĩ thuật viết chương trinh dựa vào đô thị chuyển theo phương pháp diễn giải - một phương pháp thực hiện tương đối chân nhương, dễ làm. 168 Tn ng phần phân tích cú pháp (chương 4), ta sẽ học cách viết bộ phân tích đ( quy đi xuống. Việc xây dựnu bộ phân tích được tiến hành như môí công rụhệ: áp dụng một cách mày móc các luật xây dựng.
Do đó có thể viết chươn* trinh phân tích một cách đơn giàn và chính xác (hoặc tự tạo ra các công CJ sinh tự động chương trinh nRuồn cùa bộ phân tích cú pháp). Phin tiếp theo (chương 5) ta sẽ học về cách thiết kế và thực hiện bảng ký hiệi qua kĩ thuật cây nhị phân kết hợp bảng băm (hash table). Phần này cũng t ình bày về kĩ thuật cài đật cú pháp điều khiển thông qua kĩ thuật "trên cùng ciuyến bay" - hay kĩ thuật cho phép duyệt các luật neữ nghĩa trong lúc đang phân tích. Khờ việc duyệt các luật ngữ nghĩa mà có thể kiểm tra kiêu (tức là thực hiện nhiệm vụ chính cùa bộ phân tích ngữ nghĩa) và sinh ra mã cho ưuy tính ảo VỈM trong hai chức năng cuối (chương 5 và chương 6).
Đầi ra cùa chương trình dịch là các chương, trình đích viết trong một ngôn Igừ bậc thấp, dùng để chạy trên một máy tính ảo VIM. Máy tính ào V1M chi là một cái máy do ta tự thiết kế và lập trình mô phòng. Do đó, ta phải nịhiên cứu, đưa ra cú pháp và bộ lệnh cho máy tính này sao cho gần giống với các máy tính thông thường. Ta cũng học về cách thực hiện máy tính ảc này nhờ một chương trình dịch loại khác - loại thông dịch (chương 2, phầi B).
Tuy mất công xây dựng máy tính ảo chứ không dùng máy tính thật, mưng sẽ giảm được độ phức tạp và công sức xây dựng phần sinh mã (vốn đ)i hỏi rất nhiều công sức và kinh nghiệm) đến mức thực hiện được. T a sẽ học về cách xử lý lỗi của chương trình dịch (chương 7). Trong giáo trnh này, phần này được giản lược nhiều nên rất đơn giản. T n n g chương cuối (chương 8), giáo trình sẽ đề cập đến một số cải tiến ngôn Igữ đầu vào và đầu ra cùng với hướng dẫn cách sừa chương trinh cho phù hrp với các cài tiến đó.
Sau khi cài tiến, ngôn ngữ đầu vào đã trở thành một n'ôn ngừ bậc cao thật sự, có khà năng và mức độ phức tạp gần bằng các mgòn ngữ lập trình thông thường. T h ế t kế cùa các phần đều rất "mờ", nghĩa là ta có thể dễ dàng thêm, sừa mà klpng làm rối, hỏng thiết kế tổng quát. Do đó, nhiều phần mở rộng được ra nhum ột bài tập mà bạn có thể thực hiện dễ dàng. 'Tteo các chương và các bài tập, giáo trìrth đưa ra các gợi ý, các vấn đê mới., á c hướng phát triển, các dự án để các bạn say mê có thể tự mình tìm tòi, nihiên cứu.
Bạn có thể áp dụng những kiến thức và kinh nghiệm thu đượ<c <ể xây dựng chương trình dịch hoàn chinh cho một ngôn ngữ lập trình thật SỊ. Giáo trình có cung cấp thiết kế của một số ngôn ngữ lập trình (trong phụ lụ A) để bạn tham khảo. Cũng theo các chương và bài tập, độ khó của 169 kiến thức và yèu cầu đối với bạn sẽ tăng dần. Troníỉ các chương đầu, bạn sẽ được học và làm theo.
Đen các chương cuối bạn phái tự mình giài quyết lấy một số vấn đề. Ngoài nhiệm vụ chính là giúp bạn thực hành về chương trình dịch, giáo trình còn đưa ra một sổ chưomg trình ứng dụng có ích (trong phụ lục B). Các chương trình này đều phát triển từ các kĩ thuật của chưcmg trình dịch. Các chương trình trong giáo trình chù yếu được viết trong ngôn ngữ c, một ngôn ngừ lập trình bậc cao rất mạnh và mồm déo, tiện cho các bái tập lớn.
Tuy vậy, đồ thích hợp với thói quen cùa nhiều bạn, giáo trình cũng dưa ra các chương trình nguồn tương đương viết trong ngôn ngữ Pascal trong phân phụ lục c. Hi vọng sau khi thực hành, bạn sẽ cài thiện thêm tay nghề thiết ke và lập trình, có cái nhin logic, sâu sắc hơn vào lý thuyết và thực hành môn học này. Tóm tắt n/iũvg kĩ thuật clúnlt sẽ tliục hành: Chức tìăng Kĩ thuật chinh sẽ thực hành Dựng đồ thị chuyền và viết chương trình cho nó theo Phân tích từ vựng phương pháp diễn giải. Phân tích theo phương pháp LL (1) với kĩ thuật đệ quy Phân tích cú pháp đi xuống - xây dựng chương trinh phân tích cú pháp nhờ áp dụrm luật xây dựne.
Kĩ thuật gắn các luật ngữ nghĩa (cú pháp điều khiển) Cú pháp điều khiển với luật cú pháp và duyệt chúng trong lúc đang phân tích: kĩ thuật “trên củng chuyến bay”. Phản tích ngừ nghĩa Kiểm tra kiểu nhờ cú pháp điều khiển. Sinh mà Sinh mà cho máy tính ảo nhờ cú pháp điều khiển. Quản lý bảng kỷ hiệu Tô chức bảng ký hiệu thông qua cây nhị phân.
Phát hiện và khôi phục sau khi gặp lỗi trong các phân X ử lý lồi phân tích từ vựng, cú pháp và ngừ nghĩa. Khôi phục lỗi cú pháp theo chiến lược "khôi phục cụm từ”. 170 C hư ơ ig 2 NGCN N G Ữ NGUÒN VÀ MÁY TÍNH Ả o Tnng phần này ta sẽ tìm hiểu về naỏn ngừ nguồn SLANG, ngôn neừ đích VM của chương trình dịch mà ta sẽ viết. Nói cách khác, đó là các ngôn nịữ của dầu vào và ra.
Ta sẽ tìm hiểu và thiết kế máy tính chạy được VIM -máy tính áo VIM. Quan hệ giữa SLANG, VIM và máy tính ào như hình 21 (so sánh tương ứng với hệ thống dịch điển hình Turbo Pascal): C h ư ơ g trinh 11 Chương trinh đích ngu n viét Chương ! mã V ỈM tpne trình đích ; ► SLiNG mả VIM ; ị ị ệ u v£0 Dừ liệu ra Chưong (rình Máy tỉnh ăo - -- ► f (lịch SLC VIM Hình 21. Chương trình dịch SLC dịch tử ngón ngữ lập trinh SLANG sang mă VIM và máy tin ào chạy chương trinh mã VIM. So sánh với chương trinh dịch Turbo Pascal cho máy IBM - PC.
NCÔN NGỮ NGUỒN SLANG (bước l ) 1 N p n ngĩr nguồn SLANG là một ngôn ngữ lập trình bậc cao nhỏ và đơn giản (,'LANG có thể coi là viết tắt cùa cácc từ Source LANGuage, hoặc Sinall ^ANGuage, hoặc Simplc LANGuage). Thiết kế SLANG trong bước 1 Các rờ rộng SLANG (bước 2) được trình bày trong chương 8. 171 đầu phải đạt được hai mục đích: Trước hết, ngôn ngữ này cần phải đù phức tạp để ta có the thực hành đầy đù các quá trình dịch. Do đỏ ngôn ngừ này phài có đù các thành phần và cấu trúc cơ bàn cũng nlur cẩn có them các thủ tục.
Thứ hai, ngôn ngừ này lại phải đù nhò và dơn giàn. Do đó, các thù tục lại không cỏ tham số và chi có một kiểu dừ liệu (kiều số nguycn).