intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Trình biên dịch: Chương 4, 5 - TS. Vũ Đức Lung

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
80
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Trình biên dịch - Chương 4, 5 trang bị cho người học những kiến thức về phân tích từ vựng và cú pháp trong trình biên dịch. Trong chương này gồm có những nội dung sau: Vai trò của 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,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Trình biên dịch: Chương 4, 5 - TS. Vũ Đức Lung

  1. 05/04/2012 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 TRÌNH BIÊN DỊCH  CÁC TÍNH CHẤT CỦA TOKEN (COMPILER)  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  Khoa Kỹ thuật máy tính – Automat hữu hạn không tất định (NFA)  TS. Vũ Đức Lung – Automat hữu hạn tất định (DFA)  Email: lungvd@uit.edu.vn Khoa KTMT - UIT TS. Vũ Đức Lung 1 Khoa KTMT - UIT TS. Vũ Đức Lung 2 Sự giao tiếp giữa bộ phân tích từ vựng và bộ phân Vai trò của bộ phân tích từ vựng tích cú pháp  1. Token, mẫu, trị từ vựng: Khoa KTMT - UIT TS. Vũ Đức Lung 3 Khoa KTMT - UIT TS. Vũ Đức Lung 4 CÁC TÍNH CHẤT CỦA TOKEN CHỨA TẠM CHƯƠNG TRÌNH NGUỒN 1. Cặp bộ đệm:  Phân tích từ vựng phải có nhiệm vụ chọn thông tin có liên  Cấu tạo và Quy trình hoạt động : 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. Giải thuật: if p2 ở ranh giới một nửa bộ đệm then  Khi một token được chuyển đến bộ phân tích cú pháp nó sẽ begin có dạng. 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 5 Khoa KTMT - UIT TS. Vũ Đức Lung 6 1
  2. 05/04/2012 CHỨA TẠM CHƯƠNG TRÌNH NGUỒN Đặc tả token 2.Phương pháp cầm canh 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 {∈} Giải thuật: 2. a là ký hiệu thuộc ∑ , biểu thị cho tập {a} p2 := p2 + 1; 3. r và s là hai biểu thức chính quy, biểu thị cho L(r) và L(s) If p2 ^ eof then thì: if p2 ở ranh giới một nửa bộ đệm then a) (r)|(s) là biểu thức chính quy, biểu thị cho L(r)| L(s). begin chất đầy N kỳ hiệu nhập vào nửa bên phải bộ đệm ; b) (r)(s) là biểu thức chính quy, biểu thị cho L(r)L(s). p2 := p2 + 1 c) (r)* là biểu thức chính quy, biểu thị cho (L(r))*. end d) r là biểu thức chính quy, biểu thị cho L(r). 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 Khoa/* dừng KTMT sự phân tích từ vựng*/ TS. Vũ Đức Lung - UIT 7 Khoa KTMT - UIT TS. Vũ Đức Lung 8 Đặc tả token Nhận dạng token Cho văn phạm G: Thí dụ 3.1: Cho ∑ = {a, b} stmt -> if exp then stmt 1. a|b biểu thị cho tập {a,b} | if exp then stmt else stmt 2. (a|b) |(b|a) biểu thị cho tập {aa,ab,ba,bb} |∈ exp -> term relop term |term 3. a* biểu thị cho tập { ∈ ,a,aa,aaa,…..} term -> id |num 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 9 Khoa KTMT - UIT TS. Vũ Đức Lung 10 Bảng mẫu cho token Sơ đồ dịch  Sơ đồ dịch nhận dạng token relop Khoa KTMT - UIT TS. Vũ Đức Lung 11 Khoa KTMT - UIT TS. Vũ Đức Lung 12 2
  3. 05/04/2012 Automat hữu hạn Automat hữu hạn  Automat hữu hạn không tất định (NFA) Thí dụ: Cho NFA: 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ó: 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}. 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. Bảng truyền NFA nhận dạng (a|b)*abb VD: DFA nhận dạng ngôn ngữ (a|b)*abb Khoa KTMT - UIT TS. Vũ Đức Lung 13 Khoa KTMT - UIT TS. Vũ Đức Lung 14 Chuyển NFA sang DFA Giải thuật tính ∈-closure  Giải thuật 3.2: Xây dựng tập con (Tạo DFA từ NFA).  Đẩy tất cả các trạng thái trong T lên stack; Nhập: Cho NFA gọi là N.  Khởi tạo ∈-closure (T) cho T. Xuất: DFA gọi là D, nhận dạng cùng ngôn ngữ như NFA. While stack không rỗng do 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 Begin trạng thái của N. D mô phỏng đồng thời mọi chuyển động của N trên Lấy t là phần tử trên đỉnh ra khỏi stack. chuỗi nhập cho trước bằng các tác vụ: For mỗi trạng thái u với cạnh đi từ t đến u có tên do ∈-closure (S); ∈ -closure (T); move (T, a) 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 15 Khoa KTMT - UIT TS. Vũ Đức Lung 16 Giải thuật xây dựng tập con Ví dụ chuyển NFA thành DFA 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.  Dùng giải thuật 3.2 để xây dựng DFA tương đương cho NFA While có một trạng thái T chưa được đánh dấu trong D do sau (NFA nhận dạng (a|b)*abb). 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 17 Khoa KTMT - UIT TS. Vũ Đức Lung 18 3
  4. 05/04/2012 Tìm các trạng thái cho DFA Bảng truyền 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} Từ bảng này vẽ DFA E = {1,2,4,5,6,7,10} Khoa KTMT - UIT TS. Vũ Đức Lung 19 Khoa KTMT - UIT TS. Vũ Đức Lung 20 Từ biểu thức chính quy đến NFA Phương pháp Xây dựng NFA từ biểu thức chính quy Quy tắc: 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 21 Khoa KTMT - UIT TS. Vũ Đức Lung 22 Phương pháp 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 23 Khoa KTMT - UIT TS. Vũ Đức Lung 24 4
  5. 05/04/2012 Phương pháp 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 25 Khoa KTMT - UIT TS. Vũ Đức Lung 26 Automat hữu hạn Ví dụ  Automat hữu hạn không tất định (NFA)  Dùng giải thuật để xây dựng NFA cho biểu thức chính quy Cách vẽ NFA cơ bản r = (a|b)*abb Khoa KTMT - UIT TS. Vũ Đức Lung 27 Khoa KTMT - UIT TS. Vũ Đức Lung 28 Mô phỏng NFA Giải thuật  Nhập: NFA gọi là N được xây dựng theo giải thuật 3.3, S= ∈-closure({So}) chuỗi nhập x. x được kết thúc bằng eof, N có trạng thái bắt a = nextchar đầu s0 và tập trạng thái kết thúc F. While a eof then  Xuất: Giải thuật trả lời đúng nếu N chấp nhận x, ngược lại Begin trả lời sai. S = ∈-closure(move(s,a)) a = nextchar End if S ∩ F φ then write(đúng) Else write(sai) Khoa KTMT - UIT TS. Vũ Đức Lung 29 Khoa KTMT - UIT TS. Vũ Đức Lung 30 5
  6. 05/04/2012 Xây dựng DFA trực tiếp từ biểu thức chính Trạng thái quan trọng của NFA 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  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 từ biểu thức chính quy: thì chúng được đồng nhất. Xây dựng DFA trực tiếp từ biểu thức chính quy.  NFA được xây dựng theo cấu trúc Thompson có trạng thái Tối thiểu trạng thái của DFA. 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 31 Khoa KTMT - UIT TS. Vũ Đức Lung 32 Xây dựng DFA trực tiếp từ biểu thức chính Biểu thức chính quy gia tố quy  Biểu thức r# được gọi là biểu thức chính quy gia tố. Ký hiệu Xây dựng DFA trực tiếp từ biểu thức chính quy: # không thuộc tập các ký hiệu cơ bản của biểu thức chính  Vẽ cây phân tích quy r.  Tính các giá trị Nullable, First Post (FP), Last Post (LP).  Biểu diễn biểu thức chính qui gia tố bằng cây phân tích, sao  Lập bảng Follow Post (FLP) cho tên các lá là các ký hiệu cơ bản. Các nút trung gian là  Tìm tập các trạng thái, bảng truyền các toán tử dạng: cat, or hoặc star.  Vẽ DFA Tối thiểu trạng thái của DFA. Khoa KTMT - UIT TS. Vũ Đức Lung 33 Khoa KTMT - UIT TS. Vũ Đức Lung 34 Cây phân tích Cây phân tích  Cách vẽ cây phân tích r = (a|ba)(a|b)*ba#  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 35 Khoa KTMT - UIT TS. Vũ Đức Lung 36 6
  7. 05/04/2012 Các quy tắc để tính ba hàm nullable, Cây phân tích firstpos, lastpos  Cây phân tích r = (a|ba)(a|b)*ba# Khoa KTMT - UIT TS. Vũ Đức Lung 37 Khoa KTMT - UIT TS. Vũ Đức Lung 38 Các quy tắc để tính ba hàm nullable, NULLABLE firstpos, lastpos  NULLABLE: Quy tắc:  r = (a|ba)(a|b)*ba# - 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 39 Khoa KTMT - UIT TS. Vũ Đức Lung 40 FIRST POST (FP), LAST POST (LP) 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 41 Khoa KTMT - UIT TS. Vũ Đức Lung 42 7
  8. 05/04/2012 Bảng FLP 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 43 Khoa KTMT - UIT TS. Vũ Đức Lung 44 Bảng truyền 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 45 Khoa KTMT - UIT TS. Vũ Đức Lung 46 Xây dựng DFA trực tiếp từ biểu thức chính Tối thiểu số trạng thái của DFA quy  Khái niệm DFA đầy đủ, trạng thái chết d Xây dựng DFA trực tiếp từ biểu thức chính quy:  Chuỗi w phân biệt trạng thái s với trạng thái t  Vẽ cây phân tích  Giải thuật 3.6: Tối thiểu trạng thái của DFA  Tính các giá trị Nullable, First Post (FP), Last Post (LP). Nhập: DFA, gọi là M có S, Σ , s0, F. M là DFA đầy đủ.  Lập bảng Follow Post (FLP) 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.  Tìm tập các trạng thái, bảng truyền  Phương pháp:  Vẽ DFA 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. Tối thiểu trạng thái của DFA. 2. Áp dụng thủ tục (mô phỏng 3.6) để tạo ∏ new 3. Nếu ∏ new = ∏ thì ∏ final = ∏ tiếp tục bước 4, ngược lại lặp lại bước 2, với ∏ = ∏ new 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. Khoa KTMT - UIT TS. Vũ Đức Lung 47 Khoa KTMT - UIT TS. Vũ Đức Lung 48 8
  9. 05/04/2012 Tối thiểu số trạng thái của DFA Tối thiểu số trạng thái của DFA Mô phỏng 3.6: Giải thuật tạo ∏ new  Π={(E),(ABCD)} for với mỗi nhóm G của ∏ do begin  Xét (ABCD) trên sự truyền a - Chia G thành các nhóm nhỏ hơn sao cho hai trạng thái s và t của G – A → B : thuộc (ABCD) 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ả – B→B: 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→B: cùng một nhóm của ∏ – D → E : không thuộc (ABCD) ⇒ - Ta thay G bằng các nhóm nhỏ hơn vừa được tạo nên, cho chúng tách D riêng vào ∏ new  Tương tự trên b end  Π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 49 Khoa KTMT - UIT TS. Vũ Đức Lung 50 Thiết kế bộ sinh bộ phân tích từ vựng 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  Đặt tả Lex có dạng: quy phần mềm. 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 51 Khoa KTMT - UIT TS. Vũ Đức Lung 52 Mẫu so trùng trên cơ sở NFA BÀI TẬP MẪ MẪU NFA được tạo ra từ Bài Bài 01: 01: Xây dựng DFA trực tiếp từ biểu thức chính quy sau: sự đặc tả LEX 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 Bài 02: 02: Tương tự bài 01 nhưng xây dựng DFA từ NFA Khoa KTMT - UIT TS. Vũ Đức Lung 53 Khoa KTMT - UIT TS. Vũ Đức Lung 54 9
  10. 05/04/2012 Chương 5 : Phân tích cú pháp Nội dung:  Vai trò của bộ phân tích cú pháp TRÌNH BIÊN DỊCH  Xây dựng văn phạm cho ngôn ngữ lập trình (COMPILER)  Thừa số trái  Phân tích cú pháp từ trên xuống  Khoa Kỹ thuật máy tính  TS. Vũ Đức Lung  Email: lungvd@uit.edu.vn Khoa KTMT - UIT TS. Vũ Đức Lung 1 Khoa KTMT - UIT TS. Vũ Đức Lung 2 Vai trò của bộ phân tích cú pháp Vai trò của bộ phân tích cú pháp  Bộ phân tích cú pháp nhận chuỗi các token từ bộ phân tích từ vựng để tạo ra cấu trúc cú pháp của chương trình nguồn.  Tồn tại ba loại bộ phân tích cú pháp:  Phương pháp tổng quát: Cocke-Younger-Kasami và Earley.  Phương pháp thông dụng: Phân tích từ trên xuống hay phân tích từ dưới lên. Khoa KTMT - UIT TS. Vũ Đức Lung 3 Khoa KTMT - UIT TS. Vũ Đức Lung 4 Xây dựng văn phạm cho ngôn Xây dựng văn phạm cho ngôn ngữ lập trình ngữ lập trình  Loại bỏ sự không tường minh Ví dụ 1: Cho văn phạm sau stmt -> if exp then stmt | if exp then stmt else stmt | other Văn phạm này không tường minh khi phân tích phát biểu: if E1 then if E2 then S1 else S2 vì tồn tại hai cây cú pháp cho phát biểu. Khoa KTMT - UIT TS. Vũ Đức Lung 5 Khoa KTMT - UIT TS. Vũ Đức Lung 6 1
  11. 05/04/2012 Xây dựng văn phạm cho ngôn Xây dựng văn phạm cho ngôn ngữ lập trình ngữ lập trình  Loại bỏ sự không tường minh bằng cách sửa lại văn  Văn phạ phạmm đệ qui phạm: Khớp mỗi else với một then chưa khớp gần nhất  Cho văn phạm PNC G, với A là ký hiệu không kết thúc và trước đó. nếu tồn tại A → αAβ thì A là ký hiệu đệ qui và G là văn stmt -> matched-stmt | unmatched-stmt phạm đệ qui matched-stmt-> if exp then matched-stmt else matched-stmt | other  Nếu α = ∈, đệ qui trái unmatched-stmt -> if exp then stmt  Nếu β = ∈, đệ qui phải |if exp then matched-stmt else unmatched-stmt  Loại bỏ đệ quy trái:  Các phương pháp phân tích từ trên xuống không thể nào xử if E1 then if E2 then S1 else S2 lý văn phạm đệ qui trái, do đó cần phải dùng một cơ chế biến đổi tương đương để loại bỏ các đệ qui trái. Khoa KTMT - UIT TS. Vũ Đức Lung 7 Khoa KTMT - UIT TS. Vũ Đức Lung 8 Xây dựng văn phạm cho ngôn Xây dựng văn phạm cho ngôn ngữ lập trình ngữ lập trình  Ví dụ 2: Loại bỏ đệ quy trái cho văn phạm: E -> E + T | T E → TE’ T -> T * F | F E’ → +TE’ | ∈ F -> (E) | id T → FT’ T’ → *FT’ | ∈ Khoa KTMT - UIT TS. Vũ Đức Lung 9 Khoa KTMT - UIT TS. Vũ Đức Lung 10 Xây dựng văn phạm cho ngôn Xây dựng văn phạm cho ngôn ngữ lập trình ngữ lập trình  Giải thuật 4.1: Loại bỏ đệ quy trái Nhập: Văn phạm G không có vòng lặp hoặc luật sinh rỗng. Xuất: Văn phạm tương đương G’ không có đệ quy trái. Phương pháp: G’ không còn đệ quy trái nhưng có thể có luật sinh rỗng. Khoa KTMT - UIT TS. Vũ Đức Lung 11 Khoa KTMT - UIT TS. Vũ Đức Lung 12 2
  12. 05/04/2012 Xây dựng văn phạm cho ngôn ngữ lập trình Thừa số trái  Ví dụ 3: Áp dụng giải thuật 4.1 vào văn phạm sau để loại bỏ  Ví dụ 4: Có hai luật sinh: đệ quy trái. stmt -> if exp then stmt else stmt S ->Aa | b | if exp then stmt A -> Ac | Sd | ∈  Cả hai luật sinh đều có if dẫn đầu nên ta sẽ không biết chọn Các bước thực hiện: luật sinh nào để triển khai. Vì thế để làm chậm lại quyết - Sắp xếp: S, A định lựa chọn ta sẽ tạo ra thừa số trái. - Thay S vào A: A -> Ac | Aad | bd | ∈ - Loại bỏ đệ qui trái: S  Aa | b A  bdA’ | ∈A’ A’  cA’ | adA’ | ∈ Khoa KTMT - UIT TS. Vũ Đức Lung 13 Khoa KTMT - UIT TS. Vũ Đức Lung 14 Tạo văn phạm có thừa số trái Thừa số trái Nhập: Cho văn phạm G.  Ví dụ 5 : Cho văn phạm như sau Xuất: Văn phạm G’ có thừa số trái tương đương. S -> iEtS | iEtSeS | a Phương pháp: Tìm chuỗi dẫn đầu chung của các vế phải luật E -> b sinh, ví dụ:  Áp dụng giải thuật trên cho văn phạm phát biểu if, ta có văn phạm yếu tố trái như sau. γ là chuỗi không bắt đầu bởi α. Ta thay các luật trên bằng S -> iEtSS’ | a các luật S’-> eS | ∈ A -> αA’ | γ E -> b A’-> β1 | β2 | β3 … | βn Khoa KTMT - UIT TS. Vũ Đức Lung 15 Khoa KTMT - UIT TS. Vũ Đức Lung 16 Phân tích cú pháp từ trên xuống Phân tích cú pháp đệ quy đi xuống  Ví dụ 6 : Cho văn phạm G:  Phân tích cú pháp đệ quy. S -> cAd  Phân tích cú pháp không đệ quy. A -> ab | a  Các bước phân tích cú pháp từ trên xuống: Khoa KTMT - UIT TS. Vũ Đức Lung 17 Khoa KTMT - UIT TS. Vũ Đức Lung 18 3
  13. 05/04/2012 Phân tích cú pháp đoán Phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy  Loại bỏ đệ quy trái cho văn phạm mà ta thiết kế.  Để xây dựng sơ đồ ta sẽ tiến hành các bước sau đây:  Tạo văn phạm có thừa số trái nếu cần thiết.  Tạo trạng thái bắt đầu và kết thúc.  Sơ đồ dịch cho bộ phân tích đoán nhận trước.  Với mỗi luật sinh có dạng: Sơ đồ này có đặc điểm như sau: A -> X1X2…Xn ta xây dựng đường đi từ trạng thái bắt đầu  Mỗi ký hiệu không kết thúc có một sơ đồ. đến trạng thái kết thúc sao cho các cạnh có tên X1, X2,  Tên các cạnh là token và các ký hiệu không kết thúc. X3…Xn.  Sự truyền trên token sẽ được thực hiện nếu ký hiệu nhập trùng với token đó.  Nếu có sự truyền trên ký hiệu không kết thúcA thì ta thực hiện một lệnh gọi thủ tục A. Khoa KTMT - UIT TS. Vũ Đức Lung 19 Khoa KTMT - UIT TS. Vũ Đức Lung 20 Cơ chế hoạt động của bộ phân tích cú pháp đoán Bộ phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy Ví dụ 7: Tạo sơ đồ dịch cho văn phạm G Sơ đồ dịch của các ký hiệu E→E+T|T không kết thúc của G T→T*F|F F → (E) | id  Loại bỏ đệ quy trái trong văn phạm, ta được văn phạm tương đương sau : E -> TE’ E’-> + TE’| ∈ F T -> FT’ T’-> *FT’| ∈ F -> (E) | id  Sơ đồ dịch của các ký hiệu không kết thúc của G Ví dụ: phân tích câu id*(id + id) Khoa KTMT - UIT TS. Vũ Đức Lung 21 Khoa KTMT - UIT TS. Vũ Đức Lung 22 Bộ phân tích cú pháp đoán Giải thuật nhận trước đệ quy  Sơ đồ dịch của các ký hiệu không kết thúc của G đã được thu giảm Khoa KTMT - UIT TS. Vũ Đức Lung 23 Khoa KTMT - UIT TS. Vũ Đức Lung 24 4
  14. 05/04/2012 Phân tích cú pháp đoán nhận Phân tích cú pháp từ trên xuống trước không đệ quy  Phân tích cú pháp đệ quy.  Cấu tạo của bộ phân tích cú pháp:  Phân tích cú pháp không đệ quy. Khoa KTMT - UIT TS. Vũ Đức Lung 25 Khoa KTMT - UIT TS. Vũ Đức Lung 26 Hoạt động của bộ phân tích Giải thuật  Ở trạng thái bắt đầu, stack chỉ chứa các ký hiệu mục tiêu  Nhập: Chuỗi nhập w và bảng phân tích M cho văn phạm G. của văn phạm nằm trên $, trên đỉnh stack. Bảng phân tích  Xuất: Nếu w thuộc L(G), sẽ tạo ra dẫn xuất trái của w, M là ma trận. Hai ký hiệu X và a sẽ xác định hành vi của bộ ngược lại sẽ báo lỗi. phân tích. Bộ phân tích có ba hành vi như sau:  Phương pháp: Lúc đầu cấu hình của bộ phân tích là ($S, w$)  Nếu X = a = $ bộ phân tích dừng và báo thành công. với S là ký hiệu mục tiêu của G. Đặt ip (là con trỏ hoặc còn  Nếu X = a $ bộ phân tích sẽ đẩy X ra khỏi Stack dịch gọi là đầu đọc của bộ phân tích) vào ký hiệu nhập đầu tiên đầu đọc đến ký hiệu nhập kế tiếp. của w$.  Nếu X là ký hiệu không kết thúc bộ phân tích sẽ xét bảng ma trận để tìm luật sinh hoặt lỗi. Khoa KTMT - UIT TS. Vũ Đức Lung 27 Khoa KTMT - UIT TS. Vũ Đức Lung 28 Phân tích cú pháp đoán nhận Giải thuật trước không đệ quy  Ví dụ 8: Giả sử chúng ta có văn phạm G. E -> E + T | T T -> T *F | F F -> (E) | id Thực hiện loại bỏ đệ quy trái, nhận được G’: E -> TE’ E’-> +TE’ | € T -> FT’ T’ -> *FT’| € F -> (E) | id Khoa KTMT - UIT TS. Vũ Đức Lung 29 Khoa KTMT - UIT TS. Vũ Đức Lung 30 5
  15. 05/04/2012 Phân tích cú pháp đoán nhận Các bước phân tích cú pháp câu trước không đệ quy id + id *id Phân tích cú pháp cho câu nhập w = id + id * id bằng bảng phân tích M cho trước. Khoa KTMT - UIT TS. Vũ Đức Lung 31 Khoa KTMT - UIT TS. Vũ Đức Lung 32 Xây dựng bảng phân tích M Xây dựng bảng phân tích M  first(α) là tập các ký hiệu kết thúc a, dẫn đầu các chuỗi được  Các quy tắc tính follow(A) cho tất cả các ký hiệu không kết dẫn xuất từ α, α ->aγ. Nếu α -> € thì € thuộc first (α). thúc A.  follow(A) là tập các ký hiệu kết thúc a, xuất hiện ngay bên  Cho ký hiệu $ vào follow(S), S là ký hiệu mục tiêu, $ là ký hiệu kết phải A trong dạng câu. thúc chuỗi nhập.  Tồn tại luật A-> αBβ, tất cả các ký hiệu thuộc first(β) sẽ cho vào  Các quy tắc tính first(X) với X là ký hiệu văn phạm: follow(B) trừ €.  Nếu X là ký hiệu kết thúc thì first(X) = {X}  Tồn tại luật A-> αB hoặc A-> αBβ mà first(β) = {€} thì tất cả các  Nếu X->€ là luật sinh thì ta thêm € vào first(X) ký hiệu follow(A) sẽ cho vào follow(B).  Nếu X là ký hiệu không kết thúc và X ->X1X2X3..Xn là luật sinh thì cho a vào first(X) nếu với i thì a thuộc first(Xi) và ký hiệu € ở trong tất cả first(X1) …first(Xi-1) Khoa KTMT - UIT TS. Vũ Đức Lung 33 Khoa KTMT - UIT TS. Vũ Đức Lung 34 Xây dựng bảng phân tích M Xây dựng bảng phân tích M  Ví dụ 9: : Cho văn phạm G. E -> TE’ E’-> +TE’ | €  Nhập: Văn phạm G. T -> FT’ T’ ->*FT’| €  Xuất: Bảng phân tích M. F -> (E) | id  Phương pháp:  Toàn bộ các hàm first và follow của các ký hiệu văn phạm của G: first(E) = first(T) = first(F) = {(, id}  Với mỗi luật sinh A -> α hãy thực thi bước 2 và 3. first(E’) = {+, €}; first(T’) = {*, €}  Với mỗi ký hiệu kết thúc a thuộc first(α), thêm A -> α Tính follow: vào M[A, a]. Theo định nghĩa: F -> (E) => follow(E) = {$,)} follow(E) = follow(E’) = {$, )}  Nếu ký hiệu € thuộc first(α), thêm A -> € vào M[A, b] sao T -> FT’ => follow(T) = follow(T’) cho b thuộc follow(A). Nếu $ thuộc follow(A) thì thêm A - E -> TE’ => E -> FT’E’ (theo qtắc 2) => follow(T’) = first(E’) - € > € vào M [A, $]. mà first(E’) = {+, €} => follow(T’) = {+}. Ngoài ra theo qtắc 3 => follow(E) cho vào follow(T’) => follow(T) = follow(T’) = {+, $, )}  Những phần tử của bảng M trống, hãy đánh dấu lỗi. follow(F) = {*, +, $, )} Khoa KTMT - UIT TS. Vũ Đức Lung 35 Khoa KTMT - UIT TS. Vũ Đức Lung 36 6
  16. 05/04/2012 Văn phạm LL(1) Bảng phân tích M cho ví dụ  Ví dụ 10: Cho văn phạm G. S -> iEtSS’ | a S’-> eS | € E -> b first(S) = {i,a}, first(S’) = {e,€}, first(E) = {b} follow(S) = {e,$}, follow(S’) = {e,$}, follow(E) = {t} Khoa KTMT - UIT TS. Vũ Đức Lung 37 Khoa KTMT - UIT TS. Vũ Đức Lung 38 Khắc phục lỗi trong phân tích cú Bảng phân tích M cho thí dụ pháp đoán nhận trước  Nguyên nhân vì e vừa thuộc first(S’) = {e,€} vừa thuộc  Lỗi xuất hiện trong các trường hợp sau: follow(S’) = {e,$}. • Ký hiệu kết thúc trên stack không trùng với ký hiệu nhập đang được  Văn phạm không có phần tử nào của bảng phân tích M có đọc. nhiều hơn một trị thì được gọi là văn phạm LL(1). • A là ký hiệu không kết thúc trên đỉnh stack, a trên chuỗi nhập, được đọc, mà M[A, a] là trống.  Một số heuristics được áp dụng cho việc khắc phục lỗi. Khoa KTMT - UIT TS. Vũ Đức Lung 39 Khoa KTMT - UIT TS. Vũ Đức Lung 40 Khắc phục lỗi trong phân tích cú Khắc phục lỗi trong phân tích cú pháp đoán nhận trước pháp đoán nhận trước  Ta cho tất cả các ký hiệu trong follow(A) vào tập token  Ví dụ 11 : Cho văn phạm đồng bộ của A. Ta làm như vậy cho mỗi ký hiệu không kết thúc A.  Khi phân tích cú pháp có xuất hiện lỗi, chúng ta sẽ bỏ qua các ký hiệu kết thúc trên chuỗi nhập cho đến khi xuất hiện token trên chuổi nhập, thuộc follow(A) thì ta loại A ra khỏi stack.  Khi phân tích cú pháp có xuất hiện lỗi, và A ở trên stack thì bộ phân tích sẽ loại bỏ các ký hiệu nhập cho đến khi xuất hiện token trên chuổi nhập, thuộc first(A) Khoa KTMT - UIT TS. Vũ Đức Lung 41 Khoa KTMT - UIT TS. Vũ Đức Lung 42 7
  17. 05/04/2012 Phân tích M có ký hiệu khắc phục lỗi Phân tích M có ký hiệu khắc phục lỗi )id*+ id Khoa KTMT - UIT TS. Vũ Đức Lung 43 Khoa KTMT - UIT TS. Vũ Đức Lung 44 Ví dụ Phân tích cú pháp từ dưới lên  Phân tích cú pháp từ dưới lên được hiểu là phân tích đẩy và ) ) thu giảm (Shift-Reduce parsing) là phương pháp phân tích LR (L có nghĩa là bộ phân tích sẽ đọc ký hiệu nhập từ trái sang, R có nghĩa là bộ phân tích sẽ tạo ra dẫn xuất phải ngược) .  Ví dụ 12. Cho văn phạm G. S ->aABe A ->Abc|b B ->d Phân tích câu w = abbcde. Khoa KTMT - UIT TS. Vũ Đức Lung 45 Khoa KTMT - UIT TS. Vũ Đức Lung 46 Ví dụ Cây cú pháp được xây dựng từ dưới lên của Phân tích cú pháp từ dưới lên câu w = abbcde Tóm tắt các bước thu giảm như sau:  Quá trình thu giảm nếu theo chiều ngược lại thì đó chính là quá trình dẫn xuất phải.  Quá trình này đã sinh cây cú pháp của câu phân tích từ dưới lên. Khoa KTMT - UIT TS. Vũ Đức Lung 47 Khoa KTMT - UIT TS. Vũ Đức Lung 48 8
  18. 05/04/2012 Handle Cắt tỉa handle (Handle Pruning) Cắt tỉa handle là kỹ thuật dùng để tạo ra dẫn xuất phải nhất đảo  Handle của chuỗi ký tự là một chuỗi con, mà nó so trùng với ngược từ chuỗi ký hiệu kết thúc w mà ta muốn phân tích vế phải luật sinh và nếu chúng ta thu gọn nó thành vế trái Nếu w là câu văn phạm thì w = γn. Trong đó γn là dạng câu phải của luật sinh đó thì có thể dẫn đến ký hiệu chưa kết thúc bắt thứ n của dẫn xuất phải nhất mà ta chưa biết đầu.  Ở ví dụ Cây cú pháp được xây dựng từ dưới lên của câu w = abbcde Xây dựng dẫn xuất phải ngược từ w = γn. Ta tìm ßn trong γn sao cho ßn là vế phải luật sinh An -> ßn. Thay ßn trong γn bằng An, ta nhận được dạng câu thứ (n –1) là γn –1. Quá trình thu giảm cứ tiếp tục như vậy cho đến khi đạt được γ0 chỉ còn là một ký hiệu không kết thúc và là ký hiệu mục tiêu. Khoa KTMT - UIT TS. Vũ Đức Lung 49 Khoa KTMT - UIT TS. Vũ Đức Lung 50 Cắt tỉa handle (Handle Pruning) Phân tích cú pháp thứ tự yếu  Ví dụ cho văn phạm G  Văn phạm có tính chất: không có luật sinh nào có vế phải là chuỗi rỗng (A -> €) hoặc ở vế phải không có hai ký hiệu không kết thúc đứng kề nhau gọi là văn phạm thứ tự yếu. Khoa KTMT - UIT TS. Vũ Đức Lung 51 Khoa KTMT - UIT TS. Vũ Đức Lung 52 Phân tích cú pháp thứ tự yếu Bảng phân tích S-R cho văn phạm ở ví dụ 14 2. Hoạt động Ví dụ 14. Cho văn phạm của phát biểu gán < assign stmt > -> id = < exp > < exp > -> < exp > + < term > | < term > -> < term > * < factor > | < factor > < factor > -> id | (< exp >) Ký hiệu là ký hiệu mục tiêu. Khoa KTMT - UIT TS. Vũ Đức Lung 53 Khoa KTMT - UIT TS. Vũ Đức Lung 54 9
  19. 05/04/2012 Ví dụ phân tích câu id = id + id*id Giải thuật phân tích cú pháp thứ tự yếu Trạng Stack Input Action Lúc đầu stack trạng thái chỉ có ký hiệu $. Stack nhập chứa chuỗi nhập, thái được kết thúc bởi dấu $ ; c: = false ; repeat 0 $ id = id + id * id $ S if Ký hiệu mục tiêu ở trên đỉnh stack và ký hiệu $ ở đáy stack trạng thái, đồng thời stack nhập chỉ chứa $ then 1 $ id = id + id * id $ S c:=true /*phântíchthànhcông, câycúphápxâydựngxong*/ 2 $ id = Id + id * id $ S else begin -X ở trên đỉnh stack trạng thái, Y ở trên đỉnh stack nhập. 3 $ id = id + id * id $ R -Giả sửT là trị của phần tử S-R [X, Y]; if T là rỗng then error () 4 $ id = + id * id $ R 5 $ id = + id * id $ R 6 $ id = + id * id $ S Khoa KTMT - UIT TS. Vũ Đức Lung 55 Khoa KTMT - UIT TS. Vũ Đức Lung 56 Giải thuật phân tích cú pháp thứ tự yếu Giải thuật phân tích cú pháp thứ tự yếu else if T = R then else error () //Không tìm ra luật sinh If trên đỉnh stack có chứa vế phải của luật sinh nào đó then else begin begin (a) Giải tỏa Y ra khỏi stack nhập; Gọi A ->X1X2…Xn là luật sinh nào có vế phải dài nhất so trùng với chuỗi trên stack trạng thái: (b) Đẩy Y lên đỉnh stack trạng thái; (a) Giải tỏa X1 X2…Xn ra khỏi stack; (c) Tao nút mới tên Y trên cây cú pháp; (b) ThayA lên stack. end; (c) Tạo nút mới A trên cây cú pháp, có các con là end; X1X2…Xn until c; end Khoa KTMT - UIT TS. Vũ Đức Lung 57 Khoa KTMT - UIT TS. Vũ Đức Lung 58 Xây dựng bảng phân tích S-R Xây dựng bảng phân tích S-R Định nghĩa các quan hệ :  X = Y nếu và chỉ nếu tồn tại một luật sinh mà vế phải có  Chúng ta nói X Y…) như vậy X là biên trái của handle. Nhận xét: (Nếu khi phân tích cú pháp X trên đỉnh stack trạng VD: ( ) thái, Y trên stack nhập) X A  X •>Y thì bộ phân tích sẽ thực hiện một hành vi thu giảm. Và    id  X A => Y  X •>Y nếu và chỉ nếu tồn tại một luật sinh mà vế phải có dạng …AB. A sinh ra một chuỗi ký hiệu được kết thúc bằng X (A-> …X). B sinh ra một chuỗi được bắt đầu bằngY (B - >Y…), hoặc B = Y. Khoa KTMT - UIT TS. Vũ Đức Lung 59 Khoa KTMT - UIT TS. Vũ Đức Lung 60 10
  20. 05/04/2012 Nguyên tắc tính quan hệ 2. Nếu vế phải luật sinh có X nằm kề ngay Y về phía trái (…XY…) thì < exp > -> < exp > + < term > | X -> < term > * < factor > | < factor > 3. Nếu X Z1 …Zn thì X -> id | (< exp >)  Nguyên tắc tính quan hệ •> Ký hiệu là ký hiệu mục tiêu. 1. Tồn tại A •> $ với A là ký hiệu mục tiêu. 2. Nếu X Z1…Zn thì Zn •> Y 3. Nếu X •>Y và tồn tại một luật sinh X -> Z1…Zn thì Zn •> Y 4. Nếu X •>Y và tồn tại một luật sinh Y -> Z1…Zn thì X •> Z1 Khoa KTMT - UIT TS. Vũ Đức Lung 61 Khoa KTMT - UIT TS. Vũ Đức Lung 62 Tính quan hệ ) Áp dụng luật 2 ( => •>)) •>) Luật 3 (•>) mà -> => •>)) •>) Luật 3 ) •>) “” •>$ Luật 3 (stmt•>$ mà stmt-> id = < exp > => id = < exp >•>$) •>$ Luật 3 •>$ “” •>$ “” ) •>$ “” Khoa KTMT - UIT TS. Vũ Đức Lung 65 Khoa KTMT - UIT TS. Vũ Đức Lung 66 11
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2