BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI NGUYỄN DIỆU LINH OTOMAT HỮU HẠN VÀ ỨNG DỤNG TRONG PHÂN TÍCH TỪ VỰNG LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI NGUYỄN DIỆU LINH OTOMAT HỮU HẠN VÀ ỨNG DỤNG TRONG PHÂN TÍCH TỪ VỰNG Chun ngành: Tốn ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS KIỀU VĂN HƯNG Hà Nội - 2018 LỜI CẢM ƠN Luận văn hoàn thành Trường Đại học Sư phạm Hà Nội Tác giả chân thành cảm ơn TS Kiều Văn Hưng tận tình hướng dẫn, tạo điều kiện cho tác giả hoàn thành luận văn Thạc sĩ Tác giả xin bày tỏ lòng biết ơn thầy giáo cán công nhân viên Trường Đại học Sư phạm Hà Nội quan tâm giúp đỡ Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Nguyễn Diệu Linh LỜI CAM ĐOAN Tôi xin cam đoan luận văn kết nghiên cứu riêng hướng dẫn TS Kiều Văn Hưng Trong q trình nghiên cứu, tơi kế thừa thành khoa học nhà khoa học với trân trọng biết ơn Các kết trích dẫn luận văn rõ nguồn gốc Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Nguyễn Diệu Linh Mục lục MỞ ĐẦU Otomat hữu hạn 1.1 Kiến thức sở 1.1.1 Bảng chữ, từ, ngôn ngữ 1.1.2 Ngôn ngữ quy biểu thức quy 12 1.2 Otomat hữu hạn 15 1.2.1 Otomat hữu hạn đơn định 15 1.2.2 Otomat hữu hạn không đơn định 21 1.2.3 Sự tương đương otomat đơn định không đơn định 24 1.2.4 Quan hệ otomat hữu hạn ngôn ngữ quy 27 1.2.5 Định lý Myhill – Nerode tối thiểu hóa otomat hữu hạn 30 Ứng dụng otomat hữu hạn phân tích từ vựng 38 2.1 Tổng quan ứng dụng otomat 38 2.1.1 Thiết kế kiểm tra hoạt động mạch số 39 2.1.2 Tìm kiếm từ văn 40 2.2 Phân tích từ vựng 46 2.2.1 Vai trò phân tích từ vựng 46 2.2.2 Lưu trữ tạm chương trình nguồn 50 2.2.3 Nhận dạng token 53 2.2.4 Ngôn ngữ đặc tả cho phân tích từ vựng 60 Kết luận 65 Tài liệu tham khảo 65 Mở đầu Lý chọn đề tài Ngơn ngữ hình thức tổng quát ngôn ngữ tự nhiên dạng mơ hình tốn học, nghiên cứu từ năm 1879 G.Frege phát triển N Chomsky nhiều tác giả khác vào năm 50 kỉ trước Otomat hữu hạn mơ hình máy trừu tượng đơn giản dùng để đoán nhận lớp ngơn ngữ quy - lớp ngơn ngữ có nhiều tính chất đặc biệt ứng dụng nhiều lĩnh vực công nghệ thông tin Otomat hữu hạn có vai trò quan trọng xử lý ngơn ngữ, mật mã có nhiều ứng dụng khoa học, kỹ thuật thực tế Với mong muốn tìm hiểu sâu otomat hữu hạn ứng dụng chúng, hướng dẫn TS Kiều Văn Hưng em định chọn đề tài nghiên cứu “Otomat hữu hạn ứng dụng phân tích từ vựng” cho luận văn tốt nghiệp thạc sĩ chuyên ngành Tốn ứng dụng Mục đích nghiên cứu Tìm hiểu otomat hữu hạn ứng dụng chúng phân tích từ vựng Nhiệm vụ nghiên cứu Trình bày cách hệ thống lý thuyết otomat hữu hạn ứng dụng otomat hữu hạn phân tích từ vựng Đối tượng phạm vi nghiên nghiên cứu • Đối tượng nghiên cứu: Otomat hữu hạn ứng dụng otomat phân tích từ vựng • Phạm vi nghiên cứu: Tìm hiểu tổng quan otomat hữu hạn đơn định otomat hữu hạn đa định Phương pháp nghiên cứu Tìm hiểu tài liệu, sách, báo liên quan đến kết có otomat hữu hạn Tổng hợp kiến thức trình bày cách hệ thống Đóng góp Hệ thống kiến thức otomat hữu hạn ứng dụng otomat, góp phần làm sinh động kết quả, hiểu biết otomat ngơn ngữ quy Hi vọng luận văn tài liệu tham khảo hữu ích lý thuyết otomat, ngơn ngữ hình thức nói chung lớp ngơn ngữ quy nói riêng Chương Otomat hữu hạn Lý thuyết otomat đề cập mơ hình tính tốn có vai trò quan trọng lĩnh vực khoa học máy tính Mơ hình otomat hữu hạn cơng cụ hữu hiệu để nghiên cứu lý thuyết tính tốn lĩnh vực liên quan đến khoa học máy tính với nhiều ứng dụng quan trọng xử lý văn bản, trình biên dịch, thiết kế phần cứng, ngơn ngữ lập trình trí tuệ nhân tạo Một số nhà khoa học tiêu biểu phát triển mạnh hướng nghiên cứu Mecullock, Pittis (1943), Kleene (1956), Mc – Naughton, Yamad (1960), Rabin, Shepherdson (1959), Với nghiên cứu otomat hữu hạn đơn định (DFA – Deterministic Finite Automat), otomat hữu hạn không đơn định (NFA – Nondeterministic Finite Automat), otomat không đơn định với ε chuyển (ε − N F A), otomat hữu hạn phía (two – way Finite Automat), otomat hữu hạn có (Finite Automat with output), Trong luận văn này, tìm hiểu otomat hữu hạn đơn định (DFA) otomat hữu hạn không đơn định (NFA) 1.1 Kiến thức sở 1.1.1 Bảng chữ, từ, ngôn ngữ Định nghĩa 1.1 Một tập hợp khác rỗng, hữu hạn hay vô hạn gọi bảng chữ Mỗi phần tử bảng chữ gọi chữ hay kí hiệu Trong luận văn xét bảng chữ hữu hạn, thường kí hiệu Σ Ví dụ 1.1 Sau số bảng chữ: + Σ = {a, b, c, d, e, , z}; + ∆ = {α, β, γ, δ}; + Γ = {0, 1} Định nghĩa 1.2 Cho bảng chữ Σ Một từ (hay chuỗi) dãy hữu hạn chữ bảng chữ Σ Đặc biệt, từ rỗng từ mà khơng chứa chữ bảng chữ kí hiệu ε Như vậy, từ bảng chữ Σ dãy hữu hạn gồm số lớn hay không chữ Σ, chữ xuất nhiều lần Tổng số vị trí kí hiệu xuất từ α gọi độ dài từ α kí hiệu |α| Quy ước |ε| = Tập tất từ bảng chữ Σ kí hiệu Σ∗ Σ+ = Σ∗ \ {ε} Nói cách khác, Σ∗ = Σ+ ∪ {ε} Ví dụ 1.2 Cho Σ = {1, 2, 3, , n}, Γ = {x, y} bảng chữ Khi xyx xxy từ bảng chữ Γ |xyx| = |xxy| = 1, 12, 21, { if p2 cuối nửa đầu { Đọc vào nửa cuối; p2 = p2 + 1; } else if p2 cuối nửa sau { Đọc vào nửa đầu; Dời p2 vào đầu nửa đầu; } else /* EOF vùng đệm hết chương trình nguồn */ kết thúc phân tích từ vựng; } 2.2.3 Nhận dạng token Trong phần này, dùng ngôn ngữ tạo văn phạm làm thí dụ minh họa: stmt → if expr then stmt | if expr then stmt else stmt |ε expr → term relop term 53 | term term → id | num Trong ký hiệu kết thúc if, then, else, relop, id, num cho định nghĩa quy sau: if → if then → then else → else relop →< | ≤ | = | | > | ≥ id → letter (letter | digit)* num → digit+ (.digit+ )? (E (+|−)?digit+ )? Định nghĩa quy khoảng trăng ws (white space) delim → blank | tab | newline → delim+ Mục đích xây dựng phân tích từ vựng định vị từ tố cho token vùng đệm tạo output cặp token thích hợp giá trị thuộc tính cách dùng mẫu biểu thức quy cho token sau: Sơ đồ dịch Để dễ dàng nhận dạng token, xây dựng cho token sơ đồ dịch (translation diagram) Sơ đồ dịch bao gồm trạng thái (state) ký hiệu vòng tròn cạnh mũi tên nối trạng thái Nói chung thường có nhiều sơ đồ dịch, sơ đồ đặc tả nhóm token Nếu xảy thất bại theo sơ đồ dịch dịch lui trỏ tới nơi trạng thái khởi đầu sơ đồ kích họat sơ đồ dịch 54 Hình 2.9: Mẫu biểu thức quy cho số token Do trỏ đầu trị từ vựng trỏ tới đến vị trí trạng thái khởi đầu sơ đồ, trỏ tới dịch lui lại để đến vị trí trỏ đầu trị từ vựng tới Nếu xảy thất bại tất sơ đồ dịch xem lỗi từ vựng phát khởi động thủ tục khắc phục lỗi Phần trình bày số sơ đồ dịch nhận dạng token văn phạm ví dụ Sơ đồ dịch nhận dạng cho token relop: Chúng ta dùng ký hiệu để trạng thái mà đọc ký tự, cần phải quay lui trỏ lại Sơ đồ dịch nhận dạng token id: Một kỹ thuật đơn giản để tách từ khóa khỏi danh biểu khởi tạo bảng ký hiệu lưu trữ thông tin danh biểu cách thích hợp Đối với token cần nhận dạng văn phạm này, cần 55 Hình 2.10: Sơ đồ dịch cho tốn tử quan hệ Hình 2.11: Sơ đồ dịch cho danh biểu từ khóa nhập chuỗi if, then else vào bảng ký hiệu trước đọc ký hiệu đệm nguyên liệu Đồng thời ghi bảng ký hiệu để trả token chuỗi nhận Sử dụng hàm gettoken( ) install_id( ) tương ứng để nhận token thuộc tính trả Sơ đồ dịch nhận dạng token num: Một số vấn đề nảy sinh xây dựng nhận dạng cho số không dấu Trị từ vựng cho token num phải trị từ vựng dài Do đó, việc thử nhận dạng số sơ đồ dịch phải theo thứ tự từ sơ đồ nhận dạng số dài Có nhiều cách để tránh đối sánh dư thừa sơ đồ dịch Một cách viết lại sơ đồ dịch cách tổ hợp chúng thành - cơng việc nói chung không đơn giản Một cách khác thay đổi cách đáp ứng với thất bại qua trình duyệt qua sơ 56 Hình 2.12: Sơ đồ dịch cho số không dấu Pascal đồ Phương pháp sử dụng cho phép ta vượt qua nhiều trạng thái kiểm nhận quay trở lại trạng thái kiểm nhận cuối qua thất bại xảy Sơ đồ dịch nhận dạng khoảng trắng ws (white space): Việc xử lý khoảng trắng ws khơng hồn tồn giống mẫu nói khơng có để trả cho phân tích cú pháp tìm thấy khoảng trắng chuỗi nhập Và đó, thao tác đơn giản cho việc dò tìm sơ đồ dịch phát khoảng trắng trở lại trạng thái bắt đầu sơ đồ dịch để tìm mẫu khác Hình 2.13: Sơ đồ dịch cho khoảng trắng 57 Cài đặt sơ đồ dịch Dãy sơ đồ dịch chuyển thành chương trình để tìm kiếm token đặc tả sơ đồ Mỗi trạng thái tương ứng với đoạn mã chương trình Nếu có cạnh từ trạng thái đọc ký tự tùy thuộc vào ký tự mà đến trạng thái khác Ta dùng hàm nextchar( ) đọc ký tự từ đệm input trỏ p2 di chuyển sang phải ký tự Nếu khơng có cạnh từ trạng thái hành phù hợp với ký tự vừa đọc trỏ p2 phải quay lại vị trí p1 để chuyển sang sơ đồ dịch Hàm fail( ) làm nhiệm vụ Nếu khơng có sơ đồ khác để thử, fail( ) gọi thủ tục khắc phục lỗi Để trả token, dùng biến tồn cục lexical_value Nó gán cho trỏ hàm install_id( ) install_num( ) trả về, tương ứng tìm danh biểu số Lớp token trả thủ tục phân tích từ vựng có tên nexttoken( ) int state = 0, start = 0; int lexical_value; /* để “trả về” thành phần thứ hai token */ int fail ( ) { forward = token_beginning; switch (start) { case 0: start = 9; break; case 9: start = 12; break; case 12: start = 20; break; case 20: start = 25; break; 58 case 25: recover ( ); break; default : / * lỗi trình biên dịch */ } return start; } token nexttoken ( ) { while (1) { switch (state) { case : c = nextchar ( ) ; / * c ký hiệu đọc trước */ if ( c = = blank || c = = tab || c = = newline ) { state = 0; lexeme_beginning ++ ; / * dịch trỏ đến đầu trị từ vựng */ } else if (c = = ‘ < ’) state = 1; else if (c = = ‘ = ’) state = 5; else if (c = = ‘ > ’) state = 6; else state = fail ( ) ; break ; / * trường hợp - */ [ case : c = nextchar ( ); if (isletter (c)) state=10; else state = fail ( ) ; break ; 59 case 10 : c = nextchar ( ); if (isletter (c)) state=10; else if (isdigit(c)) state = 10 ; else state = 11 ; break ; case 11 : retract (1) ; install_id ( ) ; return (gettoken ( )); / * trường hợp 12 - 24 */ case 25 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = fail ( ) ; break ; case 26 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = 27 ; break ; case 27 : retract (1) ; install_num ( ) ; return (NUM); } } } 2.2.4 Ngơn ngữ đặc tả cho phân tích từ vựng Bộ sinh phân tích từ vựng Có nhiều cơng cụ để xây dựng phân tích từ vựng dựa vào 60 biểu thức quy Lex công cụ sử dụng rộng rãi để tạo phân tích từ vựng Trước hết đặc tả cho phân tích từ vựng chuẩn bị cách tạo chương trình lex.l ngơn ngữ lex Trình biên dịch Lex dịch lex.l thành chương trình C lex.yy.c Chương trình bao gồm đặc tả sơ đồ dịch xây dựng từ biểu thức quy lex.l, kết hợp với thủ tục chuẩn nhận dạng trị từ vựng Các hành vi kết hợp với biểu thức quy lex.l đoạn chương trình C chuyển sang lex.yy.c Cuối trình biên dịch C dịch lex.yy.c thành chương trình đối tượng a.out, phân tích từ vựng chuyển dòng nhập thành chuỗi token Hình 2.14: Tạo phân tích từ vựng Lex Chú ý: Những điều ta nói nói lex UNIX Ngày có nhiều version lex Lex cho Pascal Javalex Đặc tả lex Một chương trình lex bao gồm thành phần: Khai báo %% Quy tắc dịch %% 61 Các thủ tục phụ Phần khai báo bao gồm khai báo biến, định nghĩa quy Phần quy tắc dịch cho lệnh có dạng: p1 action p2 action pn action n Trong pi biểu thức quy, action i đoạn chương trình mơ tả hành động phân tích từ vựng thực pi tương ứng phù hợp với trị từ vựng Trong lex đoạn chương trình viết C nói chung viết ngôn ngữ Các thủ tục phụ cài đặt hành động phần 2.2.2 Ví dụ 2.3 Sau trình bày chương trình Lex nhận dạng token văn phạm nêu phần trước trả token tìm thấy %{ /* định nghĩa LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */ %{ /* định nghĩa quy */ delim [t\n] 62 ws (delim)+ letter [A − Za − z] digit [0 − 9] id letter(letter| digit)* number{digit}+ \.{digit}+ ? E [+\−]?{digit}+ ? %% ws /* Khơng có action, khơng có return */ if return(IF); then return(THEN); else return(ELSE); id yylval = install_id( ); return(ID) number yylval = install_num( ); return(NUMBER) “< ” yylval = LT; return(RELOP) “ “ yylval = GT; return(RELOP) “>= “ yylval = GE; return(RELOP) %% install_id ( ) { /* Thủ tục phụ cài id vào bảng ký hiệu */ { 63 install_num ( ) { /* Thủ tục phụ cài số vào bảng ký hiệu */ } 64 Kết luận Otomat hữu hạn công cụ đốn nhận lớp ngơn ngữ quy có nhiều ứng dụng thực tế Trong luận văn này, khái niệm ngơn ngữ hình thức, ngơn ngữ quy; định nghĩa, mơ tả hoạt động số thuật toán liên quan tới otomat hữu hạn đơn định otomat không đơn định trình bày Đặc biệt, luận văn trình bày tổng quát mô tả chi tiết số mô hình ứng dụng otomat hữu hạn phân tích từ vựng Tài liệu tham khảo [A] Tài liệu tiếng Việt [1] Nguyễn Văn Định (2012), Giáo trình Otomat Ngơn ngữ hình thức, NXB Đại học Nơng nghiệp [2] Đỗ Đức Giáo (2014), Toán rời rạc ứng dụng tin học, NXBGD [3] Hồ Văn Quân (2002), Giáo trình lý ơtơmát ngơn ngữ hình thức, NXB Đại học Quốc gia TP Hồ Chí Minh [4] Đặng Huy Ruận (2002), Lý thuyết ngơn ngữ hình thức Otomat, NXB Đại học Quốc gia Hà Nội [B] Tài liệu tiếng Anh [5] Hopcroft J E., Ullman J D (1969), Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Company, Massachussetts [6] Hopcroft J E., Motwani R., Ullman J D (2001), Introduction to Automata Theory, Languages, and Computation, Addision – Wesley Publishing Company, Massachussetts [7] Peter L (1990), An Introduction to Formal Languages and Automata, D.C Heath and Company [8] Smith V J R (1995), A First course in Formal Language Theory (Second Editor), McGraw-Hill Book Company Europe 67 ... nghiên cứu Otomat hữu hạn ứng dụng phân tích từ vựng cho luận văn tốt nghiệp thạc sĩ chun ngành Tốn ứng dụng Mục đích nghiên cứu Tìm hiểu otomat hữu hạn ứng dụng chúng phân tích từ vựng Nhiệm... thống lý thuyết otomat hữu hạn ứng dụng otomat hữu hạn phân tích từ vựng Đối tượng phạm vi nghiên nghiên cứu • Đối tượng nghiên cứu: Otomat hữu hạn ứng dụng otomat phân tích từ vựng • Phạm vi...BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI NGUYỄN DIỆU LINH OTOMAT HỮU HẠN VÀ ỨNG DỤNG TRONG PHÂN TÍCH TỪ VỰNG Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN