Chương 4 : Phân tích từ vựng

Khoa KTMT - UIT TS. Vũ Đức Lung 1 TRÌNH BIÊN DỊCH (COMPILER) Khoa Kỹ thuật máy tính  TS. Vũ Đức Lung  Email: lungvd@uit.edu.vn Khoa KTMT - UIT TS. Vũ Đức Lung 2 Chương 4 : Phân tích từ vựng Nội dung: Vai trò của bộ phân tích từ vựng CÁC TÍNH CHẤT CỦA TOKEN CHỨA TẠM CHƯƠNG TRÌNH NGUỒN  Đặc tả, nhận dạng token  Sơ đồ dịch Automat hữu hạn – Automat hữu hạn không tất định (NFA) – Automat hữu hạn tất định (DFA) Khoa KTMT - UIT TS. Vũ Đức Lung 3 Vai trò của bộ phân tích từ vựng  1. Token, mẫu, trị từ vựng: Khoa KTMT - UIT TS. Vũ Đức Lung 4 Sự giao tiếp giữa bộ phân tích từ vựng và bộ phân tích cú pháp Khoa KTMT - UIT TS. Vũ Đức Lung 5 CÁC TÍNH CHẤT CỦA TOKEN  Phân tích từ vựng phải có nhiệm vụ chọn thông tin có liên quan đến token, để cất chúng vào bảng danh biểu (Ví dụ trị từ vựng).  Token luôn mang trong mình một thuộc tính duy nhất là con trỏ để chỉ đến vị trí của nó trong bảng danh biểu.  Khi một token được chuyển đến bộ phân tích cú pháp nó sẽ có dạng. Khoa KTMT - UIT TS. Vũ Đức Lung 6 CHỨA TẠM CHƯƠNG TRÌNH NGUỒN 1. Cặp bộ đệm:  Cấu tạo và Quy trình hoạt động : Giải thuật: if p2 ở ranh giới một nửa bộ đệm then begin lấp đầy N ký hiệu nhập mới vào nửa bên phải. p2 := p2 + 1; end else if p2 ở tận cùng bên phải bộ đệm then begin lấp đầy N kỳ hiệu nhập vào nửa bên trái bộ đệm. chuyển p2 về ký tự tận cùng bên trái của bộ đệm. end else p2 := p2 + 1; Khoa KTMT - UIT TS. Vũ Đức Lung 7 CHỨA TẠM CHƯƠNG TRÌNH NGUỒN 2.Phương pháp cầm canh p2 := p2 + 1; If p2 ^ eof then if p2 ở ranh giới một nửa bộ đệm then begin chất đầy N kỳ hiệu nhập vào nửa bên phải bộ đệm ; p2 := p2 + 1 end else if p2 ở tận cùng bên phải bộ đệm then begin lấp đầy N ký hiệu vào nửa bên trái bộ đệm; chuyển p2 về đầu bộ đệm end else /* dừng sự phân tích từ vựng*/ Giải thuật: Khoa KTMT - UIT TS. Vũ Đức Lung 8 Đặc tả token Các quy tắc định nghĩa biểu thức chính quy 1. là biểu thức chính quy, biểu thị cho tập { } 2. a là ký hiệu thuộc , biểu thị cho tập {a} 3. r và s là hai biểu thức chính quy, biểu thị cho L(r) và L(s) thì: a) (r)|(s) là biểu thức chính quy, biểu thị cho L(r)| L(s). b) (r)(s) là biểu thức chính quy, biểu thị cho L(r)L(s). c) (r)* là biểu thức chính quy, biểu thị cho (L(r))*. d) r là biểu thức chính quy, biểu thị cho L(r).    Khoa KTMT - UIT TS. Vũ Đức Lung 9 Đặc tả token Thí dụ 3.1: Cho = {a, b} 1. a|b biểu thị cho tập {a,b} 2. (a|b) |(b|a) biểu thị cho tập {aa,ab,ba,bb} 3. a* biểu thị cho tập {  ,a,aa,aaa,…..} Hai biểu thức chính quy tương đương r và s, ký hiệu r = s.  Khoa KTMT - UIT TS. Vũ Đức Lung 10 Nhận dạng token Cho văn phạm G: stmt -> if exp then stmt | if exp then stmt else stmt |  exp -> term relop term |term term -> id |num Khoa KTMT - UIT TS. Vũ Đức Lung 11 Bảng mẫu cho token Khoa KTMT - UIT TS. Vũ Đức Lung 12 Sơ đồ dịch  Sơ đồ dịch nhận dạng token relop Khoa KTMT - UIT TS. Vũ Đức Lung 13 Automat hữu hạn  Automat hữu hạn không tất định (NFA) Thí dụ: Cho NFA: Tập trạng thái S = {0, 1, 2, 3};  = {a, b}; Trạng thái bắt đầu So = 0; Tập trạng thái kết thúc F = {3}.  Bảng truyền NFA nhận dạng (a|b)*abb Khoa KTMT - UIT TS. Vũ Đức Lung 14 Automat hữu hạn Automat hữu hạn tất định (DFA) DFA là trường hợp đặc biệt của NFA, nó không có: 1) Sự truyền rỗng. 2) Với mỗi trạng thái S và ký hiệu nhập a chỉ tồn tại nhiều nhất một cạnh có tên a xuất phát từ S. VD: DFA nhận dạng ngôn ngữ (a|b)*abb Khoa KTMT - UIT TS. Vũ Đức Lung 15 Chuyển NFA sang DFA  Giải thuật 3.2: Xây dựng tập con (Tạo DFA từ NFA). Nhập: Cho NFA gọi là N. Xuất: DFA gọi là D, nhận dạng cùng ngôn ngữ như NFA. Phương pháp: Xây dựng bảng truyền cho D. Mỗi trạng thái của D là tập trạng thái của N. D mô phỏng đồng thời mọi chuyển động của N trên chuỗi nhập cho trước bằng các tác vụ: -closure (S);  -closure (T); move (T, a) Khoa KTMT - UIT TS. Vũ Đức Lung 16 Giải thuật tính -closure  Đẩy tất cả các trạng thái trong T lên stack;  Khởi tạo -closure (T) cho T. While stack không rỗng do Begin Lấy t là phần tử trên đỉnh ra khỏi stack. For mỗi trạng thái u với cạnh đi từ t đến u có tên do if u không thuộc -closure(T) then Begin them u vào -closure(T). đẩy u vào stack end end Khoa KTMT - UIT TS. Vũ Đức Lung 17 Giải thuật xây dựng tập con Bắt đầu -closure(S0) chỉ là một trạng thái trong các trạng thái của D chưa được đánh dấu. While có một trạng thái T chưa được đánh dấu trong D do begin Đánh dấu T {Có nghĩa là đem T ra xem xét}. for mỗi ký tự nhập a do begin U = -closure(move(T,a)) if U không có trong tập trạng thái của D then begin thêm U vào các trạng thái của D và là trạng thái chưa được đánh dấu D[T,a] = U {D[T,a] là phần tử của bảng truyền của D} end end end Khoa KTMT - UIT TS. Vũ Đức Lung 18 Ví dụ chuyển NFA thành DFA  Dùng giải thuật 3.2 để xây dựng DFA tương đương cho NFA sau (NFA nhận dạng (a|b)*abb). Khoa KTMT - UIT TS. Vũ Đức Lung 19 Tìm các trạng thái cho DFA  Các bước thực hiện:  Tính -closure(0)={0,1,2,4,7} = A //Những trạng thái trên NFA có từ “0” đi mà có sự truyền rỗng   Tính -closure(Move(A,a)) = -closure(3,8) = {1,2,3,4,6,7,8}=B • Move(A,a) = (3,8) • Tính -closure(Move(A,b)) = -closure(5) = {1,2,4,5,6,7}=C Lập lại các bước này cho tất cả các tập B,C,… cho đến khi không còn tập nào  Kết quả: A = {0,1,2,4,7} B = {1,2,3,4,6,7,8} C = {1,2,4,5,6,7} D = {1,2,4,5,6,7,9} E = {1,2,4,5,6,7,10} Khoa KTMT - UIT TS. Vũ Đức Lung 20 Bảng truyền cho DFA Từ bảng này vẽ DFA Khoa KTMT - UIT TS. Vũ Đức Lung 21 Từ biểu thức chính quy đến NFA Xây dựng NFA từ biểu thức chính quy Giải thuật 3.3: Xây dựng NFA từ biểu thức chính quy (Cấu trúcThompson’) Nhập: Biểu thức chính quy r trên . Xuất: NFA nhận dạng ngôn ngữ L(r).  Khoa KTMT - UIT TS. Vũ Đức Lung 22 Phương pháp Quy tắc: Khoa KTMT - UIT TS. Vũ Đức Lung 23 Phương pháp Giả sử N(s) và N(t) là NFA cho biểu thức chính quy s và t.  Với s|t xây dựng NFA hỗn hợp N(s|t) Khoa KTMT - UIT TS. Vũ Đức Lung 24 Phương pháp Khoa KTMT - UIT TS. Vũ Đức Lung 25 Phương pháp Khoa KTMT - UIT TS. Vũ Đức Lung 26 Automat hữu hạn  Automat hữu hạn không tất định (NFA) – Cách vẽ NFA cơ bản Khoa KTMT - UIT TS. Vũ Đức Lung 27 Automat hữu hạn Automat hữu hạn không tất định (NFA) Cách vẽ NFA cơ bản Khoa KTMT - UIT TS. Vũ Đức Lung 28 Ví dụ  Dùng giải thuật để xây dựng NFA cho biểu thức chính quy r = (a|b)*abb Khoa KTMT - UIT TS. Vũ Đức Lung 29 Mô phỏng NFA  Nhập: NFA gọi là N được xây dựng theo giải thuật 3.3, chuỗi nhập x. x được kết thúc bằng eof, N có trạng thái bắt đầu s0 và tập trạng thái kết thúc F.  Xuất: Giải thuật trả lời đúng nếu N chấp nhận x, ngược lại trả lời sai. Khoa KTMT - UIT TS. Vũ Đức Lung 30 Giải thuật S = -closure({So}) a = nextchar While a eof then Begin S = -closure(move(s,a)) a = nextchar End if S  F  then write(đúng) Else write(sai) Khoa KTMT - UIT TS. Vũ Đức Lung 31 Xây dựng DFA trực tiếp từ biểu thức chính quy Tìm hiểu 2 giải thuật để tối ưu việc so trùng mẫu được xây dựng từ biểu thức chính quy: Xây dựng DFA trực tiếp từ biểu thức chính quy. Tối thiểu trạng thái của DFA. Khoa KTMT - UIT TS. Vũ Đức Lung 32 Trạng thái quan trọng của NFA  Trạng thái quan trọng là từ nó có sự truyền khác rỗng. Như vậy nếu hai tập trạng thái có cùng số trạng thái quan trọng thì chúng được đồng nhất.  NFA được xây dựng theo cấu trúc Thompson có trạng thái kết thúc không có sự truyền ra, như vậy nó không phải là trạng thái quan trọng ( nhưng thực sự nó lại rất quan trọng). Để tránh tình trạng này người ta thêm ký hiệu # vào sau biểu thức chính quy, và trạng thái kết thúc có sự truyền trên ký hiệu #.  Khi xây dựng tập con hoàn tất thì trạng thái nào có sự truyền trên # là trạng thái chấp nhận. Khoa KTMT - UIT TS. Vũ Đức Lung 33 Biểu thức chính quy gia tố  Biểu thức r# được gọi là biểu thức chính quy gia tố. Ký hiệu # không thuộc tập các ký hiệu cơ bản của biểu thức chính quy r.  Biểu diễn biểu thức chính qui gia tố bằng cây phân tích, sao cho tên các lá là các ký hiệu cơ bản. Các nút trung gian là các toán tử dạng: cat, or hoặc star. Khoa KTMT - UIT TS. Vũ Đức Lung 34 Xây dựng DFA trực tiếp từ biểu thức chính quy Xây dựng DFA trực tiếp từ biểu thức chính quy:  Vẽ cây phân tích  Tính các giá trị Nullable, First Post (FP), Last Post (LP).  Lập bảng Follow Post (FLP)  Tìm tập các trạng thái, bảng truyền  Vẽ DFA Tối thiểu trạng thái của DFA. Khoa KTMT - UIT TS. Vũ Đức Lung 35 Cây phân tích  Là cây có nút lá là các ký hiệu cơ bản của r#.  Các nút là các toán tử.  Các toán tử trên cây phân tích như:  Toán tử kết nối  Toán tử tuyển.  Toán tử bao đóng truyền. Khoa KTMT - UIT TS. Vũ Đức Lung 36 Cây phân tích  Cách vẽ cây phân tích r = (a|ba)(a|b)*ba# Khoa KTMT - UIT TS. Vũ Đức Lung 37 Cây phân tích  Cây phân tích r = (a|ba)(a|b)*ba# Khoa KTMT - UIT TS. Vũ Đức Lung 38 Các quy tắc để tính ba hàm nullable, firstpos, lastpos Khoa KTMT - UIT TS. Vũ Đức Lung 39 Các quy tắc để tính ba hàm nullable, firstpos, lastpos  NULLABLE: Quy tắc: - Nốt lá là False (F) - Nốt (*) là True (T) - Nốt (|) là True (T) nếu 1 trong 2 nốt con là True (T) - Nốt (.) là True (T) nếu cả 2 nốt con đều True (T)  FIRST POST (FP), LAST POST (LP): Quy tắc: - Bắt đầu đánh số cho các nốt lá theo thứ tự từ 1 lớn dần (tự đánh) - FP và LP của nốt lá bằng chính số của nó - Nốt (|): FP của nó bằng tổng hợp FP của 2 nốt con. LP cũng thế - Nốt (*): FP = FP nốt con. LP cũng thế - Nốt (.): o FP: Nếu (Nullable nốt con bên trái) = F thì (FP của nó) = (FP nốt con bên trái). Nếu (Nullable nốt con bên trái) = T thì (FP của nó) = tổng hợp (FP cả 2 nốt con) o LP: Nếu (Nullable nốt con bên phải) = F thì (LP của nó) = (LP nốt con bên phải). Nếu (Nullable nốt con bên phải) = T thì (LP của nó) = tổng hợp (LP cả 2 nốt con) Khoa KTMT - UIT TS. Vũ Đức Lung 40 NULLABLE  r = (a|ba)(a|b)*ba# Khoa KTMT - UIT TS. Vũ Đức Lung 41 FIRST POST (FP), LAST POST (LP) Khoa KTMT - UIT TS. Vũ Đức Lung 42 Các quy tắc tính hàm followpos(n)  Quy tắc: - Lập bảng FLP bằng cách liệt kê các nốt lá theo hàng dọc (Số thứ tự đã đánh trước) - Chỉ xét các nốt (.) và (*), không xét nốt (|) - Cách xét: o Đối với (.): Đưa (tập FP nốt con bên phải) vào (từng giá trị LP của nốt con trái) trong bảng FLP o Đối với (*): Đưa (tập FP của chính nó) vào (từng giá trị LP của chính nó) trong bản FLP - Cứ xét hết các nốt cần xét và điền giá trị vào các dòng tương ứng trong bảng FLP Khoa KTMT - UIT TS. Vũ Đức Lung 43 Bảng FLP Khoa KTMT - UIT TS. Vũ Đức Lung 44 Tìm tập các trạng thái  Đặt [A] là trạng thái bắt đầu. [A] sẽ chứa FP của ROOT => [A] = {1,2} Xét [A] = {1,2}: Ở đây ta nhìn hình chỉ số các nốt lá và bảng FLP o 1 tương đương a => Ua =FLP(1) = {4,5,6} (Ra 1 tập khác ta đặt là {B}) o 2 tương đương b => Ub =FLP(2) = {3} (đặt là [C]) Xét {B} = {4,5,6}: o 4 tương đương a => Ua =FLP(4) = {4,5,6} (là {B}) o 5,6 tương đương b => Ub =FLP(5) U FLP(6) = {4,5,6,7} (đặt là [D]) Khoa KTMT - UIT TS. Vũ Đức Lung 45 Bảng truyền Khoa KTMT - UIT TS. Vũ Đức Lung 46 VẼ DFA  VẼ DFA theo các trạng thái ta có được (A, B, C, D, E): - A là trạng thái bắt đầu - Trạng thái nào chứa 8 sẽ là trạng thái kết thúc - Đường đi dựa vào dữ liệu ta đã xét trên kia cho từng trạng thái (đọc a, đọc b) Khoa KTMT - UIT TS. Vũ Đức Lung 47 Xây dựng DFA trực tiếp từ biểu thức chính quy Xây dựng DFA trực tiếp từ biểu thức chính quy:  Vẽ cây phân tích  Tính các giá trị Nullable, First Post (FP), Last Post (LP).  Lập bảng Follow Post (FLP)  Tìm tập các trạng thái, bảng truyền  Vẽ DFA Tối thiểu trạng thái của DFA. Khoa KTMT - UIT TS. Vũ Đức Lung 48 Tối thiểu số trạng thái của DFA  Khái niệm DFA đầy đủ, trạng thái chết d  Chuỗi w phân biệt trạng thái s với trạng thái t  Giải thuật 3.6: Tối thiểu trạng thái của DFA Nhập: DFA, gọi là M có S,  , s0, F. M là DFA đầy đủ. Xuất: DFA, gọi là M’ chấp nhận ngôn ngữ như M, với số trạng thái nhỏ nhất.  Phương pháp: 1. Tạo phần khởi đầu  có 2 nhóm: các trạng thái kết thúc F, và các trạng thái không kết thúc S –F. 2. Áp dụng thủ tục (mô phỏng 3.6) để tạo 3. Nếu = thì = tiếp tục bước 4, ngược lại lặp lại bước 2, với = 4. Chọn mỗi nhóm 1 trạng thái đại diện và đó là trạng thái của M’. 5. Nếu M’ có trạng thái chết d thì loại nó ra khỏi M’. Tất cả các sự truyền đến trạng thái d đều không xác định. new  new  new  final   Khoa KTMT - UIT TS. Vũ Đức Lung 49 Tối thiểu số trạng thái của DFA Mô phỏng 3.6: Giải thuật tạo for với mỗi nhóm G của do begin - Chia G thành các nhóm nhỏ hơn sao cho hai trạng thái s và t của G sẽ ở cùng một nhóm nhỏ hơn nếu và chỉ nếu các sự truyền trên tất cả các ký hiệu nhập a từ s và t đều đi đến các trạng thái kế tiếp ở trong cùng một nhóm của - Ta thay G bằng các nhóm nhỏ hơn vừa được tạo nên, cho chúng vào end new    new Khoa KTMT - UIT TS. Vũ Đức Lung 50 Tối thiểu số trạng thái của DFA  ={(E),(ABCD)}  Xét (ABCD) trên sự truyền a – A  B : thuộc (ABCD) – B  B : – C  B : – D  E : không thuộc (ABCD)  tách D riêng  Tương tự trên b  new = {(E), (ABC), (D)} Thông thường những trạng thái rút gọn được là có sự truyền đến cùng một trạng thái trên một ký hiệu nhập và đến chính mình trên ký hiệu nhập khác. Khoa KTMT - UIT TS. Vũ Đức Lung 51 Thiết kế bộ sinh bộ phân tích từ vựng  Thiết kế phần mềm bằng ngôn ngữ Lex.  Có thể tự động sinh ra bộ phân tích từ vựng từ đặc tả biểu thức chính quy phần mềm. Khoa KTMT - UIT TS. Vũ Đức Lung 52 Thiết kế bộ sinh bộ phân tích từ vựng  Đặt tả Lex có dạng: P1 {hành vi- 1} P2 {hành vi- 2} ……. Pn {hành vi- n}  Pi là biểu thức chính quy, hành vi – i là một đoạn chương trình sẽ được thực thi khi trị từ vựng trên chuỗi nhập so trùng mẫu với Pi.  Nếu có nhiều mẫu được so trùng, thì bộ nhận dạng sẽ chọn chuỗi trị từ vụng dài nhất. Nếu có nhiều hơn một mẫu so trùng với trị từ vựng dài nhất thì bộ nhận dạng sẽ chọn mẫu được so trùng trước nhất. Khoa KTMT - UIT TS. Vũ Đức Lung 53 Mẫu so trùng trên cơ sở NFA NFA được tạo ra từ sự đặc tả LEX Khoa KTMT - UIT TS. Vũ Đức Lung 54 BÀI TẬP MẪU Bài 01: Xây dựng DFA trực tiếp từ biểu thức chính quy sau: r=ab* (a|b)+ a a. Hãy xây dựng cây phân tích của (r)#. b. Tính các giá trị hàn nullable, first pos, last pos, follow pos c. Tìm trạng thái của DFA và tối ưu trạng thái DFA. d. DFA vừa xây dựng từ biểu thức chính quy r có chấp nhận chuỗi bbabaa không? Nếu có trình bày quá trình tiếp nhận Bài 02: Tương tự bài 01 nhưng xây dựng DFA từ NFA