Chương 5 : Phân tích cú pháp

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 5 : Phân tích cú pháp Nội dung: Vai trò của bộ phân tích cú pháp Xây dựng văn phạm cho ngôn ngữ lập trình  Thừa số trái  Phân tích cú pháp từ trên xuống Khoa KTMT - UIT TS. Vũ Đức Lung 3 Vai trò của bộ phân tích cú pháp Khoa KTMT - UIT TS. Vũ Đức Lung 4 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. • 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 5 Xây dựng văn phạm cho ngôn 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 6 Xây dựng văn phạm cho ngôn ngữ lập trình Khoa KTMT - UIT TS. Vũ Đức Lung 7 Xây dựng văn phạm cho ngôn ngữ lập trình  Loại bỏ sự không tường minh bằng cách sửa lại văn phạm: Khớp mỗi else với một then chưa khớp gần nhất trước đó. stmt -> matched-stmt | unmatched-stmt matched-stmt-> if exp then matched-stmt else matched-stmt | other unmatched-stmt -> if exp then stmt |if exp then matched-stmt else unmatched-stmt Khoa KTMT - UIT TS. Vũ Đức Lung 8 Xây dựng văn phạm cho ngôn ngữ lập trình  Văn phạm đệ qui  Cho văn phạm PNC G, với A là ký hiệu không kết thúc và nếu tồn tại A A thì A là ký hiệu đệ qui và G là văn phạm đệ qui  Nếu  = , đệ qui trái  Nếu  = , đệ qui phải  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ử 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 9 Xây dựng văn phạm cho ngôn ngữ lập trình Khoa KTMT - UIT TS. Vũ Đức Lung 10 Xây dựng văn phạm cho ngôn ngữ lập trình  Ví dụ 2: Loại bỏ đệ quy trái cho văn phạm: E -> E + T | T T -> T * F | F F -> (E) | id E  TE’ E’  +TE’ |  T  FT’ T’  *FT’ |  Khoa KTMT - UIT TS. Vũ Đức Lung 11 Xây dựng văn phạm cho ngôn 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 12 Xây dựng văn phạm cho ngôn ngữ lập trình Khoa KTMT - UIT TS. Vũ Đức Lung 13 Xây dựng văn phạm cho ngôn ngữ lập trình  Ví dụ 3: Áp dụng giải thuật 4.1 vào văn phạm sau để loại bỏ đệ quy trái. S ->Aa | b A -> Ac | Sd | € Khoa KTMT - UIT TS. Vũ Đức Lung 14 Thừa số trái  Ví dụ 4: Có hai luật sinh: stmt -> if exp then stmt else stmt | if exp then stmt  Cả hai luật sinh đều có if dẫn đầu nên ta sẽ không biết chọn luật sinh nào để triển khai. Vì thế để làm chậm lại quyết định lựa chọn ta sẽ tạo ra thừa số trái. Khoa KTMT - UIT TS. Vũ Đức Lung 15 Tạo văn phạm có thừa số trái Nhập: Cho văn phạm G. Xuất: Văn phạm G’ có thừa số trái tương đương. Phương pháp: Tìm chuỗi dẫn đầu chung của các vế phải luật sinh, ví dụ:  là chuỗi không bắt đầu bởi . Ta thay các luật trên bằng các luật A -> A’ |  A’-> 1 | 2 | 3 … | n Khoa KTMT - UIT TS. Vũ Đức Lung 16 Thừa số trái  Ví dụ 5 : Cho văn phạm như sau S -> iEtS | iEtSeS | a E -> b  Á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. S -> iEtSS’ | a S’-> eS |  E -> b Khoa KTMT - UIT TS. Vũ Đức Lung 17 Phân tích cú pháp từ trên xuống  Phân tích cú pháp đệ quy.  Phân tích cú pháp không đệ quy. Khoa KTMT - UIT TS. Vũ Đức Lung 18 Phân tích cú pháp đệ quy đi xuống  Ví dụ 6 : Cho văn phạm G: S -> cAd 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 19 Phân tích cú pháp đoán nhận trước đệ quy  Loại bỏ đệ quy trái cho văn phạm mà ta thiết kế.  Tạo văn phạm có thừa số trái nếu cần thiết.  Sơ đồ dịch cho bộ phân tích đoán nhận trước. Sơ đồ này có đặc điểm như sau:  Mỗi ký hiệu không kết thúc có một sơ đồ.  Tên các cạnh là token và các ký hiệu không kết thúc.  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 20 Phân tích cú pháp đoán nhận trước đệ quy  Để xây dựng sơ đồ ta sẽ tiến hành các bước sau đây:  Tạo trạng thái bắt đầu và kết thúc.  Với mỗi luật sinh có dạng: A -> X1X2…Xn ta xây dựng đường đi từ trạng thái bắt đầu đến trạng thái kết thúc sao cho các cạnh có tên X1, X2, X3…Xn. Khoa KTMT - UIT TS. Vũ Đức Lung 21 Cơ chế hoạt động của bộ phân tích cú pháp đoán nhận trước đệ quy Ví dụ 7: Tạo sơ đồ dịch cho văn phạm G E → E + T | T 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’| € 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 Khoa KTMT - UIT TS. Vũ Đức Lung 22 Bộ phân tích cú pháp đoán nhận trước đệ quy 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 23 Bộ phân tích cú pháp đoán 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 24 Giải thuật Khoa KTMT - UIT TS. Vũ Đức Lung 25 Phân tích cú pháp đoán nhận trước không đệ quy  Cấu tạo của bộ phân tích cú pháp: Khoa KTMT - UIT TS. Vũ Đức Lung 26 Hoạt động của bộ phân tích  Ở trạng thái bắt đầu, stack chỉ chứa các ký hiệu mục tiêu của văn phạm nằm trên $, trên đỉnh stack. Bảng phân tích M là ma trận. Hai ký hiệu X và a sẽ xác định hành vi của bộ phân tích. Bộ phân tích có ba hành vi như sau:  Nếu X = a = $ bộ phân tích dừng và báo thành công.  Nếu X = a $ bộ phân tích sẽ đẫy X ra khỏi Stack dịch đầu đọc đến ký hiệu nhập kế tiếp.  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 Giải thuật  Nhập: Chuỗi nhập w và bảng phân tích M cho văn phạm G.  Xuất: Nếu w thuộc L(G), sẽ tạo ra dẫn xuất trái của w, ngược lại sẽ báo lỗi.  Phương pháp: Lúc đầu cấu hình của bộ phân tích là ($S, w$) với S là ký hiệu mục tiêu của G. Đặt ip (là con trỏ hoặc còn gọi là đầu đọc của bộ phân tích) vào ký hiệu nhập đầu tiên của w$. Khoa KTMT - UIT TS. Vũ Đức Lung 28 Giải thuật Khoa KTMT - UIT TS. Vũ Đức Lung 29 Phân tích cú pháp đoán nhận 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 30 Phân tích cú pháp đoán nhận trước không đệ quy 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 Các bước phân tích cú pháp câu id + id *id Khoa KTMT - UIT TS. Vũ Đức Lung 32 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 dẫn xuất từ ,  ->a. Nếu  -> € thì € thuộc first ().  follow(A) là tập các ký hiệu kết thúc a, xuất hiện ngay bên phải A trong dạng câu.  Các quy tắc tính first(X) với X là ký hiệu văn phạm:  Nếu X là ký hiệu kết thúc thì first(X) = {X}  Nếu X->€ là luật sinh thì ta thêm € vào first(X)  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 Xây dựng bảng phân tích M  Các quy tắc tính follow(A) cho tất cả các ký hiệu không kết thúc A.  Cho ký hiệu $ vào follow(S), S là ký hiệu mục tiêu, $ là ký hiệu kết 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 follow(B) trừ €.  Tồn tại luật A-> B hoặc A-> B mà first() = {€} thì tất cả các ký hiệu follow(A) sẽ cho vào follow(B). Khoa KTMT - UIT TS. Vũ Đức Lung 34 Xây dựng bảng phân tích M  Ví dụ 9: : Cho văn phạm G. E -> TE’ E’-> +TE’ | € T -> FT’ T’ ->*FT’| € F -> (E) | id  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} first(E’) = {+, €}; first(T’) = {*, €} follow(E) = follow(E’) = {$, )} follow(T) = follow(T’) = {+, $, )} follow(F) = {*, +, $, )} Khoa KTMT - UIT TS. Vũ Đức Lung 35 Xây dựng bảng phân tích M  Nhập: Văn phạm G.  Xuất: Bảng phân tích M.  Phương pháp:  Với mỗi luật sinh A ->  hãy thực thi bước 2 và 3.  Với mỗi ký hiệu kết thúc a thuộc first(), thêm A ->  vào M[A, a].  Nếu ký hiệu € thuộc first(), thêm A -> € vào M[A, b] sao cho b thuộc follow(A). Nếu $ thuộc follow(A) thì thêm A - > € vào M [A, $].  Những phần tử của bảng M trống, hãy đánh dấu lỗi. Khoa KTMT - UIT TS. Vũ Đức Lung 36 Văn phạm LL(1)  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 Bảng phân tích M cho ví dụ Khoa KTMT - UIT TS. Vũ Đức Lung 38 Bảng phân tích M cho thí dụ  Nguyên nhân vì e vừa thuộc first(S’) = {e,€} vừa thuộc follow(S’) = {e,$}.  Văn phạm không có phần tử nào của bảng phân tích M có nhiều hơn một trị thì được gọi là văn phạm LL(1). Khoa KTMT - UIT TS. Vũ Đức Lung 39 Khắc phục lỗi trong phân tích cú pháp đoán nhận trước  Lỗi xuất hiện trong các trường hợp sau: • Ký hiệu kết thúc trên stack không trùng với ký hiệu nhập đang được đọc. • 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 40 Khắc phục lỗi trong phân tích 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 đồ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 Khắc phục lỗi trong phân tích cú pháp đoán nhận trước  Ví dụ 11 : Cho văn phạm Khoa KTMT - UIT TS. Vũ Đức Lung 42 Phân tích M có ký hiệu khắc phục lỗi Khoa KTMT - UIT TS. Vũ Đức Lung 43 Phân tích M có ký hiệu khắc phục lỗi Khoa KTMT - UIT TS. Vũ Đức Lung 44 Ví dụ Khoa KTMT - UIT TS. Vũ Đức Lung 45 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 46 Phân tích cú pháp từ dưới lên 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 Ví dụ Cây cú pháp được xây dựng từ dưới lên của câu w = abbcde Khoa KTMT - UIT TS. Vũ Đức Lung 48 Handle  Handle của chuỗi ký tự là một chuỗi con, mà nó so trùng với vế phải luật sinh và nếu chúng ta thu gọn nó thành vế trái của luật sinh đó thì có thể dẫn đến ký hiệu chưa kết thúc bắ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 Khoa KTMT - UIT TS. Vũ Đức Lung 49 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 ngược từ chuỗi ký hiệu kết thúc w mà ta muốn phân tích Nếu w là câu văn phạm thì w = n. Trong đó n là dạng câu phải thứ n của dẫn xuất phải nhất mà ta chưa biết 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 50 Cắt tỉa handle (Handle Pruning)  Ví dụ cho văn phạm G Khoa KTMT - UIT TS. Vũ Đức Lung 51 Phân tích cú pháp thứ tự yếu  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 52 Phân tích cú pháp thứ tự yếu 2. Hoạt động Ví dụ 14. Cho văn phạm của phát biểu gán -> id = -> + | -> * | -> id | () Ký hiệu là ký hiệu mục tiêu. Khoa KTMT - UIT TS. Vũ Đức Lung 53 Bảng phân tích S-R cho văn phạm ở ví dụ 14 Khoa KTMT - UIT TS. Vũ Đức Lung 54 Ví dụ phân tích câu id = id + id*id Trạng thái Stack Input Action 0 $ id = id + id * id $ S 1 $ id = id + id * id $ S 2 $ id = Id + id * id $ S 3 $ id = id + id * id $ R 4 $ id = + id * id $ R 5 $ id = + id * id $ R 6 $ id = + id * id $ R Khoa KTMT - UIT TS. Vũ Đức Lung 55 Giải thuật phân tích cú pháp thứ tự yếu Lúc đầu stack trạng thái chỉ có ký hiệu $. Stack nhập chứa chuỗi nhập, được kết thúc bởi dấu $ ; c: = false ; repeat 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 c:=true /*phântíchthànhcông, câycúphápxâydựngxong*/ else begin -X ở trên đỉnh stack trạng thái, Y ở trên đỉnh stack nhập. -Giả sửT là trị của phần tử S-R [X, Y]; if T là rỗng then error () Khoa KTMT - UIT TS. Vũ Đức Lung 56 Giải thuật phân tích cú pháp thứ tự yếu else if T = R then If trên đỉnh stack có chứa vế phải của luật sinh nào đó then begin 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: (a) Giải tỏa X1 X2…Xn ra khỏi stack; (b) ThayA lên stack. (c) Tạo nút mới A trên cây cú pháp, có các con là X1X2…Xn end Khoa KTMT - UIT TS. Vũ Đức Lung 57 Giải thuật phân tích cú pháp thứ tự yếu else error () //Không tìm ra luật sinh else begin (a) Giải tỏa Y ra khỏi stack nhập; (b) Đẩy Y lên đỉnh stack trạng thái; (c) Tao nút mới tên Y trên cây cú pháp; end; end; until c; Khoa KTMT - UIT TS. Vũ Đức Lung 58 Xây dựng bảng phân tích S-R Định nghĩa các quan hệ :  Chúng ta nói X <•Y nếu và chỉ nếu tồn tại một luật sinh mà vế phải có dạng …XA với A là ký hiệu không kết thúc và sinh ra một chuỗi bắt đầu bằng Y (A ->Y…) như vậy X là biên trái của handle.  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.  Ở đây có hai trường hợp xảy ra trong quá trình tìm các mối quan hệ cho cặp (X, Y): Y là ký hiệu kết thúc và Y là ký hiệu không kết thúc Khoa KTMT - UIT TS. Vũ Đức Lung 59 Xây dựng bảng phân tích S-R  X = Y nếu và chỉ nếu tồn tại một luật sinh mà vế phải có dạng …XY... Nhận xét: (Nếu khi phân tích cú pháp X trên đỉnh stack trạng thái, Y trên stack nhập)  X •>Y thì bộ phân tích sẽ thực hiện một hành vi thu giảm.  X <=•Y thì bộ phân tích sẽ thực hiện một hành vi đẩy. Khoa KTMT - UIT TS. Vũ Đức Lung 60 Nguyên tắc tính quan hệ <=•  Nguyên tắc tính quan hệ <=• 1. Tồn tại $ <=• A với A là ký hiệu mục tiêu của văn phạm cho trước. 2. Nếu vế phải luật sinh có X nằm kề ngay Y về phía trái (…XY…) thì X <=•Y 3. Nếu X Z1 …Zn thì X <=•Z1  Nguyên tắc tính quan hệ •> 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 Xây dựng bảng phân tích S-R  Ví dụ mẫu -> id = -> + | -> * | -> id | () Ký hiệu là ký hiệu mục tiêu. Khoa KTMT - UIT TS. Vũ Đức Lung 62 Tính quan hệ <=• Biểu thức Diễn giải $$<=•stmt) id<=•= Áp dụng luật 2 (do id và = nằm kề nhau nên id<=•=) = Áp dụng luật 2 (do = và nằm kề nhau nên =) kề +) + Tương tự (luật 2) <=•* “” * “” ( “” <=•) “” Khoa KTMT - UIT TS. Vũ Đức Lung 63 Tính quan hệ <=• $ Luật 3 ($ id = => $<= id = < exp >) = Áp dụng luật 3 (= mà -> => = ) = Luật 3 (= mà ->) = Do factor-> =( + + +<=• ( * *<=• ( ( ( ( (<=• ( Khoa KTMT - UIT TS. Vũ Đức Lung 64 Tính quan hệ •> Biểu thức Diễn giải stmt•>$ Áp dụng luật 1 (stmt là ký hiệu mục tiêu=> stmt•>$) •>+ Áp dụng luật 2 (do -> =>•>+) •>+ Luật 3 (•>+ mà -> => •>+) •>+ Luật 3 (•>+ mà -> => •>+) ) •>+ Luật 3 •>* Luật 2 (-> => •>*) •>* Luật 3 ) •>* “” •>) Áp dụng luật 2 (-> => •>)) •>) Luật 3 (•>) mà -> => •>)) •>) Luật 3 ) •>) “” •>$ Luật 3 (stmt•>$ mà stmt-> id = => id = < exp >•>$) •>$ Luật 3 •>$ “” •>$ “” ) •>$ “” Khoa KTMT - UIT TS. Vũ Đức Lung 65 Bảng phân tích S-R Xây dựng bảng phân tích Phần tiêu đề dòng: chứa tất cả các ký hiệu, phần tiêu đề cột chứa các ký hiệu kết thúc Các ô giao giữa tiêu đề dòng và tiêu đề cột: Nếu tiêu đề dòng và tiêu đề cột thuộc luật <=• thì điền S (tiêu đề dòng<=•tiêu đề cột) Nếu tiêu đề dòng và tiêu đề cột thuộc luật •> thì điền R Khoa KTMT - UIT TS. Vũ Đức Lung 66 Bộ phân tích cú pháp LR Các tính chất của phương pháp phân tích LR:  Bộ phân tích LR có thể nhận dạng được cấu trúc cú pháp của các ngôn ngữ lập trình do văn phạm phi ngữ cảnh tạo ra.  Phương pháp LR là phương pháp tổng quát nhất của phương pháp phân tích đẩy và thu giảm, không bị quay lui từ trước đến giờ.  Lớp văn phạm được phân tích bằng phương pháp LR là lớp văn phạm cha, bao trùm lớp văn phạm được phân tích bởi phương pháp đoán nhận trước.  Bộ phân tích có khả năng phát hiện lỗi sớm nhất khi nó rà đến ký hiệu nhập từ trái sang phải. Khoa KTMT - UIT TS. Vũ Đức Lung 67 Cấu tạo bộ phân tích cú pháp LR Khoa KTMT - UIT TS. Vũ Đức Lung 68 Hoạt động  Stack được dùng để chứa chuỗi ký hiệu có dạng s0X1s1X2…Xmsm, với sm nằm trên đỉnh stack, Xi được gọi là ký hiệu văn phạm, si là trạng thái. Cặp(si, Xi) sẽ xác định một trị được lưu chứa trong bảng phân tích. Bảng phân tích gồm hai phần biểu thị bởi hàm action và goto.  Cấu hình (configuration) của bộ phân tích LR là một cặp (nội dung stack nội dung còn lại của chuỗi nhập)  Ví dụ: (s0X1s1…Xisi…Xmsm, aiai+1…an$). Khoa KTMT - UIT TS. Vũ Đức Lung 69 Phân tích cú pháp LR  Nhập: chuỗi nhập w, bảng phân tích action goto của văn phạm G.  Xuất: nếu w thuộc L (G), nó tạo ra sự phân tích từ dưới lên. Ngược lại, bộ phân tích sẽ báo lỗi.  Phương pháp: Thời điểm ban đầu stack có trạng thái s0. Chuỗi w$ nằm trên bộ đệm nhập. Bộ phân tích đặt đầu đọc (con trỏ ip) vào ký hiệu nhập đầu tiên của w. Khoa KTMT - UIT TS. Vũ Đức Lung 70 Phân tích cú pháp LR Khoa KTMT - UIT TS. Vũ Đức Lung 71 Ví dụ Cho văn phạmG (1) E -> E + T (2) E -> T (3) T -> T * F (4) T -> F (5) F -> (E) (6) F -> id Phân tích câu w = id *id + i