Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 4: Phân tích cú pháp

t thúc a ∈ FIRST(α), thêm A→ α vào M[A,a]. 3. Nếu ε ∈ FIRST(α) thì đưa luật sinh A→ α vào M[A,b] với mỗi ký hiệu kết thúc b ∈ FOLLOW(A). Nếu ε ∈ FIRST(α) và $ ∈ FOLLOW(A) thì đưa luật sinh A→ α vào M[A,$]. 4. Ô còn trống trong bảng tương ứng với lỗi (error). Ví dụ 4.9: Áp dụng thuật toán trên cho văn phạm trong ví dụ 4.6. Ta thấy: Luật sinh E → TE' : Tính FIRST(TE') = FIRST(T) = {(,id} ⇒ M[E,id] và M[E,( ] chứa luật sinh E → TE' Luật sinh E'→ + TE' : Tính FIRST(+TE') = FIRST(+) = {+} ⇒ M[E',+] chứa E' → +TE' 79 Luật sinh E' → ε : Vì ε ∈ FIRST(E') và FOLLOW(E') = { ), $ } ⇒ E → ε nằm trong M[E',)] và M[E',$] Luật sinh T'→ * FT' : FIRST(* FT') = {* } ⇒ T' → * FT' nằm trong M[T',*] Luật sinh T' → ε: Vì ε ∈ FIRST(T') và FOLLOW(T') = {+, ), $} ⇒ T' → ε nằm trong M[T', +] , M[T', )] và M[T',$] Luật sinh F→ (E) ; FIRST((E)) = { ( } ⇒ F → ( E) nằm trong M[F, (] Luật sinh F → id ; FIRST(id) = {id} ⇒ F → id nằm trong M[F, id] Bảng phân tích cú pháp M của văn phạm được xây dựng như trong hình 4.8. 5. Văn phạm LL(1) Giải thuật 4.4 có thể áp dụng cho bất kỳ văn phạm G nào để sinh ra bảng phân tích M. Tuy nhiên, có những văn phạm (đệ quy trái hoặc mơ hồ) thì trong bảng phân tích M sẽ có thể có những ô đa trị (có chưá nhiều hơn 1 luật sinh). Ví dụ 4.10: Xét văn phạm sau: S → iE t S S' | a S' → eS | ε E → b Bảng phân tích cú pháp M của văn phạm như sau : Ký hiệu kết thúc Ký hiệu chưa kết thúc a b e i T $ S S→ a S→ iEtSS' S' S → ε S' → eS S'→ε E E→b Hình 4.9 - Bảng phân tích cú pháp M cho văn phạm ví dụ 4.10 Ðây là một văn phạm mơ hồ và sự mơ hồ này được thể hiện qua việc chọn luật sinh khi gặp ký hiệu e (else). Ô tại vị trí M [S', e] được gọi là ô đa trị. Một văn phạm mà bảng phân tích M không có các` ô đa trị được gọi là văn phạm LL(1) với ý nghĩa như sau : L: Left-to-right parse (mô tả hành động quét chuỗi nhập từ trái sang phải) L: Leftmost-derivation (biểu thị việc sinh ra một dẫn xuất trái cho chuỗi nhập) 80 1: 1-symbol lookahead (tại mỗi một bước, đầu đọc chỉ đọc trước được một token để thực hiện các quyết định phân tích cú pháp) Văn phạm LL(1) có một số tính chất đặc biệt. Không có văn phạm mơ hồ hay đệ quy trái nào có thể là LL(1). Người ta đã chứng minh rằng một văn phạm G là LL(1) nếu và chỉ nếu mỗi khi A → α | β là 2 luật sinh phân biệt của G, các điều kiện sau đây sẽ đúng: 1. Không có một ký hiệu kết thúc a nào mà cả α và β đều dẫn xuất ra các chuỗi bắt đầu bằng a. 2. Tối đa chỉ có α hoặc chỉ có β có thể dẫn xuất ra chuỗi rỗng. 3. Nếu β ⇒* ε thì α không dẫn xuất được chuỗi nào bắt đầu bằng một ký hiệu kết thúc thuộc tập FOLLOW(A). Rõ ràng văn phạm trong ví dụ 4.5 cho các biểu thức số học là LL(1), nhưng văn phạm trong ví dụ 4.10 là văn phạm mô hình hóa câu lệnh if - then - else không phải là LL(1). Vấn đề đặt ra bây giờ là làm thế nào để giải quyết các ô đa trị? Một phương án khả thi là biến đổi văn phạm bằng cách loại bỏ mọi đệ quy trái, rồi tạo yếu tố trái khi có thể được với mong muốn sẽ sinh ra một văn phạm với bảng phân tích cú pháp không chứa ô đa trị nào. Nhưng cũng có một số văn phạm mà không có cách gì biến đổi thành văn phạm LL(1). Nói chung, không có quy tắc tổng quát nào để biến một ô đa trị thành ô đơn trị mà không làm ảnh hưởng đến ngôn ngữ đang được nhận dạng bởi bộ phân tích cú pháp. Khó khăn chính khi dùng một bộ phân tích cú pháp dự đoán là việc viết một văn phạm cho ngôn ngữ nguồn. Việc loại bỏ đệ quy trái và tạo yếu tố trái tuy dễ thực hiện nhưng chúng biến đổi văn phạm trở thành khó đọc và khó dùng cho các mục đích biên dịch. 6. Phục hồi lỗi trong phân tích dự đoán Một lỗi sẽ được tìm thấy trong quá trình phân tích dự đoán khi: 1. Ký hiệu kết thúc trên đỉnh Stack không phù hợp với token kế tiếp trong dòng nhập. Hoặc : 2. Trên đỉnh Stack là ký hiệu chưa kết thúc A, token trong dòng nhập là a nhưng M[A,a] rỗng. Phục hồi lỗi theo phương pháp panic_mode là bỏ qua các ký hiệu trong dòng nhập cho đến khi gặp một phần tử trong tập hợp các token đồng bộ (synchronizing token). Tính hiệu quả của phương pháp này tùy thuộc vào cách chọn tập hợp các token đồng bộ. Một số heuristics có thể là: 1. Ta có thể đưa tất cả các ký hiệu trong FOLLOW(A) vào trong tập hợp token đồng bộ cho ký hiệu chưa kết thúc A. 2. FOLLOW(A) cũng chưa phải là một tập hợp các token đồng bộ cho A. Ví dụ, các lệnh của C kết thúc bởi ; (dấu chấm phẩy ). Nếu một lệnh thiếu dấu ; thì từ khóa của lệnh kế tiếp sẽ bị bỏ qua. Thông thường ngôn ngữ có cấu trúc 81 phân cấp, ví dụ biểu thức nằm trong một lệnh, lệnh nằm trong một khối lệnh, v.v. Chúng ta có thể thêm vào tập hợp đồng bộ của một cấu trúc những ký hiệu mà nó bắt đầu cho một cấu trúc cao hơn. Ví dụ, ta có thể thêm các từ khoá bắt đầu cho các lệnh vào tập đồng bộ cho ký hiệu chưa kết thúc sinh ra biểu thức. 3. Nếu chúng ta thêm các phần tử của FIRST(A) vào tập đồng bộ cho ký hiệu chưa kết thúc A thì quá trình phân tích có thể hòa hợp với A nếu một ký hiệu trong FIRST(A) xuất hiện trong dòng nhập. Ví dụ 4.11: Sử dụng các ký hiệu kết thúc trong tập FOLLOW làm token đồng bộ hóa hoạt động khá hữu hiệu khi phân tích cú pháp cho các biểu thức trong văn phạm ví dụ 4.6. FOLLOW(E) = FOLLOW(E') = { $, )} FOLLOW(T) = FOLLOW(T') = { +,$, )} FOLLOW(F) = {*,+, $, )} Bảng phân tích M cho văn phạm này được thêm vào các ký hiệu đồng bộ "synch", lấy từ tập FOLLOW của các ký hiệu chưa kết thúc - xác định các token đồng bộ : Ký hiệu kết thúc Ký hiệu chưa kết thúc id + * ( ) $ E E→TE' E→TE' synch synch E' E'→ +TE' E'→ ε E'→ ε T T→ FT' synch T→ FT' synch synch T' T'→ ε T'→ *FT' T'→ ε T'→ ε F F→ id synch synch F→ (E) synch synch Hình 4.10 - Bảng phân tích cú pháp M phục hồi lỗi Bảng này được sử dụng như sau: 9 Nếu M[A,a] là rỗng thì bỏ qua token a. 9 Nếu M[A,a] là "synch" thì lấy A ra khỏi Stack nhằm tái hoạt dộng quá trình phân tích. 9 Nếu một token trên đỉnh Stack không phù hợp với token trong dòng nhập thì lấy token ra khỏi Stack. Chẳng hạn, với chuỗi nhập : + id * + id, bộ phân tích cú pháp và cơ chế phục hồi lỗi thực hiện như sau : STACK INPUT OUTPUT $ E $ E $ E' T + id * + id $ id * + id $ id * + id $ error, nhảy qua + E → T E' T → F T' 82 $ E' T' F $ E' T' id $ E' T' $ E' T' F * $ E' T' F $ E' T' $ E' $ E' T + $ E' T $ E' T' F $ E' T' id $ E' T' $ E' $ id * + id $ id * + id $ * + id $ * + id $ + id $ + id $ + id $ + id $ id $ id $ id $ $ $ $ F → id T' → * F T' error, M[F,+] = synch pop F T → ε E' → + T E' T' → F T' F→ id T' → ε E' → ε IV. PHÂN TÍCH CÚ PHÁP TỪ DƯỚI LÊN Phần này sẽ giới thiệu một kiểu phân tích cú pháp từ dưới lên tổng quát gọi là phân tích cú pháp Shift -Reduce. Một dạng dễ cài đặt của nó gọi là phân tích cú pháp thứ bậc toán tử (Operator - Precedence parsing) cũng sẽ được trình bày và cuối cùng, một phương pháp tổng quát hơn của kỹ thuật Shift - Reduce là phân tích cú pháp LR (LR parsing) sẽ được thảo luận. 1. Bộ phân tích cú pháp Shift - Reduce Phân tích cú pháp Shift - Reduce cố gắng xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Ðây có thể xem là quá trình thu gọn (reduce) một chuỗi w thành một ký hiệu bắt đầu của văn phạm. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế phải của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế trái của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng. Ví dụ 4.12: Cho văn phạm: S → a A B e A→ A b c | b B → d Câu abbcde có thể thu gọn thành S theo các bước sau: a b b c d e a A b c d e a A d e 83 a A B e S Thực chất đây là một dẫn xuất phải nhất đảo ngược như sau : S ⇒ rm aABe ⇒rm aAde ⇒rm aAbcde ⇒rm abbcde (Dẫn xuất phải nhất là chuỗi các thay thế ký hiệu chưa kết thúc phải nhất) 2. Handle Handle của một chuỗi là một chuỗi con hợp với vế phải của 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ụ 4.13: Xét văn phạm sau: E → E + E E → E * E E → (E) E→ id Chuỗi dẫn xuất phải : E ⇒rm E + E (các handle được gạch dưới) ⇒rm E + E * E ⇒rm E + E * id3 ⇒rm E + id2 * id3 ⇒rm id1 + id2 * id3 3. Cắt tỉa handle (Handle Pruning) Handle pruning 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à chúng ta muốn phân tích. Nếu w là một câu của 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à chúng ta chưa biết. S ⇒ γ0 ⇒rm γ1 ⇒rm γ2 .. .. ⇒rmγn-1 ⇒rm γn = w Ðể xây dựng dẫn xuất này theo thứ tự ngược lại, chúng ta tìm handle βn trong γn và thay thế βn bởi An (An là vế trái của luật sinh An → βn) để được dạng câu phải thứ n -1 là γn-1. Quy luật trên cứ tiếp tục. Nếu ta có một dạng câu phải γ0 = S thì sự phân tích thành công. Ví dụ 4.14: Với văn phạm: E → E + E | E * E | (E) | id Và câu nhập: id1 + id2 * id3 , ta có các bước thu gọn câu nhập thành ký hiệu bắt đầu E như sau : 84 Dạng câu phải Handle Luật thu gọn id1 + id2 * id3 E + id2 * id3 E + E * id3 E + E * E E + E E id1 id2 id3 E * E E + E E → id E → id E → id E → E * E E → E + E Thành công 4. Cài đặt bộ phân tích cú pháp Shift - Reduce Có hai vấn đề cần phải giải quyết nếu chúng ta dùng kỹ thuật phân tích cú pháp này. Thứ nhất là định vị chuỗi con cần thu gọn trong dạng câu dẫn phải, và thứ hai là xác định luật sinh nào sẽ được dùng nếu có nhiều luật sinh chứa chuỗi con đó ở vế phải. Cấu tạo: Dùng 1 Stack để lưu các ký hiệu văn phạm. Dùng 1 bộ đệm nhập INPUT để giữ chuỗi nhập cần phân tích w. Ta dùng ký hiệu $ để đánh dấu đáy Stack và xác định cuối chuỗi nhập. Hoạt động: 1. Khởi đầu thì Stack rỗng và w nằm trong bộ đệm input. 2. Bộ phân tích đẩy các ký hiệu nhập vào trong Stack cho đến khi một handle β nằm trên đỉnh Stack. 3. Thu gọn β thành vế trái của một luật sinh nào đó. 4. Lặp lại bước 2 và 3 cho đến khi gặp một lỗi hoặc Stack chứa ký hiệu bắt đầu và bộ đệm input rỗng (thông báo kết thúc thành công). Ví dụ 4.15: Với văn phạm E → E + E | E * E | (E) | id và câu nhập id1 + id2 * id3 Quá trình phân tích cú pháp sẽ thực hiện như sau: STACK INPUT ACTION $ $ id1 $ E $ E + $ E + id2 $ E + E $ E + E * $ E + E * id3 id1 + id2 * id3 $ + id2 * id3 $ + id2 * id3 $ id2 * id3 $ * id3 $ * id3 $ id3 $ $ Đẩy Thu gọn bởi E → id Đẩy Đẩy Thu gọn bởi E → id Đẩy Đẩy 85 $ E + E * E $ E + E $ E $ $ $ Thu gọn bởi E → id Thu gọn bởi E → E * E Thu gọn bởi E → E + E Chấp nhận V. PHÂN TÍCH CÚ PHÁP THỨ BẬC TOÁN TỬ Lớp văn phạm có tính chất không có luật sinh nào có vế phải là ε hoặc có hai ký hiệu chưa kết thúc nào nằm kế nhau có thể dễ dàng xây dựng bộ phân tích cú pháp Shift- Reduce hiệu quả theo lối thủ công. Một trong những kỹ thuật phân tích dễ cài đặt nhất gọi là phân tích cú pháp thứ bậc toán tử. 1. Quan hệ thứ tự ưu tiên Bảng định nghĩa 3 quan hệ thứ bậc được cho như sau : Quan hệ Ý nghĩa a <• b a = b a •> b a có độ ưu tiên thấp hơn b a có độ ưu tiên bằng b a có độ ưu tiên cao hơn b y Hình 4.11 - Các quan hệ thứ bậc toán tử 2. Sử dụng quan hệ thứ tự ưu tiên của toán tử Các quan hệ ưu tiên này giúp việc xác định handle. Trước hết, ta dựa vào các quy tắc sau để xây dựng bảng quan hệ ưu tiên giữa các ký hiệu kết thúc. 1. Nếu toán tử θ1 có độ ưu tiên cao hơn θ2 thì θ1 •> θ2 và θ2 <• θ1; (E + E * E + E thì handle là E * E). 2. Nếu toán tử θ1 có độ ưu tiên bằng θ2 thì : . θ1 •> θ2 và θ2 •> θ1 nếu các toán tử là kết hợp trái. . θ1 <• θ2 và θ2 <• θ1 nếu các toán tử là kết hợp phải. Ví dụ 4.16: Toán tử + và - có độ ưu tiên bằng nhau và kết hợp trái nên: + •> + ; + •> - ; - •> - ; - •> + Phép toán ↑ kết hợp phải nên ↑ <• ↑ E - E + E ⇒ handle là E - E E ↑ E ↑ E ⇒ handle là E ↑ E (phần cuối) Ví dụ 4.17: Với chuỗi nhập id + id * id 86 Ta có bảng quan hệ thứ bậc các toán tử như sau : id + * $ id + * $ <• <• <• •> •> •> <• •> <• •> <• •> •> •> Sử dụng $ để đánh dấu cuối chuỗi và $ <• θ, ∀θ. Ta có chuỗi với các quan hệ thứ bậc được chèn vào là : $ + * $ Chẳng hạn, <• được chèn vào giữa $ bên trái và id bởi vì <• là mục ở hàng $ và cột id. Handle có thể tìm thấy thông qua quá trình sau : • 1. Duyệt chuỗi từ trái sang phải cho đến khi gặp •> đầu tiên (trong ví dụ của chúng ta là •> sau id đầu tiên). 2. Sau đó, duyệt ngược lại (hướng sang trái), vượt qua các = (nếu có) cho đến khi gặp a <• (trong ví dụ, chúng ta quét ngược về đến $). 3. Handle là chuỗi chứa mọi ký hiệu ở bên trái •> đầu tiên và bên phải <• được gặp trong bước (2), chứa luôn cả các ký hiệu chưa kết thúc xen giữa hoặc bao quanh (trong ví dụ, handle là id đầu tiên). Với ví dụ trên, sau khi thu gọn id thành E ta được $ E + E * E $. ƒ Bỏ các ký hiệu chưa kết thúc E ta được $ + * $. ƒ Thêm các quan hệ ưu tiên ta được $ $ . Ðiều này chứng tỏ handle là E * E được thu gọn thành E. Vì các ký hiệu chưa kết thúc không ảnh hưởng gì đến việc phân tích cú pháp, nên chúng ta không cần phải phân biệt chúng. ‰ Giải thuật 4.5: Phân tích cú pháp thứ bậc toán tử Input: Chuỗi nhập w và bảng các quan hệ thứ bậc. Output: Nếu w là chuỗi chuẩn dạng đúng thì cho ra một cây phân tích cú pháp. Ngược lại, thông báo lỗi. Phương pháp: Khởi đầu, Stack chứa ký hiệu $ và bộ đệm chứa câu nhập dạng w$. Ðặt con trỏ ip trỏ tới ký hiệu đầu tiên của w$ ; Repeat forever If $ nằm ở đỉnh Stack và ip chỉ đến $ then return 87 Else begin If a <• b hoặc a = b then begin Ðẩy b vào Stack; Dịch ip chỉ đến ký hiệu tiếp theo trong bộ đệm; end Else if a •> b then /* thu gọn */ Repeat Lấy ký hiệu trên đỉnh Stack ra; Until Ký hiệu kết thúc trên đỉnh Stack có quan hệ <• với ký hiệu kết thúc vừa lấy ra; else error ( ) End VI. BỘ PHÂN TÍCH CÚ PHÁP LR Phần này giới thiệu một kỹ thuật phân tích cú pháp từ dưới lên khá hiệu quả, có thể sử dụng để phân tích một lớp rộng các văn phạm phi ngữ cảnh. Kỹ thuật này được gọi là phân tích cú pháp LR(k). L (left - to - right): Duyệt chuỗi nhập từ trái sang phải. R (rightmost derivation): Xây dựng chuỗi dẫn xuất phải nhất đảo ngược. k : Số lượng ký hiệu nhập được xét tại mỗi thời điểm dùng để đưa ra quyết định phân tích. Khi không đề cập đến k, chúng ta hiểu ngầm là k = 1. Các ưu điểm của bộ phân tích cú pháp LR - Bộ phân tích cú pháp LR có thể được xây dựng để nhận biết hầu như tất cả các ngôn ngữ lập trình được tạo ra bởi văn phạm phi ngữ cảnh. - Phương pháp phân tích cú pháp LR là phương pháp tổng quát của phương pháp chuyên thu gọn không quay lui. Nó có thể được cài đặt có hiệu quả như các phương pháp chuyên thu gọn khác. - Lớp văn phạm có thể dùng phương pháp LR là một lớp rộng lớn hơn lớp văn phạm có thể sử dụng phương pháp dự đoán. - Bộ phân tích cú pháp LR cũng có thể xác định lỗi cú pháp nhanh ngay trong khi duyệt dòng nhập từ trái sang phải. Nhược điểm chủ yếu của phương pháp này là cần phải thực hiện quá nhiều công việc để xây dựng được bộ phân tích cú pháp LR theo kiểu thủ công cho một văn phạm ngôn ngữ lập trình điển hình. 88 1. Thuật toán phân tích cú pháp LR OUTPUT a1 sm STACK Chương trình phân tích cú pháp LR action INPUT ... ai ... an $ goto Xm sm-1 Xm-1 . . . s0 Hình 4.12 - Mô hình bộ phân tích cú pháp LR • Stack lưu một chuỗi s0X1s1X2s2 ... Xmsm trong đó sm nằm trên đỉnh Stack. Xi là một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack bên dưới nó. • Bảng phân tích bao gồm 2 phần: hàm action và hàm goto. 9 action[sm, ai] có thể có một trong 4 giá trị : 1. shift s: đẩy s, trong đó s là một trạng thái. 2. reduce A→ β: thu gọn bằng luật sinh A→ β. 3. accept: Chấp nhận 4. error: Báo lỗi 9 Goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra một trạng thái. Cấu hình (configuration) của một bộ phân tích cú pháp LR là một cặp thành phần, trong đó, thành phần đầu là nội dung của Stack, phần sau là chuỗi nhập chưa phân tích: (s0X1s1X2s2 ... Xmsm, ai ai+1 ... an $) Với sm là ký hiệu trên đỉnh Stack, ai là ký hiệu nhập hiện tại, cấu hình có được sau mỗi dạng bước đẩy sẽ như sau : 1. Nếu action[sm, ai] = Shift s : Thực hiện phép đẩy để được cấu hình mới: (s0X1s1X2s2 ... Xmsm ais, ai +1 ... an $) Phép đẩy làm cho s nằm trên đỉnh Stack, ai+1 trở thành ký hiệu hiện hành. 2. Nếu action [sm, ai] = Reduce(A → β) thì thực hiện phép thu gọn để được cấu hình: (s0X1s1X2s2 ... Xm - ism - i As, ai ai +1 .... an $) 89 Trong đó, s = goto[sm - i, A] và r là chiều dài số lượng các ký hiệu của β. Ở đây, trước hết 2r phần tử của Stack sẽ bị lấy ra, sau đó đẩy vào A và s. 3. Nếu action[sm, ai] = accept: quá trình phân tích kết thúc. 4. Nếu action[sm, ai] = error: gọi thủ tục phục hồi lỗi. ‰ Giải thuật 4.6 : Phân tích cú pháp LR Input: Một chuỗi nhập w, một bảng phân tích LR với hàm action và goto cho văn phạm G. Output: Nếu w ∈ L(G), đưa ra một sự phân tích dưới lên cho w . Ngược lại, thông báo lỗi. Phương pháp: Khởi tạo s0 là trạng thái khởi tạo nằm trong Stack và w$ nằm trong bộ đệm nhập. Ðặt ip vào ký hiệu đầu tiên của w$; Repeat forever begin Gọi s là trạng thái trên đỉnh Stack và a là ký hiệu được trỏ bởi ip; If action[s, a] = Shift s' then begin Ðẩy a và sau đó là s' vào Stack; Chuyển ip tới ký hiệu kế tiếp; end else if action[s, a] = Reduce (A → β) then begin Lấy 2 * | β| ký hiệu ra khỏi Stack; Gọi s' là trạng thái trên đỉnh Stack; Ðẩy A, sau đó đẩy goto[s', A] vào Stack; Xuất ra luật sinh A → β; end else if action[s, a] = accept then return else error ( ) end Ví dụ 4.18: Hình sau trình bày các hàm action và goto của bảng phân tích cú pháp LR cho văn phạm của các biểu thức số học dưới đây với các toán tử 2 ngôi + và * (1) E→ E + T Action Goto (2) E→ T Trạng thái id + * ( ) $ E T F (3) T → T * F 0 s5 s4 1 2 3 (4) T→ F 1 s6 acc 90 (5) F → (E) 2 r2 s7 r2 r2 (6) F → id 3 r4 r4 r4 r4 4 s5 s4 8 2 3 Ý nghĩa: 5 r6 r6 r6 r6 si : chuyển trạng thái i 6 s5 s4 9 3 ri : thu gọn bởi luật sinh i 7 s5 s4 1 0 acc: accept (chấp nhận) 8 s6 s11 error : khoảng trống 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Hình 4.13 - Bảng phân tích cú pháp SLR cho văn phạm ví dụ Với chuỗi nhập id * id + id, các bước chuyển trạng thái trên Stack và nội dung bộ đệm nhập được trình bày như sau : STACK INPUT ACTION (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) 0 0 id 5 0 F 3 0 T 2 0 T 2 * 7 0 T 2 * 7 id 5 0 T 2 * 7 F 10 0 T 2 0 E 1 0 E 1 + 6 0 E 1 + 6 id 5 0 E 1 + 6 F 3 0 E 1 + 6 T 9 0 E 1 id * id + id $ * id + id $ * id + id $ * id + id $ id + id $ + id $ + id $ + id $ + id $ id $ $ $ $ $ Shift Reduce by F→ id Reduce by T → F Shift Shift Reduce by F → id Reduce by T → T * F Reduce by E→ T Shift Shift Reduce by F → id Reduce by T → F Reduce by E→ E + T Thành công 2. Văn phạm LR Làm thế nào để xây dựng được một bảng phân tích cú pháp LR cho một văn phạm đã cho? Một văn phạm có thể xây dựng được một bảng phân tích cú pháp cho nó được gọi là văn phạm LR. Có những văn phạm phi ngữ cảnh không thuộc lọai LR, nhưng 91 nói chung là ta có thể tránh được những văn phạm này trong hầu hết các kết cấu ngôn ngữ lập trình điển hình. Có một sự khác biệt rất lớn giữa các văn phạm LL và LR. Ðể cho một văn phạm là LR(k), chúng ta phải có khả năng nhận diện được sự xuất hiện của vế phải của một luật sinh ứng với k ký hiệu đọc trước. Ðòi hỏi này ít khắt khe hơn so với các văn phạm LL(k). Vì vậy, các văn phạm LR có thể mô tả được nhiều ngôn ngữ hơn so với các văn phạm LL. 3. Xây dựng bảng phân tích cú pháp SLR Phần này trình bày cách xây dựng một bảng phân tích cú pháp LR từ văn phạm. Chúng ta sẽ đưa ra 3 phương pháp khác nhau về tính hiệu quả cũng như tính dễ cài đặt. Phương pháp thứ nhất được gọi là "LR đơn giản" (Simple LR - SLR), là phương pháp "yếu" nhất nếu tính theo số lượng văn phạm có thể xây dựng thành công bằng phương pháp này, nhưng đây lại là phương pháp dễ cài đặt nhất. Ta gọi bảng phân tích cú pháp tạo ra bởi phương pháp này là bảng SLR và bộ phân tích cú pháp tương ứng là bộ phân tích cú pháp SLR, với văn phạm tương đương là văn phạm SLR. a. Mục (Item): Cho một văn phạm G, mục LR(0) văn phạm là một luật sinh của G với một dấu chấm mục tại vị trí nào đó trong vế phải. Ví dụ 4.19: Luật sinh A → XYZ có 4 mục như sau : A → •XYZ A → X• YZ A → XY• Z A → XYZ• Luật sinh A → ε chỉ tạo ra một mục A → • b. Văn phạm tăng cường (Augmented Grammar) Giả sử G là một văn phạm với ký hiệu bắt đầu S, ta thêm một ký hiệu bắt đầu mới S' và luật sinh S' → S để được văn phạm mới G' gọi là văn phạm tăng cường. c. Phép toán bao đóng (Closure) Giả sử I là một tập các mục của văn phạm G thì bao đóng closure(I) là tập các mục được xây dựng từ I theo qui tắc sau: 1. Tất cả các mục của I được thêm cho closure(I). 2. Nếu A → α • Bβ ∈ closure(I) và B → γ là một luật sinh thì thêm B → • γ vào closure(I) nếu nó chưa có trong đó. Lặp lại bước này cho đến khi không thể thêm vào closure(I) được nữa. Ví dụ 4.20: Xét văn phạm tăng cường của biểu thức: E' → E E → E + T | T T → T * F | F 92 F → (E) | id Nếu I là tập hợp chỉ gồm văn phạm { E'→ • E } thì closure(I) bao gồm: E' → • E (Luật 1) E → • E + T (Luật 2) E → • T (Luật 2) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) Chú ý rằng: Nếu một B - luật sinh được đưa vào closure(I) với dấu chấm mục nằm ở đầu vế phải thì tất cả các B - luật sinh đều được đưa vào. d. Phép toán Goto Goto(I, X), trong đó I là một tập các mục và X là một ký hiệu văn phạm là bao đóng của tập hợp các mục A → αX•β sao cho A → α•Xβ ∈ I. Cách tính goto(I, X): 1. Tạo một tập I' = ∅. 2. Nếu A → α•Xβ ∈ I thì đưa A→ αX•β vào I', tiếp tục quá trình này cho đến khi xét hết tập I. 3. Goto(I, X) = closure(I') Ví dụ 4.21: Giả sử I = { E' → E•, E → E • + T }. Tính goto (I, +) ? Ta có I' = { E→ E + • T } ( goto (I, +) = closure(I') bao gồm các mục : E → E + • T (Luật 1) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) e. Giải thuật xây dựng họ tập hợp các mục LR(0) của văn phạm G' Gọi C là họ tập hợp các mục LR(0) của văn phạm tăng cường G'. Ta có thủ tục xây dựng C như sau : Procedure Item (G') begin C := closure({ S' → •S}); 93 Repeat For Với mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto (I, X) ≠ ∅ và goto(I, X) ∉ C do Thêm goto(I, X) vào C; Until Không còn tập hợp mục nào có thể thêm vào C; end; Ví dụ 4.22: Với văn phạm tăng cường G' của biểu thức trong ví dụ 4.20 : Ta xây dựng họ tập hợp mục C của văn phạm như sau: Closure({E'→ E}): I0 : E'→ • E E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id Goto (I0, E) I1: E'→ E • E → E • + T Goto (I0, T) I2: E → T • T → T • * F Goto (I0, F) I3: T → F • Goto (I0, ( ) I4: F → (• E) E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id Goto (I0, id) I5: F → id • Goto (I1, +) I6: E → E + • T T → • T * F T → • F F → • (E) F → • id Goto (I2, *) I7: T → T* • F F → • (E) F → • id Goto (I4, E) I8: T → (E •) E → E • + T Goto (I6,T) I9: E → E + T • T → T • * F Goto (I7,F) I10: T → T * F • Goto (I8,) ) I11: F → (E) • f. Thuật toán xây dựng bảng phân tích SLR 94 ‰ Giải thuật 4.7: Xây dựng bảng phân tích SLR Input: Một văn phạm tăng cường G' Output: Bảng phân tích SLR với hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, ..., In }, họ tập hợp các mục LR(0) của G'. 2. Trạng thái i được xây dựng từ Ii .Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu A → α • aβ ∈ Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j". Ở đây a là ký hiệu kết thúc. 2.2. Nếu A → α• ∈ Ii thì action[i, a] = "reduce (A → α)", ∀a ∈ FOLLOW(A). Ở đây A không phải là S' 2.3. Nếu S' → S• ∈ Ii thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là SLR(1). Giải thuật sinh ra bộ phân tích cú pháp sẽ thất bại trong trường hợp này. 3. Với mọi ký hiệu chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto [i, A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là “error” 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa S’→ • S Ví dụ 4.23: Ta xây dựng bảng phân tích cú pháp SLR cho văn phạm tăng cường G' trong ví dụ 4.20 trên. E' → E E → E + T | T T → T * F | F F → (E) | id (0) E'→ E (1) E → E + T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → id 1. C = { I0, I1, ... I11 } 2. FOLLOW(E) = {+, ), $} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 4.22, ta thấy: Trước tiên xét tập mục I0 : Mục F → • (E) cho ra action[0, (] = "shift 4", và mục F → • id cho action[0, id] = "shift 5". Các mục khác trong I0 không sinh được hành động nào. Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho action[1, +] = "shift 6". Kế đến xét I2 : E → T • 95 T → T • * F Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] = "reduce (E ( T)". Mục thứ hai làm cho action[2,*] = "shift 7". Tiếp tục theo cách này, ta thu được bảng phân tích cú pháp SLR đã trình bày trong hình 4.13. Bảng phân tích xác định bởi giải thuật 4.7 gọi là bảng SLR(1) của văn phạm G, bộ phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng SLR(1) gọi là văn phạm SLR(1). Mọi văn phạm SLR(1) đều không mơ hồ. Tuy nhiên có những văn phạm không mơ hồ nhưng không phải là SLR(1). Ví dụ 4.24: Xét văn phạm G với tập luật sinh như sau: S → L = R S → R L → * R L → id R → L Ðây là một văn phạm không mơ hồ nhưng không phải là văn phạm SLR(1). Họ tập hợp các mục C bao gồm: I0 : S' → • S S → • L = R S → • R L → • * R L → • id R → • L I1 : S' → S • I2 : S → L • = R R → L • I3 : S → R • I4 : L → * • R R → • L L → • * R L → • id I5 : L → id • I6 : S → L = • R R → • L L → • * R L → • id I7 : L → * R• I8 : R → L• I9 : S → L = R• 96 Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = ∈ FOLLOW(R), nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" ⇒ Có sự đụng độ tại action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1). 4. Xây dựng bảng phân tích cú pháp LR chính tắc (Canonical LR Parsing Table) a. Mục LR(1) của văn phạm G là một cặp dạng [A → α•β, a], trong đó A → αβ là luật sinh, a là một ký hiệu kết thúc hoặc $. b. Thuật toán xây dựng họ tập hợp mục LR(1) ‰ Giải thuật 4.8: Xây dựng họ tập hợp các mục LR(1) Input : Văn phạm tăng cường G’ Output: Họ tập hợp các mục LR(1). Phương pháp: Các thủ tục closure, goto và thủ tục chính Items như sau: Function Closure (I); begin Repeat For Mỗi mục [A → α•Bβ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi ký hiệu kết thúc b ∈ FIRST (βa) sao cho [B → • γ, b] ∉ I do Thêm [B → •γ, b] vào I; Until Không còn mục nào có thể thêm cho I được nữa; return I; end; Function goto (I, X); begin Gọi J là tập hợp các mục [A → αX•β, a] sao cho [A → α•Xβ, a]∈ I; return Closure(J); end; Procedure Items (G'); begin C := Closure ({[S' → •S, $]}) Repeat For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do 97 Thêm goto(I, X) vào C; Until Không còn tập các mục nào có thể thêm cho C; end; Ví dụ 4.25: Xây dựng bảng LR chính tắc cho văn phạm tăng cường G' có chứa các luật sinh như sau : S' Æ S (1) S Æ L = R (2) S Æ R (3) L Æ * R (4) L Æ id (5) R Æ L Trong đó: tập ký hiệu chưa kết thúc ={S, L, R} và tập ký hiệu kết thúc {=, *, id, $} I0 : S' → • S, $ Closure (S' Æ •S, $) S → • L = R, $ S → • R, $ L → • * R, = | $ L → • id, = | $ R → • L, $ Goto (I0,S) I1 : S' → S •, $ Goto (I0, L) I2 : S → L • = R, $ R → L •, $ Goto (I 0,R) I3: S → R •, $ Goto (I0,*) I4: L → * • R, = | $ R Æ • L, = | $ L → • * R, = | $ R → • id, = | $ Goto (I0,id) I5 : L → id •, = | $ Goto (I4,R) I7 : L → * R•, = | $ Goto (I4, L) I8 : R→ L•, = | $ Goto (I6,R) I9 : S → L = R•, $ Goto (I6,L) I10 : R → L•, $ Goto (I6,*) I11 : L → * • R, $ R → • L, $ L → • * R, $ R → • id, $ Goto (I6, id) I12 : L → id •, $ Goto (I11,R) I13 : R → * R•, $ Goto (I11,L) ≡ I10 98 Goto (I2,=) I6 : S → L = • R, $ R → • L, $ L → • * R, $ L → • id, $ Goto (I11,*) ≡ I11 Goto (I11,id) ≡ I12 c. Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc ‰ Giải thuật 4.9: Xây dựng bảng phân tích LR chính tắc Input: Văn phạm tăng cường G' Output: Bảng LR với các hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, .... In } là họ tập hợp mục LR(1) 2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu [A → α • aβ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift j". Ở đây a phải là ký hiệu kết thúc. 2.2. Nếu [A → α •, a]∈ Ii , A ∈ S' thì action[i, a] = " reduce (A → α)" 2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept". Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không phải là LR(1) và giải thuật sẽ thất bại. 3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là "error" 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa [S' → •S,$] Bảng phân tích xác định bởi giải thuật 4.9 gọi là bảng phân tích LR(1) chính tắc của văn phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1). Ví dụ 4.26: Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên Action Goto Trạng thái = * id $ S L R 0 s4 s5 1 2 3 1 acc 2 s6 r5 3 r2 4 s4 s5 8 7 5 r4 99 6 s11 s12 10 9 7 r3 8 r5 9 r1 10 r5 11 s11 s12 10 13 12 r4 13 r3 Hình 4.14 - Bảng phân tích cú pháp LR chính tắc Mỗi văn phạm SLR(1) là một văn phạm LR(1), nhưng với một văn phạm SLR(1), bộ phân tích cú pháp LR chính tắc có thể có nhiều trạng thái hơn so với bộ phân tích cú pháp SLR cho văn phạm đó. 5. Xây dựng bảng phân tích cú pháp LALR Phần này giới thiệu phương pháp cuối cùng để xây dựng bộ phân tích cú pháp LR - kỹ thuật LALR (Lookahead-LR), phương pháp này thường được sử dụng trong thực tế bởi vì những bảng LALR thu được nói chung là nhỏ hơn nhiều so với các bảng LR chính tắc và phần lớn các kết cấu cú pháp của ngôn ngữ lập trình đều có thể được diễn tả thuận lợi bằng văn phạm LALR. a. Hạt nhân (core) của một tập hợp mục LR(1) 1. Một tập hợp mục LR(1) có dạng {[ A → α•β, a]}, trong đó A → αβ là một luật sinh và a là ký hiệu kết thúc có hạt nhân (core) là tập hợp {A → α •β}. 2. Trong họ tập hợp các mục LR(1) C = { I0, I1, ..., In } có thể có các tập hợp các mục có chung một hạt nhân. Ví dụ 4.27: Trong ví dụ 4.25, ta thấy trong họ tập hợp mục có một số các mục có chung hạt nhân là : I4 và I11 I5 và I12 I7 và I13 I8 và I10 b. Thuật toán xây dựng bảng phân tích cú pháp LALR ‰ Giải thuật 4.10: Xây dựng bảng phân tích LALR Input: Văn phạm tăng cường G' Output: Bảng phân tích LALR Phương pháp: 1. Xây dựng họ tập hợp các mục LR(1) C = { I0, I1, ..., In } 100 2. Với mỗi hạt nhân tồn tại trong tập các mục LR(1) tìm trên tất cả các tập hợp có cùng hạt nhân này và thay thế các tập hợp này bởi hợp của chúng. 3. Ðặt C' = { I0, I1, ..., Im } là kết quả thu được từ C bằng cách hợp các tập hợp có cùng hạt nhân. Action tương ứng với trạng thái i được xây dựng từ Ji theo cách thức như giải thuật 4.9. Nếu có một sự đụng độ giữa các action thì giải thuật xem như thất bại và ta nói văn phạm không phải là văn phạm LALR(1). 4. Bảng goto được xây dựng như sau Giả sử J = I1 ∪ I2 ∪ ... ∪ Ik. Vì I1, I2, ... Ik có chung một hạt nhân nên goto (I1,X), goto (I2,X), ..., goto (Ik,X) cũng có chung hạt nhân. Ðặt K bằng hợp tất cả các tập hợp có chung hạt nhân với goto (I1,X) ⇒ goto(J, X) = K. Ví dụ 4.28: Với ví dụ trên, ta có họ tập hợp mục C' như sau C' = {I0, I1, I2, I3, I411, I512, I6, I713, I810, I9 } I0 : S' → • S, $ closure (S' Æ •S, $) : S → • L = R, $ S → • R, $ L → • * R, = L → • id, = R → • L, $ I1 = Goto (I0,S) : S' → S •, $ I2 = Goto (I0, L) : S → L • = R, $ R → L •, $ I3 = Goto (I 0,R) : S → R • I411 = Goto (I0,*), Goto (I6,*) : L → * • R, = | $ R → • L, = | $ L → • * R, = | $ R → • id, = | $ I512 = Goto (I0,id), Goto (I6,id) : L → id •, = | $ I6 = Goto(I2,=) : S → L = • R,$ R → • L, $ L → • * R, $ L → • id, $ I713 = Goto(I411, R) : L → * R•, = | $ I810 = Goto(I411, L), Goto(I6, L): R → L•, = | $ I9 = Goto(I6, R) : S → L = R•, $ Ta có thể xây dựng bảng phân tích cú pháp LALR cho văn phạm như sau: 101 Action Goto State = * id $ S L R 0 s411 s512 1 2 3 1 acc 2 s6 3 r2 411 810 713 512 r4 r4 6 s411 s512 810 9 713 r3 r3 810 r5 r5 9 r1 Hình 4.15 - Bảng phân tích cú pháp LALR Bảng phân tích được tạo ra bởi giải thuật 4.10 gọi là bảng phân tích LALR cho văn phạm G. Nếu trong bảng không có các action đụng độ thì văn phạm đã cho gọi là văn phạm LALR(1). Họ tập hợp mục C' được gọi là họ tập hợp mục LALR(1). VII. SỬ DỤNG CÁC VĂN PHẠM MƠ HỒ Như chúng ta đã nói trước đây rằng mọi văn phạm mơ hồ đều không phải là LR. Tuy nhiên có một số văn phạm mơ hồ lại rất có ích cho việc đặc tả và cài đặt ngôn ngữ. Chẳng hạn văn phạm mơ hồ cho kết cấu biểu thức đặc tả được một cách ngắn gọn và tự nhiên hơn bất kỳ một văn phạm không mơ hồ nào khác. Văn phạm mơ hồ còn được dùng trong việc tách biệt các kết cấu cú pháp thường gặp cho quá trình tối ưu hóa. Với một văn phạm mơ hồ, chúng ta có thể đưa thêm các luật sinh mới vào văn phạm. Mặc dù các văn phạm là đa nghĩa, trong mọi trường hợp, chúng ta sẽ đưa thêm các quy tắc khử mơ hồ (disambiguating rule), để chỉ cho phép chọn một cây phân tích cú pháp cho mỗi một câu nhập. Theo cách này, đặc tả ngôn ngữ về tổng thể vẫn là đơn nghĩa. 1. Sử dụng độ ưu tiên và tính kết hợp của các toán tử để giải quyết đụng độ. Xét văn phạm của biểu thức số học với hai toán tử + và * : E Æ E + E | E * E | (E) |id (1) Ðây là một văn phạm mơ hồ vì nó không xác định độ ưu tiên và tính kết hợp của các tóan tử + và *. Trong khi đó ta có văn phạm tương đương không mơ hồ cho biểu thức có dạng như sau: 102 E Æ E + T | T T Æ T * F | F (2) F Æ (E) | id Văn phạm này xác định rằng + có độ ưu tiên thấp hơn * và cả hai toán tử đều kết hợp trái. Tuy nhiên có 2 lý do để chúng ta sử dụng văn phạm (1) chứ không phải là (2): 1. Dễ dàng thay đổi tính kết hợp và độ ưu tiên của + và * mà không phá hủy các luật sinh và số các trạng thái của bộ phân tích (như ta sẽ thấy sau này). 2. Bộ phân tích cho văn phạm (2) sẽ mất thời gian thu gọn bởi các luật sinh E Æ T và T Æ F. Hai luật sinh này không nói lên được tính kết hợp và độ ưu tiên. Nhưng với văn phạm (1) thì làm thế nào để tránh sự đụng độ? Trước hết chúng ta hãy thành lập bộ sưu tập C các tập mục LR(0) của văn phạm tăng cường của nó. I0: E'→ • E E → • E + E E → • E * E E → • (E) E → • id Goto(I0,E) I1: E'→ E • E → E • + E E → E • * E Goto(I0,() I2: E → (• E) E → • E + E E → • E* E E → • (E) E → • id Goto(I0,id) I3: E → id• Goto(I1,+ ) I4: E → E + • E E → • E + E E → • E * E E → • ( E) Goto(I2,E) I6: E'→ (E •) E → E • + E E → E • * E Goto(I2,() ≡ I2 Goto(I2,id) ≡ I3 Goto(I4,E) I7: E → E + E • E → E • + E E → E • * E Goto(I4,( ) ≡ I2 Goto(I4,id) ≡ I3 Goto(I5,E) I8: E → E * E • E → E • + E E → E • * E Goto(I5,() ≡ I2 Goto(I5,id) ≡ I3 Goto(I6,)) I9: E → (E) • Goto(I6,+) ≡ I4 Goto(I6,*) ≡ I5 103 E → • id Goto(I1,*) I5: E → E * • E E → • E + E E → • E * E E → • ( E) E → • id Goto(I7,+) ≡ I4 Goto(I7,*) ≡ I5 Goto(I8,+) ≡ I4 Goto(I8,*) ≡ I5 Bảng phân tích SLR đụng độ được xây dựng như sau : Action Goto Trạng thái id + * ( ) $ E 0 s3 s2 1 1 s4 s5 acc 2 s3 6 3 r4 r4 r4 r4 4 s3 s2 7 5 s3 s2 8 6 s4 s5 s9 7 s4 / r1 s5 / r1 r1 r1 8 s4 / r2 s5 / r2 r2 r2 9 r3 r3 r3 r3 Hình 4.16 - Bảng phân tích cú pháp SLR đụng độ Nhìn vào bảng SLR trong hình trên, ta thấy có sụ đụng độ tại action [7, +] và action [7,*]; action [8, +] và action [8,*]. Chúng ta sẽ giải quyết sự đụng độ này bằng quy tắc kết hợp và độ ưu tiên của các toán tử. Xét chuỗi nhập id + id * id Stack Input Output 0 0 id 3 0 E 1 0 E 1 + 4 0 E 1 + 4 id 3 0 E 1 + 4 E 7 id + id * id $ + id * id $ + id * id $ id * id $ * id $ * id $ Shift s3 Reduce by E Æ id Shift s4 Shift s3 Reduce by E Æ id 104 Bây giờ đến ô đụng độ action[7, *] nên lấy r1 hay s5? Lúc này chúng ta đã phân tích qua phần chuỗi id * id. Nếu ta chọn r1 tức là thu gọn bởi luật sinh E Æ E + E, có nghĩa là chúng ta đã thực hiện phép cộng trước. Do vậy nếu ta muốn tóan tử * có độ ưu tiên cao hơn + thì phải chọn s5. Nếu chuỗi nhập là id + id + id thì quá trình phân tích văn phạm dẫn đến hình trạng hiện tại là : Stack Output 0 E 1 + 4 E 7 + id $ Sẽ phải xét action [7, +] nên chọn r1 hay s4? Nếu ta chọn r1 tức là thu gọn bởi luật sinh E Æ E + E tức là + thực hiện trước hay toán tử + có kết hợp trái => action [7, +] = r1 Một cách tương tự nếu ta quy định phép * có độ ưu tiên cao hơn + và phép * kết hợp trái thì action [8, *] = r2 vì * kết hợp trái (xét chuỗi id * id * id). Action [8,+] = r2 vì toán tử * có độ ưu tiên cao hơn + (trường hợp xét chuỗi id * id + id) Sau khi đã giải quyết được sự đụng độ đó ta có được bảng phân tích SLR đơn giản hơn bảng phân tích của văn phạm tương đương (2) (chỉ sử dụng 10 trạng thái thay vì 12 trạng thái). Tương tự, ta có thể xây dựng bảng phân tích LR chính tắc và LALR cho văn phạm (1). 2. Giải quyết trường hợp văn phạm mơ hồ IF THEN ELSE Xét văn phạm cho lệnh điều kiện: Stmt Æ if expr then stmt else stmt | if expr then stmt | other Ðể đơn giản ta viết i thay cho if expr then, S thay cho stmt, e thay cho else và a thay cho other, ta có văn phạm viết lại như sau : S’ Æ S S Æ iS eS (1) S Æ iS (2) S Æ a (3) Họ tập hợp mục C các tập mục LR(0) là: 105 I0 : S' → • S, S → • iSeS S → • iS S → • a Goto (I0,S) I1 : S' → S • Goto (I0,i) I2 : S → i • SeS S → i • S S → • iSeS S → • iS S → • a Goto (I0,a) I3: S → a • Goto (I2, S) I4: S → iS• eS S → iS• Goto (I4,e) I5 : S → iSe• S S → • iSeS S → • iS S → • a Goto (I5,S) I6 : S → iSeS• Goto(I2,i) ≡ I2 Goto(I2,a) ≡ I3 Goto(I5,i) ≡ I2 Goto(I5,a) ≡ I3 Ta xây dựng bảng phân tích SLR đụng độ như sau: Action Goto Trạng thái i e a $ S 0 s2 s3 1 1 acc 2 s2 s3 4 3 r3 r3 4 s5| r2 r2 5 s2 s3 6 6 r1 Hình 4.17 - Bảng phân tích cú pháp LR cho văn phạm if - else Ðể giải quyết đụng độ tại action[4, e]. Trường hợp này xảy ra trong tình trạng chuỗi ký hiệu if expr then stmt nằm trong Stack và else là ký hiệu nhập hiện hành. Sử dụng nguyên tắc kết hợp mỗi else với một then chưa kết hợp gần nhất trước đó nên ta phải Shift else vào Stack để kết hợp với then nên action [4, e] = s5. Ví dụ 4.29: Với chuỗi nhập i i a e a (if expr1 then if expr2 then a1 else a2) 106 Stack Input Output 0 0 i 2 0 i 2 i 2 0 i 2 i 2 a 3 0 i 2 i 2 S 4 0 i 2 i 2 S 4 e 5 0 i 2 i 2 S 4 e 5 a 3 0 i 2 i 2 S 4 e 5 S 6 0 i 2 S 4 0 s 1 i i a e a $ i a e a $ a e a $ e a $ a $ $ $ $ $ $ Shift s2 Shift s2 Shift s3 Reduce by S Æ a Shift s5 Shift s3 Reduce by S Æ a Reduce by S Æ iS eS Reduce by S Æ iS VIII. BỘ SINH BỘ PHÂN TÍCH CÚ PHÁP Phần này trình bày cách dùng một bộ sinh bộ phân tích cú pháp (parser generator) hỗ trợ cho việc xây dựng kỳ đầu của một trình biện dịch. Một trong những bộ sinh bộ phân tích cú pháp là YACC (Yet Another Compiler - Compiler). Phiên bản đầu tiên của Yacc được S.C.Johnson tạo ra và hiện Yacc được cài đặt như một lệnh của hệ UNIX và đã được dùng để cài đặt cho hàng trăm trình biên dịch. 1. Bộ sinh thể phân tích cú pháp Yacc Đặc tả Yacc Translate.y Yacc Compiler Y.tab.c Y.tab.c C Compiler Input a.out Output a.out Hình 4.18 - Tạo một chương trình dịch input / output với Yacc Một chương trình dịch có thể được xây dựng nhờ Yacc bằng phương thức được minh họa trong hình 4.18 trên. Trước tiên, cần chuẩn bị một tập tin, chẳng hạn là translate.y, chứa một đặc tả Yacc của chương trình dịch. Lệnh yacc translate.y của hệ UNIX sẽ biến đổi tập tin translate.y thành một chương trình C có tên là y.tab.C bằng phương pháp LALR đã trình bày ở trên. Chương trình y.tab.C là một biểu diễn của bộ phân tích cú pháp LALR được viết bằng ngôn ngữ C cùng với các thủ tục C khác có thể do người sử dụng chuẩn bị. Bằng cách dịch y.tab.C cùng với thư viện ly chứa chương trình phân tích cú pháp LR nhờ lệnh cc y.tab.C - ly chúng ta thu được một chương trình đối tượng a.out thực hiện quá trình dịch được đặc tả bởi chương trình Yacc ban đầu. Nếu cần thêm các thủ tục khác, chúng có thể được biên dịch hoặc được tải vào y.tab.C giống như mọi chương trình C khác. 107 2. Ðặc tả YACC Một chương trình nguồn Yacc bao gồm 3 phần: Phần khai báo % % Các luật dịch %% Các thủ tục Ví dụ 4.30: Ðể minh họa việc chuẩn bị một chương trình nguồn Yacc, chúng ta hãy xây dựng một chương trình máy tính bỏ túi đơn giản, đọc một biểu thức số học, ước lượng rồi in ra giá trị số của nó. Chúng ta xây dựng bắt đầu từ văn phạm sau : E → E + T | T T → T * F | F F → (E) | digit Token digit là một ký hiệu số từ 0 đến 9. Một chương trình Yacc dành cho văn phạm này như sau : %{ # include %} % token DIGIT %% line : expr '\n' { print ("%d\n", $1); } ; expr : expr '+' term { $$ = $1 + $3; } | term ; term : term '* ' factor { $$ = $1 * $3; } | factor ; factor: '(' expr ')' { $$ = $2 ; } | DIGIT ; 108 %% yylex ( ) { int c c = getchar ( ); if (isdigit(c)) { yyval = c -'0'; return DIGIT; } return c; } Phần khai báo có thể bao gồm 2 phần nhỏ: - Khai báo C đặt nằm trong cặp dấu %{ và }%. Những khai báo này sẽ được sử dụng trong phần 2 và phần 3. - Khai báo các token (DIGIT là một token). Các token khai báo ở đây sẽ được dùng trong phần 2 và phần 3. Phần luật dịch: Mỗi luật dịch là một luật sinh kết hợp với hành vi ngữ nghĩa. Mỗi luật sinh có dạng → | | ... được mô tả trong Yacc : : { hành vi ngữ nghĩa 1 } | { hành vi ngữ nghĩa 2 } ... | { hành vi ngữ nghĩa n } ; Trong luật sinh, các ký tự nằm trong cặp dấu nháy đơn. 'c' là một ký hiệu kết thúc c, một chuỗi chữ cái và chữ số không nằm trong cặp dấu nháy đơn và không được khai báo là token sẽ là ký hiệu chưa kết thúc. Hành vi ngữ nghĩa của Yacc là một chuỗi các lệnh C có dạng: ƒ $$ Giá trị thuộc tính kết hợp với ký hiệu chưa kết thúc bên vế trái. ƒ $I Giá trị thuộc tính kết hợp với ký hiệu văn phạm thứ i (kết thúc hoặc chưa) của vế phải. 109 Phần thủ tục: Là các thủ tục viết bằng ngôn ngữ C Ở đây một bộ phân tích từ vựng yylex( ) sinh ra một cặp gồm token và giá trị thuộc tính kết hợp với nó. Các token được trả về phải được khai báo trong phần khai báo. Giá trị thuộc kết hợp với token giao tiếp với bộ phân tích cú pháp thông qua biến yylval (một biến được định nghĩa bởi yacc) Chú ý: Chúng ta có thể kết hợp Lex và Yacc bằng cách dùng #include "lex.yy.c" thay cho thủ tục yylex( ) trong phần thứ 3. 110 BÀI TẬP CHƯƠNG IV 4.1. Cho văn phạm G chứa các luật sinh sau: S → ( L)⏐ a L → L , S | S a) Hãy chỉ ra các thành phần của văn phạm phi ngữ cảnh cho G. b) Viết văn phạm tương đương sau khi loại bỏ đệ quy trái . c) Xây dựng bộ phân tích cú pháp dự đoán cho văn phạm. d) Hãy dùng bộ phân tích cú pháp đã được xây dựng để vẽ cây phân tích cú pháp cho các câu nhập sau: i) (a, a) ii) (a, (a, a)) iii) (a, (a, a), (a, a))) e) Xây dựng dẫn xuất trái, dẫn xuất phải cho từng câu ở phần d f) Hãy cho biết ngôn ngữ do văn phạm G sinh ra ? 4.2. Cho văn phạm G chứa các luật sinh sau: S → aSbS⏐ bSaS | ε a) Chứng minh văn phạm này là mơ hồ bằng cách xây dựng 2 chuỗi dẫn xuất trái khác nhau cho cùng câu nhập abab. b) Xây dựng các chuỗi dẫn xuất phải tương ứng cho câu nhập abab. c) Vẽ các cây phân tích cú pháp tương ứng. d) Văn phạm này sinh ra ngôn ngữ gì ? e) Xây dựng bộ phân tích cú pháp đệ quy lùi cho văn phạm trên. Có thể xây dựng bộ phân tích cú pháp dự đoán cho văn phạm này không ? 4.3. Cho văn phạm G chứa các luật sinh sau: bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | (bexpr) | true | false a) Hãy xây dựng bộ phân tích cú pháp dự đoán cho văn phạm G. b) Xây dựng cây phân tích cú pháp cho câu : not ( true and false ) c) Chứng minh rằng văn phạm này sinh ra toàn bộ các biểu thức boole. 111 d) Văn phạm G có là văn phạm mơ hồ không ? Tại sao ? e) Xây dựng bộ phân tích cú pháp SLR cho văn phạm. 4.4. Cho văn phạm G chứa các luật sinh sau: R → R + R | RR | R* | (R) | a | b a) Chứng minh rằng văn phạm này sinh ra mọi biểu thức chính quy trên các ký hiệu a và b. b) Chứng tỏ đây là văn phạm mơ hồ. c) Xây dựng văn phạm không mơ hồ tương đương với thứ tự ưu tiên của các phép tóan giảm dần như sau : phép bao đóng, phép nối kết, phép hợp. d) Vẽ cây phân tích cú pháp trong cả hai văn phạm trên cho câu nhập : a + b * c e) Xây dựng bộ phân tích cú pháp dự đoán từ văn phạm không mơ hồ. f) Xây dựng bảng phân tích cú pháp SLR cho văn phạm G. Ðề nghị một quy tắc giải quyết đụng độ sao cho các biểu thức chính quy được phân tích một cách bình thường. 4.5. Văn phạm sau đây là một đề nghị điều chỉnh tính mơ hồ cho văn phạm chứa câu lệnh if - then - else: Stmt → if expr then stmt | matched_stmt Matched_Stmt → if expr then matched_stmt else stmt | other Chứng minh rằng văn phạm này vẫn mơ hồ. 4.6. Thiết kế văn phạm cho các ngôn ngữ sau. Ngôn ngữ nào là chính quy? a) Tập tất cả các chuỗi 0 và 1 sao cho mỗi số 0 có ít nhất một số 1 ở ngay sau nó. b) Các chuỗi 0 và 1 với số số 0 bằng số số 1. c) Các chuỗi 0 và 1 với số số 0 không bằng số số 1. d) Các chuỗi 0 và 1 không chứa chuỗi 001 như chuỗi con. 4.7. Cho văn phạm G chứa các luật sinh sau : S → aSa | aa Xây dựng bộ phân tích cú pháp đệ quy lùi cho văn phạm với yêu cầu phải thử khả triển aSa trước aa. 112 4.8. Cho văn phạm G chứa các luật sinh sau: S → aAB A → Abc | b B → d a) Xây dựng bộ phân tích cú pháp dự đoán cho văn phạm . b) Hãy dùng bộ phân tích cú pháp đã được xây dựng để phát sinh cây phân tích cú pháp cho câu nhập: abbcd 4.9. Cho văn phạm G chứa các luật sinh sau: E → E or T | T T → T and F | F F → ( E) | not F | id a) Hãy xây dựng bộ phân tích cú pháp dự đoán cho văn phạm. b) Vẽ cây phân tích cú pháp cho câu nhập : id and not ( id or id ) 4.10. Cho văn phạm G chứa các luật sinh sau: S → AB A → Ab | a B → cB | d a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . b) Hãy dùng bộ phân tích cú pháp đã xây dựng để phát sinh cây phân tích cú pháp cho câu nhập: abccd 4.11. Cho văn phạm G: S → D • D | D D → DB | B B → 0 | 1 a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . b) Hãy dùng bộ phân tích cú pháp đã xây dựng để phát sinh cây phân tích cú pháp cho câu nhập: 101•101 4.12. Cho văn phạm G Assign → id : = exp Exp → Exp + Term | Term 113 Term → Term * Factor | Factor Factor → id | ( Exp ) a) Xây dựng bộ phân tích cú pháp thứ tự ưu tiên cho văn phạm . b) Hãy dùng bộ phân tích cú pháp đã được xây dựng để phát sinh cây phân tích cú pháp cho câu nhập: id : = id + id * id 4.13. Cho văn phạm mơ hồ như sau: S → AS | b A → SA | a a) Xây dựng họ tập hợp mục LR(0) cho văn phạm này. b) Xây dựng bảng phân tích cú pháp SLR . c) Thực hiện quá trình phân tích cú pháp SLR khả triển cho chuỗi nhập : abab d) Xây dựng bảng phân tích cú pháp chính tắc . e) Xây dựng bảng phân tích cú pháp LALR . 4.14. Cho văn phạm G như sau: E → E + T | T T → TF | F F → F * | a | b a) Xây dựng bảng phân tích cú pháp SLR cho văn phạm này. b) Thực hiện quá trình phân tích cú pháp SLR cho chuỗi nhập : b + ab* a c) Xây dựng bảng phân tích cú pháp LALR. 4.15. Chứng tỏ rằng văn phạm sau đây: S → Aa | bAc | dc | bda A → d là LALR(1) nhưng không phải SLR(1). 4.16. Cho văn phạm G như sau: E → E sub R | E sup E | { E } | c R → E sup E | E a) Xây dựng bảng phân tích cú pháp SLR cho văn phạm này. b) Ðề nghị một quy tắc giải quyết đụng độ để các biểu thức text có thể được phân tích một cách bình thường. 114 4.17. Viết một chương trình Yacc nhận chuỗi input là các biểu thức số học, sinh ra output là chuỗi biểu thức hậu tố tương ứng. 4.18. Viết một chương trình Yacc nhận biểu thức chính quy làm chuỗi input và sinh ra output là cây phân tích cú pháp của nó. 115