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

ao trong hai từ khóa "PARSER_BEGIN(parser_name)" và "PARSER_END(parser_name)". Tiếp đến là danh sách các cú pháp luật sinh. Các tùy chọn và luật sinh sẽ được trình bày dưới đây. Tham số name trong cặp từ khóa PARSER_BEGIN và PARSER_END là tên của bộ phân tích cú pháp được sinh ra. Đối với đề tài name có tên là WaveParser thì JavaCC tự động chèn các tên này vào sau các file tùy chọn được sinh ra như WaveParserConstants.java, WaveParserTokenManager.java … PARSER_BEGIN(parser_name) . . . class parser_name . . . { . . . } . . . PARSER_END(parser_name) a. Các từ khóa và tùy chọn của JavaCC JavaCC cung cấp một tập các từ khóa như bảng sau: EOF IGNORE_CASE JAVACODE LOOKAHEAD MORE options PARSER_BEGIN PARSER_END SKIP SPECIAL_TOKEN TOKEN TOKEN_MGR_DECLS Ngoài ra JavaCC còn cung cấp một số từ khóa thuộc loại tùy chọn trong một file đặc tả cú pháp của JavaCC. LOOKAHEAD: Số token được nhìn trước trước khi quyết định lựa chọn một điểm trong quá trình phân tích. Mặc định có giá trị 1. Số nhỏ hơn, quá trình phân tích nhanh hơn. Số này có thể định nghĩa lại cho các luật sinh cụ thể trong phạm vi ngữ pháp để định rõ tính chất giai đoạn sau. CHOICE_AMBIGUITY_CHECK: Đây là một tùy chọn số nguyên có giá trị mặc định là 2. Đây là số token có được trong việc kiểm tra sự lựa chọn của hình thức "A | B | ..." cho tình trạng có nhiều nghĩa. - 47 - OTHER_AMBIGUITY_CHECK: Đây là một tùy chọn số nguyên có giá trị mặc định là 1. Đây là số token có được trong việc kiểm tra tất cả các hình thức khác nhau của sự lựa chọn (ví dụ của hình thức "(A)*", "(A)+", and "(A)?") cho tình trạng có nhiều nghĩa. Việc này mất nhiều thời gian hơn sự kiểm tra lựa chọn, do đó giá trị mặc định được thiết lập là 1 hơn là 2. STATIC: Đây là một tùy chọn kiểu boolean có giá trị mặc định là true. Nếu true tất cả các phương thức và biến của lớp theo lý thuyết đều là static trong sự phát sinh cú pháp và quản lý token. DEBUG_PARSER: Đây là một tùy chọn kiểu boolean có giá trị mặc định là false. Tùy chọn này được sử dụng để gỡ lỗi từ việc phát sinh cú pháp. Thiết lập tùy chọn này là true là nguyên nhân quá trình phân tích cú pháp phát sinh dấu hiệu của hành động. DEBUG_LOOKAHEAD: Đây là tùy chọn kiểu boolean có giá trị mặc định là false. Thiết lập tùy chọn này là true là nguyên nhân quá trình phân tích cú pháp phát sinh tất cả dấu hiệu thông tin nó thực hiện khi tùy chọn DEBUG_PARSER là true, đó cũng là nguyên nhân để nó phát sinh ra dấu hiệu hành động đã thi hành trong thao tác lookahead. DEBUG_TOKEN_MANAGER: Tùy chọn boolean có giá trị mặc định là false. Tùy chọn này được sử dụng để gỡ lỗi thông tin từ các token đã phát sinh. Thiết đặt tùy chọn này là true là nguyên nhân để quản lý token phát sinh dấu hiệu của hành động. Dấu hiệu này khá rộng và chỉ nên sử dụng nó khi có một lỗi từ vựng, những lỗi thông báo đến bạn và bạn không biết tại sao. Điển hình trong trường hợp này, bạn có thể giải quyết vấn đề bằng cách chú ý đến vài dòng trước đó của dấu hiệu. ERROR_REPORTING: Tùy chọn boolean có giá trị mặc định là true. Thiết lập tùy chọn này là false là nguyên nhân các lỗi mắc phải từ các lỗi phân tích cú pháp có báo cáo thiếu chi tiết. Lý do để thiết lập tùy chọn này là false là để cải tiến sự thực thi. JAVA_UNICODE_ESCAPE: Đây là tùy chọn boolean có giá trị mặc định là false. Khi thiết lập true, sự phân tích cú pháp đã phát sinh sử dụng một luồng vào xử lý bởi Java Unicode escapes(\u...) trước khi gửi ký tự tới token manager. Mặc định Java Unicode escapes không xử lý. UNICODE_INPUT: Đây là tùy chọn kiểu boolean giá trị mặc định là false. Khi thiết lập true, sự phân tích cú pháp đã phát sinh sử dụng một luồng nhập để đọc file Unicode. Mặc định file ASCII được thừa nhận. Tùy chọn này được bỏ qua nếu một trong hai tùy chọn USER_TOKEN_MANAGER, USER_CHAR_STREAM được thiết lập là true. IGNORE_CASE: Tùy chọn kiểu boolean có giá trị mặc định là false. Thiết lập tùy chọn này là true là nguyên nhân phát sinh ra token manager để bác bỏ trong trường hợp token được chỉ định rõ và những hồ sơ đưa vào. Tùy chọn này hữu dụng trong việc viết ngữ pháp cho ngôn ngữ như HTML. - 48 - USER_TOKEN_MANAGER: Tùy chọn kiểu boolean, giá trị ngầm định là false. Hành động mặc định là phát sinh ra một token manager làm việc trên những token ngữ pháp đã chỉ rõ. Nếu nó được thiết lập true, bộ phân tích cú pháp được phát sinh để thừa nhận những token từ bất kỳ token quản lý nào thuộc kiểu "TokenManager"- giao diện được phát sinh vào trong thư mục bộ phân tích cú pháp. b. Bộ quản lý Token Phần đặc tả từ vựng của JavaCC được tổ chức thành tập các trạng thái từ vựng “lexical states”. Mỗi trạng thái từ vựng có một định danh. Trạng thái từ vựng chuẩn là DEFAULT. Trình quản lý token được sinh ra tại mỗi thời điểm sẽ có một trạng thái từ vựng trong tập các trạng thái từ vựng. Khi trình quản lý token khởi tạo nó sẽ có trạng thái từ vựng mặc định là DEFAULT. Trạng thái từ vựng bắt đầu có thể được xác định giống như là tham số khi xây dựng một đối tượng quản lý token. Có 4 loại biểu thức chính qui: SKIP, MORE, TOKEN, và SPECIAL_TOKEN. o SKIP: Bỏ qua chuỗi từ vựng khi gặp khai báo SKIP. o MORE: Tiếp tục cho đến khi gặp trạng thái kế tiếp, đưa chuỗi từ vựng khi gặp khai báo MORE vào trạng thái chờ. Chuỗi này sẽ là tiền tố cho chuỗi kế tiếp. o TOKEN: Tạo ra một token sử dụng chuỗi và gửi nó vào bộ phân tích cú pháp. o SPECIAL_TOKEN: Tạo ra một token đặc biệt không tham gia vào quá trình phân tích. c. Luật sinh Có 4 loại luật sinh trong JavaCC gồm javacode_production , bnf_production, regular_expr_production, token_manager_decls. javacode_production và bnf_production được sử dụng để định nghĩa ngữ pháp trực tiếp cho bộ phân tích cú pháp. regular_expr_production được sử dụng để định nghĩa ngữ pháp của các Token, trình quản lý Token sử dụng các ngữ pháp này để tạo ra Token manager, có thể hiểu đây các đặc tả token trong bộ phân tích cú pháp. token_manager_decls được sử dụng để giới thiệu các khai báo dùng để chèn vào bên trong trình quản lý token. • javacode_production javacode_production là một cách để viết mã Java cho một số các luật sinh thay vì sử dụng EBNF. Điều này hữu ích khi mà việc định nghĩa một cú pháp bằng EBNF quá khó khăn. Ví dụ sau minh họa cho việc định nghĩa xác định luật sinh của một block. JAVACODE void skip_to_matching_brace() { Token tok; - 49 - int nesting = 1; while (true) { tok = getToken(1); if (tok.kind == LBRACE) nesting++; if (tok.kind == RBRACE) { nesting--; if (nesting == 0) break; } tok = getNextToken(); } } • bnf_production bnf_production ::= java_access_modifier java_return_type java_identifier "(" java_parameter_list ")" ":" java_block "{" expansion_choices "}" bnf_production là luật sinh chuẩn được sử dụng trong JavaCC. Mỗi luật sinh BNF có vế trái là một đặc tả không kết thúc. Luật sinh BNF sẽ định nghĩa đặc tả không kết thúc này theo cách thức của BNF mở rộng hay EBNF. Điều này được thực hiện giống như các khai báo của các phương thức trong Java. Có 2 phần chính ở vế phải của luật sinh BNF : - Phần thứ nhất là tập các khai báo và mã của Java(Java block). Các mã java này sẽ được sinh ra ở phần đầu của các phương thức cho luật sinh BNF. Mỗi khi phương thức luật sinh này được thực thi trong quá trình phân tích cú pháp thì những khai báo và mã java này sẽ được thực thi. Khai báo trong phần này sẽ có mặt ở tất cả các hành động trong EBNF. JavaCC không xử lý bất kỳ một khai báo hoặc đoạn mã java nào, ngoại trừ việc bỏ qua các dấu ngoặc đơn và thu thập tất cả mã lệnh để làm cơ sở trong các phương thức được sinh ra sau này. - Phần thứ hai của vế phải là các lựa chọn mở rộng expansion_choices có cú pháp như sau: expansion_choices ::= expansion ( "|" expansion )* Các expansion_choices được viết giống như một danh sách của một hoặc nhiều các mở rộng (expansion) được ngăn cách nhau bởi các dấu hoặc | . expansion ::= ( expansion_unit )* - 50 - Một mở rộng(expansion) được viết thành một tập các đơn vị mở rộng(expansion units). Một expansion đúng khi tất cả các expansion units đều đúng. Ví dụ, mở rộng (expansion) "{" decls() "}" bao gồm 3 đơn vị mở rộng(expansion units) “{” , decls(), và “}”. Một cú pháp đúng cho mở rộng này là phải bắt đầu bằng một dấu “{” kết thúc bởi dấu “}” và thỏa mãn hàm decls() ở phần thân. Một đơn vị mở rộng(expansion_unit) có thể là một lookahead, một tập các khai báo và mã java (java_block), Các lựa chọn mở rộng(expansion_choices), .. expansion_unit ::= local_lookahead | java_block | "(" expansion_choices ")" [ "+" | "*" | "?" ] | "[" expansion_choices "]" | [ java_assignment_lhs "=" ] regular_expression | [ java_assignment_lhs "=" ] java_identifier "(" java_expression_list ")" Một đơn vị mở rộng có thể gồm các lựa chọn mở rộng có các tùy chọn “+”, “*”, “?”. lookahead ::= "LOOKAHEAD" "(" [ java_integer_literal ] [ "," ] [ expansion_choices ] [ "," ] [ "{" java_expression "}" ] ")" Số token được nhìn trước trước khi quyết định lựa chọn một điểm trong quá trình phân tích. Mặc định có giá trị 1. Số nhỏ hơn, quá trình phân tích nhanh hơn. Số này có thể định nghĩa lại cho các luật sinh cụ thể trong phạm vi ngữ pháp để định rõ tính chất giai đoạn sau. Ví dụ của luật sinh BNF: void WriteStatement() : { Token t; } { "printf" t = { jjtThis.name = t.image; } } • regular_expr_production regular_expr_production ::= [ lexical_state_list ] regexpr_kind [ "[" "IGNORE_CASE" "]" ] ":" "{" regexpr_spec ( "|" regexpr_spec )* "}" - 51 - Một luật sinh biểu thức chính qui (regular_expr_production) được sử dụng để định nghĩa các thực thể từ vựng sẽ được phân tích bởi trình quản lý token. Một luật sinh biểu thức chính qui (regular_expr_production) bắt đầu với một đặc tả của các tình trạng cho ứng dụng của nó. Tình trạng chuẩn là DEFAULT, đây là tình trạng mặc định cho các thực thể token. • token_manager_decls token_manager_decls ::= "TOKEN_MGR_DECLS" ":" java_block Phần khai báo của trình quản lý token ( token_manager_decls ) bắt đầu bằng từ khóa "TOKEN_MGR_DECLS" theo sau là dấu “:” và tập các khai báo và câu lệnh java(Java Block). 3. 5. 5 Excution Processor Excution Processor (EP) là thành phần đảm nhiệm chức năng xử lý các phép toán và các lệnh trong wave. EP sẽ được gọi đến để xử lý sau quá trình phân tích để lấy xác định phép toán cần được xử lý trong Wave Head. Các phép toán trong Wave được xử lý ở mức đơn giản là chỉ gồm một toán tử và hai toán hạng. Cấu trúc của EP bao gồm 3 thành phần chính đó là: Execution Control Unit (ECU), Operand Fetch Unit (OFU), Data Processing Unit (DPU) và Matching Unit (MU). • Execution Control Unit sẽ lấy ra chỉ lệnh và các tên của các toán hạng bên trái, bên phải. ECU chịu trách nhiệm điều khiển quá trình xử lý. • Operand Fetch Unit sẽ lấy ra giá trị của các biến bên trái, bên phải của toán hạng và điều khiển quá trình lưu trữ dữ liệu. • Data Processing Unit là thành phần xử lý sau khi đã xác định được toán tử và dữ liệu sẵn sàng. • Matching Unit đảm nhận công việc xử lý tìm kiếm trong KN. - 52 - Hình 3-11: Excution Processor 3. 5. 6 TrackProcessor Track Processor (TP) quản lý Track Forest của WI. TP xử lý tất cả các echo và suspended tail thông qua track. Track Processor nhận thông điệp điều khiển từ các thành phần khác thông qua Track Queue (TQ). Các thông điệp đi vào Track Queue gồm có: • CREATE: Thông điệp yêu cầu tạo track. • EXPANDH, EXPANDS: Tạo các nhánh con (Track con) của track hiện tại. EXPANDH dùng trong trường hợp các nhánh được sinh ra bởi lệnh hop, còn EXPANDS là trường hợp các nhánh sinh ra bởi các sector của wave head. • ACTIVATE: Thông điệp này sẽ được gửi ngay sau khi gửi hết thông điệp EXPAND để kích hoạt TN hiện tại. • ECHO: Thông điệp echo từ các nhánh con được gửi lên TN cha. • TAIL: Thông điệp gửi chuỗi wave tail đến các nhánh con để tiếp tục phát triển. Dưới đây là một quá trình nhận và xử lý các thông điệp của Track Processor - 53 - PROP Parent / Children / NONE 0 Wave Env #.C==b b c a PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent Children NONE 2 Wave Env C==b C==b TRR2 TRR3 TRR1 Hình 3-12: Sau khi nhận và xử lý CREATE Hình 3-13: Sau khi nhận và xử lý EXPANDH - 54 - PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent / Children NONE 2 Wave Env C==b C==b TRR2 TRR3 TRR1 Hình 3-14: Sau khi nhận và xử lý ACTIVATE - 55 - PROP Parent Children / NONE 0 Wave Env b c a PROP Parent Children / NONE 0 Wave Env PROP Parent / Children NONE 0 Wave Env C==b C==b TRR2 TRR3 TRR1 -1 2x Hình 3-15: Sau khi nhận ECHO từ các nhánh con - 56 - 3. 5. 7 Communication Processor Communication Processor đóng vai trò liên lạc giữa các WI trên các máy tính trong mạng. Khi chuỗi wave di chuyển trong KN bằng các lệnh hop, chúng có thể lan truyền từ WI trong máy tính này sang WI trên máy tính khác. Quá trình di chuyển của các chuỗi wave đó đều phải thông qua CP. Để đảm bảo dữ liệu giữa các máy tính là an toàn nên CP xử dụng giao thức TCP/IP của tầng giao vận để truyền và nhận các thông điệp, kết nối giữa các máy tính sẽ được giữ nguyên từ lúc các WI được thiết lập cho đến khi WI rời khỏi mạng. CP quản lý Communication Queue, đây là một hàng đợi chứa các thông điệp sẽ được gửi đi. PROP Parent Children / NONE 0 Wave Env b c a PROP Parent / Children NONE 0 Wave Env C==b TRR2 TRR1 -1 2x Hình 3-16: Sau khi xử lý ECHO nhận được - 57 - Cấu trúc chung của các thông điệp: • Type: kiểu của thông điệp bao gồm : o WAVE: thông điệp gửi wave đi o CREATE TRACK: thông điệp yêu cầu tạo track trên máy khác, o CREATE NODE: thông điệp yêu cầu tạo một node trong KN, o CREATE LINK: thông điệp yêu cầu tạo link giữa 2 node trong KN, o ECHO: thông điệp gửi echo đi, TAIL: thông điệp gửi wave tail đi) • Destination Address: địa chỉ của máy nhận thông điệp. • Source Address: địa chỉ của máy gửi thông điệp. • Data: Thành phần dữ liệu của thông điệp. 3. 6 Quan hệ giữa các thành phần trong Wave Interpreter Tổ chức các thành phần trong WI và quan hệ giữa chúng được thể hiện trong Hình 3-18: Quan hệ giữa các thành phần trong Wave Interpreter. Các thông điệp đến WI đều thông qua Communication Processor với 3 kiểu thông điệp chính là Wave, Echo và Tail. Type Destination Address Source Address Data Communication Queue Communication Message Hình 3-17: Communication Processor - 58 - Wave nhận được từ CP sẽ được gửi vào WQ để phân tích và xử lý, ngoài ra wave có thể được chèn vào WQ một cách trực tiếp từ WI, hoặc từ TP khi kích hoạt các nhánh để gửi các suspended wave. Thành phần EP cũng có thể gửi các wave vào WQ khi xử lý các sector, các toán tử code injection của ngôn ngữ Wave. Sự lan truyền của wave phụ thuộc vào TP và EP. Nếu trạng thái track của wave được kích hoạt, sự lan truyền của wave phụ thuộc gián tiếp vào EP, đầu tiên EP sẽ gửi thông điệp điều khiển vào TQ, thông điệp sẽ được TP xử lý và chuỗi wave được lan truyền khi track tương ứng được kích hoạt. Thông điệp ECHO và TAIL được CP và TP xử lý. Mỗi khi chuỗi wave kết thúc trong chế độ track EP sẽ tạo ra thông điệp ECHO và gửi vào TQ. Các suspended tail sẽ được TP gửi đi sau khi xử lý các ECHO mà điều kiện của rule được thỏa mãn để kích hoạt track. Các thành phần xử lý trong WI độc lập với nhau, mỗi thành phần sẽ xử lý dữ liệu trong các hàng đợi riêng. Tuy nhiên, EP có thể coi là thành phần xử lý chính, khi EP chịu trách nhiệm điều khiển toàn bộ quá trình xử lý wave và khởi tạo các thông điệp điều khiển tới các thành phần xử lý khác. PARSING UNIT (PU) TRACK PROCESSOR (TP) EXECUTION PROCESSOR (EP) COMMUNICATION PROCESSOR (CP) trackless sectors, code injection, hop, action track operations TQ resumed tails, activated sectors propagations, echoes, tails CQ wave, create KN echoes, tails ™ ƒÆ½Ä! waves  echoes  tails  WQ KN TN Hình 3-18: Quan hệ giữa các thành phần trong Wave Interpreter - 59 - WI là một hệ thống mở hoàn toàn khi 3 thông điệp WAVE, ECHO và TAIL có thể gửi trực tiếp từ bên ngoài vào trong hệ thống tới các node và link hoặc giữa các track. Người dùng có thể tương tác với WI bằng cách gửi các thông điệp tới CP hoặc trực tiếp gửi vào WQ thông qua các giao diện được cung cấp trên máy có cài đặt WI. Tương ứng với 3 loại thông điệp, WI có thể được tổ chức thành 3 luồng điều khiển chính cho từng thông điệp và thực thi một cách hoàn toàn độc lập. Các luồng điều khiền đó chính là đầu vào WI từ bên ngoài hệ thống, không những thế chúng còn tương tác qua lại lẫn nhau trong WI tạo thành chu trình xử lý các đoạn mã wave trên các node trong KN. Các hoạt động cơ bản của WI và tương tác giữa chúng được mô tả như trong Hình 3-19.Trước tiên, chúng tôi sẽ đưa ra cái nhìn tổng quát về các luồng chính này, sau đó sẽ mô tả chi tiết chúng trong phần tiếp theo. • Luồng xử lý Wave: Khi nhận được một wave từ bên ngoài, chuỗi wave thông thường được xử lý theo các bước: phân tích và xử lý wave head (parse, process_head), tạo ra các nhánh (spread_branches), sao chép wave tail cho các nhánh (replicate_tail) và lan tỏa chuỗi wave thu được đến các node đích (propagate). Quá trình này sẽ được tiếp tục cho đến khi chuỗi wave kết thúc hoặc được gửi ra ngoài hệ thống. • Luồng xử lý Echo: mỗi echo nhận được sẽ được gửi cho TP xử lý. Quá trình xử lý echo trải qua các bước: kích hoạt echo (activate_echo), gửi echo lên track cha (propagate_echo), và kết hợp echo nhận được với echo đã có ở track cha. Nếu tất cả các nhánh con của track cha đều đã gửi echo lên, thì quá trình lại được tiếp tục đối với track cha. Vòng lặp cứ tiếp diễn cho đến khi echo được gửi ra bên ngoài hệ thống. • Luồng xử lý Tail: tail từ các rule sẽ được gửi ngược lại thông qua track xuống các track con. Một wave tail từ bên ngoài đến sẽ được gửi tới track tương ứng và gửi xuống các track con thông qua hệ thống track hiện tại. Quá trình gửi wave tail sẽ được lặp lại cho đến khi tới các node đích hoặc wave tail được gửi đến các track con ở bên ngoài hệ thống. - 60 - Hình 3-19: Luồng xử lý giữa các thành phần trong Wave Interpreter 3. 6. 1 Luồng xử lý Wave Các wave nằm trong WQ độc lập với nhau, do đó sẽ được xử lý đồng thời. Đầu tiên, khi có wave nằm trong WQ, WI sẽ lần lượt lấy ra các wave, tách thành phần wave string và wave envrironment. Chuỗi wave thu được sẽ trải qua 2 giai đoạn: phân tích bởi PU và xử lý bởi EU. Ở giai đoạn phân tích, chuỗi wave được tách ra thành wave head và wave tail. Trong giai đoạn xử lý, wave head sẽ được xử lý ở node hiện tại và phụ thuộc vào kết quả xử lý mà wave tail sẽ được lan tỏa đến các node đích để tiếp tục quá trình thông dịch. Quá trình xử lý wave head được chia ra làm 7 trường hợp xử lý bao gồm: hop, action, sectors, control_rule, echo_dot_halt, code_injection, và external_call. Chi tiết về các trường hợp này được mô tả dưới đây: - 61 - • Hop Lệnh hop giúp cho wave di chuyển từ node này sang node khác cũng như từ WI này sang WI khác trong mạng. Quá trình xử lý hop như sau: 9 parser: wave string được phân tích thành wave head và wave tail. Wave head được phân tích thành 2 toán hạng và toán tử. 9 process_head: Toán tử xác định được từ bước trên dùng để xác định cấu trúc điều khiển trong 7 trường hợp xử lý. Trong trường hợp này là hop được xác định bằng toán tử ‘#’ 9 hop: xử lý lệnh hop. Hai toán hạng được xác định giá trị ở vị trí hiện tại trong KN. 9 match_KN: hai toán hạng sẽ được khớp với link và node của KN nối với node hiện tại. Nếu wave ở trong chế độ CREATE thì các link và node mới được tạo ra. Kết quả của bước này là danh sách các node thỏa mãn điều kiện. 9 spread_branch: Với mỗi node đích, một wave mới được tạo ra cùng với các biến frontal và biến environment ở node hiện tại. 9 replicate_tail: wave tail được gán làm wave string cho mỗi wave mới tạo ra. 9 activate_branch: kích hoạt xử lý các wave. 9 propagate: các wave tạo ra được gửi đến các node đích. Nếu node đích nằm trên cùng KN thì quá trình lan tỏa kết thúc và wave tail được gửi đến các node đích để tiếp tục được xử lý. Ngược lại wave sẽ được gửi ra ngoài mạng để tới node đích trên KN của máy khác. Độ dài của chuỗi wave giảm dần do wave head bị mất đi sau mỗi chu trình. Chu trình liên tục được diễn ra cho đến khi chuỗi wave di chuyển sang WI khác hoặc wave tail rỗng. Chuỗi wave rỗng nghĩa là đã được xử lý xong và có thể echo sẽ được gửi đi thông báo trạng thái kết thúc của wave • Action Các action được thực hiện ngay trên node hiện tại, bao gồm các toán tử gán và các toán tử so sánh. Các action được thực hiện dựa trên hai toán hạng bên trái và bên phải. Trong phép gán, kết quả sẽ được lưu trữ vào toán hạng bên trái. Trong các phép so sánh, trạng thái thực hiện của phép toán sẽ được ước lượng và quá trình xử lý chuỗi wave sẽ dừng lại nếu phép so sanh trả về kết quả là ‘fail’. Luồng xử lý các action sẽ bao gồm các bước sau: 9 parse: wave head và wave tail được tách ra từ chuỗi wave. Trong trường hợp này toán tử được xác định là các phép gán hoặc các phép so sánh. 9 process_head: quá trình xử lý chuyển sang xử lý các action 9 action_sequence: xử lý toán tử thu được. Việc xử lý các phép gán và các phép so sánh là khác nhau nên được chuyển thành 2 bước xử lý nhỏ hơn: − process_assign: Đây là bước xử lý cho các phép gán. Kết quả của phép gán sẽ được lưu lại vào toán hạng bên trái. - 62 - − process_filter: Các phép so sánh được xử lý. Nếu điều kiện so sánh được thỏa mãn thì quá trình xử lý sẽ tiếp tục, ngược lại việc xử lý sẽ ngừng lại và một echo thể hiện trạng thái thất bại được gửi đi (start_echo) − resume_tail: Khi action được xử lý xong, quá trình xử lý wave sẽ được tiếp tục lặp lại ở node hiện tại. • Sectors Nếu trong wave head chứa nhiều sector (mỗi sector phân cách nhau bởi dấu phẩy) thì chuỗi wave sẽ được phân chia ở node hiện tại thành các nhánh khác nhau. Mỗi nhánh nhận một wave string khác nhau, mà mỗi wave string là một sector được nối với wave tail. Việc xử lý sector cũng gần giống với hop nhưng khác một chút đó là các wave do quá trình xử lý sector sinh ra vẫn tiếp tục được xử lý ở node hiện tại. Quá trình xử lý các sector sẽ như sau: 9 parse: Wave head và wave tail được chia ra từ chuỗi wave, trong wave head chứa cú pháp của sector (chứa dấu phẩy phân cách). Trong trường hợp này, thay vì xác định các toán từ thì chuỗi wave giữa các sector sẽ được tách ra và trả lại cho bước xử lý tiếp theo. 9 process_head: quá trình xử lý chuyển sang xử lý các sector. 9 sectors: các nhánh ứng với mỗi sector bắt đầu được tạo ra. 9 spread_branches: mỗi nhánh ứng với một sectors được tạo ra trên cùng node hiện tại. Các biến frontal, environment được sao chép cho mỗi nhánh. 9 replicate_tail: wave tail sẽ được sao chép cho mỗi nhánh. Khác với việc sao chép wave tail trong hop, ở đây wave tail được nỗi vào chuỗi wave nằm trong từng nhánh được tách ra từ các sector trước đó. Các dấu ngoặc thừa bị xóa bỏ. 9 activate_branch: kích hoạt nhánh để xử lý (khác với hop, việc xử lý các sector không có bước propagation do các nhánh vẫn nằm trên node hiện tại) 9 resume_tail: wave string thu được sẽ tiếp tục được xử lý từ bước đầu tiên • Code injection Ngôn ngữ wave cho phép chèn vào các đoạn chương trình ngay trong quá trình xử lý từ các biến đi cùng wave trong quá trình đi chuyển hay từ các biến nằm trong node mà chuỗi wave đi qua. Đoạn chương trình được đưa vào sẽ nối vào đầu của wave tail và tiếp tục được xử lý trên cùng node với chuỗi wave trước đó. 9 parser: wave head và wave tail được tách ra. Wave head là toán tử ‘^’ đứng trước một biến báo hiệu đoạn mã được chèn thêm vào chính là giá trị của biến đó. 9 process_head: quá trình xử lý chuyển sang xử lý lệnh code injection 9 code_injection: Giá trị của biến được lấy ra và chuyển sang dạng xâu (nếu cần thiết). String thu được sẽ nối vào đầu của wave tail, quá trình xử lý với chuỗi wave tổng hợp lại tiếp tục từ đầu trên cùng node hiện tại. • External call - 63 - Toán tử external call là cách giao tiếp của WI với các hệ thống khác thông qua hệ điều hành. Một lời gọi external call sẽ tạm dừng nhánh hiện tại và tiếp tục quay lại xử lý sau khi lời gọi kết thúc. 9 parser: Quá trình phân tích gặp toán tử external call (cú pháp của ‘?’) 9 process_head: quá trình xử lý chuyển sang xử lý external call 9 external_call: hai toán tử được lấy giá trị và kết hợp thành lệnh để gọi chương trình. Lệnh này sẽ được gửi đi, nhánh hiện tại sẽ tạm treo cho đến khi chương trình được gọi thực hiện xong và trả về kết quả. 9 resume_tail: chuỗi wave sẽ tiếp tục quay lại quá trình xử lý • Control rule Chuỗi wave có 2 trạng thái lan tỏa, một là trong trạng thái không có track và một là trong trạng thái track. Khi di chuyển trong trạng thái track, sau mỗi lệnh hop, hoặc xử lý các sector thì sẽ tạo ra track mới nối với track hiện tại. Một control rule sẽ thiết lập một điểm điều khiển vào node hiện tại, việc điều khiển này được gắn với chuỗi wave nằm trong cặp mở đóng ngoặc của cú pháp rule. Chuỗi wave này gọi là enclosed wave. Quá trình xử lý được chia làm 2 phần: 9 Các biến frontal và environment của nhánh hiện tại sẽ được nhân bản cho enclosed wave, và một track mới được tạo ra. 9 Rule được gán cho track vừa tạo ra để xử lý các echo và wave tail sẽ được treo tại track mới này. Các luật tuần tự (SQ, OQ, AQ) đảm bảo các nhánh được thực hiện một cách lần lượt. Sau khi kích hoạt các nhánh thì chỉ duy nhất một nhánh được thực hiện và các nhánh khác sẽ tạm treo lại. Các bước xử lý như sau: 9 parser: Wave head và wave tail được tách ra. Wave head chứa một trong số các Rule của ngôn ngữ Wave và chuỗi wave nằm trong cặp mở đóng ngoặc. 9 process_head: Quá trình xử lý chuyển sang xử lý rule 9 control_rule: Xứ lý rule trong wave head 9 extract_head: tách wave string nằm trong cặp mở đóng ngoặc của rule, và tách các biến frontal, environment khỏi wave. 9 create_track: tạo ra track mới và track hiện tại (nếu có) sẽ là track cha của track vừa tạo 9 assign_rule: track mới tạo ra sẽ được gán với rule để xử lý các echo về sau. 9 suspend_tail: wave tail sẽ được treo ở track vừa tạo ra. • Echo dot halt Echo dot halt là các toán từ đặc biệt được xử dụng để kết thúc chuỗi wave đang thực thi trên node hiện tại và gửi lại các echo cho track. Sau đó, wave tail được treo tại track có thể được tiếp tục lan tỏa trong node hiện tại. Các bước xử lý như sau: - 64 - 9 parse: wave head và wave tail được tách ra, wave head chứa toán tử echo dot halt (cú pháp của ‘!’). 9 process_head: chuyển quá trình xủ lý sang echo dot halt 9 echo_dot_halt: giá trị của echo được xác định 9 start_echo: echo được gán cho track hiện tại và tiếp tục được lan tỏa lên trên theo track. 9 cancel_tail: wave tail sẽ được xóa bỏ sau khi gửi echo. Không chỉ có lệnh echo dot halt gửi echo sau khi xử lý mà lệnh hop và các lệnh so sánh cũng gửi echo. Lệnh hop sẽ gửi echo nếu việc khớp các toán hạng với KN thất bại. Các lệnh so sánh cũng gửi echo nếu điều kiện so sánh không được thỏa mãn. 3. 6. 2 Luồng xử lý các echo và điều khiển các rule Các echo sẽ lan truyền ngược lên gốc của hệ thống track và kết hợp với nhau tại các TN. Các echo sẽ được đồng bộ với nhau bằng cách track cha sẽ chờ các track con sau khi kết thúc gửi echo lên. Sau khi tất cả các echo đã được nhận đủ, track cha lại tiếp tục kích hoạt việc gửi echo tổng hợp lên trên. Quá trình trên sẽ tiếp tục cho đến khi gặp track có kèm theo rule hoặc echo được gửi tới gốc của hệ thống track. Sau khi xử lý xong chuỗi wave lan tỏa trong chế độ track, chương trình sẽ gửi thông điệp xóa track, để xóa toàn bộ dữ liệu lưu trữ trong track và giải phóng bộ nhớ phục vụ cho những đoạn mã wave tiếp theo. Trong track có thể gắn thêm rule hoặc không. Nếu track có gắn thêm rule thì việc kết hợp các echo sẽ không giống với khác track thông thường mà chịu sự qui định khác nhau của mỗi rule. Thêm vào đó, đối với các rule tuần tự có thể kích hoạt các track bị treo sau khi nhận được echo từ track con. Các rule còn thay đổi hành động của track sau khi nhận được các echo từ track con. Trong trường hợp này, thay vì gửi echo lên trên, chuỗi wave tail bị treo trong track sẽ được gửi đến các track con nếu điều kiện của rule được thỏa mãn. WT tail 2 1 3 7 4 5 6 Node đích Hình 3-20: Lan truyền echo lên trên - 65 - Các bước xử lý echo như trong ta thấy, ban đầu khi các track đã phát triển tới được node đích, quá trình echo sẽ được thực hiện từ các node đích ngược trở lên trên về track cha. Khi echo lên tới track có gán rule thì dựa vào echo tổng hợp được và rule thì wave tail sẽ được gửi trở lại các track lá. Các bước xử lý echo được thể hiện trong luồng thứ 2 của Hình 3-19: Luồng xử lý giữa các thành phần trong Wave Interpreter. Các echo sẽ bắt đầu lan tỏa từ các node đích khi chuỗi wave kết thúc hoặc bị hủy bỏ bởi các điều kiện không thỏa mãn trong phép so sánh hay khi xử lý lệnh echo dot halt. Echo được kích hoạt tại các track lá, sau đó lan truyền và đồng bộ trong hệ thống track. Luồng xử lý echo có thể chia làm 3 phần đó là: gửi các echo đi, xóa track và tổng hợp echo tại track chứa rule. • Gửi các echo Đây là phần chính trong luồng xử lý echo, bắt đầu khi chuỗi wave kết thúc xử lý. Các echo có thể được nhận từ ngoài mạng hoặc từ trong cùng WI, khi nhận được echo các bước xử lý bắt đầu sau bước start_echo: 9 activate_echo: echo được kích hoạt trong track và bắt đầu lan tỏa. 9 propagate_echo: echo được gửi lên track cha. Nếu track cha nằm trên máy khác thì echo sẽ được gửi ra bên ngoài mạng. 9 merge_echo: bước này do track cha xử lý khi nhận được echo, echo sẽ được tổng hợp lại với echo đang lưu trữ trong track. Nếu track cha nhận đủ echo từ các track con, quá trình này lại được tiếp tục đối với track cha. • Xóa track Cũng gần giống với việc lan tỏa các echo trong quá trình xóa track cũng có một thông báo được gửi đi, nhưng thay vì chỉ gửi echo lên trên, công việc xóa track lại bắt đầu từ track cha.Thông điệp xóa track sẽ được gửi đi sau khi chuỗi wave thực hiện xong, hoặc chuỗi wave chuyển từ chế độ track sang chế độ thông thường. Các bước xóa track diễn ra như sau: 9 activate_echo: quá trình xóa track được kích hoạt. tail 2 1 3 7 4 5 6 Node đích Hình 3-21: Gửi tail cho các track con - 66 - 9 delete_track: track được xóa và tất cả các dữ liệu lưu trữ trong track được giải phóng. 9 propagate_echo: thông điệp xóa track được gửi xuống các track con 9 merge_echo: nếu track con nằm trên cùng WI với track cha, quá trình xóa track được lặp lại. Nếu không cùng WI thì thông điệp xóa track sẽ được gửi ra ngoài mạng. • Tổng hợp echo tại Track có rule Nếu rule được gán vào track thì quá trình xử lý echo sẽ thay đổi tùy thuộc vào ý nghĩa của từng rule khác nhau. Mỗi rule định nghĩa những điều kiện logic làm thay đổi việc tổng hợp các echo. Ví dụ như đối với luật AS nếu gặp ít nhất một echo mang giá trị FALSE thì giá trị của echo tại track là FALSE. Các rule tuần tự còn bao gồm các nhánh bị treo lại, và các nhánh sẽ lần lượt được kích hoạt sau khi nhận được echo và điều kiện của rule được thỏa mãn. Thông thường đối với các rule, các wave tail bị treo lại sẽ được gửi đến tất cả các track con sau khi track nhận đủ echo và điều kiện của rule được thỏa mãn. Sau khi gửi tail đi thì rule cũng sẽ bị xóa khỏi track và tính chất của rule cũng sẽ mất đi. Các rule trong track sẽ được kích hoạt mỗi khi nhận được echo từ một trong số các track con. 9 activate_echo: echo được kích hoạt trong track. Trong trường hợp này track được kích hoạt là một trong số các track con của track có gắn rule. 9 propagate_echo: echo được gửi lên track cha có gắn rule. Tại đây có 3 trường hợp có thể xảy ra. − activate_branch: nếu track hiện tại được gán rule tuần tự (SQ, OS, AS) thì nhánh tiếp theo sẽ được kích hoạt và xử lý. − delete_rule: nếu điều kiện của rule được thỏa mãn, rule được xóa khỏi track và wave tail được gửi đến các track con. − forward_tail: wave tail bắt đầu được truyền đi từ track hiện tại • Luồng xử lý Tail Quá trình gửi tail thông qua hệ thống track là luồng xử lý cuối cùng của WI. Quá trình này được kích hoạt bởi các rule hoặc có thông điệp tail đến từ mạng. Trên mỗi track nhận được tail, tail sẽ tiếp tục được được gửi đến các track con của nó cho đến khi track hiện tại là các track lá hoặc track được gửi nằm bên ngoài hệ thống. Các bước xử lý tail diễn ra như sau: 9 forward_tail: tail được nhân ra và gửi đến tất cả các track con, lặp lại cho đến khi tới được các track cuối cùng. 9 delete_track: bước này chỉ sử dụng khi track gửi tail đi không có track cha và chuỗi wave sau quá trình này sẽ chuyển sang trạng thái lan tỏa không có track. Tại bước này track sẽ bị xóa đi sau khi gửi tail đến các track con và giải phóng toàn bộ vùng nhớ mà track chiếm dụng. - 67 - 9 resume_tail: Khi các track cuối cùng nhận được tail. Tại các track này wave tail cùng với các biến frontal, environment được lưu trữ kết hợp tạo thành wave và tiếp tục quá trình xử lý. 3. 6. 3 Xây dựng trình biên dịch Wave trên ngôn ngữ Java Phần dưới đây tôi xin giới thiệu sơ qua về các lớp chính và quan hệ giữa chúng khi được viết trên ngôn ngữ Java. • Hệ thống Knowledge Network • Hệ thống Track Forest • Wave và waveEnvironment - 68 - • Các thành phần xử lý - 69 - CHƯƠNG 4. THỰC HIỆN VÀ KẾT QUẢ Ở các chương trước chúng ta đã tìm hiểu về công nghệ Wave và từng bước xây dựng trình biên dịch cho ngôn ngữ này. Trong chương này chúng ta sẽ sử dụng chính công nghệ Wave để mô phỏng một số vấn đề, bài toán như: tạo lưới đơn hướng (có thể tạo ở trên máy khác), đa hướng, di chuyển để tránh hoặc vòng quanh chứng ngại vật, 3D và thực tại ảo… 4. 1 Cài đặt 4. 1. 1 Các yêu cầu về phần cứng Muốn cài đặt và chạy các chương trình mô phỏng và hiển thị tệp tin VRML, chúng ta cần phải có những máy tính với phần cứng tối thiểu như sau: - CPU Pentium 4 - Bộ nhớ màn hình 64MB - RAM 128MB ( phụ thuộc vào yêu cầu tối thiểu của hệ điều hành được cài đặt) - Màn hình, chuột, bàn phím - Ổ đĩa cứng trống tối thiểu 30MB Để chạy được các chương trình trên nhiều máy tính, chúng ta cần phải có từ hai máy tính trở lên với cấu hình mỗi máy tối thiểu theo yêu cầu trên và mỗi máy phải có một card mạng và kết nối mạng với nhau. 4. 1. 2 Các yêu cầu về phần mềm Chương trình mô phỏng và hiển thị tệp tin VRML đòi hỏi từng phần mềm khác nhau được cài đặt sẵn, để chạy được tất cả các chương trình, cần phải có tối thiểu các phần mềm sau: - Hệ điều hành Windows, Linux, Unix, … (Bắt buộc phải sử dụng Windows để chạy chương trình GnuPlot và hiển thị tệp tin VRML tại các phiên bản hiện tại) - JRE phiên bản 6 - Java 3D phiên bản 1.5.2 - Netbeans 6.1 (Dùng để chạy chương trình dễ dàng hơn) - Bộ thư viện X3D - GnuPlot phiên bản 4.2.5 - 70 - 4. 2 Thử nghiệm 4. 2. 1 Sử dụng chương trình Chương trình WAVE có thể được đóng gói để chạy như một ứng dụng riêng biệt, tuy nhiên, vì trong chương trình chúng ta sử dụng các thư viện của WAVE để chạy nên chúng ta sẽ gộp chung chương trình hiển thị và WAVE vào chung một project của Netbeans cho thuận tiện hơn khi chạy. Để chạy chương trình mô phỏng các bài toán ở dạng 2D, chúng ta cần phải chạy chương trình là lớp Sim trong gói (package) sim của project WAVE. Khi mới được chạy, chương trình sẽ xuất hiện cửa sổ chưa có nội dung. Hình 4-1. Chương trình hiển thị khi mới được chạy Sau khi chương trình hiển thị đã chạy, chúng ta chạy cả project WAVE (RUN project) để chạy chương trình WAVE. Lúc này, chương trình WAVE cũng xuất hiện một cửa sổ. - 71 - Hình 4-2. Chương trình WAVE khi bắt đầu chạy Sau đó, để thực hiện mô phỏng cho một bài toán cụ thể, chúng ta chọn nút Browse… của cửa sổ chương trình WAVE sau đó chọn các tệp tin tương ứng trong thư mục Simulation để chạy tiếp chương trình. 4. 2. 2 Tạo lưới thực địa Chúng ta muốn tạo lưới và hiển thị trên chương trình hiển thị, cần lựa chọn tệp tin tạo lưới trong thư mục Simulation. Tùy thuộc vào nội dung mà chúng ta tạo lưới sẽ được tạo khác nhau. Giả sử, ở đây, chúng ta tạo ra một lưới 5x5, chương trình hiển thị sẽ hiển thị lưới ra màn hình: Hình 4-3. Lưới 5x5 - 72 - Chương trình WAVE cũng đưa ra thông báo, chúng ta có thể xem được tại cửa sổ Output của Netbeans: Hình 4-4. Cửa sổ output của Netbeans 4. 3 Di chuyển tự do Bài toán di chuyển tự do của một vật từ tọa độ (1-1) đến (5-5) được mô phỏng trong chương trình có kết quả chạy như sau: Hình 4-5. Vị trí đầu tiên 1-1 - 73 - Hình 4-6. Chạy ngẫu nhiên tới vị trí tiếp theo - 74 - Hình 4-7. Các bước chạy ngẫu nhiên tiếp theo - 75 - Hình 4-9. Dừng khi chạy tới đích 4. 3. 1 Di chuyển tránh chướng ngại vật Đối tượng di chuyển từ nút (1-1) đến (5-5) mà không đi qua chướng ngại vật Hình 4-8. Tiếp tục chạy ngẫu nhiên - 76 - Hình 4-10. Di chuyển qua chướng ngại vật - 77 - 4. 3. 2 Di chuyển vòng quanh chướng ngại vật Đối tượng đi vòng quanh chướng ngại vật mà không đi đến các điểm nằm cách xa chướng ngại vật hoặc đi xuyên qua chướng ngại vật: Hình 4-11. Vượt qua chướng ngại vật và về đến đích - 78 - Hình 4-12. Di chuyển vòng quanh chướng ngại vật - 79 - Hình 4-13. Vòng quanh chướng ngại vật 1 vòng thì dừng - 80 - 4. 4 Di chuyển cùng nhau kiểu tịnh tiến Hai đối tượng sẽ cùng nhau di chuyển đến đích: 4. 4. 1 Hiển thị hình ảnh 3D động bằng GnuPlot Bằng cách sử dụng GnuPlot, chúng ta có thể hiển thị các hình ảnh 3D động trên nhiều máy, mỗi máy hiển thị một phần hình ảnh động. Hình ảnh hiển thị 3D trên máy thứ nhất với tọa độ x trong khoảng từ 1 đến 5: Hình 4-14. Di chuyển tịnh tiến cùng nhau - 81 - Hình 4-15. Hình ảnh 3D trên máy thứ nhất sử dụng GnuPlot Máy thứ hai hiển thị phần hình ảnh 3D tiếp theo với x nằm trong khoảng từ 6 đến 10: Hình 4-16. Hình ảnh 3D trên máy thứ hai sử dụng GnuPlot 4. 4. 2 Hiển thị hình ảnh 3D của tệp tin VRML Từ KN của WAVE, WAVE sẽ tạo ra một tệp tin VRML và chương trình sẽ hiển thị tệp tin VRML này dưới dạng 3D: - 82 - Hình 4-17. Tệp tin VRML được hiển thị sau khi được tạo bởi KN 4. 4. 3 Hiển thị hình ảnh 3D với các góc nhìn khác nhau Các vật thể được mô tả trong tệp tin VRML được mô tả giống như các vật thể trong tệp tin VRML được hiển thị trong Hình 4-17. Tệp tin VRML được hiển thị sau khi được tạo bởi KN, sau khi thay đổi Transform, nó lại được hiển thị theo một cách khác: - 83 - Hình 4-18. Các đối tượng hiển thị theo cách khác thi thay đổi Transform Hình 4-19. Một cách nhìn khác thi thay đổi Transform 4. 4. 4 Hiển thị hình ảnh 3D VRML trên nhiều máy Các đối tượng khác nhau được đặt trên các máy khác nhau, mỗi một đối tượng được hiển thị trên một máy. Từ một tệp tin VRML được hiển thị như bây giờ Hình - 84 - 4-20. Hiển thị đối tượng đầu tiên trên máy 1, mỗi máy sẽ nhận nhiệm vụ đưa ra từng đối tượng: Trên máy thứ nhất hiển thị đối tượng đầu tiên là hình trụ: Hình 4-20. Hiển thị đối tượng đầu tiên trên máy 1 Máy 2 hiển thị hình nón: - 85 - Hình 4-21. Hiển thị đối tượng thứ hai trên máy 2 - 86 - CHƯƠNG 5. PHỤ LỤC 5. 1 JJTree 5. 1. 1 Giới thiệu JJTree là một bộ tiền xử lý của JavaCC, quá trình biên dịch JJTree kết hợp việc phân tích từ loại xây dựng nên cây hành động tương ứng với những đoạn mã riêng biệt trong JavaCC. Việc thực thi JJTree thông qua JavaCC sẽ tạo ra các từ loại. JJTree phát sinh mã để tạo nên cấu trúc cây cú pháp với nhiều nút, mỗi nút có các lá là các ký hiệu (biến, từ khóa…) trong ngôn ngữ lập trình. JJTree định nghĩa một nút giao diện Java mà tất cả việc phân tích các nút của cây phải được tiến hành. Nút giao diện này cung cấp các phương thức thực thi như việc tạo dựng các nút cha, thêm vào các nút con và việc gọi lại chính nó. JJTree thao tác một trong hai nút, simple và multi. Nút simple, mỗi bộ phân tích cú pháp nút cây cụ thể là một loại SimpleNode. Còn nút mutil, kiểu của bộ phân tích cú pháp nút cây này được lấy từ tên của nút. JavaCC phân tích cú pháp từ trên xuống còn JJTree lại xây dựng bộ phân tích cú pháp từ dưới lên. Để làm điều này JJTree sử dụng một ngăn xếp để đưa vào các nút đã được tạo ra. Khi mà các nút con này tìm thấy các nút cha thì nó lấy các nút con thêm vào các nút cha. Nó tiếp tục lấy các nút cha vừa mới được tạo ra để đưa vào ngăn xếp, nút cha này lại được xem như các nút con và quá trình này lại được tiếp diễn cho tới khi kết thúc. 5. 1. 2 Các kiểu cấu trúc cây - Khai báo với số lượng nút cụ thể void Assignment() #Assignment(2) : {} { Id() "=" Expression() } - Khai báo với số lượng nút con chưa xác định rõ o Có giới hạn void Assignment() #Assignment(>2) : o Không có giới hạn void Assignment()#Assignment - 87 - 5. 2 Thực thi trên ngôn ngữ simpleLang Trong phần trên, chúng tôi đã giới thiệu qua về JavaCC, file cú pháp của JavaCC, các tùy chọn khi biên dịch file cú pháp để tạo ra bộ parser thỏa mãn yêu cầu của người dùng. Trong phần này, dựa vào những khái niệm và tính chất của file cú pháp, ta sẽ tìm hiểu cách tạo ra bộ parser cho ngôn ngữ simpleLang – một ngôn ngữ rất đơn giản định nghĩa toán tử cộng. Thành phần chính dùng để xây dựng lên bộ parser cho ngôn ngữ simpleLang là file cú pháp jjt (jjtree) bao gồm các các từ tố và đặc tả cú pháp của ngôn ngữ simpleLang. Cú pháp định nghĩa ngôn ngữ simpleLang trong JavaCC có dạng như sau : void simpleLang() : {} { addExpr() } void addExpr() : {} { integerLiteral() ( "+" integerLiteral() )? } void integerLiteral() : {} { } SKIP : { " " | "\t" | "\n" | "\r" } TOKEN : { } Ý nghĩa : - Định nghĩa ngôn ngữ simpleLang gồm phép toán duy nhất là toán tử cộng (addExpr()) - Toán tử cộng được định nghĩa bởi 2 hay nhiều integerLiteral cách nhau bới dấu + - Một integerLiteral được định nghĩa là một từ tố là một số nguyên Việc xây dựng bộ parser dựa trên file cú pháp .jj sẽ phải tích hợp rất nhiều đoạn code java vào trong file .jj và không tận dụng được những lợi ích mà Java IDE mang lại trong quá trình phát triển chương trình. Như đã nói ở trên, file jjtree được tạo ra làm bộ tiền xử lý cho quá trình tạo ra file .jj, jjtree sẽ định nghĩa được các hành động, thuộc tính trên từng node của cây cú pháp, do vậy sẽ có khả năng tùy biến cao hơn cho quá trình lập trình(thiết lập, thay đổi giá trị, sự kiện… tại mỗi node). Cú pháp của file jjtree tương ứng với cú pháp của file .jj như sau : SimpleNode simpleLang() : #Root {} { addExpr() { return jjtThis; }} void addExpr() : {} { integerLiteral() ( "+" integerLiteral() #Add(2) )? } void integerLiteral() : #IntLiteral {} { } SKIP : { " " | "\t" | "\n" | "\r" } TOKEN : { } - 88 - Ý nghĩa : Tương tự như file .jj ở phần trên ta đã xem xét, file jjtree định nghĩa cú pháp và từ tố theo cùng cách thức, điểm khác biệt đó là jjtree tạo ra các class java (các AST) tại từng node của cây cú pháp. Trong ngôn ngữ simpleLang có 3 AST được tạo ra (sau dấu #) là : ASTRoot, ASTAdd và ASTIntLiteral thừa kế từ lớp SimpleNode – mang những thuộc tính chung nhất của một node trong cây cú pháp. Ví dụ 1: Cây cú pháp cho 1 biểu thức đơn Ví dụ 2: Cây cú pháp với phép toán cộng Làm việc với cây cú pháp Phần trên ta đã tạo được ra cây cú pháp, việc sử dụng cây cú pháp như thế nào tùy thuộc vào mục đích của người lập trình. Mỗi node trong cây cú pháp được gọi là một SimpleNode bao gồm một số thuộc tính và phương thức như : node cha, danh sách các node con, giá trị tại node, duyệt cây từ node hiện thời đổ xuống… SimpleParser parser = new SimpleParser(new StringReader( expression )); SimpleNode rootNode = parser.simpleLang(); rootNode.dump(); sẽ cho kết quả: Root Add IntLiteral IntLiteral Một phương thức quan trọng trong SimpleNode đó là lấy ra giá trị của các node con của một node, câu lệnh như sau: SimpleNode lhs = addNode.jjtGetChild( 0 ); - 89 - SimpleNode rhs = addNode.jjtGetChild( 1 ); sẽ lấy ra 2 node con của node addNode. Thiết lập và lấy giá trị tại node Quá trình phân tích cú pháp ở trên chưa cho phép lấy ra giá trị IntLiteral tại các node mang giá trị là số nguyên. Để làm được điều này ta cần thêm các phương thức set và get để thiết lập và lấy giá trị tại node: public class SimpleNode extends Node { String m_text; public void setText( String text ) { m_text = text; } public String getText() { return m_text; } ... } Và trong file jjt ta cần sửa mã: void integerLiteral() : #IntLiteral {} } thành: void integerLiteral() : #IntLiteral { Token t; } { t= { jjtThis.setText( t.image );} } Khi đó cây cú pháp của phép toán 42+1 sẽ có dạng như sau: Root Add IntLiteral[42] IntLiteral[1] 5. 3 Xây dựng bộ parser cho ngôn ngữ Wave Wave cũng giống như các ngôn ngữ khác, cũng bao gồm các đặc tả về Token, đặc tả cú pháp của ngôn ngữ. Dựa vào những phần trình bày bên trên, công việc chính cần làm đó là tạo ra file đặc tả cú pháp (jjt) của Wave. Một phần file jjt của Wave: options { STATIC = false; - 90 - MULTI = true; VISITOR = true; } PARSER_BEGIN(WAVEParser) package ast; public class WAVEParser { public static void main(String args[]) { System.err.println("Reading a \"WAVEProgram\" from standard input..."); WAVEParser p = new WAVEParser(System.in); try { SimpleNode wave = p.Wave(); wave.dump(" "); System.err.println("Thank you."); } catch (Exception e) { System.out.println("Oops."); System.out.println(e.getMessage()); e.printStackTrace(); } } final public String WaveTail() { return m_waveTail; } private String m_waveTail; } PARSER_END(WAVEParser) TOKEN: { )+> | <STRING: "`" (~["`","\n","\r"])*"'" | (["a"-"z","_"] ( | )*)> | | | } Ví dụ quá trình parse chuỗi Wave “Fa=1.Fa+1.T=Fa “ sẽ cho kết quả như sau: - 91 - WAVEProgram : Fa=1.Fa+1.T=Fa Zone : Fa=1 Sector : Fa=1 Assign : Fa=1 FrontalVar : Fa IntConst : 1 Zone : Fa+1 Sector : Fa+1 Sum : Fa+1 FrontalVar : Fa IntConst : 1 Zone : T=Fa Sector : T=Fa TerminalOutput : T=Fa FrontalVar : Fa - 92 - CHƯƠNG 6. TÀI LIỆU THAM KHẢO TÀI LIỆU TIẾNG ANH [1] Peter Sapaty, Mobile processing in Distributed and Open environments, 1998 [2] Bell, G., A. Parisi, and M. Pesce, The Virtual Reality Modelling Language: Version 1.0 Specification, November 9, 1995. [3] Bruno, J., and S. M. Altman, “A Theory of Asychronous Control Networks,” IEEE Trans. Comput., Vol. C-20, No. 6, June 1971. [4] Sapaty, P. S,. “Active Information Field as a Model for the Structural Solution of Task on Graphs and Networds,” Proc. USSR Academy of Sciences: Technical Cybernetics, No. 5, 1984 (in Russian). [5] Varbanov, S., and P. S. Sapaty, “An Information System Based on the Wave Navigation Techniques,” Abstr. International Conference, AIMSA’86, Varna, Bulgaria, 1986. [6] Sapaty, P.S., “The Wave-0 Language as a Framework of Navigational Structures for Knowledge Bases Using Semantic Networks,” Proc. USSR Academy of Sciences: Technical Cybernetics, No. 5, 1986 (in Russian). [7] Borst, P., The First Implementation of the WAVE System for UNIX and TCP/IP Computer Networks, TR 18/92, Faculty of Informatics, University of Karlsrule. Karlsruhe, Germany, December 1992. [8] Borst, P.M., H.-T Goetz, P. S. Sapaty, and W. Xorn, “Paralled Knowledge Processing in Open Networks,” Proc. International Conference and Exhibition “Hight- Perfor-mance Computing in Networks” (HPCN Europe ‘94), Munich, Germany, April 1994. [9] Corbin M. J., and P. S. Sapaty, “Distributed Object-Based Simulation in Wave,” J. Simul. Pract. Theory, Vol. 3, No.3, pp. 157-181, 1995. [10] Merchant F., L. F. Bic, P. M. Borst, M. J. Corbin, M. Dillencourt, M. Fukuda, and P. S. Sapaty, “Simulating Autonomous Objects in a S patial Database Using WAVE,” Proc. 9th European Simulation Multiconference, Prague, Czechoslovakia, June 1995. [11] Livatharas, C., “Integration of Heterogeneous Databases Using WAVE,” M.Sc. Project Report, Department of Electrical Engineering, University of Surrey. Surrey, England, August 1995. [12] Vuong, S., and I. Ivanov, “Mobile Intelligent Agent Systems: WAVE vs. JAVA,” Proc, etaCOM’96, Portland, Oreg., May 1996. [13] Vuong, S., and L. Mathy, “Simulating the Mobile-IP Protocol Using Wave,” Proc, etaCOM’96, Porland, Oreg., May 1996. [14] Darling, J. C. C., P.S Sapaty, and M. J. Underhill, “Distributed Virtual Reality: A Fully Dynamic Approach,” Proc. 15th Workshop on Standards for the - 93 - Interoperability of Distributed Simulations, Institute for Simulation and Training, University of Central Florida, Orlando, Fla., September 1995. [15] Tan, H. K. V,. “Distributed Dynamic 3D Virtual Reality,” M.Sc Telematics Diploma Project (base on WAVE), Department of Electrical Engineering, University of Surrey, Surrey, England, 1997. WEBSITE THAM KHẢO [16] [17] https://javacc.dev.java.net/ [18] [19] [20] [21] [22]