Luận văn Xây dựng trình biên dịch cho ngôn ngữ Wave

- 1 - ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CHƯƠNG 1. Bùi Thanh Hiếu XÂY DỰNG TRÌNH BIÊN DỊCH CHO NGÔN NGỮ WAVE XÂY DỰNG BỘ PHÂN TÍCH CÚ PHÁP CHƯƠNG TRÌNH KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin - 2 - MỤC LỤC Mục lục hình vẽ ................................................................................................... 5  Khái niệm và cụm từ viết tắt .............................................................................. 8  CHƯƠNG 1.  GIỚI THIỆU .............................................................................. 9  1. 1  Wave............................................................................................................................9  1. 2  Các ứng dụng của Wave..........................................................................................10  1. 3  Nội dung khóa luận..................................................................................................11  CHƯƠNG 2.  NGÔN NGỮ WAVE................................................................ 12  2. 1  Giới thiệu về Ngôn ngữ Wave .................................................................................12  2. 2  Node, Link và Không gian phân tán : Knowledge Network (KN) ......................12  2. 3  Tổ chức chung của ngôn ngữ Wave .......................................................................13  2. 4  Cấu trúc dữ liệu cơ bản của Wave .........................................................................14  2. 5  Biến Spatial và kiểu .................................................................................................14  2. 5. 1  Task variables ................................................................................................................15  2. 5. 2  Environment variables ..................................................................................................15  2. 6  Các hành động - ACTS............................................................................................15  2. 6. 1  Control acts....................................................................................................................15  2. 6. 2  Fusion acts: Các phép toán hợp nhất...........................................................................17  2. 7  Rules – Các luật trong Wave ..................................................................................17  2. 8  Wave và mô hình lập trình truyền thống ..............................................................19  2. 8. 1  Sơ đồ luồng (SD) ...........................................................................................................19  2. 8. 2  Wave và mô hình lập trình song song ..........................................................................20  2. 8. 3  Wave và mô hình lập trình tuần tự...............................................................................22  CHƯƠNG 3.  XÂY DỰNG BỘ INTERPRETER ......................................... 28  3. 1  Wave không có Rule ................................................................................................28  - 3 - 3. 1. 1  Chi tiết ví dụ về các bước của Wave .............................................................................28  3. 1. 2  Thuật toán tổng quát cho Wave không có Rule ...........................................................30  3. 2  Wave có Rule ............................................................................................................31  3. 2. 1  Ví dụ về Wave có Rule...................................................................................................31  3. 2. 2  Thuật toán tổng quát cho Wave có Rule .....................................................................33  3. 3  Hệ thống Track ........................................................................................................36  3. 3. 1  Rule dựa trên bộ điều khiển Track...............................................................................36  3. 3. 2  Thuật toán cho Bộ xử lý track ......................................................................................39  3. 3. 3  Sự lan tỏa Track ............................................................................................................40  3. 4  Tổng quan và kiến trúc của Wave Interpreter .....................................................41  3. 5  Các thành phần trong Wave Interpreter...............................................................42  3. 5. 1  Wave và Wave Queue ....................................................................................................42  3. 5. 2  Knowledge Network.......................................................................................................42  3. 5. 3  Track Forest ..................................................................................................................43  3. 5. 4  Parsing Unit...................................................................................................................44  3. 5. 5  Excution Processor........................................................................................................51  3. 5. 6  TrackProcessor..............................................................................................................52  3. 5. 7  Communication Processor ............................................................................................56  3. 6  Quan hệ giữa các thành phần trong Wave Interpreter........................................57  3. 6. 1  Luồng xử lý Wave..........................................................................................................60  3. 6. 2  Luồng xử lý các echo và điều khiển các rule ...............................................................64  3. 6. 3  Xây dựng trình biên dịch Wave trên ngôn ngữ Java ...................................................67  CHƯƠNG 4.  THỰC HIỆN VÀ KẾT QUẢ .................................................. 69  4. 1  Cài đặt .......................................................................................................................69  4. 1. 1  Các yêu cầu về phần cứng ............................................................................................69  4. 1. 2  Các yêu cầu về phần mềm.............................................................................................69  4. 2  Thử nghiệm...............................................................................................................70  - 4 - 4. 2. 1  Sử dụng chương trình...................................................................................................70  4. 2. 2  Tạo lưới thực địa ...........................................................................................................71  4. 3  Di chuyển tự do ........................................................................................................72  4. 3. 1  Di chuyển tránh chướng ngại vật .................................................................................75  4. 3. 2  Di chuyển vòng quanh chướng ngại vật ......................................................................77  4. 4  Di chuyển cùng nhau kiểu tịnh tiến........................................................................80  4. 4. 1  Hiển thị hình ảnh 3D động bằng GnuPlot...................................................................80  4. 4. 2  Hiển thị hình ảnh 3D của tệp tin VRML......................................................................81  4. 4. 3  Hiển thị hình ảnh 3D với các góc nhìn khác nhau .....................................................82  4. 4. 4  Hiển thị hình ảnh 3D VRML trên nhiều máy..............................................................83  CHƯƠNG 5.  PHỤ LỤC.................................................................................. 86  5. 1  JJTree .......................................................................................................................86  5. 1. 1  Giới thiệu .......................................................................................................................86  5. 1. 2  Các kiểu cấu trúc cây ....................................................................................................86  5. 2  Thực thi trên ngôn ngữ simpleLang.......................................................................87  5. 3  Xây dựng bộ parser cho ngôn ngữ Wave...............................................................89  CHƯƠNG 6.  TÀI LIỆU THAM KHẢO....................................................... 92  - 5 - Mục lục hình vẽ Hình 1-1: Mô hình Wave .......................................................................................................................10  Hình 2-1: Knowledge Network ..............................................................................................................13  Hình 2-2: Thành phần của Spread Diagrams .........................................................................................20  Hình 2-3: Tự động tách trong chuỗi Wave.............................................................................................21  Hình 2-4: Một số trường hợp xử lý song song .......................................................................................21  Hình 2-5: Wave xử lý song song có kèm theo Rule...............................................................................22  Hình 2-6: Xử lý tuần tự không Rule và có Rule.....................................................................................23  Hình 2-7: Wave xử lý tuần tự có Rule ...................................................................................................23  Hình 2-8: một số trường hợp với mệnh đề If – else ...............................................................................24  Hình 2-9: Một số trường hợp với mệnh đề If – else...............................................................................24  Hình 2-10: else – if với filter..................................................................................................................25  Hình 2-11: Else – if parallel ...................................................................................................................25  Hình 2-12: Else – if với Rule .................................................................................................................26  Hình 2-13: Switch ..................................................................................................................................26  Hình 2-14: Câu lệnh lặp sử dụng Repetition..........................................................................................27  Hình 2-15: Câu lệnh lặp sử dụng Recursion ..........................................................................................27  Hình 3-1: Wave có Rule.........................................................................................................................31  Hình 3-2: Tạo track trong quá trình Wave thực thi và lan tỏa .................................................................1  Hình 3-3: Trạng thái và biến frontal.........................................................................................................1  Hình 3-4: Gửi echo và tổng hợp các kết quả trạng thái, sau đó loại các Track Link, Track Node thừa ..1  Hình 3-5: Truyền Tail tới các Track Node ngoài cùng (Node lá) ............................................................1  Hình 3-6: Kích hoạt Tail trong các Node lá .............................................................................................1  Hình 3-7. Các thành phần của Wave Interpreter ....................................................................................41  Hình 3-8: Wave và Wave Queue..............................................................................................................1  Hình 3-9: Knowledge Network ................................................................................................................1  Hình 3-10: Track Forest ...........................................................................................................................1  - 6 - Hình 3-11: Excution Processor ..............................................................................................................52  Hình 3-12: Sau khi nhận và xử lý CREATE ............................................................................................1  Hình 3-13: Sau khi nhận và xử lý EXPANDH ........................................................................................1  Hình 3-14: Sau khi nhận và xử lý ACTIVATE........................................................................................1  Hình 3-15: Sau khi nhận ECHO từ các nhánh con...................................................................................1  Hình 3-16: Sau khi xử lý ECHO nhận được ............................................................................................1  Hình 3-17: Communication Processor .....................................................................................................1  Hình 3-18: Quan hệ giữa các thành phần trong Wave Interpreter ...........................................................1  Hình 3-19: Luồng xử lý giữa các thành phần trong Wave Interpreter ...................................................60  Hình 3-20: Lan truyền echo lên trên ........................................................................................................1  Hình 3-21: Gửi tail cho các track con ......................................................................................................1  Hình 4-1. Chương trình hiển thị khi mới được chạy ..............................................................................70  Hình 4-2. Chương trình WAVE khi bắt đầu chạy.................................................................................71  Hình 4-3. Lưới 5x5................................................................................................................................71  Hình 4-4. Cửa sổ output của Netbeans...................................................................................................72  Hình 4-5. Vị trí đầu tiên 1-1...................................................................................................................72  Hình 4-6. Chạy ngẫu nhiên tới vị trí tiếp theo........................................................................................73  Hình 4-7. Các bước chạy ngẫu nhiên tiếp theo ........................................................................................1  Hình 4-9. Dừng khi chạy tới đích...........................................................................................................75  Hình 4-8. Tiếp tục chạy ngẫu nhiên .........................................................................................................1  Hình 4-10. Di chuyển qua chướng ngại vật .............................................................................................1  Hình 4-11. Vượt qua chướng ngại vật và về đến đích..............................................................................1  Hình 4-12. Di chuyển vòng quanh chướng ngại vật ................................................................................1  Hình 4-13. Vòng quanh chướng ngại vật 1 vòng thì dừng.......................................................................1  Hình 4-14. Di chuyển tịnh tiến cùng nhau ...............................................................................................1  Hình 4-15. Hình ảnh 3D trên máy thứ nhất sử dụng GnuPlot..............................................................81  Hình 4-16. Hình ảnh 3D trên máy thứ hai sử dụng GnuPlot..................................................................81  Hình 4-17. Tệp tin VRML được hiển thị sau khi được tạo bởi KN .......................................................82  - 7 - Hình 4-18. Các đối tượng hiển thị theo cách khác thi thay đổi Transform ............................................83  Hình 4-19. Một cách nhìn khác thi thay đổi Transform.........................................................................83  Hình 4-20. Hiển thị đối tượng đầu tiên trên máy 1 ................................................................................84  Hình 4-21. Hiển thị đối tượng thứ hai trên máy 2..................................................................................85  - 8 - Khái niệm và cụm từ viết tắt CP Communication Processor CQ Communication Queue EU Execution Unit KN Knowledge Network PU Parsing Unit SD Spread Diagrams SNR Set of Nodes reached TF Track Forest TN Track Node TP Track Processor TQ Track Queue WI Wave Interpreter WQ Wave Queue - 9 - CHƯƠNG 2. GIỚI THIỆU Ở chương này chúng tôi trình bày tổng quan về công nghệ Wave nhằm trả lời các câu hỏi sau: Wave là gì? Nó khác và ưu điểm hơn so với các hệ thống bình thường ở chỗ nào? Các ứng dụng viết trên Wave sử dụng trong lĩnh vực gì? 2. 1 Wave Ngày nay, các hệ thống mở và mạng máy tính đang phát triển rất nhanh và được cả thế giới quan tâm. Hệ thống mạng máy tính kết nối công việc từ khắp nơi trên thế giới, mạng máy tính cũng giữ một khối lượng khổng lồ dữ liệu dịch vụ và thông tin. Những công cụ tương tác không chỉ để tìm kiếm thông tin, dịch vụ hoặc file ngay trên máy tính mà còn được mở rộng về địa lý, không gian… và hoàn toàn mở trên Internet. Một ví dụ điển hình ở đây chính là World Wide Web. Tuy nhiên, hầu hết các mô hình và công cụ lập trình phân tán thiếu đi khả năng linh hoạt để khai thác thông tin về cấu trúc mở một cách tự động. Những mô hình lập trình và hệ thống phân tán truyền thống thường dựa trên dữ liệu đóng. Công việc được xử lý trong các ứng dụng phân tán thường phải được định nghĩa trước hoặc được gọi thông qua việc kích hoạt thủ tục, phương thức. Phần lớn việc xử lý và tương tác thông qua việc trao đổi thông điệp chứa dữ liệu. Ngoài ra hệ thống phân tán có thể cung cấp dữ liệu và dịch vụ chia sẻ. Trong mạng máy tính, dịch vụ và thông tin chỉ nằm ở các máy chủ ứng dụng (ví dụ như việc sử dụng của các tổ chức kinh doanh…). Tuy nhiên, phương pháp tiếp cận này vẫn chưa tối ưu. Do đó, chúng ta sẽ cần phải tích hợp linh hoạt các máy chủ ứng dụng trong một hệ thống tổng thể và có cơ sở hạ tầng mở hơn nữa. WAVE không chỉ là một mô hình. Wave còn là công nghệ dựa trên sự liên kết và điều khiển của các hệ thông lớn được hỗ trợ bởi mạng máy tính và viễn thông. Wave cho phép linh động tạo các cấu trúc điều khiển và việc xử lý mạng tri thức (phân tán và song song) thông minh. Các cấu trúc này có thể cung cấp khả năng tự tổ chức, phục hồi, tạo khuôn mẫu để kết nôai tới các hệ thống khác. Công nghệ này dựa trên việc cài đặt nhiều tác nhân thông minh trên hệ thống phân tán để tối ưu hóa việc xử lý dữ liệu cục bộ thông qua việc lan tỏa thông tin ở các hệ thống nhỏ với nhau hoặc ở hai hệ thống nhỏ khác nhau. Tất cả công việc trên đều được thông dịch qua ngôn ngữ Wave. Mã đệ quy được viết từ ngôn ngữ này có khả năng tự lan tỏa trong không gian hệ thống. Không giống các hệ thống truyền thống, nó là một hệ thống dựa trên sự linh động của chương trình có thể tùy ý mở rộng về mặt địa lý và hỗ trợ nhiều máy tính trên mạng. Trong Wave, chương trình có thể cho vào trong hệ thống bất kỳ chỗ nào. Khi đó các chương trình này có khả năng lan tỏa qua mạng như virus. Nhiều người sử dụng có thể độc lập phát triển các chương trình Wave hoặc liên kết trong cùng một hệ thống không gian, chia sẻ biến cục bộ (biến này được liên kết với Node) với các biến khác (được kèm theo sự duy chuyển của mã Wave). Nói cách khác: • Wave là một ngôn ngữ, model đặc biệt và là công nghệ mới cho hệ thống song song, phân tán hay