Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và Automata

sau thuộc vế trái của tập luật sinh Danh sách vế trái (tương ứng thứ tự với vế phải) // ký hiệu để nhận dạng dữ liệu theo sau thuộc vế phải của tập luật sinh Danh sách vế phải (tương ứng thứ tự với vế trái) Do đó có thể soạn thảo tập văn phạm G bằng một trình soạn thảo văn bảng bất kỳ là lưu ở dạng .txt, chương trình cũng sẽ lưu tập văn phạm với định dạng trên khi bạn bấm nút lưu. IV - TỔ CHỨC CẤU TRÚC DỮ LIỆU 1) Cấu Trúc Dữ Liệu Cho Văn Phạm G=(V,T,S,P) a) Lưu tập V : Là một mãng ký tự là chữ in hoa 012345678... Lưu tập T : Là một mãng ký tự là chữ thường. 01234567... c) Lưu biến khỡi đầu S : Sử dụng một char để lưu S d) Lưu tập các luật sinh P : Sử dụng một mãng chuỗi ký tự cho vế phải và một mãng cho vế trái Vế Trái Vế Phải0011223344...... 2- Cấu Trúc Dữ Liệu Cho Giải Thuật CYK a) Sơ đồ cấu trúc dữ liệu ji 1234...n1stringstringstringstringstringstringstringstringstring2...3...nstring b) Hiện Thực : Bảng phân tích cú pháp T là một mãng hai chiều, ở đây giới hạn chiều dài tối đa của chuỗi nhập (số token) là MAX ký tự do đó, mãng T được khai báo như sau trong Visual C++: CString T [MAX][MAX]; Một số tác vụ khi thực hiện giải thuật CYK : + Hội hai tập hợp trả về tập hợp kết quả CString Hoi(CString B, CString C) { int i; CString Temp; Temp=""; for(i=0;iai int Pa(CString A, CString a) { int soluat; int i; soluat=ArrayVeTrai.GetSize(); for(i=0;ip)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } +Trả về ký tự sau dấu chấm char ChrAfterDot(items *pt) { int sl,ch; CString Vp; sl=(pt->p); ch=(pt->i); Vp=ArrayVePhai[sl]; if (ch  p=0 Cho A vào trong Vn p > Tổng LS Đ S S p=p+1 Luật sinh thứ p có dạng A --> A1A2…An mà A1A2…An  Vn p=0 Cho A vào trong Vn Đ Đ S S p=p+1 p > Tổng LS Luật sinh thứ p có dạng A --> x1x2…xm với m1và xi  (VT) p=0 Cho vào P^ các tổ hợp có thể có bằng cách thay thế các biến  Vn bằng  Đ Đ S S p=p+1 p > Tổng LS END p=0 1- Loại Bỏ Các Luật Sinh  2- Loại Bỏ Các Luật Sinh Đơn Vị START Luật sinh thứ p có dạng A --> B p=0 Cho luật sinh thứ p vào trong P^ p > Tổng LS S Đ S Đ p=p+1 Cho luật sinh thứ p vào trong P* Tạo đồ thị phụ thuộc cho P* - Aùp dụng việc thay thế bằng cách : lấy vế phải của luật sinh không đơn vị có vế trái là vế phải của luật sinh đơn vị thay vào vế phải của luật sinh đơn vị tương ứng - Cho các luật sinh thay thế vào P^ END START V1= { } Thêm A vào V1 Luật sinh p có dạng A x1x2… xn với xi  T*  V1 V1 chứa A rồi Đ Đ S Đ S S p=p+1 p=0 p> Tổng LS Cho vào trong P1 các luật sinh trong P mà có VP  (V1 T*) Loại bỏ các luật sinh vô dụng loại 1 p1> Tổng LSP1 If VT=”Biến khỡi Đầu” then For (I=0; I=2 Cho tất cả các luật sinh có dạng A a vào trong P^ Đ S Thay các ký hiệu kết thúc (ví dụ là a) ở vế phải bằng vế trái sinh ra nó (có trong tập P^) nếu không có thì sinh ra ký tự đại diện Ba,và đặt Ba a vào trong P^ p=p+1 p=p+1 Sau bước trên ta có được luật sinh : A C1C2…Cn, ta tiến hành chia nhỏ luật sinh này thành các luật sinh có chiều dài bằng 2 như sau : str=VP; n=Len(str) Repeat if (n=2) then cho luật sinh A vào P^ else STP=str[0]+Dk Cho A STP vào trong P^ str=Right(Len-1); n=n-1; k++; Until (n=2) p> Tổng LS END 4- Process Dạng Chuẩn Chomsky S Đ 5- Process Dạng Chuẩn Greibach START Loại bỏ các luật sinh  Loại bỏ các luật sinh đơn vị Loại bỏ các luật sinh vô dụng G=(V,T,S,P) Đánh số thứ tự các biến trong V từ 1 đến n TEMP=P (tập luật sinh) Tất cả các luật sinh trong P có có ở tất cả các dạng sau: Ai  Ajxj ,j >I Zi  Ajxj , jn Ai  axi i Tổng LS p=0 Luật sinh thứ p có vế trái là Zi và ký hiệu đầu tiên của vế phải thuộc (A1, … An) Thay thế kí hiệu của vế phải luật sinh thứ p bằng vế trái của ký hiệu tương ứng Đ S S Đ p=p+1 Thay thế các ký hiệu kết thúc nằm trên vế phải của các luật sinh trong P mà không ở vị trí đầu tiên bằng các ký hiệu đại điện Bi END 6- Lưu Đồ Giài Thuật Phân Tích Cú Pháp Earley START i=0 i > Tổng Luật Sinh i0=i0+1 i=i+1 Luật sinh thứ i có dạng S -->  Cho [S--> ., 0] vào trong I0 Đ S S S S S Đ Đ Đ Đ Bước 1 Bước 2&3 Luật sinh thứ i0 trong I0 có dạng [B -->., 0] i0 =0 Luật sinh thứ i0 trong I0 có dạng [A -->.B,0] I0 > TổngLS trong I0 Cho vào I0 trạng thái [B-->.,0] của các luật sinh trong P có dạng B--> - Tính lại TổngLS Cho vào I0 trạng thái [A--> B.,0] của các trạng thái trong I0 có dạng [A--> B.,0] -Tính lại TổngLS A x=x+1 Đ S S Đ Đ Đ S S A Luật sinh thứ x trong Ij-1 có dạng [B -->.a, I] với (a=aj) x=0 j=1 Cho [B -->.a, i] vào trong Ij x > TổngLS trong Ij-1 y=0 Luật sinh thứ y trong Ij có dạng [A -->. , i] Tìm trong P các luật sinh có dạng : [B --> thì cho vào Ij tập : [B --> ., k] - Cập nhật lại LSJ Tìm trong tập Ii các thực thể có dạng : [B -->.A, k] thì cho vào Ij tập : [B -->A ., k] - Cập nhật lại LSJ Luật sinh thứ y trong Ij có dạng [A -->.B , i] S S Đ Đ END j>n (n chiều dài chuỗi y>LSJ j=j+1 Bước 5&6 Bước 4 y =y+1 7- Lưu đồ Giải thuật phân tích cú pháp CYK Bước 2 START i=1,p=0 luật sinh thứ p có dạng A--> ai Cho A vào trong ti1 i=i+1,p=0 p=p+1 p> số luật sinh Đ Đ S S S Đ i>= chiều dài chuỗi Bước 1 i=1, j=2,p=0 p=p+1 k=k+1 Đ S p> số luật sinh Đ Đ S S luật sinh thứ p có dạng A--> BC mà B tik và C  ti+k,j-k tij= tij  {A} k>=j k=1 A B A (1  i  n ) AND (1 j  n-i+1) i=i+1 B Đ Đ S S j> n (chiều dài chuỗi) i=1 j=j+1 END VI - THIẾT KẾ MỘT SỐ FROM NHẬP - XUẤT QUANG TRỌNG Dựa vào các form được thiết kế ở phần này, lập trình viên thiết kế các phần giao diện cho bộ công cụ. Xóa Luật Nhập Luật Biến Khởi Đầu: -----> Băng nhập Tập luật sinh Tập Kh Không Kết Thúc Thêm Xóa Tập Kh Kết Thúc Xóa Thêm Bỏ Qua Đồng Ý Mở File Lưu File a ) Form Nhập VP PNC Form này được thiết kế để tạo giao diện khi nhập văn phạm phi ngữ cảnh, trong Form cho phép, nhập, lưu hay mở văn từ file, có thể bỏ qua hay chấp nhận văn phạm vừa nhập. b) Form Loại Bỏ Các Luật Sinh Rỗng, Đơn Vị, Vô Dụng Loại bỏ luật sinh rỗng Loại bỏ luật sinh đv Loại bỏ luật sinh Vd Loại bỏ hết các luật Đóng Minh họa giả thuật Tập luật sinh kết quả Tập luật sinh ban đầu Sử dụng form này khi thực hiện viết các giải thuật loại bỏ các luật sinh rỗng, đơn vị, vô dụng. Khi bấm một nút thì giải thuật tương ứng sẽ thực hiện. c) Form Chuyển Văn Phạm Về Dạng Chuẩn Chomsky Chomsky >>> Xem VP Chomsky Xem VP Đầu Giúp Đỡ Đóng Minh họa giả thuật Tập luật sinh dạng chuẩn Chomsky Tập luật sinh ban đầu Form này dành cho thực hiện giải thuật Chomsky, Form thực hiện giải thuật Greibach tương tự . Biến Khởi Đầu G=(V,T,{S},P) Đóng Tập Luật Sinh Tập biến Tập ký hiệu kết thúc d) Form Dùng Để Hiển Thị Văn Phạm Gốc Form này dùng để hiển thị văn phạm gốc khi người sử dụng có yêu cầu xem, văn phạm gốc hiển thị đầy đủ : Biến khỡi đầu : S Tập các ký hiệu kết thúc : T Tập các ký hiệu không kết thúc : V Tập các luật sinh : P e) Form Thực Hiện Giải Thuật CYK Câu Nhập : Hiển Thị Bảng phân Tích T Văn Phạm dạng Chomsky Chuỗi Dẫn Xuất Xem văn phạm gốc Giúp đỡ Phân tích câu nhập Dữ liệu minh họa cho giải thuật bao gồm : Bảng phân tích T Chuỗi dẫn xuất ra câu nhập Tập văn phạm ở dạng chuẩn Chomsky Khi nhập liệu xong, người sử dụng bấm nút “Phân Tích Câu Nhập” thì giải thuật CYK sẽ hiện thực. Câu Nhập : Tập luật sinh P Các trạng thái Si Chuỗi Dẫn Xuất Xem văn phạm gốc Giúp đỡ Phân tích câu nhập f) Form Thực Hiện Giải Thuật Earley Dữ liệu minh họa cho giải thuật bao gồm : Các trạng thái Si Chuỗi dẫn xuất ra câu nhập Tập văn phạm P (tổng quát) Khi nhập liệu xong, người sử dụng bấm nút “Phân Tích Câu Nhập” thì giải thuật Earley sẽ hiện thực VI - THIẾT KẾ HỆ THỐNG MENU Hệ thống Menu của chương trình được thiết kế theo dạng pushdown (trình đơn đẩy xuống). 1) Cấu trúc của hệ thống Menu : Bắt ĐầuCông CụNgôn Ngữ Tự Nhiên Giúp Đỡ Giúp ĐỡThông Tin Về Chương Trình Nhận Dạng …Biên Soạn Văn Phạm..Biên Soạn Từ Điển… Loạt bỏ các luật sinh … Alt+BCác Dạng Chuẩn … Alt+DCác Giải Thuật Phân Tích Cú Pháp Tạo mới văn phạmĐóng văn phạm hiện hànhMở văn phạmThoát Dạng Chuẩn ChomskyDạng Chuẩn Greibach Giải Thuật CYK … Alt+KGiải Thuật Earley… Alt+ESo Sánh Độ Phức Tạp 2) Hoạt động của từng Menu Item Bắt Đầu : Bắt Đầu | Tạo Mới Văn Phạm : Khích hoạt process “Nhập Văn Phạm” cho phép người sử dụng định nghĩa tập văn phạm mà mình sẽ làm việc trên nó. Bắt Đầu | Đóng văn phạm hiện hành : Tập văn phạm hiện hành đang làm việc sẽ xóa khỏi vùng nhớ cấp phát cho nó, khi muốn làm việc lại phải thực hiện Tạo Mới Văn Phạm Bắt Đầu | Mở Văn Phạm : Mở văn phạm làm việc được lưu từ file. Công Cụ : Công Cụ | Loại Bỏ Các Luật Sinh : Kích hoạt Dialog “Loại Bỏ Luật Sinh” trong Dialog này thực hiện các process sau : + Loại bỏ các luật sinh  + Loại bỏ các luật sinh đơn vị + Loại bỏ các luật sinh vô dụng Công Cụ | Các Dạng Chuẩn | Dạng Chuẩn Chomsky : Kích hoạt process “Dạng Chuẩn Chomsky” Công Cụ | Các Dạng Chuẩn | Dạng Chuẩn Greibach : Kích hoạt process “Dạng Chuẩn Greibach” Công Cụ | Các Giải Thuật Phân Tích Cú Pháp | Giải Thuật CYK : Kích hoạt process “Giải thuật CYK” Công Cụ | Các Giải Thuật Phân Tích Cú Pháp | Giải Thuật Earley : Kích hoạt process “Giải thuật Earley” Công Cụ | Các Giải Thuật Phân Tích Cú Pháp | So Sánh Độ Phức Tạp : Thực hiện so sánh độ phức tạp của hai giải thuật : “Giải thuật Earley” & “Giải thuật CYK”. Ngôn Ngữ Tự Nhiên Ngôn Ngữ Tự Nhiên | Nhận Dạng : Phần áp dụng giải thuật Earley để nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh). Ngôn Ngữ Tự Nhiên | Biên Soạn Văn Phạm : Công cụ dùng để biên soạn tập văn phạm của ngôn ngữ tự nhiện (là một công cụ của bộ nhận dạng) Ngôn Ngữ Tự Nhiên | Nhận Dạng : Công cụ dùng để biên soạn bô từ điển token của các từ trong Tiếng Anh. (là một công cụ của bộ nhận dạng) Giúp Đỡ Giúp Đỡ | Giúp Đỡ : Hích hoạt hệ thống Help Contents Giúp Đỡ | Thông Tin Về Chương Trình : Kích hoạt màn hình giới thiệu thông tin về chương trình ? ABC Gram. AX AX. E CYK Pgre  Pch  Big O Nhập văn phạm Giúp Đỡ Nhận dạng Biên Soạn Văn Phạm Biên Soạn Từ Điển So Sánh Độ Phức tạp Giải Thuật Earley Giải Thuật CYK Xóa văn Phạm Loại bỏ các luật sinh Dạng Chuẩn Chomsky Dạng Chuẩn Greibach VII - THIẾT KẾ HỆ THỐNG TOOLBAR Tất cả các chức năng hoạt động của thanh toolbar tương tự như hoạt động của các Menu Items tương ứng như mô tả ở phần VI PHẦN 5 SO SÁNH ĐỘ PHỨC TẠP CỦA HAI GIẢI THUẬT CYK VÀ EARLEY GIỚI THIỆU Qua phần phân tích và thiết kế, để việc thiết kế các process phù hợp với các giải thuật đã trình bày trong phần lý thuyết nên việc tính toán độ phức tạp của CYK và Earley không được lồng vào trong các process này. Do đó trong phần này chỉ dành riêng cho việc trình bày cách hiện thực để tính toán độ phức tạp của hai giải thuật trên. Trong phần này giúp cho sinh viên thấy được một cách trực quan (bằng hình ảnh) độ phức tạp của hai giải thuật trên các loại văn phạm khác nhau cũng như cách thức hiện thực tính toán độ phức tạp từ đó tự rút ra kết luận cho hai giải thuật này. HIỆN THỰC TÍNH ĐỘ PHỨC TẠP Để hiện thực tính độ phức tạp của hai giải thuật chúng ta chấp nhận các giả thiết sau : Mỗi một lần tham khảo một luật sinh là một bước tính toán Tất cả các phép toán khác như +,-.*,/ gán … được bỏ qua Không tính đến quá trình chuyển văn phạm sang dạng chuẩn Chomsky cho giải thuật CYK. Do đó độ phức tạp của hai giải thuật CYK và Earley chỉ phụ thuộc vào số lần tham khảo các luật sinh. Ý tưởng để tính toán độ phức tạp ta sử dụng một biến toàn cục DPT để đếm số lần tham khảo đến các luật sinh hay từng phần tử trong tập trạng thái (đối với Earley) hay bảng T(đối với CYK).  Trong code chương trình chỗ nào tham khảo đến những phần tử trên đều tăng biến DPT lên 1. III- SO SÁNH THỰC NGHIỆM Sau đây là một chương trình trong bộ công cụ được viết để so sánh độ phức tạp của hai giải thuật CYK và Earley trên các loại văn phạm khác nhau : Chương trình cho phép người sử dụng so sánh độ phức tạp của hai giải thuật CYK và Earley sau khi đã nhập tập văn phạm cho bộ công cụ. Chuỗi cần so sánh được đánh vào ô “Câu Nhập”. SAU ĐÂY LÀ CÁC KẾT QUẢ VÀ ĐỒ THỊ MINH HỌA : VĂN PHẠM G1 (Văn phạm biểu thức số hoc) E T+E E T T F*T T F F (E) F aCâu nhậpLengthCYKEarleya+a3174115a+a+a+a71014237a+a+a+a+a+a112766391a+a+a+a+a+a+a+a155734577a+a+a+a+a+a+a+a+a+a1910222795a+a+a+a+a+a+a+a+a+a+a+a23165341045a+a+a+a+a+a+a+a+a+a+a+a+a+a27249741327 Hình 1: Đường cong độ phức tạp theo văn phạm G1 VĂN PHẠM G2 (Có luật sinh đơn vị và vô dụng) S aS | A | C A a B aa C aCbCâu NhậpLengthCYKEarleyaa21495(aa)2479208(aa)36216377(aa)48449610(aa)510802915(aa)61212991300(aa)71419641773(aa)81628212342(aa)91838943015 Hình 2: Đường cong độ phức tạp theo văn phạm G2 VĂN PHẠM G3 (Văn Phạm GRE của Jay Earley) X a | Xb | Ya Y e | YdYCâu NhậpLengthCYKEarleyededea622297ededeab410658125ededeab10161312167(ed)4eabb121074200(ed)7eabb182880426(ed)8eabb203782530 Hình 3: Đường cong độ phức tạp theo văn phạm G3 IV- KẾT LUẬN Qua chương trình tự viết cho bộ công cụ bằng các giải thuật đã trình bày trong phần lý thuyết và các giả thiết để tính toán độ phức tạp như đã nêu ở phần II (với cách đặt giả thiết khác nhau thì độ phức tạp của giải thuật tính ra sẽ khác nhau) cùng với các dữ liệu thực tế nhập vào cho từng loại văn phạm, tôi có một vài nhập xét sau : Với văn phạm G1 và G2 giải thuật Earley luôn luôn có độ phức tạp lớn hơn Với tập văn phạm G2 là loại văn phạm vừa có luật sinh đơn vị và luật sinh vô dụng, do đó khi loại bỏ 2 loại luật sinh trên thì tập văn phạm thực tế mà CYK thao tác chỉ còn là {S DS,Da, Sa} trong khi đó Earley phải thao tác trên văn phạm gốc ban đầu. Cho nên khi chiều dài chuỗi nhập nhỏ thì CYK có độ phức tạp lớn hơn, tuy nhiên khi chiều dài chuỗi nhập tăng lên thì Earley lại có độ phức tạp nhỏ hơn rất nhiều do lúc này số lương phần tử trong bảng T sinh ra rất lớn. Về mặt lý thuyết giải thuật CYK và Earley có độ phức tạp thời gian là O(n3), tuy nhiên với Earley thì O(n3) chỉ là cận trên trong khi CYK luôn luôn là O(n3). PHẦN 6 NHẬN DẠNG NGÔN NGỮ TỰ NHIÊN I- GIỚI THIỆU Đây là phần áp dụng các giải thuật phân tích cú pháp để nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh). Qua phần nhận xét và đánh giá hai giải thuật phân tích cú pháp Earley và CYK, chúng ta nhận thấy giải thuật CYK không thích hợp cho việc nhận dạng ngôn ngữ tự nhiên với các lý do sau : + Phải chuyển văn phạm NNTN về dạng chuẩn Chomsky + Số bước thực hiện của gt CYK lớn hơn rất nhiều so với giải thuật Earley (xem phần hiện thực so sánh độphức tạp của hai giải thuật này để thấy rõ hơn). Do đó trong phần áp dụng nhận dạng ngôn ngữ tự nhiên sẽ sử dụng giải thuật Earley để thực hiện. Trong phần này thực hiện nhiệm vụ : Phân tích câu nhập và in ra chuỗi dẫn xuất nếu câu nhập thuộc ngôn ngữ đã cho. Sơ đồ DFD khi nhận dạng câu nhập : User Nhập VP NNTN Văn phạm NNTN Văn phạm Phân tích token Nhận dạngNNTN Câu nhập tiếng Anh Chuỗi token của câu nhập Chuỗi dẫn xuất Từ Điển Token Tạo từ điển Từ Quá trình nhận dạng một câu nhập có thể mô tả như sau : Chuỗi nhập là một câu tiếng Anh sẽ được đưa qua bộ “phân tích token”, đâu ra sẽ là một chuỗi các token của câu nhập. Chuỗi token này sẽ được bộ “nhận dạng NNTN” phân tích theo giải thuật Earley dựa vào tập văn phạm NNTN định nghĩa trước. Bộ “nhận dạng NNTN” sẽ in ra quá trình dẫn xuất ra câu nhập nếu nó thuộc văn phạm đã cho. Bộ nhận dạng chỉ nhận dạng được những từ có trong từ điển, nếu không có sẽ báo lỗi. Nếu chúng ta tạo ra được bộ từ điển càng nhiều từ thì bộ nhận dạng sẽ nhận dạng được nhiều câu nhập hơn. Ví dụ : Cây dẫn xuâ`t i see a book on the table. Nhận dạng NNTN Phân Tích Token Các token XÂY DỰNG TỪ ĐIỂN CÁC TOKEN Để phục vụ cho việc nhận dạng câu nhập, ta cần phải xây dựng một bộ từ điển cho ngôn ngữ đó. Để tạo ra được bộ từ điển này cần có một sự góp ý và trợ giúp rất nhiều của các chuyên gia về ngôn ngữ học, biên soạn từ điển. Thực chất của bộ từ điển token là phân các từ ra thành nhiều nhóm, sẽ nhóm được đại diện bằng một token. Trong luận văn này, tôi xin trình bày một cách biên soạn bộ từ điển token như sau : Bộ từ điển được chia làm 4 trường TokenlexmeLoại từ Nghĩa Tiếng ViệtChứa loại từ Chứa lemex của token Chứa giá trị là token  Các từ trong tiếng Anh chia ra thành các nhóm như sau : TokenLoại từn p v t s o d a j b Noun Prepositional Intransitive verb Transitive verb Pronoun_subject Pronoun_Object Determiners Article Adj. Tobe ví dụ : TokenLexmeLoại từNghĩa ViệtnbookNounquyển sáchnpenNountờ báoptoPrepositionaltớipwithPrepositionalvớivgoIntransitive verbđivrunIntransitive verbchạytlikeTransitive verbthíchtseeTransitive verbthấysIPronoun_StôishePronoun_Sanh taomePronoun_OtôioherPronoun_Ocô ấyaanArticlemộtaaArticlemộtatheArticledthatDeterminerskiadthisDeterminersnàyjbeautifulAdjđẹp…………Xin xem thêm phần kết quả hiện thực bộ từ điển ở phần 8. III- VĂN PHẠN NGÔN NGỮ TỰ NHIÊN Sau đây là văn phạm có thể xử lý ngôn ngữ tự nhiên. Khi thực hiện giải thuật Earley cho văn phạm này thì câu nhập là câu tiếng Anh. (0) (1)(2)s(3)(4)(5) (6) (7) (8) (9) (10)b(11)(12)n(13) (14)j(15) (16)d(17) (18)  (19)a(20) (21)r(22) (23) (24)p(25) (26)o(27)(28)(29) (30)t(31)(32)v Ví dụ : Để thấy rõ hơn các kết quả từ việc biên soạn từ điển token đến nhận dạng xin xem phần 7 “Minh họa kết quả” phần “Nhận dạng ngôn ngữ tự nhiên”. PHẦN 7 TÌM HIỂU WINDOWS HELP VÀ PHẦN MỀM XÂY DỰNG HỆ THỐNG HELP WINDOWS HELP DESIGNER PRO I- GIỚI THIỆU Một tiêu chuẩn chất lượng của một chương trình chuyên nghiệp là phạm vi và mức độ hoàn chỉnh của hệ thống Help của nó. Trong chương này, chúng ta tìm hiểu các vấn đề sau :  Các khái niệm liên quan đến việc xây dựng hệ thống Help  Các bước cần thiết để xây dựng hệ thống Help chuyên nghiệp  Công cụ Windows Help Desginer Pro để xây dựng hệ thồng Help II- TÌM HIỂU WINDOWS HELP 1- Các Khái Niệm  Topic : Đơn vị thông tin của hệ thống Help, được viết cho một chủ đề. Chủ đề bao gồm chuỗi văn bản xuất hiện trong hệ thống Help, Chủ đề được liên kết với pop_up (hộp bật lên), hot spots (vùng tác động) và các lệnh nhảy theo chuỗi ngữ cảnh kết hợp với chủ đề.  Pop_up : Văn bản của chủ đề tham chiếu được xuất hiện đúng lúc trong hệ thống Help và có hình chữ nhật bao quanh. Pop_up sẽ mất đi khi người sử dụng bấm chuột ra phía ngoài khung.  Context String : (chuỗi ngữ cảnh). Chuỗi tham chiếu đến chủ đề và được dùng giống như tên biến tượng trưng trong hệ thống Help. Mọi tham chiếu đến chủ đề được hình thành thông qua chuỗi ngữ cảnh.  Hot spot : Vùng ảnh hưởng của chuột trong văn bản hay ảnh có liên kết với chuỗi ngữ cảnh hay sự thực hiện của marco. Việc nhấp chuột vào hot spot sẽ làm nhảy đến chủ đề có chuỗi ngữ cảnh tham chiếu đến, người sử dụng nhận biết được hot spot khi thấy con chuột đổi từ hình mũi tên sang dạng bàn tay.  Marco : Là khả năng sẵn có của Windows Help nhằm thực hiện một số tác vụ trợ giúp. Các marco có thể được gọi vào lúc mở tập tin help, nảy đến một chủ đề, hay chọn hot spot, nút trợ giúp help, menu. Hệ thống Help có sẵn 52 marco chuẩn.  Jump : Là chuyển đến một chủ đề khác theo ý muốn của người dùng  Tập tin RTF : Đây là các tập tin Rich Text Format có thể được soạn thảo nhờ chương trình soạn văn bản có hỗ trợ file RTF. Microsoft Word for Windows có thể tạo ra file RTF. Tập tin RTF chứa văn bản nguồn để tạo ra hệ thống Help, thông qua trình biên dịch để chuyển thành tập tin .HLP  Tập Tin HPJ : (Help Project) - Đây là tập tin chủ đề chứa các lệnh liên quan đến tập tin .RTF nhằm chuyển đến trình biên dịch Help các quan hệ của chuỗi ngữ cảnh, ảnh bipmap, các tùy chọn cấu hình nhằm điều khiển Help Compiler. Tập tin .HPJ dạng mã ASCII thông thường.  Help ContextID : Số nguyên kết hợp với chuỗi ngữ cảnh được liệt kê trong phần [MAP] của tập tin .HPJ. Các số nguyên này sẽ được dùng như giá trị của thuộc tính Help ContextID của control hay biểu mẫu. Help File HELPFILE.HLP (File thực thi) Bitmap File(s) *.BMP Graphics Help Project File HELPFILE.HPJ SHED File(s) *.SHG Graphics và Hot spot Topics File(s) *.RTF Save dưới dạng file Rich Text Format Help Compiler HCRTF.EXE Hình 1 : Các thành phần của hệ thống help 2- Các Thành Phần Trong File Help Project Phần Mục đích và mô tả[OPTION]Xác định các tùy chọn để điều khiển quá trình biên dịch[FILES]Liệt kê tất cả các file tiêu đề văn bản RTF chứa trong chương trình đã được dịch, phần này là bắt buộc.[BUILDTAGS]Xác định các build để sử dụng trong chương trình dịch. Phần này là tùy chọn [CONFIG]Tạo ra các menu của tác giả và các nút bấm trong file help[BITMAP]Chỉ định các file bitmap chứa trong chương trình được dịch. Phần này không bắt buộc phải có nếu file help project đã liệt kê danh sách các đường dẫn cho các file bitmap trong phần [OPTION] bằng cách sử dụng tùy chọn BMROOT.[MAP]Phần này tổ chức các chuỗi nội dung với các số nguên HelpContextID. Phần này là tùy chọn[ALIAS]Gán một hay nhiều chuỗi nội dung đến tiêu đề Help mẫu, phần này là tùy chọn.[WINDOWS]Định nghĩa các tính chất của cửa sổ Help cùng với kiểu và các tính chất của mọi cửa sổ thứ hai có thể được sử dụng trong hệ thống Help. Phần này là bắt buộc nếu bạn có sử dụng cửa sổ thứ 2 Các thành phần của tham số Option trong file .HPJ : + BMRoot : Chỉ thư mục chứa các file hình ảnh được sử dụng trong file .rtf + CharSet : Chỉ định tập hợp các ký tự default + Compress : Chỉ định cách thức nén của file help. + Content : Chỉ định Topic ID + CNT : Chỉ định file content của file help. + Copyright : Dùng để thêm thông tin về version và tác giả của file help. + BDCS : Dùng chỉ định Topic ID sử dụng mã 1 byte hay 2 byte. + HLP : Chỉ định tên của file help 3- Các Bước Cần Thiết Để Xây Dựng Hệ Thống Help  Xác định rõ đối tượng sử dụng Help, chỉ rõ trình độ, kỹ năng và định hướng tác vụ của người dùng Help. Nếu cần phải thành lập nhiều hệ thống help để áp dụng cho các loại người sử dụng khác nhau.  Thiết kế kiến trúc của chủ đề thể hiện các quan hệ giữa các chủ đề mà bạn sẽ đưa vào hệ thống Help. Bắt đầu bằng phần tổng quát nhất của kiến trúc rồi thêm các tầng kế tiếp ở mức thấp hơn.  Thiết kế kịch bản minh họa các nét chính cho mỗi chủ đề help, các từ khóa cho mỗi chủ đề hay các từ được tham chiếu đến các chủ đề.  Nếu mỗi kịch bản có nhiều nét chính (3 hay 4) thì nên chú ý cẩn thận việc tách một chủ đề lớn thành các chủ đề nhỏ hơn.  Mục tiêu thống nhất là cố gắng làm cho mỗi chủ đề nằm gọn trong một trang Help (Toàn màn hình không cần có thanh cuốn). III - CÔNG CỤ WINDOWS HELP DESGINER PRO 1- Giới thiệu bộ công cụ Công cụ này được lấy từ Internet ở địa chỉ :http//www.devgr.com, địa chỉ Email liên lạc : [email protected] Vì là công cụ chưa có bản quyền nên ở cuối mỗi Topic sẽ có dòng văn bản cảnh báo của nhà sản xuất. Nếu đăng ký (trả tiền) thì dòng chú thích này sẽ mất. Qua phần trình bày ở trên ta nhận thấy để thiết kế một hệ thống help người lập trình cần phải nhớ rất nhiều mã để chèn vào file .RTF . Nick Ameladiotis đã đưa ra bộ công cụ WINDOWS HELP DESGINER PRO nhằm giúp cho nhà lập trình thiết kế một hệ thống help hoàn chỉnh mà không cần nhớ đến các mã điều khiển. Bộ công cụ giống như một trình soạn thảo văn bản, khi soạn thảo một Topic nào thì click vào mục Topic, đặt tên và bắt đầu soạn thảo, bộ soạn cho phép chèn vào các hình ảnh, file AVI, các ký hiệu symbol. Đầu ra của bộ công cụ là các file : HELPFILE.CNT HELPFILE.HPJ HELPFILE.RTF Các file này sẽ qua Compliler Help để dịch qua file thực thi .HLP Để biết được chi tiết hơn về bộ công cụ này xin viếng thăn trang WEB : http//www.devgr.com Chuơng trình viết trong luận văn tốt nghiệp sử dụng bộ công cụ này để tạo ra file help thực thi. File Hep Project của chương trình ; This file is maintained by WHD. Do not modify this file directly. ; ; This help project was created with Windows Help Designer V 2.1.5.3 ; *** UNREGISTERED *** ; Windows Help Designer is copyright (C) 1996, 1997, by Nick Ameladiotis ; Visit for more informations ; [OPTIONS] REPORT=Yes ERRORLOG=H:\KS2_K7\LVTN_KS2\WHELP\Automat.LOG [WINDOWS] main="", , 0,(255,255,225),(192,192,192),0 ; [FILES] Automat.RTF [MAP] Topic1=0x1 Topic2=0x2 Topic3=0x3 Topic4=0x4 Topic5=0x5 Topic6=0x6 Topic7=0x7 Topic8=0x8 Topic9=0x9 Topic10=0xA Topic11=0xB V=0xC S=0xD T=0xE Topic15=0xF Topic16=0x10 Topic17=0x11 Topic18=0x12 Topic19=0x13 Topic20=0x14 PHẦN 8 GIỚI THIỆU KẾT QUẢ CHƯƠNG TRÌNH Màn Hình Giới Thiệu : GIỚI THIỆU HỆ THỐNG HELP 1- Màn Hình Help Contents Ví dụ một nội dung Help II- BIẾN ĐỔI VĂN PHẠM Nhập Văn Phạm Làm Việc Tập văn phạm mà các giải thuật sẽ làm việc có thể được nhập trực tiếp và lưu vào file, có thể lấy tập văn phạm đã lưu xuống file để sử dụng bằng cách sử dụng nút “Mở Văn Phạm”. Nếu có luật sinh rỗng thì được nhập là #.(ví dụ A #) 2- Loại Bỏ Các Luật Sinh Rỗng Ghi chú : Văn phạm nhập cho việc loại bỏ các luật sinh rỗng như sau : S ADaC A BC B b B # C D C # D d Nếu có luật sinh rỗng thì được nhập là #.(ví dụ A #) Loại Bỏ Các Luật Sinh Đơn Vị Ghi Chú : Văn phạm sử dụng cho việc loại bỏ luật sinh đơn vị như sau SAa SB BA Bbb Aa Abc AB Nếu có luật sinh rỗng thì được nhập là #.(ví dụ A #) Loại Bỏ Các Luật Sinh Vô Dụng Ghi Chú : Văn phạm sử dụng cho các luật sinh vô dụng như sau: S aS S A S C A a B aa CaCb Nếu có luật sinh rỗng thì được nhập là #.(ví dụ A #) III- CÁC DẠNG CHUẨN 1-Dạng Chuẩn Chomsky Ghi chú : Văn phạm nhập cho dạng chuẩn Chomsky có dạng S Aba AaaB BAc Nếu có luật sinh rỗng thì nhập là # (ví dụ : A #) 2-Dạng Chuẩn Greibach Ghi chú : Văn phạm nhập cho dạng chuẩn Greibach có dạng SAB SBBB A BAA A aa BDD DAA Nếu có luật sinh rỗng thì nhập là # (ví dụ : A #) IV- GIẢI THUẬT PHÂN TÍCH CÚ PHÁP Giải Thuật Earley Ghi chú : Văn phạm nhập cho dạng chuẩn Chomsky có dạng E T+E E T TF*T TF F(E) F a Nếu có luật sinh rỗng thì nhập là # (ví dụ : A #) Giải Thuật CYK Ghi chú : Văn phạm nhập cho dạng chuẩn Chomsky có dạng E T+E E T TF*T TF F(E) F a Nếu có luật sinh rỗng thì nhập là # (ví dụ : A #) V- SO SÁNH ĐỘ PHỨC TẠP CỦA HAI GIẢI THUẬT EARLEY VÀ CYK Ghi Chú : Văn phạm dùng để so sánh : E T+E E T TF*T TF F(E) F a Nếu có luật sinh rỗng thì nhập là # (Ví dụ A #) VI- NHẬN DẠNG NGÔN NGỮ TỰ NHIÊN Biên Soạn Từ Điển Đây là công cụ dùng để biên soạn bộ từ điể token dùng để sử dụng cho việc nhận dạng ngôn ngữ tự nhiên Để bộ nhận dạng nhận biết được càng nhiều câu nhập thì bộ từ điển phải được định nghĩa càng lớn. 2- Biên Soạn Văn Phạm Công cụ này cho phép người sử dụng biên soạn lại tập văn phạm được lưu từ file (hay biên soạn lại mới và lưu xuống file) Xin xem thêm phần 6 để biết chi tiết định nghĩa tập văn phạm ngôn ngữ tự nhiên. 3- Nhận Dạng Ngôn Ngữ Tự Nhiên Nếu câu nhập thuộc ngôn ngữ tự nhiên thì bộ công cụ sẽ in chuỗi dẫn xuất cho nó, ngược lại báo lỗi là “câu nhập không thuộc văn phạm” Để bộ nhận dạng nhận biết được càng nhiều câu nhập thì bộ từ điển phải được định nghĩa càng lớn. PHẦN 9 PHỤ LỤC - MÃ CHƯƠNG TRÌNH GIẢI THUẬT EARLEY // gtEARLEY.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "gtEARLEY.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // gtEARLEY dialog //====================================== gtEARLEY::gtEARLEY(CWnd* pParent /*=NULL*/) : CDialog(gtEARLEY::IDD, pParent) { //{{AFX_DATA_INIT(gtEARLEY) //}}AFX_DATA_INIT } void gtEARLEY::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(gtEARLEY) DDX_Control(pDX, IDC_EDIT_STR, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_I, m_list_thuc_the); DDX_Control(pDX, IDC_LIST_P, m_list_p); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(gtEARLEY, CDialog) //{{AFX_MSG_MAP(gtEARLEY) ON_BN_CLICKED(IDC_BUTTON_EARLEY, OnButtonEarley) ON_BN_CLICKED(IDC_BUTTON_VPDAU, OnButtonVP_Goc) ON_BN_CLICKED(IDC_BUTTON_HELP, OnButtonHelp) ON_EN_CHANGE(IDC_EDIT_STR, OnChangeChuoi_Nhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // gtEARLEY message handlers BOOL gtEARLEY:: OnInitDialog() { int soluat;//So luat sinh da luu int i; CString luatsinh; CDialog::OnInitDialog(); soluat=ArrayVePhai.GetSize(); char st[250]; char str[250]; //Cho hien lai tap luat sinh for(i=0;i"+ArrayVePhai[i]; strcpy(str,LPCTSTR(luatsinh)); sprintf(st,"(%d) %s",i,str); m_list_p.AddString(st); } //Copy cac bien toan cuc cho Dialog VPBanDau BanDau.ArrayKkt.Copy(ArrayKkt); BanDau.ArrayKt.Copy(ArrayKt); BanDau.ArrayVePhai.Copy(ArrayVePhai); BanDau.ArrayVeTrai.Copy(ArrayVeTrai); BanDau.ArrayLuatSinh.Copy(ArrayLuatSinh); BanDau.BienKhoiDau=BienKhoiDau; return TRUE; } //==================================== //Khoi dong mot con tro items *gtEARLEY::Init(items *f) { f=NULL; return f; } //==================================== //Khoi dong tap thuc the void gtEARLEY::Init_thucthe() { int i; for (i=0;ip)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } //============================================== //Hien thi cac trang thai trong tap thuc the void gtEARLEY::Display_Items(items *f, int th) { items *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); sprintf(ft,"%d ]",s); trangthai="[ " + ArrayVeTrai[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } } //============================================== void gtEARLEY::OnButtonEarley() { // TODO: Add your control notification handler code here CString str; CString stdx; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_Items(tapthucthe[0],0); else { for (i=0;if while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt->i)+1,0); flay=1;} pt=pt->link; } } else //luat 3 { for (i=0;ilink; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void gtEARLEY::luat456() { CString str; int j,chieudaichuoi; items *q; CString a; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;jp),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q->i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } //========================================== //Thuc hien luat so 5 va so 6 void gtEARLEY::luat56(int th) { items *q;// con tro cua tap j=th items *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt->i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;ilink; } }//ket thuc luat56 //================================================ //Tra ve chuoi ky tu truoc dau cham CString gtEARLEY::StrBeforeDot(int ls, int ch) { int i; CString Temp,Vp; Vp=ArrayVePhai[ls]; Temp=""; for(i=0; ip); ch=(pt->i); Vp=ArrayVePhai[sl]; if (chp==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } void gtEARLEY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here BanDau.DoModal(); } int gtEARLEY::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai.GetSize(); for (i=0; ip]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt->f)==i) && (ArrayVePhai[pt->p]==ArrayVePhai[ls])&&//(ArrayVePhai[pt->p].GetLength()==m) && (ArrayVeTrai[pt->p]==ArrayVeTrai[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai[q->p].GetLength(),r,l); k=k-1; l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================== //tra ve 1 neu co tra ve 0 neu khong co int gtEARLEY::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void gtEARLEY::XayDungTapT_N() { int sokytu; int i; //Xay dung tap T sokytu=ArrayKt.GetSize(); for(i=0;iso) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void gtEARLEY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j=0) { if (st[k]==ArrayVeTrai[i]) { str=st.Left(k); str=str+ArrayVePhai[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void gtEARLEY::OnButtonHelp() { // TODO: Add your control notification handler code here WinHelp(8,HELP_CONTEXT);//(0,HELP_CONTENTS); } void gtEARLEY::OnChangeChuoi_Nhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_dan_xuat.ResetContent(); m_list_thuc_the.ResetContent(); } GIẢI THUẬT CYK // gtCKY.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "gtCKY.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // gtCKY dialog gtCKY::gtCKY(CWnd* pParent /*=NULL*/) : CDialog(gtCKY::IDD, pParent) { //{{AFX_DATA_INIT(gtCKY) //}}AFX_DATA_INIT } void gtCKY::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(gtCKY) DDX_Control(pDX, IDC_EDIT_STR, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_TABLE_T, m_list_t); DDX_Control(pDX, IDC_LIST_P, m_list_p); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(gtCKY, CDialog) //{{AFX_MSG_MAP(gtCKY) ON_BN_CLICKED(IDC_BUTTON_CYK, OnButtonCYK) ON_BN_CLICKED(IDC_BUTTON_VP_DAU, OnButtonVP_Goc) ON_EN_CHANGE(IDC_EDIT_STR, OnChangeChuoiNhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // gtCKY message handlers BOOL gtCKY:: OnInitDialog() { int soluat;//So luat sinh da luu int i; char st[250]; CString luatsinh; CDialog::OnInitDialog(); Chomsky(); soluat=ChomskyVeTrai.GetSize(); //Cho hien lai tap luat sinh for(i=0;i"+ChomskyVePhai[i]; m_list_p.AddString(luatsinh); } m_list_t.SetHorizontalExtent(3000); m_list_dan_xuat.SetHorizontalExtent(700); m_list_p.SetHorizontalExtent(200); //Copy cac bien toan cuc cho Dialog VPBanDau Goc_Chomsky.ArrayKkt.Copy(ArrayKkt); Goc_Chomsky.ArrayKt.Copy(ArrayKt); Goc_Chomsky.ArrayVePhai.Copy(ArrayVePhai); Goc_Chomsky.ArrayVeTrai.Copy(ArrayVeTrai); Goc_Chomsky.ArrayLuatSinh.Copy(ArrayLuatSinh); Goc_Chomsky.BienKhoiDau=BienKhoiDau; Goc_Chomsky.ChomskyKkt.Copy(ChomskyKkt); Goc_Chomsky.ChomskyKt.Copy(ChomskyKt); Goc_Chomsky.ChomskyVePhai.Copy(ChomskyVePhai); Goc_Chomsky.ChomskyVeTrai.Copy(ChomskyVeTrai); Goc_Chomsky.ChomskyBanDau=ChomskyBanDau; Goc_Chomsky.VeTrai_TG.Copy(VeTraiVoDung); Goc_Chomsky.VePhai_TG.Copy(VePhaiVoDung); return TRUE; } //Thuc hien giai thuat CYK void gtCKY::OnButtonCYK() { // TODO: Add your control notification handler code here int i,j,chieudaichuoi; int soluatdanxuat; CString str,stdx; m_chuoi_nhap.GetWindowText(str); Goc_Chomsky.str=str; m_list_t.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); chieudaichuoi=str.GetLength(); for (i=0;i1) { k=1; while(kai int gtCKY::Pa(CString A, CString a) { int soluat; int i; soluat=ChomskyVeTrai.GetSize(); for(i=0;iabgd void gtCKY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ChomskyVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ChomskyVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=l; } else k=k+1; }//while }//for } //=============================================== void gtCKY::InDanXuat_Chuoi(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //////////////////////////////////////////// //Hien Thi van pham goc void gtCKY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here Goc_Chomsky.DoModal(); } /////////////////////////////////////////// //Phan chuyen van pham bat ky ve gtCKY void gtCKY::LoaiBoTatCa() { //Loai Bo Rong { CStringArray Vn;//Mang chua cac ve trai co kha ngag sinh ra rong; CString V; CString string; CString stringp; CString Vtemp; CString stringkt; CString stringkkt_kt; int i;//bien de duyet int soluat; int soluattrong; int sokt; //Xoa het cac gia tri trong VePhaiRong & VeTraiRong VePhaiRong.RemoveAll(); VeTraiRong.RemoveAll(); {//Tim cac ky hieu khong ket thuc dan xuat ra rong sokt=ArrayKt.GetSize(); for(i=0;i=2) {//begin while if(sokytu==2) { Str1=PhaiTemp[haiso-2]+PhaiTemp[haiso-1]; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Str1); } else { St=PhaiTemp[b]; //sprintf(Str,"(X%d)",k); sprintf(Str,"%c",k); while(FindStr(Str,V)==1) {k++;sprintf(Str,"%c",k);} Stp=St+Str; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Stp); stringT=Str; k++; } sokytu=sokytu-1; b=b+1; }//end while PhaiTemp.RemoveAll(); }//end else }//end for ChomskyVeTrai.Append(TraiX); ChomskyVePhai.Append(PhaiX); //Copy Cac bien cho van pham Dialog Chdlog; {//bat dau CStringArray Temp; CString Vv; soluat=ChomskyVeTrai.GetSize(); for (i=0;ip)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } //============================================== //Hien thi cac trang thai trong tap thuc the void ndnntn::Display_its(its *f, int th) { its *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); str_t=DoiToSt2(str_t); str_s=DoiToSt2(str_s); sprintf(ft,"%d ]",s); //trangthai="[ " + ArrayVeTrai1[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; trangthai="[ " + ArrayVeTrai2[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } m_list_thuc_the.AddString(" "); } //============================================== //TÛnh tËp trÁng thÀi S0 void ndnntn::luat123() { int i; int kq23; int soluatsinh; soluatsinh=ArrayVeTrai1.GetSize(); //luat 1 for(i=0;if while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt->i)+1,0); flay=1;} pt=pt->link; } } else //luat 3 { for (i=0;ilink; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void ndnntn::luat456() { CString str; int j,chieudaichuoi; its *q; CString a; str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;jp),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q->i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } //========================================== //Thuc hien luat so 5 va so 6 void ndnntn::luat56(int th) { its *q;// con tro cua tap j=th its *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai1.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt->i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;ilink; } }//ket thuc luat56 //================================================ //Tra ve chuoi ky tu truoc dau cham CString ndnntn::StrBeforeDot(int ls, int ch) { int i; CString Temp,Vp; Vp=ArrayVePhai1[ls]; Temp=""; for(i=0; ip); ch=(pt->i); Vp=ArrayVePhai1[sl]; if (chp==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } /////////////////////////////////////////////////// int ndnntn::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai1.GetSize(); for (i=0; ip]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt->f)==i) && (ArrayVePhai1[pt->p]==ArrayVePhai1[ls])&&//(ArrayVePhai1[pt->p].GetLength()==m) && (ArrayVeTrai1[pt->p]==ArrayVeTrai1[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai1[q->p].GetLength(),r,l); k=k-1; l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================== //tra ve 1 neu co tra ve 0 neu khong co int ndnntn::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void ndnntn::XayDungTapT_N() { int sokytu; int i; //Xay dung tap T sokytu=ArrayKt1.GetSize(); for(i=0;iso) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void ndnntn::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai1[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai1[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j=0) { if (st[k]==ArrayVeTrai1[i]) { str=st.Left(k); str=str+ArrayVePhai1[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void ndnntn::OnButtonPhanTich() { // TODO: Add your control notification handler code here CString str; CString stdx,temp; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); m_list_token.AddString("Token\tLexme\tLoÁi Tơ"); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); token=nexttoken(); str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_its(tapthucthe[0],0); else { for (i=0;i"+temp; stdx=stdx.Left(stdx.GetLength()-1); InDanXuat(stdx,85); m_nghia_viet.SetWindowText(nghia_viet); } } /////////////////////////////////////////////////////////// void ndnntn::OnButtonXemVPTN() { // TODO: Add your control notification handler code here VP_TN.DoModal(); } /////////////////////////////////////////////////// //Tra ve so thu tu cua ky hieu khong ket thuc int ndnntn::SoThuTu(CString st) { int i,stt; stt=ArrayKkt1.GetSize(); for(i=0;i<stt;i++) if (ArrayKkt1[i]==st) return i; return -1; } ///////////////////////////////////////// //Doi mot chuoi tu st1 sang st2 CString ndnntn::DoiToSt2(CString st) { int i,len,stt; CString st_temp; len=st.GetLength(); for (i=0;i<len;i++) { stt=SoThuTu(st[i]); if(stt!=-1) st_temp=st_temp+ArrayKkt2[stt]; else st_temp=st_temp+st[i]; } return st_temp; } //Tra ve mot token khi doc het mot chu CString ndnntn::nexttoken() { int i,len,stt; int beginning,forward; CString str,token,c,st; m_chuoi_nhap.GetWindowText(str); len=str.GetLength(); beginning=0; forward=0; if (len==0) MessageBox("BÁn Ch§a NhËp Vªo C¡u CÇn Ph¡n TÛch","Th¤ng BÀo"); else if (str[len-1]!='.') MessageBox("Lỉi NhËp C¡u, Cuçi C¡u Ph¶i Câ DÊu ChÊm (.)","Th¤ng BÀo"); else { while(forward<len) { if(str[forward]==' ') {forward++;beginning++;} else if ((isalpha(str[forward])&& (str[forward+1]==' ')) ||(isalpha(str[forward])&& (str[forward+1]=='.'))) { for(i=beginning;i<=forward;i++) c=c+str[i]; forward++; beginning=forward; stt=Find_TD(c); if(stt==-1) { token=token+"$"; st="$\t"+c+"\tLỉi Ch§a CËp NhËt Vªo Tơ ˜iĨn"; m_list_token.AddString(st); } else { token=token+token_td[stt]; st=token_td[stt]+"\t"+lexme_td[stt]+"\t"+loaitu_td[stt]+"\t"+tiengviet_td[stt]; if (nghia_viet.GetLength()==0)nghia_viet=nghia_viet+tiengviet_td[stt]; else nghia_viet=nghia_viet+" "+tiengviet_td[stt]; m_list_token.AddString(st); } c=""; } else forward++; } } return token; } //////////////////////////////////////////////// int ndnntn::Find_TD(CString st) { int i,stt; stt=lexme_td.GetSize(); for(i=0;i<stt;i++) if (lexme_td[i]==st) return i; return -1; } void ndnntn::OnChangeChuoiNhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); nghia_viet=""; } PHẦN 10 TÀI LIỆU THAM KHẢO A Introduction To Formal Languages And Automata Peter Linz University of California at Davis 372 Trang Compilers - Principle, Techniques, and Tool Alfred V. Aho Ravi Sethi Jeffrey D. Ulman 796 Trang The Theory Of Parsing, Translation, and Compiling - Volume 1 : Parsing Alfred V. Aho Feffrey D. Ullman 541 Trang Trình Biên Dịch Phan Thị Tươi 458 Trang - Nhà xuất bản giáo dục An Efficient Context-Free Parsing Algorithm - Jay Earley University of California Natural Language Processing In LISP Gazdar Gerald Chris Mellish 524 Trang 7- Website :