Môn học ngôn ngữ hình thức và automata có rất nhiều ứng dụng trong lĩnh vực khoa học máy tính như xây dựng các trình biên dịch, nhận dạng và chuyển đổi giữa các ngôn ngữ khác nhau Do đó mà môn học này là một môn học bắt buộc cho các sinh viên ngành CNTT trong các trường đại học.
Để giúp cho các sinh viên có điều kiện học tốt và thực hành các bài tập của môn học này, luận văn này đi sâu vào việc mô phỏng lại hoạt động của các giải thuật trong phần ngôn ngữ phi ngữ cảnh đặc biệt là các giải thuật phân tích cú pháp Earley và CYK.
Sinh viên có thể khai thác cơ sở lý thuyết của môn học thông qua hệ thống Help của chương trình.
Xin cám ơn thầy Hồ Văn Quân đã tận tình hướng dẫn và giúp đỡ tôi hoàn thành bản luận văn tốt nghiệp như yêu cầu của đề bài.
1. GIỚI THIỆU ĐỀ TÀI
Yêu cầu của đề tài là :
“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.” Ngoài các giải thuật biến đổi văn phạm, tập trung vào nghiên cứu và hiện thực hai giải thuật phân tích cú pháp CYK và Earley, Đánh giá số bước phân tích của mỗi giải thuật.
Aùp dụng nhận dạng một câu nhập thuộc ngôn ngữ tự nhiên (Tiếng Anh)
2. MỤC ĐÍCH & Ý NGHĨA
Hiện nay, ở nước ta việc áp dụng giảng dạy các môn học thông qua các mô hình giảng dạy thiết kế trên máy tính còn gặp nhiều khó khăn, một trong những nguyên nhân là thiếu các phần mềm hỗ trợ việc học và giảng dạy.
Luận văn này ra đời không nằm ngoài mục đích giúp sinh viên nghành CNTT có một công cụ để hỗ trợ thêm cho việc học môn học “Ngôn Ngữ Hình Thức & Automata” . Bộ công cụ này cho phép sinh thấy rõ cách thức hoạt động của một số giải thuật của phần ngôn ngữ phi ngữ cảnh, cũng như thấy được ứng dụng của các giải thuật phân tích cú pháp.
3. NỘI DUNG CHÍNH CỦA LUẬN VĂN TỐT NGHIỆP
Nội dung của luận văn được chia làm 8 phần, cụ thể như sau:
¨Phần 1 : Là phần giới thiệu về đề tài, cùng ý nghĩa và tầm quan trọng của nó.
¨Phần 2 : Đây là phần tìm hiểu về cơ sở lý thuyết có liên quan, trong phần 2 này được chia làm 4 chương với các chủ đề tìm hiểu khác nhau cụ thể là :
Chương 1 : Một số khái niệm cơ bản của môn học
Mục đích của chương này là giúp cho người đọc làm quen với một số khái niệm về Ngôn ngữ Hình thức & Automat như chuỗi, ngôn ngữ và văn phạm chính qui, ngôn ngữ và văn phạm PNC, cây dẫn xuất để có thể dễ dàng đọc tiếp những phần sau.Tuy nhiên, người đọc có thể bỏ qua chương này nếu đã nắm được các khái niệm trên.
Chương 2 :Các giải thuật biến đổi văn phạm PNC & các dạng chuẩn
Trong chương này tập trung tìm hiểu các giải thuật biến đổi văn phạm PNC như : Loại bỏ các luật sinh rỗng, đơn vị, vô dụng cũng như chuyển đổi một văn phạm PNC bất kỳ về hai dạng chuẩn Chomsky và Greibach, đây là phần lý thuết cơ bản làm nền tảng cho việc thực hiện giải thuật phân tích cú pháp CYK sau này.
Chương 3 : Trình bày Một số giải thuật và công cụ phân tích cú pháp thông dụng bao gồm phương pháp từ trên xuống (top -down) và từ dưới lên (bootom -up) mục đích là giúp cho người đọc có sơ sở để so sánh với hai giải thuật phân tích cú pháp tổng quát CYK và Earley
Chuơng 4 : Giải thuật phân tích cú pháp Earley và CYK, đây là phần chính của luận văn, trong chương này chú trọng đến việc tìm hiểu về giải thuật để phân tích cú pháp và tạo chuỗi dẫn xuất cho câu nhập, cũng như so sánh độ phức tạp của hai giải thuật này với các giải thuật ở chương 3.
¨Phần 3 : Tìm hiểu lý thuyết về phần mềm hỗ trợ học tập và giảng dạy, cách thức để thiết kế và lựa chọn mô hình giảng dạy tốt.
¨Phần 4 : Tập trung phân tích và thiết kế cho mô hình vừa chọn, phần này dựa trên các lý thuyết đã tìm hiểu ở phần 2 và mô hình giảng dạy để đưa ra
·Lựa chọn ngôn ngữ lập trình
·Cấu trúc dữ liệu cho các giải thuật sử dụng trong chương trình
·Cách thức nhập liệu, cấu trúc file lưu trữ
·Cách trình bày dữ liệu xuất
·Các lưu đồ thuật toán, tính toán độ phức tạp
·
¨Phần 5 : So sánh độ phức tạp giữa hai giải thuật phân tích cú pháp CYK và Earley, trong phần này đưa ra các giả thiết để thực hiện tính độ phức tạp cho hai giải thuật trên bằng chương trình cũng như đưa ra những minh họa bằng ví dụ thực tế (với các đồ thị minh họa)
¨Phần 6 : Aùp dụng nhận dạng ngôn ngữ tự nhiên, trong phần này sẽ trình bày các vấn đề liên quan đến việc nhận dạng một câu nhập (Tiếng Anh) và cách thức xây dựng bộ từ điển token.
¨Phần 7 : Thiết kế Help : đây cũng là một phần quan trọng của một chương trình trợ giúp học tập, trong phần này chú trọng tìm hiểu thiết kế một hệ thống Help. Đặc biệt là thiết kế hệ thống Help cho chương trình thông qua công cụ Windows Help Designer Pro (down load từ http://www.devgr.com)
¨Phần 8 : Giới thiệu chuơng trình kết quả.
¨Phần 9 : Phụ lục - Mã chương trình
¨Phần 10 : Giới thiệu các tài liệu tham khảo
146 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3875 | Lượt tải: 5
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 m1và
xi (VT)
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 , jn
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.
AX
AX.
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,Da, Sa} 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 : namela@devgr.com
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
SAa
SB
BA
Bbb
Aa
Abc
AB
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
CaCb
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
AaaB
BAc
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
SAB
SBBB
A BAA
A aa
BDD
DAA
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
TF*T
TF
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
TF*T
TF
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
TF*T
TF
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 :
Các file đính kèm theo tài liệu này:
- 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.DOC