Giáo trình môn Chương trình dịch

bên phải A làm nút đang xét. 3) Nếu nút đang xét ∈ Σ (là ký hiệu kết thúc) a thì đối sánh a với ký hiệu vào hiện tại. + Nếu trùng nhau: thì lấy nút ngay bên phải a làm nút đang xét, con trỏ dịch sang bên phải một ký hiệu trên xâu w. + Nếu không: quay lại nút trước đó và lặp lại b2 với thử lựa chọn tiếp theo. Thủ tục trên lặp lại sau hữu hạn bước và có 2 khả năng xảy ra: - Nếu gặp trường hợp đối sánh hết xâu vào và cây không còn nút nào chưa xét nữa thì ta được một cây phân tích. - Nếu đã quay lui hết tất cả các trường hợp mà không sinh được cây phân tích thì kết luận xâu vào không phân tích được bởi văn phạm đã cho. S a S b S a S c a * S b S (8) S a S b S a S c a * S (9) S a S b S a S c c 10 * Điều kiện để một văn phạm phi ngữ cảnh phân tích được bởi thuật toán Top- down là văn phạm không có đệ qui trái. (Vì vậy ta phải thực hiện loại bỏ đệ quy trái trước khi phân tích văn phạm theo phương pháp topdown) * Độ phức tạp thuật toán là hàm số mũ n với n là độ dài xâu vào. 2.3.2. phân ttích bottom - up. Phương pháp phân tích Bottom-up về tư tưởng là ngược lại với phương pháp Top-down. - Xây dựng cú pháp cho xâu nhập bắt đầu từ lá lên tới gốc. Đây là quá trình rút gọn một xâu thành một kí hiệu mở đầu của văn phạm. Tại mỗi bước rút gọn, một xâu con bằng một xâu phải của một sản xuất nào đó thì xâu con này được thay thế bởi vế trái của sản xuất đó. (còn gọi là phương pháp gạt thu gọn - shift reduce parsing). Cã 2 vÊn ®Ò: x¸c ®Þnh handle vµ chän luËt sinh. * CÊu t¹o: - 1 STACK ®Ó lu c¸c ký hiÖu v¨n ph¹m. - 1 BUFFER INPUT ®Ó gi÷ chuçi cÇn ph©n tÝch w. - Dïng $ ®Ó ®¸nh dÊu ®¸y stack vµ cuèi chuçi nhËp. * Ho¹t ®éng: - Khëi ®Çu th× stack rçng vµ w n»m trong input buffer. Bé ph©n tÝch gạt lần lượt các ký hiệu đầu vào từ trái sang phải vào ngăn xếp đến khi nào đạt được một thu gọn thì thu gọn (thay thế vế phải xuất hiện trên đỉnh ngăn xếp bởi vế trái của sản xuất đó).Nếu có nhiều cách thu gọn tại một trạng thái thì lưu lại cho quá trình quay lui. Quá trình cứ tiếp tục, nếu dừng lại mà chưa đạt đến trạng thái kết thúc thì quay lại tại bước quay lui gần nhất. - Nếu quá trình đạt đến trạng thái ngăn xếp là $S và xâu vào là $ thì quá trình kết thúc và phân tích thành công. - Nếu đã xét hết tất cả các trường hợp, tức là không quay lui được nữa mà chưa đạt đến trạng thái kết thúc thì dừng lại và thông báo xâu vào không phân tích được bởi văn phạm đã cho. Ví dụ: S -> aABe; A -> Abc | b; B -> d; Phân tích câu vào “abbcde” quá trình phân tích Bottom-up như sau: Ngăn xếp Đầu vào Hành động $ abbcde$ gạt $a bbcde$ gạt $ab bcde$ thu gọn A -> b $aA bcde$ gạt $aAb cde$ thu gọn A -> b (2) $aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc $aA de$ gạt $aAd e$ thu gọn B -> d $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Vẽ cây cho quá trình phân tích và quay lui trên, chúng ta có kết quả như sau: Quá trình 1 Quá trình 2 Quá trình suy dẫn cũng có thể được viết lại như sau: Abbcde => aAbcde (A -> b) => aAde (A -> Abc) => aABe (B -> d) => S (S -> aABe) Nếu viết ngược lại chúng ta sẽ được dẫn xuất phải nhất: S =>rm aABe =>rm aAde =>rm aAbcde =>rm abbcde - Quá trình phân tích Bottom-up là quá trình sinh dẫn suất phải nhất a b b c d e A A B* a b b c d e A A* a b b c d e A B A S (2c) Quá trình 3 - Phân tích Bottom-up không phân tích được văn phạm có các sản xuất B->ε hoặc có suy dẫnA =>+ A * Handle của một chuỗi Handle của một chuỗi là một chuỗi con của nó và là vế phải của một sản xuất trong phép thu gọn nó thành ký hiệu vế trái của 1 sản xuất. Ví dụ: Trong ví dụ trên. Ngăn xếp Đầu vào Hành động Handle Suy dẫn phải Tiền tố khả tồn $ abbcde$ gạt $a bbcde$ gạt abbcde a $ab bcde$ thu gọn A -> b b abbcde ab $aA bcde$ gạt aAbcde aA $aAb cde$ thu gọn A -> b (2) b aAbcde aAb $aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) d không phải là handle do áp dụng thu gọn này là không thành công $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc Abc AAbcde $aA de$ gạt $aAd e$ thu gọn B -> d d AAde $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Chú ý Handle là chuỗi mà chuỗi đó phải là một kết quả của suy dẫn phải từ S và phép thu gọn xảy ra trong suy dẫn đó. W = a 1 a 2... a n Stack β α a i a i+1 ... a n $ Sản xuất A -> β Trên ngăn xếp chứa xâu y = α β , β là vế phải của một sản xuất được bộ phân tích áp dụng để thu gọn và bước thu gọn này phải dẫn đến quá trình phân tích thành công thì β là handle của chuỗi α β v (v là phần chuỗi còn lại trên input buffer). Vậy nếu S =>*rm α Aw =>rm α β w thì β là handle của suy dẫn phải α β w Trong việc sử dụng ngăn xếp để phân tích cú pháp gạt thu gọn, handle luôn luôn xuất hiện trên đỉnh của ngăn xếp. * Tiền tố khả tồn (viable prefixes) Xâu ký hiệu trong ngăn xếp tại mỗi thời điểm của một quá trình phân tích gạt - thu gọn là một tiền tố khả tồn. Ví dụ: tại một thời điểm trong ngăn xếp có dữ liệu là α β và xâu vào còn lại là w thì α β w là một dạng câu dẫn phải và α β là một tiền tố khả tồn. 2.3.2.Phân tích LL. Tử tưởng của phương pháp phân tích LL là khi ta triển khai một ký hiệu không kết thúc, lựa chọn cẩn thận các sản xuất như thế nào đó để tránh việc quay lui mất thời gian.Tức là phải có một cách nào đó xác định dực ngay lựa chọn đúng mà không phải thử các lựa chọn khác. Thông tin để xác định lựa chọn dựa vào những gì đã biết trạng thái và kí hiệu kết thúc hiện tại. LL: là một trong các phương pháp phân tích hiệu quả, nó cũng thuộc chiến lược phân tích topdown nhưng nó hiệu quả ở chỗ nó là phương pháp phân tích không quay lui. - Bộ phân tích tất định: Các thuật toán phân tích có đặc điểm chung là xâu vào được quét từ trái sang phải và quá trình phân tích là hoàn toàn xác định, do đó ta gọi là bộ phân tích tất định. (Phân tích topdown và bottom – up có phải là phân tích tất định không? – không do quá trình phân tích là không xác định). L: left – to – right ( quét từ phải qua trái ) L : leftmosst – derivation (suy dẫn trái nhất); k là số ký hiệu nhìn trước để đưa ra quyết định phân tích. Giả sử ký hiệu không kết thúc A có các sản xuất: A -> α 1 | α 2 | . . . | α n thoả mãn tính chấ:t các xâu α 1, α 2, . . ., α n suy dẫn ra các xâu với ký hiệu tại vị trí đầu tiên là các ký hiệu kết thúc khác nhau, khi đó chúng ta chỉ cần nhìn vào ký hiệu đầu vào tiếp theo sẽ xác định được cần khai triển A theo α i nào. Nếu cần tới k ký hiệu đầu tiên thì mới phân biệt được các xâu α 1, α 2, . . ., α n thì khi đó để chọn luật sản xuất nào cho khai triển A chúng ta cần nhìn k ký hiệu đầu vào tiếp theo. Văn phạm LL(k) là văn phạm cho phép xây dựng bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k kí hiệu vào nằm ngay bên phải của vị trí vào hiện tại. Ngôn ngữ sinh ra bởi văn phạm LL(k) là ngôn ngữ LL(k). Thông thường chúng ta xét với k=1. 2.3.2.1. First và follow. * First của một xâu: First(α ) cho chúng ta biết xâu α có thể suy dẫn đến tận cùng thành một xâu bắt đầu bằng ký hiệu kết thúc nào. Định nghĩa First( α ) First(α ) là tập chứa tất cả các ký hiệu kết thúc a mà a có thể là bắt đầu của một xâu được suy dẫn từ α + First(α ) = {a ∈ T | α =>* aβ } + ε ∈ First(α ) nếu α =>* ε Thuật toán tính First(X) với X là một ký hiệu văn phạm: 1. nếu X là ký hiệu kết thúc thì First(X) = {X} 2. nếu X -> ε là một sản xuất thì thêm ε vào First(X) 3. nếu X -> Y1...Yk là một sản xuất thì thêm First(Y1) vào First(X) trừ ε nếu First(Yt) chứa ε với mọi t=1,...,i với i<k thì thêm First(Yi+1) vào First(X) trừ ε . Nếu trường hợp i=k thì thêm ε vào First(X) Cách tính First( α ) với α là một xâu. Giả sử α = X1X2 . . . Xk. Ta tính như bước 3 của thuật toán trên: 1. thêm First(X1) vào First(α ) trừ ε 2. nếu First(Xt) chứa ε với mọi t=1,...,i với i<k thì thêm First(Xi+1) vào First(α ) trừ ε . Nếu trường hợp i=k thì thêm ε vào First(α ) - Tính First của các ký hiệu không kết thúc: lần lượt xét tất cả các sản xuất.Tại mỗi sản xuất, áp dụng các qui tắc trong thuật toán tính First để thêm các ký hiệu vào các tập First. Lặp lại và dừng khi nào gặp một lượt duyệt mà không bổ sung thêm được bất kỳ ký hiệu nào vào tập First và ta đã tính xong các tập First cho các ký hiệu. Ví dụ 1: Cho văn phạm sau: S -> AB; A -> aA | ε ; B -> bB | ε Hãy tính First của các ký hiệu S, A, B Kết quả: Fisrt(A) = {a, ε }; First(B) = {b,ε }; First(S) = {a,b,ε } * Follow của một ký hiệu không kết thúc: Định nghĩa follow(A) A là kí hiệu không kết thúc. Follow(A) với A là ký hiệu không kết thúc là tập các ký hiệu kết thúc a mà chúng có thể xuất hiện ngay bên phải của A trong một số dạng câu. Nếu A là ký hiệu bên phải nhất trong một số dạng câu thì thêm $ vào Follow(A). + Follow(A) = {a∈T | ∃ S =>* α Aaβ } + $ ∈ Follow(A) khi và chỉ khi tồn tại suy dẫn S =>* α A Thuật toán tính Follow(A) với A là một ký hiệu không kết thúc 1. thêm $ vào Follow(S) với S là ký hiệu bắt đầu (chú ý là nếu ta xét một tập con với một ký hiệu E nào đó làm ký hiệu bắt đầu thì cũng thêm $ vào Follow(E)). 2. nếu có một sản xuất dạng B->α Aβ và β ≠ ε thì thêm các phần tử trong First(β ) trừ ε vào Follow(A). thật vậy: nếu a ∈ First(β ) thì tồn tại β =>*aγ , khi đó, do có luật B->α Aβ nên tồn tại S =>* α 1Bβ 1 => α 1α Aβ β 1=>α 1α Aaγ β 1 Theo định nghĩa của Follow thì ta có a ∈ Follow(A) 3. nếu có một sản xuất dạng B->α A hoặc B->α Aβ với ε ∈ First(B) thì mọi phần tử thuộc Follow(B) cũng thuộc Follow(A) thật vậy: nếu a ∈ Follow(B) thì theo định nghĩa Follow ta có S =>* α 1Baβ 1 =>* α 1α Aaβ 1 , suy ra a ∈ Follow(A) - Để tính Follow của các ký hiệu không kết thúc: lần lượt xét tất cả các sản xuất. Tại mỗi sản xuất, áp dụng các qui tắc trong thuật toán tính Follow để thêm các ký hiệu vào các tập Follow . Lặp lại và dừng khi nào gặp một lượt duyệt mà không bổ sung được ký hiệu nào vào các tập Follow. Ví dụ ở trên, ta tính được tập Follow cho các ký hiệu S, A, B như sau: Follow(S) = {$} Follow(A) = {b,$} Follow(B) = {} VÝ dô2: Víi v¨n ph¹m E →T E'; E' →+ T E' | ∈; T →F T'; T' →* F T' | ∈; F → (E) | id Theo ®Þnh nghÜa FIRST V× F →E) FIRST(F) = {(, id} F → (id) Tõ T → F T' v× ( ( FIRST(F) ( FIRST(T)= FIRST(F) Tõ E →T E' v× ( ( FIRST(T) ( FIRST(E)= FIRST(T) V× E' →ε ⇒ε ∈ FIRST(E') MÆt kh¸c do E' ( +T E' mµ FIRST(+)={ +} ( FIRST(E')= {+, (} T¬ng tù FIRST(T')= { *, (} VËy ta cã FIRST(E)= FIRST(T)= FIRST(F)= { (, id} FIRST(E')= {+, ε } FIRST(T')= { *, ε } Tính follow : ĐÆt $ vµo trong FOLLOW(E). Áp dông luËt 2 cho luËt sinh F→ (E) ⇒ε ∈FOLLOW(E) ⇒FOLLOW(E)={$,ε } Áp dông luËt 3 cho E → TE' ⇒ε ,$ ∈ FOLLOW(E') ⇒ FOLLOW(E')={$,ε }. Áp dông luËt 2 cho E→TE' ⇒ mäi phÇn tö # ε cña FIRST(E') tøc + (FOLLOW(T). Áp dông luËt 3 cho E' E' → +TE' , E' → ε ⇒ FOLLOW(E') ⊂ FOLLOW(T) ⇒ ⇒ FOLLOW(T) = { +, ε , $ }. Ap dụng luËt 3 cho T→FT' th× FOLLOW(T') =FOLLOW(T)={+, $, ε }. Ap dông luËt 2 cho T→ FT' ⇒* ∈FOLLOW(F) Ap dông luËt 3 cho T' → * F T' ;T→ ε ' th× FOLLOW(T') ( FOLLOW(F)th× FOLLOW(F)= { *, +, $, )} VËy ta cã FOLLOW(E)= FOLLOW(E') = { $, )} FOLLOW(T)= FOLLOW(T') = { +,$, )} FOLLOW(F)= {*,+, $, )} 2.3.2.2. lập bảng phân tích LL(1). Bảng phân tích LL(1) là một mảng hai chiều: Một chiều chứa các ký hiệu không kết thúc, chiều còn lại chứa các ký hiệu kết thúc và $. Vị trí M(A,a) chứa sản xuất A->α trong bảng chỉ dẫn cho ta biết rằng khi cần khai triển ký hiệu không kết thúc A với ký hiệu đầu vào hiện tại là a thì áp dụng sản xuất A->α . Thuật toán xây dựng bảng LL(1): Input: Văn phạm G. Output: Bảng phân tích M. Phương pháp: 1. với mỗi sản xuất A->α , thực hiện bước 2 và bước 3 2. với mỗi ký hiệu kết thúc a ∈ First(α ), định nghĩa mục M(A,a) là A- >α 3. nếu ε ∈ First(α ) và với mỗi b ∈ Follow(A) thì định nghĩa mục M(A,b) là A->α (nếu ε ∈ First(α ) và $ ∈ Follow(A) thì thêm A->α vào M[A,$]) Đặt tất cả các vị trí chưa được định nghĩa trong bảng là “lỗi”. VÝ dô: E → T E'; E' → + T E' | ε ; T →F T'; T' → * F T' | ε ; F → (E) | id TÝnh FIRST(TE') = FIRST(T) = {(,id} ( M[E,id] vµ M[E,( ] Kí tự chưa kết thúc Kí tự kết thúc Id + * ( ) $ E E→ TE' E→ TE' E' E→ +TE' E→ ε E'→ ε T T→ FT' T→ FT' T' T'→ ε T'→ +FT' T' → ε T'→ ε F F→ id F→ (E) XÐt luËt sinh E → TE' chøa luËt sinh E →TE' XÐt luËt sinh E'→+ TE' TÝnh FIRST(+TE') = FIRST(+) = {+} ( M[E',+] chøa E'→+TE' LuËt sinh E' → ε v× ε ∈ FIRST(() = FIRST(() FOLLOW(E') = { ), $} ( E→ ε n»m trong M[E',)] vµ M[E',$] LuËt sinh T→FT' : FIRST(FT') = {*} LuËt sinh T' → ε: ε ∈ FIRST(α ) vµ FOLLOW(T')= {+, ), $} LuËt sinh F→ (E) ; FIRST(((E)) = {(} LuËt sinh F →id ; FIRST(id)={id} 2.3.2.3. văn phạm LL (k) và LL (1) Giải thuật trên có thể áp dụng 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 và nhập nhằng) thì trong bảng phân tích M có những ô chứa nhiềuhơn một luật sinh. Ví dụ: Văn phạm S → iEtSS’ | aS’ → eS | ε Ε → b Ký tù cha kÕt thóc Ký tù kÕt thóc A B e i t $ S S→ a S→ iEtSS' S' S → ε S'→ ε E E→ b * Định nghĩa: Văn phạm LL(1) là văn phạm xây dựng được bảng phân tích M có các ô chỉ được định nghĩa nhiều nhất là một lần. * Điều kiện để một văn phạm là LL(1) - Để kiểm tra văn phạm có phải là văn phạm LL(1) hay không ta lập bảng phân tích LL(1) cho văn phạm đó. Nếu có mục nào đó trong bảng được định nghĩa nhiều hơn một lần thì văn phạm đó không phải là LL(1), nếu trái lại thì văn phạm là LL(1). - Cách khác là dựa vào định nghĩa, một văn phạm là LL(1) phải thoả mãn điều kiện sau: nếu A -> α | β là hai sản xuất của văn phạm đó thì phải thoả mãn: a) không tồn tại một ký hiệu kết thúc a mà a ∈ First(α ) và a ∈ First(β ) b) không thể đồng thời ε thuộc First(α ) và First(β ). c) Nếu ε ∈ First(α ) thì Follow(A) và First(β ) không có phần tử nào trùng nhau. 2.3.2.4. Thuật toán phân tích LL(1) * Mô tả: Cơ sở của phân tích LL là dựa trên phương pháp phân tích topdown và máy ôtômát đẩy xuống. - Vùng đệm chứa xâu vào với cuối xâu là ký hiệu kết thúc xâu $. - Ngăn xếp chứa các ký hiệu văn phạm thể hiện quá trình phân tích. Đáy ngăn xếp kí hiệu $. - Bảng phân tích M lµ mét m¶ng hai chiÒu M[A,a], trong ®ã A lµ ký hiÖu chøa kÕt thóc, a lµ ký hiÖu kÕt thóc hoÆc $. - Thành phần chính điều khiển phân tích. Mô hình của phân tích cú pháp LL Tại thời điểm hiện tại, giả sử X là ký hiệu trên đỉnh ngăn xếp và a là ký hiệu đầu vào. Các hành động điều khiển được thực hiện như sau: 1. nếu X = a = $, quá trình phân tích thành công 2. nếu X = a ≠ $, lấy X ra khỏi ngăn xếp và dịch con trỏ đầu vào đến ký hiệu tiếp theo 3. nếu X là một ký hiệu không kết thúc, xét mục M(X,a) trong bảng phân tích. Có hai trường hợp xảy ra: a) nếu M(A,a) = X -> Y1. . .Yk thì lấy X ra khỏi ngăn xếp và đẩy vào ngăn xếp Y1, . . ., Yk theo thứ tự ngược lại (để ký hiệu được phân tích tiếp theo trên đỉnh ngăn xếp phải là Y1, tạo ra dẫn xuất trái). b) nếu M(A,a) là lỗi thì quá trình phân tích gặp lỗi và gọi bộ khôi phục lỗi. * Thuật toán : - Input: Một xâu w và một bảng phân tích M của văn phạm G. - Output: Đưa ra suy dẫn trái nhất của w nếu w ∈ L(G), báo lỗi nếu w ∉ L(G). - Method: Ở trạng thái khỉ đầu ngăn xép được đặt các kí hiệu $S (S là đỉnh của cây phân tích còn xâu vào là w$ ) Đặt con trỏ ip trỏ đến kí tự đầu tiên của xâu w$ Repeat {Giả sử X là kí hiệu đỉnh của ngăn xếp, a là kí hiệu vào tiếp theo} If (X ∈Σ ) or (X = $) then If x=a then Pop X từ đỉnh ngăn xếp và loại bỏ a khỏi xâu vào Else error (); Else {X không phải là kí tự kết thúc} If M[X,a] = X → Y1, Y2, Yk then Begin Pop X từ ngăn xếp; Push Yk, Yk-1, Y1 vào ngăn xếp, với Y1 ở đỉnh; Đưa ra sản xuất X → Y1, Y2, Yk ; End; Else Error(); Until X = $ {ngăn xếp rỗng} Ví dụ 2: Cho văn phạm: E->TE’; E’->+TE’ | ε ; T->FT’; T’->*FT’ | ε ; F- >(E) | id a) tính First và Follow cho các ký hiệu không kết thúc. b) tính First cho vế phải của các sản xuất. c) xây dựng bảng phân tích LL(1) cho văn phạm trên d) phân tích LL đối với xâu vào “id+id*id” Ký hiệu văn phạm First Follow E (, id ), $ E’ +, ε ), $ T (, id +, ), $ T’ *, ε +, ), $ F (, id +, *, ), $ Sản xuất First của vế phải E->TE’ (, id E’->+TE’ + T->FT’ (, id T’->*FT’ * F->(E) ( F->id Id Bảng phân tích LL(1) Ký hiệu Vế trái Ký hiệu đầu vào Id + * ( ) $ E E->TE’ E->TE’ E’ E’->+TE’ E’->ε E’->ε T T->FT’ T->FT’ T’ T’->ε T’->*FT’ T’->ε T’->ε F F->id F->(E) Phân tích LL(1) cho xâu vào “id+id*id”: Ngăn xếp Xâu vào Đầu ra $E id+id*id$ E->TE’ $E’T id+id*id$ T->FT’ $E’T’F id+id*id$ F->id $E’T’id id+id*id$ rút gọn id $E’T’ +id*id$ T’->ε $E’ +id*id$ E’->+TE’ $E’T+ +id*id$ rút gọn + $E’T id*id$ T->FT’ $E’T’F id*id$ F->id $E’T’id id*id$ rút gọn id $E’T’ *id$ T’->*FT’ $E’T’F* *id$ rút gọn * $E’T’F id$ F->id $E’T’id id$ rút gọn id $E’T’ $ T’->ε $E’ $ E’->ε $ $ Từ bảng phân tích, chúng ta có suy dẫn trái như sau: E=>TE’=>FT’E’=>idT’E’=>idE’=>id+TE’=>id+FT’E’=>id+idT’E’=>id+id *FT’E’=> id+id*idT’E’=>id+id*idE’=>id=id*id . 2.3.4. Phân tích LR. LR là kỹ thuật phân tích cú pháp từ dưới lên khá hiệu quả, có thể được sử dụng để phân tích một lớp khá lớn các văn phạm phi ngữ cảnh. Kỹ thuật này gọi là phân tích cú pháp LR(k), trong đó: - L là Left to right chỉ việc quét xâu vào từ trái quá phải. - R là Right most parsing chỉ việc suy dẫn sinh ra là suy dẫn phải. - k là số ký hiệu nhìn trước để đưa ra quyết định phân tích. * Phân tích LR có nhiều ưu điểm: - Nhận biết được tất cả các cấu trúc của ngôn ngữ lập trình được tạo ra dựa theo các văn phạm phi ngữ cảnh. - LR là phương pháp phân tích cú pháp gạt - thu gọn không quay lui tổng quát nhất đã được biết đến nhưng lại có thể được cài đặt hiệu quả như những phương pháp gạt - thu gọn khác. - lớp văn phạm phân tích được nhờ phương pháp LR là một tập bao hàm thực sự của lớp văn phạm phân tích được bằng cách phân tích cú pháp dự đoán. - Phát hiện được lỗi cú pháp ngay khi có thể trong quá trình quét đầu vào từ trái sang. * Nhược điểm chủ yếu: ta phải thực hiện quá nhiều công việc để xây dựng được bộ phân tích LR cho một ngôn ngữ lập trình. 2.3.4.1. Thuật toán phân tích LR. Phân tích LR là một thể phân tích cú pháp gạt - thu gọn, nhưng điểm khác biệt so với phân tích Bottom-up là nó không quay lui. Tại mỗi thời điểm nó xác định được duy nhất hành động gạt hay thu gọn. * Mô hình: gồm các thành phần sau: - 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.  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  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 $) * Hoạt động: 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 $) 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 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ụ: Cho văn phạm: (1) E -> E + T (2) E -> T (3) T -> T * F (4) T -> F (5) F -> ( E ) (6) F -> a Giả sử chúng ta đã xây dựng được bảng phân tích action và goto như sau: chú ý: các giá trị trong action được ký hiệu như sau: a) si có nghĩa là shift i b) rj có nghĩa là reduce theo luật (j) c) acc có nghĩa là accept d) khoảng trống biểu thị lỗi trạng thái Action goto a + * ( ) $ E T F 0 s5 S4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 S4 8 2 3 5 r6 r6 r6 r6 6 s5 S4 9 3 7 s5 S4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng phân tích cú pháp Chúng ta sử dụng thuật toán LR để phân tích xâu vào “a*a+a” đối với dữ liệu trên như sau: Ngăn xếp Đầu vào Hành động 0 id * id + id $ gạt 0 id 5 * id + id $ thu gọn F->id 0 F 3 * id + id $ thu gọn T->F 0 T 2 * id + id $ gạt 0 T 2 * 7 id + id $ gạt 0 T 2 * 7 id 5 + id $ thu gọn F->id 0 T 2 * 7 F 10 + id $ thu gọn T->T*F 0 T 2 + id $ thu gọn E->T 0 E 1 + id $ gạt 0 E 1 + 6 id $ gạt 0 E 1 + 6 id 5 $ thu gọn F->id 0 E 1 + 6 F 3 $ thu gọn T->F 0 E 1 + 6 T 9 $ thu gọn E->E+T 0 E 1 $ chấp nhận (accepted) Quá trình phân tích LR Một số đặc điểm của phân tích LR: - Một tính chất cơ bản đối với bộ phân tích cú phát LR là xác định được khi nào handle xuất hiện trên đỉnh ngăn xếp. - Ký hiệu trạng thái trên đỉnh ngăn xếp đã xác định mọi thông tin của quá trình phân tích vì nó chỉ đến tập mục có nghĩa của tiền tố khả tồn trong ngăn xếp. Dựa vào các mục này, chúng ta có thể xác định khi nào thì gặp một handle trên đỉnh ngăn xếp và thực hiện hành động thu gọn. - Một nguồn thông tin khác để xác định hành động gạt-thu gọn là k ký hiệu đầu vào tiếp theo. Thông thườn chúng ta xét k=0 hoặc 1. - Điểm khác biệt giữa phương pháp phân tích LR với phương pháp phân tích LL là: Để cho một văn phạm là LR(k), chúng ta phải có khả năng xác định được sự xuất hiện của vế phải của một sản xuất khi đã thấy tất cả quá trình dẫn xuất từ vế phải đó với thông tin thêm là k ký hiệu đầu vào tiếp theo. Điều kiện này rõ ràng là chính xác hơn so với điều kiện của văn phạm LL(k) là việc sử dụng một sản xuất chỉ dựa vào k ký hiệu đầu vào tiếp theo. Chính vì vậy mà quá trình phân tích LR ít có xung đột hơn, hay nói cách khác là văn phạm của nó rộng hơn LL rất nhiều. 2.3.4.2. Một số khái niệm. 1) Tiền tố khả tồn (viable prefixes) Xâu ký hiệu trong ngăn xếp tại mỗi thời điểm của một quá trình phân tích gạt - thu gọn là một tiền tố khả tồn. Ví dụ: tại một thời điểm trong ngăn xếp có dữ liệu là α β và xâu vào còn lại là w thì α β w là một dạng câu dẫn phải và α β là một tiền tố khả tồn. 2) Mục (Item) : Cho một văn phạm G. Với mỗi sản xuất A->xy, ta chèn dấu chấm vào tạo thành A->x .y và gọi kết quả này là một mục. Mục A->x.y cho biết qúa trình suy dẫn sử dụng sản xuất A->xy và đã suy dẫn đến hết phần x trong sản xuất, quá trình suy dẫn tiếp theo đối với phần xâu vào còn lại sẽ bắt đầu từ y. Ví dụ: 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 → • 3) Mục có nghĩa (valid item) Một mục A->β 1.β 2 gọi là mục có nghĩa(valid item) đối với tiền tố khả tồn α β 1 nếu tồn tại một dẫn xuất: S =>*rm α Aw =>rm α β 1β 2w Tập tất cả các mục có nghĩa đối với tiền tố khả tồn gọi là tập I. Một tập mục có nghĩa đối với một tiền tố khả tồn nói lên rất nhiều điều trong quá trình suy dẫn gạt - thu gọn: Giả sử quá trình gạt thu gọn đang ở trạng thái với ngăn xếp là x và phần ký hiệu đầu vào là v (*) ngăn xếp đầu vào $x v$ thế thì, quá trình phân tích tiếp theo sẽ phụ thuộc vào tập mục có nghĩa I của tiền tố khả tồn thuộc x. Với một mục [A->β 1.β 2] ∈ I, cho chúng ta biết x có dạng α β 1, và quá trình phân tích phần còn lại w của xâu đầu vào nếu theo sản xuất A->β 1β 2 sẽ được tiếp tục từ β 2 của mục đó. Hành động gạt hay thu gọn sẽ phụ thuộc vào β 2 là rỗng hay không. Nếu β 2 = ε thì phải thu gọn β 1 thành A, còn nếu β 2 ≠ ε thì việc phân tích theo sản xuất A->β 1β 2 đòi hỏi phải sử dụng hành động gạt. Nhận xét: - Mọi quá trình phân tích tiếp theo của trạng thái (*) đều phụ thuộc vào các mục có nghĩa trong tập các mục có nghĩa I của tiền tố khả tồn x. - Có thể có nhiều mục có nghĩa đối với một tiền tố x. Các mục này có thể có các hành động xung đột (bao gồm cả gạt và thu gọn), trong trường hợp này bộ phân tích sẽ phải dùng các thông tin dự đoán, dựa vào việc nhìn ký hiệu đầu vào tiếp theo để quyết định nên sử dụng mục có nghĩa nào với tiền tố x (tức là sẽ cho tương ứng gạt hay thu gọn). Nếu quá trình này cho những quyết định không xung đột (duy nhất) tại mọi trạng thái thì ta nói văn phạm đó phân tích được bởi thuật toán LR. - Tư tưởng của phương pháp phân tích LR là phải xây dựng được tập tất cả các mục có nghĩa đối với tất cả các tiền tố khả tồn. 4) Tập chuẩn tắc LR(0) LR(0) là tập các mục có nghĩa cho tất cả các tiền tố khả tồn. LR(0) theo nghĩa: LR nói lên đây là phương pháp phân tích LR, còn số 0 có nghĩa là số ký tự nhìn trước là 0. 5) Văn phạm gia tố( Augmented Grammar) (mở rộng) Văn phạm G - ký hiệu bắt đầu S, 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 gia tố. Ví dụ: cho văn phạm G gồm các sản xuất S -> aSb | a thì văn phạm gia tố của G, ký hiệu là G’ gồm các sản xuất S’-S, S->aSb | a với S’ là ký hiệu bắt đầu. Ta xây dựng văn phạm gia tố của một văn phạm theo nghĩa, đối với văn phạm ban đầu, quá trình phân tích sẽ bắt đầu bởi các sản xuất có vế trái là S. Khi đó, chúng ta xây dựng văn phạm gia tố G’ thì mọi quá trình phân tích sẽ bắt đầu từ sản xuất S’->S Sử dụng hai phép toán: phép tính bao đóng closure(I) của một tập mục I và phép sinh ra tập mục cho các tiền tố khả tồn mới goto(I,X) như sau: 6) Phép toán closure Nếu I là một tập các mục của một văn phạm G thì closure(I) là tập các mục được xây dựng từ I bằng hai qui tắc sau: 1. khởi đầu mỗi mục trong I đều được đưa vào closure(I) 2. nếu [A -> α .Bβ ] ∈ closure(I) và B->γ là một sản xuất thì thêm [B -> .γ ] vào closure(I) nếu nó chưa có ở đó. Áp dụng qui tắc này đến khi không thêm được một mục nào vào closure(I) nữa. Trực quan: nếu [A -> α .Bβ ] là một mục có nghĩa đối với một tiền tố khả tồn xα thì với B->γ là một sản xuất ta cũng có [B->.γ ] là một mục có nghĩa đối với tiền tố khả tồn xα . Phép toán tính bao đóng của một mục là để tìm tất cả các mục có nghĩa tương đương của các mục trong tập đó. Theo định nghĩa của một mục là có nghĩa đối với một tiền tố khả tồn, chúng ta có suy dẫn S =>*rm xAy =>rm xα Bβ y sử dụng sản xuất B -> γ ta có suy dẫn S =>*rm xα γ β y. Vậy thì [B->.γ ] là một mục có nghĩa của tiền tố khả tồn xα Ví dụ: Xét văn phạm mở rộng của biểu thức: E' → E E → E + T | T T → T * F | F 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) E' → • E được đặt vào closure(I) theo luật 1. Khi có một E đi ngay sau một • , bằng luật 2 ta thêm các sản xuất E với các chấm nằm ở đầu trái ( E → • E + T và E → • T). Bây giờ lại có T đi theo sau một •, ta lại thêm T → • T * F và T → • F vào. Cuối cùng ta có Closure(I) như trên. 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. * Phép toán goto goto(I,X) với I là một tập các mục và X là một ký hiệu văn phạm. goto(I,X) được định nghĩa là bao đóng của tập tất cả các mục [A->α X.β ] sao cho [A->α .Xβ ] ∈ I. Trực quan: Nếu I là tập các mục có nghĩa đối với một tiền tố khả tồn γ nào đó thì goto(I,X) là tập các mục có nghĩa đối với tiền tố khả tồn γ X. gọi tập J=goto(I,X) thì cách tính tập J như sau: 1. nếu [A->α .Xβ ] ∈ I thì thêm [A->α X.β ] vào J 2. J=closure(J) Phép toán goto là phép phát triển để xây dựng tất cả các tập mục cho tất cả các tiền tố khả tồn có thể. Ví dụ : Giả sử I = {E' → E•, E → E • + T}. Tính goto (I, +) ? Ta có J = { 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) Tính Goto(I,+) bằng cách kiểm tra I cho các mục với dấu + ở ngay bên phải chấm. E’ → E• không phải mục như vậy nhưng E → E • + T thì đúng. Ta chuyển dấu chấm qua bên kia dấu + để nhận được E → E + • T và sau đó tính closure cho tập này. Như vậy, cho trước một văn phạm, ta có thể sử dụng hai phép toán trên để sinh ra tất cả các tiền tố khả tồn có thể và tập mục có nghĩa của từng tiền tố khả tồn. Với việc sử dụng phép tính closure và goto như trên, chúng ta xây dựng được tập các mục gọi là tập mục LR(0). Thuật toán xây dựng LR(0) như sau: Cho văn phạm G, văn phạm gia tố của nó là G’ Tập C là tập các tập mục LR(0) được tính theo thuật toán như sau: 1). C = {closure({[S’->.S]})} 2). Đối với mỗi mục I trong C và mỗi ký hiệu văn phạm X, tính goto(I,X). Thêm goto(I,X) vào C nếu không rỗng và không trùng với bất kỳ tập nào có trong C Thực hiện bước 2 đến khi nào không thêm được tập nào nữa vào C C là tập xác định tất cả các mục có nghĩa đối với tất cả các tiền tố khả tồn vì chúng ta xuất phát từ mục [S’ -> .S] và xây dựng các mục có nghĩa cho tất cả các tiền tố khả tồn. Xây dựng tập C dựa trên hàm goto có thể được xem như một sơ đồ chuyển trạng thái của một DFA. Trong đó, I0 là trạng thái xuất phát, bằng cách xây dựng các trạng thái tiếp bằng chuyển trạng thái theo đầu vào là các ký hiệu văn phạm. Đường đi của các ký hiệu đầu vào chính là các tiền tố khả tồn. Các trạng thái chính là tập các mục có nghĩa của các tiền tố khả tồn đó. Ví dụ: Cho văn phạm G: E -> E + T | T; T -> T * F | F; F -> ( E ) | id Hãy tính LR(0) - Xét văn phạm G’ là văn phạm gia tố của G. Văn phạm G’ gồm các sản xuất sau: E’ -> E; E -> E + T | T; T -> T * F | F; F -> ( E ) | a Tính theo thuật toán trên ta có kết quả như sau: Closure({E'→ E}): I0: E’ -> .E E -> .T T -> .F F -> .(E) F -> .a Goto (I0, id) I5: F -> a. Goto (I0, E) I1: E’ -> E. E -> E.+T Goto (I1, +) I6: E -> .E+T E -> E+.T T -> .T*F T -> .F F -> .(E) F -> .a Goto (I0, T) I2: E -> T. T -> T.*F Goto (I2, *) I7: T -> T*.F F -> .(E) F -> .a Sơ đồ chuyển trạng thái của DFA cho các tiền tố khả tồn: I 0 I 1 I 6 I 9 I 7 I 4 I 3 I 5 I 2 I 7 I 10 I 4 I 5I 3 I 4 I 8 I 11 I 6 I 2 I 3 I 5 E + T * F ( a T * F ( a F ( E ) + ( T F a a 2.3.4.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 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. Sự khác biệt rất lớn giữa các văn phạm LL và LR: Ðối với văn phạm LR(k), 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 sản xuất nào đó bằng cách xem tất cả những gì suy dẫn được từ vế phải qua k kí hiệu vào được nhìn vượt quá. Ðòi hỏi này ít khắt khe hơn so với các văn phạm LL(k). Đối với văn phạm LL(k): ta phải nhận biết được sản xuất nào được dùng chỉ với k kí hiệu đầu tiên mà vế phải của nó suy dẫn ra. 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. 2.3.4.3. Xây dựng bảng phân tích 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. Phương pháp thứ 2 là phương pháp LR chuẩn ( canonical LR): phương pháp mạnh nhất nhưng tốn kém nhất. Phương pháp thứ 3: LR nhìn vượt (LALR – LookaheadLR) là phương pháp trung gian về sức mạnh và chi phí giữ 2 phương pháp trên. Phương pháp này làm việc với hầu hết các văn phạm. Trong phần này ta sẽ xem xét cách xây dựng các hàm action và goto của phân tích SLR từ ôtômát hữu hạn đơn định dùng để nhận dạng các tiền tố có thể có. Cho văn phạm G, ta tìm văn phạm gia tố của G là G’, từ G’ xây dựng C là tập chuẩn các tập mục cho G’, xây dựng hàm phân tích Action và hàm nhẩy goto từ C bằng thuật toán sau. 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ụ 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ụ 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 • 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ạng thái Action goto a + * ( ) $ E T F 0 s5 S4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 S4 8 2 3 5 r6 r6 r6 r6 6 s5 S4 9 3 7 s5 S4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 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ụ: 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: I 0 : S' → • S S → • L = R S → • R L → • * R L → • id R → • L I 1 : S' → S • I 2 : S → L • = R R → L • I 3 : S → R • I 4 : L → * • R R → • L L → • * R L → • id I 5 : L id • I 6 : S → L = • R R → • L L → • * R L → • id I 7 : L → * R• I 8 : R → L• I 9 : S → L = R• 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). 2.3.4.4. Xây dựng bảng phân tích LR chuẩn. * 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 $. * Thuật toán xây dựng họ tập hợp mục LR(1)  Giải thuật: 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 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ụ: Xây dựng bảng LR chính tắc cho văn phạm gia tố G' có các luật sinh sau : S'  S (1) S  L = R3 (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 (I2,=) I6 : S → L = • R, $ R → • L, $ L → • * R, $ 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 Goto (I11,*) ≡ I11 Goto (I11,id) ≡ I12 * 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: 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ụ : Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên Trạng thái Action Goto = * id $ S L R 0 s4 s5 1 2 3 1 acc 2 s6 r5 3 r2 4 s4 s5 8 7 5 r4 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 đó. 2.3.4.5. Xây dựng bảng phân tích 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ụ : 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ậ: 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 } 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ụ : 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 : State Action Goto = * 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 - 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). 2.4. Bắt lỗi. * Giai đoạn phân tích cú pháp phát hiện và khắc phục được khá nhiều lỗi. Ví dụ lỗi do các từ tố từ bộ phân tích từ vựng không theo thứ tự của luật văn phạm của ngôn ngữ. * Bộ bắt lỗi trong phần phân tích cú pháp có mục đích: + Phát hiện, chỉ ra vị trí và mô tả chính xác rõ rang các lỗi. + Phục hồi quá trìh phân tích sau khi gặp lỗi đủ nhanh để có thể phát hiện ra các lỗi tiếp theo. + Không làm giảm đáng kể thời gian xử lý các chương trình viết đúng. * Các chiến lược phục hồi lỗi. - Có nhiều chiến lược mà bộ phân tích có thể dùng để phục hồi quá trình phân tích sau khi gặp một lỗi cú pháp. Không có chiến lược nào tổng quát và hoàn hảo, có một số phương pháp dùng rộng rãi. + Phục hồi kiểu trừng phạt: Phương pháp đơn giản nhất và được áp dụng trong đa số các bộ phân tích. Mỗi khi phát hiện lỗi bộ phân tích sẽ bỏ qua một hoặc một số kí hiệu vào mà không kiểm tra cho đến khi nó gặp một kí hiệu trong tập từ tố đồng bộ. Các từ tố đồng bộ thường được xác định trước ( VD: end, ; ) Người thiết kế chương trình dịch phải tự chọn các từ tố đồng bộ. Ưu điểm: Đơn giản, không sợ bj vòng lặp vô hạn, hiệu quả khi gặp câu lệnh có nhiều lỗi. + Khôi phục cụm từ: Mỗi khi phát hienj lỗi, bộ phân tích cố gắng phân tích phần còn lại của câu lệnh. Nó có thể thay thế phần đầu của phần còn lại xâu này bằng một xâu nào đó cho phép bộ phân tích làm việc tiếp. Những việc này do người thiết kế chương trình dịch nghĩ ra. + Sản xuất lỗi: Người thiết kế phải có hiểu biết về các lỗi hường gặp và gia cố văn phạm của ngôn ngữ này tại các luật sinh ra cấu trúc lỗi. Dùng văn phạm này để khôi phục bộ phân tích. Nếu bọ phân tích dùng một luật lỗi có thể chỉ ra các cấu trúc lỗi phát hiện ở đầu vào. Ngoài ra ngừơi ta có cách bắt lỗi cụ thể hơn trong từng phương pháp phân tích khác nhau. 2.4.1. Khôi phục lỗi trong phân tích tất định LL. * Một lỗi được phát hiện trong phân tích LL khi: - Ký hiệu kết thúc nằm trên đỉnh ngăn xếp không đối sánh được với ký hiệu đầu vào hiện tại. - Mục M(A,a) trong bảng phân tích là lỗi (rỗng). * Khắc phục lỗi theo kiểu trừng phạt là bỏ qua các ký hiệu trên xâu vào cho đến khi xuất hiện một ký hiệu thuộc tập ký hiệu đã xác định trước gọi là tập ký hiệu đồng bộ. Xét một số cách chọn tập đồng bộ như sau: a) Đưa tất cả các ký hiệu trong Follow(A) vào tập đồng bộ hoá của ký hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một phần tử của Follow(A) thì lấy A ra khỏi ngăn xếp và tiếp tục quá trình phân tích. b) Đưa tất cả các ký hiệu trong First(A) vào tập đồng bộ hoá của ký hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một phần tử thuộc First(A) thì quá trình phân tích được tiếp tục. Ví dụ: với ví dụ trên, ta thử phân tích xâu vào có lỗi là “)id*+id” với tập đồng bộ hoá của các ký hiệu không kết thúc được xây dựng từ tập First và tập Follow của ký hiệu đó. Ngăn xếp Xâu vào Hành động $E )id*+id$ M(E,)) = lỗi, bỏ qua ‘)’ để găp id ∈ First(E) $E id*+id$ E->TE’ $E’T id*+id$ T->FT’ $E’T’F id*+id$ F->id $E’T’id id*+id$ rút gọn id $E’T’ *+id$ T’->*FT’ $E’T’F* *+id$ rút gọn * $E’T’F +id$ M(F,+) = lỗi, bỏ qua. Tại đây xảy ra hai trường hợp(ta chọn a): a).bỏ qua + vì id ∈ First(F) b).bỏ qua F vì + ∈ Follow(F) $E’T’F id$ F->id $E’T’id id$ rút gọn id $E’T’ $ T’->ε $E’ $ E’->ε $ $ 2.4.2. Khôi phục lỗi trong phân tích LR. Một bộ phân tích LR sẽ phát hiện ra lỗi khi nó gặp một mục báo lỗi trong bảng action (chú ý sẽ không bao giờ bộ phân tích gặp thông báo lỗi trong bảng goto). Chúng ta có thể thực hiện chiến lược khắc phục lỗi cố gắng cô lập đoạn câu chứa lỗi cú pháp: quét dọc xuống ngăn xếp cho đến khi tìm được một trạng thái s có một hành động goto trên một ký hiệu không kết thúc A ngay sau nó. Sau đó bỏ đi không hoặc nhiều ký hiệu đầu vào cho đến khi gặp một ký hiệu kết thúc a thuộc Follow(A), lúc này bộ phân tích sẽ đưa trạng thái goto(s,A) vào ngăn xếp và tiếp tục quá trình phân tích. Phương pháp phân tích bảng CYK (Cocke – Younger – Kasami) - Giải thuật làm việc với tất cả các VP PNC. Thời gian phân tích là: n3 (n là độ dài xâu vào cần phân tích), nếu văn phạm không nhập nhằng thì thờI gian phân tích là: n2. - Điều kiện của thuật toán là văn phạm PNC ở dạng chuẩn chômsky (CNF) và không có ε sản xuất (sản xuất A → ε ) và các kí hiệu vô ích. Giải thuật CYK: - Tạo một hình tam giác (mỗi chiều có độ dài là n , n là độ dài của xâu). Thực hiện giải thuật: Begin 1) For i:=1 to n do ∆ ij = { A | A → a là một sản xuất và a là kí hiệu thứ i trong w}; 2) For j:=2 to n do For i:=1 to (n – j +1) do Begin ∆ ij = ∅; For k:=1 to (j -1) do ∆ ij = ∆ ij ∪ { A | A → BC là một sản xuất; B ∈ ∆ ik C∈ ∆ i+k, j -k }; end; end; Ví dụ: Xét văn phạm chuẩn chômsky S → AB|BC; A → BA|a; B → CC|b; C → AB|a; (1) (2) (3) (4) (5) (6) (7) (8) Xâu vào w= baaba; i j b a a b a B A,C A,C B A,C S,A B S,C S,A ∅ B B ∅ S,A,C S,A,C b a a b a B A,C A,C B A,C S,A B S,C S,A ∅ B B ∅ S,A,C S,A,C - Quá trình tính ∆ ij . VD: tính ∆ 24 , Tính: ∆ 21 = {A,C}, ∆ 33 = {B}, ∆ 21∆ 33 = {AB,CB} Do (1), (7) nên đưa S,C vào ∆ 24. ∆ 22 = {B}, ∆ 42 = {S,A}, ∆ 22∆ 42 = {BS,BA} Do (3) nên đưa A vào ∆ 24. ∆ 23 = {B}, ∆ 51 = {A,C}, ∆ 23∆ 51 = {BA,BC} (2),(3) nên đưa S,C vào ∆ 24. Kết quả: ∆ 24 = {S,A,C}. - Nếu S ở ô cuối cùng thì ta kết luận: Xâu vào phân tích thành công và có thể dựng được cây phân tích cho nó. Số lượng cây phân tích = số lượng S có trong ô này. b a a b a B A,C A,C B A,C S,A B S,C S,A ∅ B B ∅ S,A,C S,A,C A B S BB A C C b a C A B a a b Bài tập Luyện tập: cho văn phạm E -> T + E | T T -> a Hãy xây dựng bảng SLR(1) cho văn phạm trên Thực hành: Thử nghiệm trên văn phạm biểu thức nêu trên 1) xây dựng tập LR(0) tự động 2) xây dựng bảng phân tích SLR(1) tự động 3) phân tích xâu vào