Luận văn 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

u trung gian, đáp ứng các nhu cầu hoạt động, lưu trữ của mô hình. Người sử dụng chỉ có thể giao tiếp với mô hình thông qua dữ liệu nhập và dữ liệu xuất. Các yêu cầu học tập của người sử dụng được chuyển đổi thành dữ liệu nhập, qua một số bước tính toán, phân tích mô hình sẽ đưa ra các dữ liệu xuất để giải thích hoặc đáp ứng các yêu cầu của người sử dụng. Dữ liệu cục bộ của mô hình có thể được trình bày hoặc che dấu tùy mục đích của mô hình. Hoạt động của mô hình Các hoạt động của mô hình có thể chia làm hai loại chính như sau : + Hoạt động nhập xuất : Đây là các hoạt động thể hiện sự giao tiếp của mô hình của người sử dụng. Các phương thức nhập/xuất đảm nhận việc nhận các dữ liệu nhập của mô hình và thể hiện các dữ liệu xuất ra các thiết bị ngoại vi (màn hình, máy in,…) để giảng dạy cho người sử dụng. + Hoạt động xử lý, tính toán dữ liệu : Các hoạt động xử lý các dữ liệu cục bộ của mô hình phục vụ cho yêu cầu dạy và học. Các phương thức này đảm nhận việc chuyển đổi dữ liệu nhập thành các dữ liệu cục bộ của mô hình. Mô hình sẽ tính toán, xử lý trên dữ liệu cục bộ và chuyển thành các dữ liệu xuất. - VÍ DỤ VỀ MỘT PHẦN MỀM TRỢ GIÚP HỌC TẬP Ví dụ đưa ra ở đây là phần mềm trợ giúp học tập môn Anh Văn LANGMaster INTERACTIVE ENGLISH. Trong phần mềm chứa đựng được tất cả các đặc tính của một phần mềm giảng dạy hiện đại: - Những bài học được xếp từ dễ đến khó, tuy nhiên vẫn cho phép người sử dụng lựa chọn những phần mà mình quan tâm mà không cần học những phần trước. - Đưa ra những hình thức thực hành và luyện tập phong phú như : điền vào chỗ trống, chọn từ đúng, tập phát âm. - Báo cáo lại mức độ tiếp thu của người học qua từng bài giảng, để người học nhận biết được trình độ từ đó cũng cố kiến thức cho những bài học tiếp theo. - Đặc biệt phần mềm LANGMaster INTERACTIVE ENGLISH đã đưa ra một phương pháp giải dạy hiện đại, đó là phương pháp học từ và thành ngữ RE-WISE: + Phương pháp RE_WISE được thiết kế với sự tham gia của các chuyên gia về việc học và về mô hình toán học của việc học /quên trong nhiều năm từ đó đưa ra một thống kê quá trình học và quên các sự kiện đã được thu nhận. Qua ví dụ trên cho thấy được các tính chất của một phần mềm giảng dạy hiện tại cũng như một phương pháp giảng dạy tốt được đưa ra sẽ giúp ích rất nhiều trong việc học. 3.6- PHÂN TÍCH ĐIỀU KIỆN DẠY VÀ HỌC HIỆN TẠI và LOẠI PHẦN MỀM GIẢNG DẠY CẦN THIẾT KẾ Trên cơ sở thiết kế một phần mền giảng dạy cho các đối tượng là những sinh viên theo học ngành Máy Tính. Chuơng trình “Xây dựng bộ công cụ thực hiện một số giải thuật trong Lý thuyết Ngôn ngữ Hình thức & Automata”, cố gắng đưa những nội dung cơ bản của mô học nhằm góp phần giúp cho sinh viên nắm bắt được các cơ sở lý thuyết. Hiện nay với điều kiện về cơ sở vật chất cũng như các tài liệu thông tin và phương tiện giài dạy còn chưa đầy đủ như ở nước ta tồn tại các hình thức dạy và học sau: + Hình thức học tập trung (học trên lớp có thầy cô hướng dẫn) + Hình thức học hàm thụ từ xa (học theo sự hướng dẫn của người chuyên môn theo giáo trình hay sách vở được định hướng sẳn). + Hình thức tự học (Học theo nhu cầu , do điều kiện không cho phép theo học hai hình thức trên). Do đó việc thiết kế ra các phần mềm trợ giúp việc giảng dạy rất cần thiết rất cần thiết cho nhu cầu giảng dạy hiện tại. Dựa vào những phân tích trên cùng với các mô trường dạy và học vừa nêu, tôi quyết định xây dựng công cụ “Xây dựng bộ công cụ thực hiện một số giải thuật trong Lý thuyết Ngôn ngữ Hình thức & Automata” theo phía cạnh mô hình giảng dạy . PHẦN 4 PHÂN TÍCH VÀ THIẾT KẾ Sau đây chúng ta bắt đầu đi vào việc phân tích cụ thể cho bộ công cụ thực hiện một số giải thuật trong môn học “ Lý Thuyết Ngôn Ngữ Hình Thức & Automata” phần ngôn ngữ phi ngữ cảnh. I - YÊU CẦU ĐẶT RA CHO CHƯƠNG TRÌNH 1.1 Mục Tiêu Của Chương Trình Mục tiêu chính của chương trình là : Với bộ công cụ được xây dựng nó sẽ hổ trợ đắt lực cho người giảng dạy, giảm thiểu thời gian trong việc soạn giáo án cho các bài tập áp dụng một số giải thuật mà chúng tôi thể hiện trong chuơng trình, giúp cho sinh viên nắm bắt được cách thức thực hiện một bài tập theo các giải thuật đã nêu ra, giúp người học kiểm tra kiến thức của mình, thực hành một số bài tập từ đó nâng kiến thức khi học các lý thuyết liên quan. 1.2- Các Yêu Cầu Phải Viết Trong Chương Trình Trên cơ sở thiết kế phần mềm dạy và học cho những đối tượng là những những sinh viên theo học ngành khoa học máy tính. Chuơng trình hỗ trợ việc học một số giải thuật của môn học “Ngôn Ngữ Hình Thức & Automat” cố gắng thực hiện được các vấn đề sau: + Đưa ra những nội dung cơ bản liên quan đến môn học nhằm góp phần giúp cho sinh viên hiểu và nắm bắt nội dung của lý thuyết liên quan, phần này được tích hợp trong hệ thống Help của chương trình. + Thực hiện một bộ công cụ trợ giúp cho sinh viên học một số giải thuật trong môn học “Ngôn ngữ hình thức & Automata” như : (1) Loại bỏ các luật sinh rỗng (2) Loại bỏ các luật sinh đơn vị (3) Loại bỏ các luật sibnh vô dụng (4) Chuyển một văn phạm bất kỳ về dạng chuẩn Chomsky Chuyển một văn phạm bất kỳ về dạng chuẩn Greibach Hiện thực giải thuật phân tích cú pháp CYK Hiện thực giải thuật phân tích cú pháp Earley So sánh độ phức tạp của hai giải thuật PTCP trên. Áp dụng nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh). + Quá trình thực hiện các giải thuật phải thể hiện được các bước dữ liệu trung gian để sinh viên dễ dàng nắm bắt cách thực hiện giải thuật. II- MÔI TRƯỜNG HOẠT ĐỘNG và CÁC SƠ ĐỒ DFD 2.1 Môi Trường Hoạt Động & Ngôn Ngữ Lập Trình Đây là một chuơng trình mang tính dành học việc học, nghiên cứu cách thực hiện giải thuật nên chương trình chỉ thiết kế chạy trên máy tính cá nhân, hiện tại vấn đề chạy trên mạng chưa đặt ra ở đây. Chuơng trình phát triển chạy trên môi trường HĐH Microsoft Windows 95, đây là một HĐH được sử dụng rỗng rãi nhất hiện nay trên thế giới . Chương trình sẽ kế thừa những tiện ích của HĐH này nên sẽ không thể chạy trên môi trường DOS hay Windows 3.11 Ngôn ngữ Visual C++ 5.0 được sử dụng để hiện thực hệ thống, đây là một ngôn ngữ lập trình huớng đối tượng mạnh và hiện nay được sử dụng rộng rãi. Đặc biệt chương trình sẽ sử dụng các class được định nghĩa trong MFC . 2.2 Sơ Đồ DFD Tổng Quát a) Trường hợp biến đổi văn phạm Văn Phạm phi ngữ cảnh bất kỳ Bộ công cụ thực hiện Thông báo quá trình thực hiện giải thuật và kết quả User User Yêu cầu : - Bỏ các LS rỗng - Bỏ các LS đơn vị - Bỏ các LS vô dụng - Dạng chuẩn chomsky - Dạng chuẩn Greibach b) Trường hợp phân tích một câu nhập Văn Phạm phi ngữ cảnh bất kỳ Bộ công cụ thực hiện Thông báo quá trình thực hiện giải thuật & kết quả Câu nhập User User + Bộ công cụ bao hàm các prosess lớn sau : Process Loại bỏ các luật sinh rỗng (l). Process Loại bỏ các luật sinh đơn vị. Process Loại bỏ các luật sinh vô dụng. Process Chuyển một văn phạm bất kỳ về dạng chuẩn Chomsky. Process Chuyển một văn phạm bất kỳ về dạng chuẩn Greibach. Process Phân tích một câu nhập theo giải thuật CYK. Process Phân tích một câu nhập theo giải thuật Earley. Process So sánh số bước phân tích của hai giải thuật CYK và Earley.(*) Process Nhận dạng ngôn ngữ tự nhiên (**) * : Xin xem chi tiết quá trình thiết kế ở phần 5 - Trang ** : Xin xem chi tiết quá trình thiết kế ở phần 6 - Trang c) Mô hình Data Flow Diagram Chi Tiết + Biến đổi văn phạm User Văn phạm G Nhập VPPNC G Loại bỏ tất cả VP Loại bỏ l VP Loại bỏ đơn vị VP Loại bỏ vô dụng Loại bỏ đơn vị Loại bỏ luật sinh l Dạng chuẩn Greibach User Văn Phạm Thông báo Thông báo kết quả Thông báo kết quả Thông báo kết quả Thông báo kết quả Thông báo kết quả Loại bỏ luật sinh vôdụng Loại bỏ luật sinh đơn vị Văn phạm G Dạng Chuẩn Chomsky Văn phạm G VP không có rỗng, đơn vị, vô dụng VP không có rỗng, đơn vị, vô dụng Yêu cầu DC Chomsky Yêu cầu DC Greibach + Phân Tích Câu Nhập User Văn phạm G Nhập VPPNC G Bộ phân tích cú pháp CYK Câu nhập Câu nhập Bộ phân tích cú pháp Earley Loại bỏ luật sinh l User User Văn Phạm Thông báo kết quả Thông báo kết quả VP dạng chuẩn Chomsky Loại bỏ luật sinh đơn vị Loại bỏ luật sinh vô dụng Văn phạm không có các luật sinh đơn vị Văn phạm không có các luật sinh vô dụng Văn phạm không có các luật sinh l Chuyển về dạng chuẩn Chomsky III- CÁCH THỨC NHẬP VÀ XUẤT DỮ LIỆU Nhập Liệu Dữ liệu đầu vào là câu nhập và văn phạm phi ngữ cảnh G, dựa vào các dữ liệu này bộ công cụ tiến hành phân tích theo yêu cầu. Bộ công cụ Bàn phím File lưu trữ Lưu file Nhận dữ liệu từ File 7 + Chương trình có hai hình thức để đưa đữ liệu vào cho bộ công cụ : Nhập dữ liệu từ bàn phím Nhập từ file lưu trữ trên đĩa từ, file này do người sử dụng lưu lại khi nhập liệu từ bàn phí hoặc có thể soạn thảo bằng một trình soạn thảo văn bản theo đúng format của chương trình. Xuất dữ liệu Dữ liệu xuất ở đây chủ yếu là các dòng văn bản kết quả xuất ra màn hình cho người sử dụng xem, đồng thời lưu xuống file để lưu trữ (dữ liệu lưu là các tập văn phạm kết quả khi thực hiện biến đổi văn phạm) Một số dữ liệu trung gian cũng được hiển thị để minh họa quá trình phân tích, có thể minh họa việc trình bày dữ liệu xuất của bộ công cụ qua so đồ sau : Bộ công cụ Lưu kết quả xuống file Dữ liệu kết quả Dữ liệu minh họa cho giải thuật Hiển thị lên màn hình Màn Hình File lưu trữ 3.3 Định Dạng File Dữ Liệu Dữ liệu lưu trữ ở đây là bộ văn phạm phi ngữ cảnh G=(V,T,S,P), do đó có thể đề nghị một định dạng như sau : //ký hiệu để nhận dạng biến khỡi đầu Biến khỡi đầu // ký hiệu để nhận dạng dữ liệu theo sau thuộc tập V Danh sách các ký hiệu không kết thúc // ký hiệu để nhận dạng dữ liệu theo sau thuộc tập T Danh sách các ký hiệu kết thúc // ký hiệu để nhận dạng dữ liệu theo 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 0 1 2 3 4 5 6 7 8 . . . Lưu tập T : Là một mãng ký tự là chữ thường. 0 1 2 3 4 5 6 7 . . . 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ải 0 0 1 1 2 2 3 3 4 4 . . . . . . 2- Cấu Trúc Dữ Liệu Cho Giải Thuật CYK a) Sơ đồ cấu trúc dữ liệu j i 1 2 3 4 ... n 1 string string string string string string string string string 2 ... 3 ... n string 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;i<B.GetLength();i++) if (Temp.Find(B[i])==-1) Temp=Temp+B[i]; for(i=0;i<C.GetLength();i++) if (Temp.Find(C[i])==-1) Temp=Temp+C[i]; return Temp; } +Tìm kiếm các luật sinh có vế trái =BC thì trả về chuỗi chứa vế trái của tất cả các luật sinh đó ngược lại trả về trống CString TimLuatSinhBC(CString B, CString C) { int soluat; CString temp,st; int i; temp=B+C; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if (temp==ArrayVePhai[i]) st=st+ArrayVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } + Nếu có luật sinh thì trả về string chứa tất cả các vế trái ngược lại trả về chuỗi rỗng CString TimLuatSinh_a(CString a) { int soluat; CString st; int i; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if (ArrayVePhai[i]==a) st=st+ArrayVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } +Nếu chuỗi thuộc ngôn ngữ L thì trả về 1 ngược lại trả về 0 int KiemTraChuoiThuocL(CString st) { int i,len; len=st.GetLength(); for(i=0;i<len;i++) if(st[i]==BienKhoiDau) return 1; return 0; } +Trả về số thứ tự của luật sinh P-->ai int Pa(CString A, CString a) { int soluat; int i; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if ((ArrayVeTrai[i]==A)&&(ArrayVePhai[i]==a)) return i; return -1; Cấu Trúc Dữ Liệu Cho Giải Thuật Earley Danh Sách chứa các thực thể của I0 . . . . ... I3 I2 I1 I0 Mãng các con trỏ, trỏ đến các thực thể P ,i ,f P ,i ,f P ,i ,f a) Sơ đồ cấu trúc dữ liệu b) Hiện Thực : - Để thể hiện một thực thể ta sử dụng một bộ 3 biến nguyên như sau : + p : chỉ số thứ tự của luật sinh + i : chỉ vị trí dấu chấm ( . ) trong tập thực thể + f : chỉ vị trí tập thực thể như vậy để xác định một thực thể ta chỉ cần xác định bộ ba (p, i,f) - Tập thực thể các I0, I1, ... là một mãng các con trỏ vị trí bắt đầu của tập thực thể - Mỗi thực thể Ii chứa con trỏ trỏ đến đầu danh sách liên kết chứa các thực thể c) Cách hiện thực cấu trúc dữ liệu trên trong ngôn ngữ C Định nghĩa một phần tử trong danh sách liên kết : typedef struct item { int p; int i; int f; struct item *link; } items; trong đó : + p : chỉ số thứ tự của luật sinh + i : chỉ vị trí dấu chấm ( . ) trong tập thực thể + f : chỉ vị trí tập thực thể + link : là con trỏ trỏ đến phần tử kết tiếp. Khai báo một mãng các trỏ, trỏ đến tập thực thể items items *tapthucthe[MAX]; trong đó MAX : số lượng tập thực thể lớn nhất, số lượng này sẽ bằng với chiều dài chuỗi nhập d) Một số tác vụ cơ bản khi thực hiện giải thuật Earley (sử dụng ngôn ngữ C) + Khởi động một thực thể: items *Init(items *f) { f=NULL; return f; } + Khởi động tập thực thể : void Init_thucthe() { int i; for (i=0;i<MAX; i++) tapthucthe[i]=Init(tapthucthe[i]); } + Đưa dữ liệu vào một tập thực thể nào đó: items *Insert_data(items *pt, int k,int j ,int f) { items *p,*q,*before; p=new items; (p->p)=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<Vp.GetLength()) return (Vp[ch]); else return ""; V - CÁC LƯU ĐỒ THUẬT TOÁN CHO CÁC PROCESS START Luật sinh thứ p có dạng A --> l 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 l Đ Đ S S p=p+1 p > Tổng LS END p=0 1- Loại Bỏ Các Luật Sinh l 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<chiều dài VP luật sinh p1;I++) if VP[I] ÎV1 then B=BÈVP[I] p1=0, B={ } (p1 biến duyệt các luật sinh trong P1) Đ S p1=p1+1 A 3- Loại Bỏ Các Luật Sinh Vô Dụng Dựa và tập B và các luật sinh trong P1, tạo đồ thị phụ thuộc cho P1 Loại bỏ các biến và luật sinh tương ứng của nó ra khỏi tập luật sinh P1 A END Loại bỏ các luật sinh vô dụng loại 2 START Loại bỏ các luật sinh l Loại bỏ các luật sinh đơn vị Loại bỏ các luật sinh vô dụng p=0 Luật sinh thứ p có chiều dài vế phả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 l 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 < 1 Thực hiện loại bỏ đệ qui trái và thay thế S Đ S Đ i=n Thay thế Ai vào trong các xuất hiện của nó ở vị trí đầu tiên trên các vế phải của luật sinh Ai-1 bằng các vế phải của nó i=i-1 A START Loại bỏ các luật sinh l Loại bỏ các luật sinh đơn vị Loại bỏ các luật sinh vô dụng Cho tất cả các luật sinh có dạng Aà a vào trong P^ START Cho tất cả các luật sinh có dạng Aà a vào trong P^ A p>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 --> a Cho [S--> .a, 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 -->g., 0] i0 =0 Luật sinh thứ i0 trong I0 có dạng [A -->a.Bb,0] I0 > TổngLS trong I0 Cho vào I0 trạng thái [B-->.g,0] của các luật sinh trong P có dạng B-->g - Tính lại TổngLS Cho vào I0 trạng thái [A--> aB.b,0] của các trạng thái trong I0 có dạng [A--> aB.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.ab, I] với (a=aj) x=0 j=1 Cho [B -->a.ab, i] vào trong Ij x > TổngLS trong Ij-1 y=0 Luật sinh thứ y trong Ij có dạng [A -->a. , i] Tìm trong P các luật sinh có dạng : [B -->g thì cho vào Ij tập : [B --> .g, k] - Cập nhật lại LSJ Tìm trong tập Ii các thực thể có dạng : [B -->a.Ab, k] thì cho vào Ij tập : [B -->aA .b, k] - Cập nhật lại LSJ Luật sinh thứ y trong Ij có dạng [A -->a.Bb , 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 Đầu Cô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+B Các Dạng Chuẩn … Alt+D Cá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ành Mở văn phạm Thoát Dạng Chuẩn Chomsky Dạng Chuẩn Greibach Giải Thuật CYK … Alt+K Giải Thuật Earley… Alt+E So 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 l + 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