Giáo trình môn học Trình biên dịch - Chương 4: Phân tích cú pháp

CHÖÔNG 4 PHAÂN TÍCH CUÙ PHAÙP 4.1. Vai troø cuûa boä phaân tích cuù phaùp - Phöông phaùp toång quaùt: Cocke-Younger-Kasami vaø Earley. - Phaân tích töø treân xuoáng. - Phaân tích töø döôùi leân. 4.2. Xaây döïng vaên phaïm cho ngoân ngöõ laäp trình Loaïi boû söï khoâng töôøng minh stmt → if exp then stmt if exp then stmt else stmt | other Thí duï: phaùt bieåu: if E1 then if E2 then S1 else S2 laø phaùt bieåu khoâng töôøng minh - Loaïi boû söï khoâng töôøng minh. Quy öùôc hoaëc söûa vaên phaïm. stmt → matched-stmt lunmatched-stmt matched-stmt→ if exp then matched-stmt else matched-stmt1 | other unmatched-stmt → if exp then stmt | if exp then matched-stmt else unmatched-stmt Loaïi boû ñeä quay traùi Vaên phaïm goïi laø ñeä quy traùi neáu toàn taïi daãn xuaát. A ⇒ Aα, vôùi α ⊂ ( Vt ∪ Vn) Ñeä quy traùi laø bao goàm ñeä quy traùi ñôn giaûn (tröïc tieáp) vaø ñeä quy traùi toång quaùt. Ñeå loaïi boû ñeä quy ñôn giaûn, ta seõ thay theáõ taäp luaät sinh: A → Aα1⏐Aα2⏐ ⏐Aαm⏐β1⏐β2⏐..⏐βn baèng caëp luaät sinh A→ β1A’⏐β2A’⏐⏐βnA.’ A’→α1A’⏐α2A’⏐ ..⏐αmA’⏐∈ Thí duï 4.1. Loaïi boû ñeä quy traùi cho vaên phaïm: E → E + T ⏐ T T → T * F ⏐ F F → (E) ⏐ id Giaûi thuaät 4.1. Loaïi boû ñeä qy traùi Nhaäp: Vaên phaïm G khoâng coù voøng laëp hoäi luaät sinh roãng. Xuaát : Vaên phaïm töông ñöông G’ khoâng coù ñeä quy traùi. Phöông phaùp: AÙp duïng giaûi thuaät ôû moâ phoûng 4.1 cho G. G’ khoâng coøn ñeä quy traùi nhöng coù theå coù luaät sinh roãng. Saép xeáp caucus kyù hieäu khoâng keát thuùc theo moät thöù töï naøo ñoù: A1, A2, . An . Moâ phoûng 4.1. Giaûi thuaät loaïi boû ñeä quy traùi töø vaên phaïm for i := 1 to n do for j := 1 to i - 1 do begin - Thay caùc luaät sinh coù daïng Ai → Aj γ baèng caùc luaät sinh Ai→ δ1γ⏐δ2γ⏐..⏐δkγ - Vôùi Aj luaät sinh coù daïng Ai → δ1⏐δ2⏐ .⏐δk - Loaïi taát caû caû caùc luaät sinh coù ñeä quy traùi tröïc tieáp trong caùc Ai luaät sinh end; Thí duï: Chuùng ta coù aùp duïng giaûi thuaät 4.1 vaøo vaên phaïm sau ñeå loaïi boû ñeä quy traùi. S→ Aa⏐ b A → Ac⏐ Sd ⏐∈ Thöøa soá traùi: Thí duï ta coù hai luaät sinh: stmt → if exp then stmt else stmt ⏐if exp then stmt Caû hai luaät sinh ñeàu coù if daãn ñaàu neân ta seõ khoâng bieát choïn luaät sinh naøo ñeå trieån khai. Vì theá ñeå laøm chaäm laïi quyeát ñònh löïa choïn chuùng ta seõ taïo ra thöøa soá traùi. Giaûi thuaät 4.2. Taïo vaên phaïm coù thöøa soá traùi Nhaäp: cho vaên phaïm G. Xuaát: vaên phaïm G’ coù thöøa soá traùi töông ñöông. Phöông phaùp: Tìm chuoãi daãn ñaàu chung cuûa caùc veá phaûi luaät sinh, thí duï: A → αβ1⏐αβ2⏐..⏐αβn⏐γ . γ laø chuoãi khoâng baét ñaàu bôûi α. Ta thay caùc luaät treân baèng caùc luaät A→αA’ A’→ β1⏐β2⏐⏐βn Thí du: ï Ta aùp duïng giaûi thuaät treân cho vaên phaïm phaùt bieåu if, nöôùc vaên phaïm töông ñöông S → i E t SS’⏐a S’→ e S⏐∈ E → b 4.3. Phaân tích cuù phaùp töø treân xuoáng Phaân tích cuù phaùp ñeä quy ñi xuoáng. Phaân tích cuù phaùp ñoaùn nhaän tröùôc. 1. Phaân tích cuù phaùp ñeä quy ñi xuoáng Thí duï: Cho vaên phaïm G : S→ cAd A → ab ⏐ a S S c cA d A d a b) a b a) Hình 4.4. Caùc böôùc phaân tích cuù phaùp töø treân xuoáng 2. Phaân tích cuù phaùp ñoaùn nhaän tröôùc - Haõy loaïi boû ñeä quy traùi cho vaên phaïm maø chuùng ta thieát keá. - Haõy taïo vaên phaïm coù thöøa soá traùi neáu caàn thieát. Sô ñoà dòch cho boä phaân tích ñoaùn nhaän tröôùc Sô ñoà naøy coù ñaëc ñieåm nhö sau: - Moãi kyù hieäu khoâng keát thuùc coù moät sô ñoà. - Teân caùc caïnh laø token vaø caùc kyù hieäu khoâng keát thuùc. Söï truyeàn treân token seõ ñöôïc thöïc hieän neáu kyù hieäu nhaäp truøng vôùi token ñoù. Neáu coù söï truyeàn treân kyù hieäu khoâng keát thuùc A thì ta thöïc hieän moät leänh goïi thuû tuïc A. Ñeå xaây döïng sô ñoà chuùng ta seõ tieán haønh caùc böôùc sau ñaây: 1. Taïo traïng thaùi baét ñaàu vaø keát thuùc. 2. Vôùi moãi luaät sinh coù daïng A Æ X1X2Xn , ta xaây döïng ñöôøng ñi töø traïng thaùi baét ñaàu ñeán traïng thaùi keát thuùc sao cho caùc caïnh coù teân X1, X2, X3Xn. Cô cheá hoaït ñoäng cuûa boä phaân tích ñoaùn nhaän tröôùc Thí duï 4.3. Chuùng ta haõy taïo sô ñoà dòch cho vaên phaïm G: E Æ TE’ E’Æ + TE’ |∈ T Æ FT’ T’Æ ∗ FT’ |∈ F’Æ (E) | id T E’ + T E’ E: T: F T’ T’: F’ T’ ∈ ∗ 2 9 1 3 Hình 4.5. Sô ñoà dòch cuûa caùc kyù hieäu khoâng keát thuùc cuûa G E’: ∈ 4 5 630 1 7 10 11 12 8 ( )∈ F: id 1 714 15 16 )( E Hình 4.6. Sô ñoà dòch cuûa caùc kyù hieäu khoâng keát thuùc cuûa G, ñaõ ñöôïc thu giaûm Giaûi thuaät: procedure E; procedure T; procedure F; begin nextchar (c); if c = ‘(‘ then begin match (‘(‘); E; match (‘)‘); end else if c = id then match (id) else error; E: F: id 6 170 14 15 163 + T: 7 10 ∗ 13 T ∈ ∈F end; {F} begin F; while c = ‘*‘ do F; end; {T} begin T; while c = ‘+‘ do T; end; {E} 3. Phaân tích cuù phaùp ñoaùn nhaän tröôùc khoâng ñeä quy Caáu taïo cuûa boä phaân tích cuù phaùp Stack a1a2 an $ boä ñeäm nhaäp X Chöông trình ñieàu khieån Y Z $ Baûng phaân tích M Xuaát Hình 4.7. Moâ hình caáu taïo cuûa boä phaân tích ñoaùn nhaän tröôùc khoâng ñeä quy. Hoaït ñoäng cuûa boä phaân tích ÔÛ traïng thaùi baét ñaàu, stack chæ chöùa caùc kyù hieäu muïc tieâu cuûa vaên phaïm naèm treân $, treân ñænh stack. Baûng phaân tích M laø ma traän. Hai kyù hieäu X vaø a seõ xaùc ñònh haønh vi cuûa boä phaân tích. Boä phaân tích coù ba haønh vi nhö sau: 1. Neáu X = a = $. 2. Neáu X = a ≠ $. 3. Neáu X laø kyù hieäu khoâng keát thuùc. Giaûi thuaät 4.2. Phaân tích cuù phaùp ñoaùn nhaän tröôùc khoâng ñeä quy. Nhaäp: chuoãi nhaäp w vaø baûng phaân tích M cho vaên phaïm G. Xuaát: neáu w thuoäc L (G), seõ taïo ra daãn xuaát traùi cuûa w, ngöôïc laïi seõ baùo loãi. Phöông phaùp: luùc ñaàu caáu hình cuûa boä phaân tích laø ($S, w$) vôùi S laø kyù hieäu muïc tieâu cuûa G. Ñaët ip (laø con troû hoaëc coøn goïi laø ñaàu ñoïc cuûa boä phaân tích) vaøo kyù hieäu nhaäp ñaàu tieân cuûa w$. Moâ phoûng 4.2. Chöông trình phaân tích cuù phaùp ñoaùn nhaän tröôùc repeat X treân stack vaø kyù hieäu a ñang ñöôïc ñaàu ñoïc ip ñoïc; if X laø kyù hieäu keát thuùc hoaëc $ then if X = a then begin - ñaåy X ra khoûi stack; - dòch ñaàu ñoïc ñeán kyù hieäu nhaäp keá tieáp; end else error () else ifM [X, a] = X Æ X1X2Xk then begin - ñaåy X ra khoûi stack; - ñaåy XkXk-1 X1 leân stack (X1 treân ñænh stack); - xuaát luaät sinh X Æ X1X2 Xk ; end else error () until X = $ Thí duï 4.4. Giaû söû chuùng ta coù vaên phaïm G. E Æ E + T | T T Æ T ∗ F | F F Æ (E) | id Chuùng ta seõ thöïc hieän loaïi boû ñeä quy traùi, nhaän ñöôïc G’: E Æ TE’ E’Æ + TE’ |∈ T Æ FT’ T Æ ∗ FT’ |∈ F Æ (E) | id Baây giôø chuùng ta seõ phaân tích cuù phaùp cho caâu nhaäp w = id + id * id baèng baûng phaân tích M cho tröôùc, ôû Baûng 4.1. Baûng 4.1. Baûng phaân tích M cho vaên phaïm G Kyù hieäu nhaäpKyù hieäu khoâng keát thuù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) Quaù trình phaân tích cuù phaùp caâu nhaäp w = id + id ∗ id seõ ñöôïc trình baøy ôû baûng 4.2. Baûng 4.2. Caùc böôùc phaân tích cuù phaùp caâu id + id ∗ id Stack Chuoãi nhaäp Xuaát Stack Chuoãi nhaäp Xuaát $E id + id ∗ id $ $E’T’F id ∗ id $ T Æ FT’ $E’T id + id ∗ id $ E Æ TE’ $E’T’id id ∗ id $ F Æ id $E’T’F id + id ∗ id $ T Æ FT’ $E’T’ ∗ id $ $E’T’id id + id ∗ id $ F Æ id $E’T’F∗ ∗ id $ T’Æ ∗FT’ $E’T’ + id ∗ id $ $E’T’F id $ $E’ + id ∗ id $ T’Æ ∈ $E’T’id id $ F Æ id $E’T+ + id ∗ id $ E’Æ +TE’ $E’T’ $ $E’T id ∗ id $ $E’ $ T’Æ ∈ $ $ E’Æ ∈ Xaây döïng baûng phaân tích M a. first vaø follow first(α) laø taäp c kyù hieäu keát thuùc a, daãn ñaàu caùc chuoãi ñöôïc daãn xuaát töø α, α ⇒ aγ. Neáu α ⇒ ∈ thì ∈ thuoäc first(α). follow(A) laø taäp caùc kyù hieäu keát thuùc a, xuaát hieän ngay beân phaûi A trong daïng caâu. Nhö vaäy toàn taïi daãn xuaát S ⇒ αAaβ. Neáu giöõa A vaø a toàn taïi chuoãi kyù hieäu, thì noù seõ daãn xuaát ra chuoãi roãng. Neáu A ôû taän cuøng beân phaûi cuûa daïng caâu thì $ thuoäc follow(A). - Caùc quy taéc tính first(X) vôùi X laø kyù hieäu vaên phaïm. - Caùc quy taéc tính follow(A) cho taát caû caùc kyù hieäu khoâng keát thuùc A. Thí duï 4.5. Cho vaên phaïm G. E Æ TE’ E’Æ + TE’⏐∈ T Æ FT’ T’Æ ∗ FT’⏐∈ F’Æ (E)⏐id Toaøn boä caùc haøm first vaø follow cuûa caùc kyù hieäu vaên phaïm cuûa G : first(E) = first(T) = first(F) = {(, id} first(E’) = {+, ∈} ; first(T’) = {*, ∈} follow(E) = follow(E’) = {$, )} follow(T) = follow(T’) = {+, $, )} follow(F) = {*, +, $, )} b. Xaây döïng baûng phaân tích M Giaûi thuaät 4.3. Xaây döïng baûng phaân tích M. Nhaäp: vaên phaïm G. Xuaát: baûng phaân tích M. Phöông phaùp: 1. Vôùi moãi luaät sinh A Æ α haõy thöïc thi böôùc 2 vaø 3. 2. Vôùi moãi kyù hieäu keát thuùc a thuoäc first(α), theâm A Æ α vaøo M[A, a]. 3. Neáu kyù hieäu ∈ thuoäc first(α), theâm A Æ α vaøo M[A, b] sao cho b thuoäc follow(A). Neáu $ thuoäc follow(A) thì theâm A Æ α vaøo M [A, $]. 4. Nhöõng phaàn töû cuûa baûng M troáng, haõy ñaùnh daáu loãi. Vaên phaïm LL (1) Thí duï 4.7. Cho vaên phaïm G. S Æ iEtSS’⏐a ; S’Æ eS⏐∈ ; E Æ b Baûng 4.3. Baûng phaân tích M cho thí duï 4.7. Kyù hieäu nhaäpCaùc kyù hieäu khoâng KT a b e i t $ S S Æ a S Æ iEtSS’ S’ S’Æ ∈ S’Æ eS S’Æ ∈ E E Æ b - Vaên phaïm khoâng coù phaàn töû naøo cuûa baûng phaân tích M coù nhieàu hôn moät trò thì ñöôïc goïi laø vaên phaïm LL (1). - Vaên phaïm LL (1) coù caùc tính chaát sau. Khaéc phuïc loãi trong phaân tích cuù phaùp ñoaùn nhaän tröôùc Loãi xuaát hieän trong caùc tröôøng hôïp sau: Moät laø kyù hieäu keát thuùc treân stack khoâng truøng vôùi kyù hieäu nhaäp ñang ñöôïc ñoïc. Hai laø A laø kyù hieäu khoâng keát thuùc treân ñænh stack, a treân chuoãi nhaäp, ñöôïc ñoïc, maø M [A, a] laø troáng. Moät soá heuristics ñöôïc aùp duïng cho vieäc khaéc phuïc loãi. Thí duï 4.8. Cho vaên phaïm E Æ TE’ ; E’Æ + TE’⏐∈ ; T Æ FT’ ; T’Æ * FT’⏐∈; F Æ (E)⏐id first(E) = first(T) = first(F) = {(, id)} first(E’) = {+, }∈; first (T’) = {*, }∈ follow(E) = follow(E’) = {$, )} follow(T) = follow(T’) = {+, $, )} follow(F) = {*, +, $, )} Baûng 4.4. Phaân tích M coù kyù hieäu khaéc phuïc loãi. Kyù hieäu nhaäpKyù hieäu khoâng KT 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 4.4. Phaân tích cuù phaùp töø döôùi leân Phaân tích cuù phaùp töø döôùi leân ñöôïc hieåu laø phaân tích ñaåy vaø thu giaûm (Shift-Reduce parsing) laø phöông phaùp phaân tích LR. Thí duï 4.9. Cho vaên phaïm G. S Æ aABe ; A Æ Abc⏐b ; BÆ d Phaân tích caâu w = abbcde. Toùm taét caùc böôùc thu giaûm nhö sau: Quaù trình thu giaûm neáu theo chieàu ngöôïc laïi thì ñoù chính laø quaù trình daãn xuaát phaûi. Quaù trình naøy ñaõ sinh caây cuù phaùp cuûa caâu phaân tích töø döôùi leân. Hình 4.8. Caây cuù phaùp ñöôïc xaây döïng töø döôùi leân cuûa caâu w = abbcde. Handle Tìm kieám handle Baét ñaàu töø chuoãi caàn phaân tích w, ta ñaët w = γn . γn laø daïng caâu ñöôïc daãn xuaát ôû laàn thöù n. S = γ0⇒ γ1⇒ γ2⇒ ⇒ γn-1⇒ γn = w Xaây döïng daãn xuaát phaûi ngöôïc töø w = γn . Ta tìm βn trong γn sao choβn laø veá phaûi luaät sinh AnÆ βn . Thay βn trong γn baèng An , ta nhaän ñöôïc daïng caâu thöù (n – 1) laø γn – 1. Quaù trình thu giaûm cöù tieáp tuïc nhö vaäy cho ñeán khi ñaït ñöôïc γo chæ coøn laø moät kyù hieäu khoâng keát thuùc vaø laø kyù hieäu muïc tieâu. 1. Phaân tích cuù phaùp thöù töï yeáu Vaên phaïm coù tính chaát: khoâng coù luaät sinh naøo coù veá phaûi laø chuoãi roãng (A Æ ∈) hoaëc ôû veá phaûi khoâng coù hai kyù hieäu khoâng keát thuùc ñöùng keà nhau goïi laø vaên phaïm thöù töï yeáu. n rm rmrm 2 r -1 rmrm 1 Boä phaân tích cuù phaùp thöù töï yeáu 1. Caáu taïo $ X1 X2 Xn-1 Xn Y1 Y2 Yn-1 Yn $ Chöông trình phaân tích Baûng phaân tích S-R Hình 4.9. Moâ hình boä phaân tích cuù phaùp thöù töï yeáu Xuaát 2. Hoaït ñoäng Thí duï 4.10. Cho vaên phaïm cuûa phaùt bieåu gaùn Æ id = Æ + | Æ * ⏐ Æ id ⏐ () Kyù hieäu laø kyù hieäu muïc tieâu. Baûng 4.6. Baûng phaân tích S-R cho vaên phaïm ôû thí duï 4.10. id ∗ + ( ) = $ R* S S R S R R R R R R R id R R R S R * S S + S S ( S S ) R R R R = S S $ S Giaûi thuaät 4.4. Phaân tích cuù phaùp thöù töï yeáu Moâ phoûng 4.3. Giaûi thuaät cuûa chöông trình phaân tích thöù töï yeáu - Luùc ñaàu stack traïng thaùi chæ coù kyù hieäu $. Stack nhaäp chöùa chuoãi nhaäp, ñöôïc keát thuùc bôûi daáu $ ; c:=false ; repeat if Kyù hieäu muïc tieâu ôû treân ñænh vaø kyù hieäu $ ôû ñaùy stack traïng thaùi, ñoàng thôøi stack nhaäp chæ chöùa $ then c:=true /∗phaân tích thaønh coâng, caây cuù phaùp xaây döïng xong∗/ else begin - X ôû treân ñænh stack traïng thaùi, Y ôû treân ñænh stack nhaäp. - Giaû söû T laø trò cuûa phaàn töû S-R [X, Y]; if T laø roãng then error () else if T = R then if treân ñænh stack coù chöùa veá phaûi cuûa luaät sinh naøo ñoù then begin - Goïi A Æ X1 X2 Xn laø luaät sinh naøo coù veá phaûi daøi nhaát so truøng vôùi chuoãi treân stack traïng thaùi: (a) Giaûi toûa X1 X2 Xn ra khoûi stack; (b) Thay A leân stack. (c) Taïo nuùt môùi A treân caây cuù phaùp, coù caùc con laø X1 X2 Xn end else error () else begin (a) Giaûi toûa Y ra khoûi stack nhaäp; (b) Ñaåy Y leân ñænh stack traïng thaùi; (c) Tao nuùt môùi teân Y treân caây cuù phaùp; end; end; until c; 3. Xaây döïng baûng phaân tích S-R Ñònh nghóa caùc quan heä : - Chuùng ta noùi X <• Y neáu vaø chæ neáu toàn taïi moät luaät sinh maø veá phaûi coù daïng XA vôùi A laø kyù hieäu khoâng keát thuùc vaø sinh ra moät chuoãi baét ñaàu baèng Y (A ⇒ Y). - X •> Y neáu vaø chæ neáu toàn taïi moät luaät sinh maø veá phaûi coù daïng AB. A sinh ra moät chuoãi kyù hieäu ñöôïc keát thuùc baèng X (A ⇒ X). B sinh ra moät chuoãi ñöôïc baét ñaàu baèng Y (B ⇒ Y), hoaëc B = Y. ÔÛ ñaây coù hai tröôøng hôïp xaûy ra trong quaù trình tìm caùc moái quan heä cho caëp (X, Y): • Tröôøng hôïp 1: Y laø kyù hieäu keát thuùc Tröôøng hôïp 2: Y laø kyù hieäu khoâng keát thuùc. a. Toàn taïi $ ≤• A vôùi A laø kyù hieäu muïc tieâu cuûa vaên phaïm cho tröôùc. b. Neáu veá phaûi luaät sinh coù X naèm keà ngay Y veà phía traùi (XY) thì X ≤• Y c. Neáu X ≤• Y maø toàn taïi moät luaät sinh Y Æ Z1 Zn thì X ≤• • Z1 d. Toàn taïi A •> $ vôùi A laø kyù hieäu muïc tieâu e. Neáu X ≤• •Y vaø toàn taïi moät luaät sinh X Æ Z1 Zn thì Zn • > Y g. Neáu X •> Y vaø toàn taïi moät luaät sinh Y Æ Z1 Zn thì X • > Z1 4. Vaên phaïm thöù töï yeáu Moät vaên phaïm ñöôïc goïi laø thöù töï yeáu neáu thoûa caùc ñieàu kieän sau: 1. Khoâng coù hai luaät sinh coù cuøng moät veá phaûi. 2. Khoâng coù phaàn töû S-R [X, Y] naøo cuûa baûng S-R vöøa coù trò S vöøa coù trò R. 3. Neáu toàn taïi luaät sinh AÆX1 X2 Xn vaø luaät sinh BÆXiXi+1 Xn thì khoâng toàn taïi quan heä Xi – 1 ≤• • B. 2. Boä phaân tích cuù phaùp LR - Caùc tính chaát cuûa phöông phaùp phaân tích LR - Giaûi thuaät phaân tích cuù phaùp LR 1. Boä phaân tích cuù phaùp coù caáu taïo nhö sau: a1 a2 ai an $ Sm Xm Sm –1 Xm – 1 $ action goto baûng phaân tích Chöông trình ñieàu khieån boä ñeäm nhaäp Stack xuaát Hình 4.11. Moâ hình boä phaân tích cuù phaùp LR 2. Hoaït ñoäng Stack ñöôïc duøng ñeå chöùa chuoãi kyù hieäu coù daïng s0 X1 s1 X2 Xm sm. Caëp (sm, ai ) seõ xaùc ñònh moät trò ñöôïc löu chöùa trong baûng phaân tích. Baûng phaân tích goàm hai phaàn bieåu thò bôûi haøm action vaø goto. Caáu hình (configuration) cuûa boä phaân tích LR: s0 X1 s1 Xi si Xm sm, ai ai+1 an $). Caáu hình naøy cho chuùng ta daïng caâu X1 X2 Xm ai ai+1 an. Giaûi thuaät 4.5. Phaân tích cuù phaùp LR Nhaäp: chuoãi nhaäp w, baûng phaân tích action goto cuûa vaên phaïm G. Xuaát: neáu w thuoäc L (G), noù taïo ra söï phaân tích töø döôùi leân. Ngöôïc laïi, boä phaân tích seõ baùo loãi. Phöông phaùp: - Thôøi ñieåm ban ñaàu stack coù traïng thaùi s0. - Chuoãi w$ naèm treân boä ñeäm nhaäp. - Boä phaân tích ñaët ñaàu ñoïc (con troû ip) vaøo kyù hieäu nhaäp ñaàu tieân cuûa w. c:=false; /*c laø bieán luaän lyù, baùo cho bieát quaù trình phaân tích keát thuùc*/ repeat - Ñaët s laø traïng thaùi treân ñænh stack a laø kyù hieäu nhaäp ñöôïc ip chæ ñeán if action [s, a] = shift(s’) then begin (a)ñaåy a leân stack (b)sau ñoù ñaåy s’ leân ñænh stack (c)chuyeån ip sang kyù hieäu nhaäp keá tieáp; end else if action [s, a] = reduce(A Æ β) then begin (a)ñaåy (2*⏐β⏐) kyù hieäu ra khoûi stack, s’ laø traïng thaùi treân ñænh stack (b)Tìm j = goto [s’, A]; (c)ñaåy A vaø sau ñoù laø j leân ñænh stack; (d)xuaát luaät A Æ β end else if action [s, a] = accept then c := true else error (); until c; Thí duï 4.12. Cho vaên phaïm G (1) E Æ E + T (2) E Æ T (3) T Æ T * F (4) T Æ F (5) F Æ (E) (6) F Æ id Baûng 4.8. Baûng phaân tích cho vaên phaïm G ôû thí duï 4.12. action goto id + * ( ) $ 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 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Traïng thaùi Thí duï: Phaân tích caâu w = id ∗ id + id Vaên phaïm LR Xaây döïng baûng phaân tích SLR Ñònh nghóa thöïc theå LR (0) Thí duï: G coù luaät sinh A Æ XYZ, seõ cho boán thöïc theå: AÆ•XYZ; AÆX•YZ; AÆXY•Z; AÆXYZ• Neáu A Æ ∈ seõ cho ta thöïc theå A Æ • • YÙ töôûng cô baûn cuûa giaûi thuaät xaây döïng baûng phaân tích SLR laø töø vaên phaïm, chuùng ta ñi tìm DFA, nhaän daïng chuoãi daãn ñaàu beân traùi cuûa daïng caâu (viable prefixe). Ñònh nghóa vaên phaïm gia toá: neáu G laø vaên phaïm, thì G’ laø vaên phaïm gia toá, laø G coù S’ laø kyù hieäu muïc tieâu vaø coù theâm luaät sinh S’Æ S. Pheùp bao ñoùng – Closure. Giaûi thuaät tính closure. Moâ phoûng 4.4. Giaûi thuaät tính haøm closure function closure (| : item) : item; begin J := |; repeat for vôùi moãi thöïc theå A Æ α.Bβ trong J vaø vôùi moãi luaät sinh B Æ γ trong G sao cho thöïc theå B Æ • γ chöa coù trong J do theâm B Æ • γ vaøo J; until khoâng theå theâm thöïc theå môùi vaøo J; closure := J; end; Giaûi thuaät tính goto: haøm goto (I, X) vôùi I laø taäp caùc thöïc theå, X laø kyù hieäu vaên phaïm. Goto (I, X) laø closure cuûa taäp caùc thöïc theå coù daïng A Æ αX.β sao cho thöïc theå A Æ α.Xβ ôû trong I. Moâ phoûng 4.5. Giaûi thuaät tính taäp tuyeån caùc taäp thöïc theå procedure items (G’); begin C := {closure ({S’Æ • S}}} repeat for vôùi moãi taäp thöïc theå I trong C vaø vôùi moãi kyù hieäu vaên phaïm X sao cho pheùp goto (I, X) khoâng roãng vaø khoâng coù trong C do theâm goto (I, X) vaøo C; until khoâng theå theâm taäp thöïc theå môùi vaøo C; end; Thí duï 4.13. Cho vaên phaïm gia toá G’ E’Æ E ; E Æ E + T ; E Æ T T Æ T* F ; T Æ F ; F Æ (E) ; F Æ id Haõy tìm taäp C vaø sô ñoà DFA. Xaây döïng baûng phaân tích SLR Giaûi thuaät 4.6. Xaây döïng baûng phaân tích Nhaäp: vaên phaïm gia toá G’ Xuaát: baûng phaân tích SLR vôùi haøm action vaø goto cho vaên phaïm G’ Phöông phaùp: 1. Xaây döïng C = {Io, I1, In}. 2. i laø traïng thaùi ñaïi dieän cho taäp thöïc theå Ii. a. Neáu A Æ α•aβ laø thöïc theå ôû trong Ii vaø goto (Ii, a) = Ij thì phaàn töû action [i, a] = shift(j), vôùi a phaûi laø kyù hieäu keát thuùc. b. Neáu A Æ α• ôû trong Ii thì action [i, a] = reduce(A Æα) vôùi a laø taát caû caùc kyù hieäu naèm trong follow (A). A khoâng phaûi laø S’ (kyù hieäu muïc tieâu môùi). c. Neáu S’Æ S• ôû trong Ii thì action [i, $] = accept. 3. Cho taát caû caùc kyù hieäu khoâng keát thuùc A. Neáu goto [Ii, A]=Ij thì haøm goto [i, A]=j. 4. Taát caû caùc phaàn töû cuûa baûng phaân tích khoâng ñöôïc xaùc ñònh baèng quy taéc 2 vaø 3, chuùng ta coi laø loãi. 5. Traïng thaùi baét ñaàu cuûa boä phaân tích laø taäp thöïc theå coù chöùa thöïc theå S’Æ•S. Thí duï 4.14. Xaây döïng baûng phaân tích SLR cho vaên phaïm G ôû thí duï 4.13. Thí duï 4.15. Cho vaên phaïm G. (1) S Æ L = R (2) S Æ R (3) L Æ * R (4) L Æ id (5) R Æ L Ta nhaän thaáy ñuïng ñoä khi action [2, =] = s6 ñoàng thôøi action [2, =] = r5 vaø action [2, $] = r5. Do ñoù taïi phaàn töû action [2, =] coù hai trò s6 vaø r5. Nhö vaäy G khoâng phaûi laø vaên phaïm SLR. Xaây döïng baûng phaân tích Canonical LR Daïng toång quaùt cuûa thöïc theå laø [A Æ α.β, a] vôùi A Æ αβ laø luaät sinh vaø a laø kyù hieäu keát thuùc hoaëc daáu $. Thöïc theå coù daïng nhö theá ñöôïc goïi laø thöïc theå LR (1). Neáu β = ∈ thì thöïc theå seõ coù daïng [A Æ α• , a]. Luùc naøy chuùng ta thöïc hieän thu giaûm baèng luaät sinh A Æ α chæ vôùi ñieàu kieän kyù hieäu nhaäp keá tieáp laø a. Chuùng ta noùi thöïc theå LR (1) [A Æ α.β, a] laø hôïp leä vôùi chuoãi kyù hieäu daãn ñaàu daïng caâu γ neáu toàn taïi daãn xuaát phaûi: S ⇒ δAw ⇒ δαβw vôùi rm rm 1. γ = δα vaø 2. hoaëc a laø kyù hieäu daãn ñaàu cuûa w, hoaëc w = ∈ thì a laø $. Thí duï 4.16. Cho vaên phaïm G S Æ BB B Æ aB | b Tính taäp tuyeån caùc thöïc theå LR (1) Pheùp tính closure Giaûi thuaät 4.7. Xaây döïng caùc taäp thöïc theå LR (1). Moâ phoûng 4.7. Giaûi thuaät tính caùc taäp thöïc theå LR (1) cho vaên phaïm gia toá G’ function closure (I: items): items; begin repeat for vôùi moãi thöïc theå [A Æ α • Bβ, a] trong , vôùi moãi luaät sinh B Æ η trong G’ vaø vôùi moãi kyù hieäu keát thuùc b thuoäc first sao cho thöïc theå [B Æ • η, b] khoâng coù trong | do theâm thöïc theå [B Æ η, b] vaøo | until khoâng theå theâm thöïc theå môùi vaøo |; closure := |; end; function goto (| :items; X: symbol): items; begin j laø taäp caùc thöïc theå coù daïng [A Æ αX• β, a] sao cho thöïc theå [A Æ α• Xβ, a] ôû trong | ; goto := closure (J); end; procedure items (G’); begin d := {closure ({S’Æ• S, $}}}; repeat for vôùi moãi taäp thöïc theå | ôû trong C vaø vôùi moãi kyù hieäu vaên phaïm X sao cho goto (|, X) khoâng roãng vaø chöa coù trong C do theâm goto (|, X) vaøo C; until khoâng theå theâm taäp thöïc theå môùi vaøo C; end; Thí duï 4.17. Xaây döïng caùc taäp thöïc theå LR (1) cho vaên phaïm gia toá G’: S’Æ .S ; S Æ CC ; C Æ cC|d Giaûi thuaät 4.8. Xaây döïng baûng phaân tích Canonical LR. Nhaäp: vaên phaïm gia toá G’ Xuaát: baûng phaân tích Canonical LR vôùi hai haøm action vaø goto cho G’ Phöông phaùp: 1. Xaây döïng C = {Io, I1, , In}. 2. Traïng thaùi i ñaïi dieän cho Ii. a. Neáu thöïc theå [A Æ α.aβ, b] ôû trong Ii vaø goto (Ii , a) = Ij thì phaàn töû action [i, a] = shift(j), a phaûi laø kyù hieäu keát thuùc. b. Neáu [A Æ α• , a] ôû trong Ii, A ≠ S’ thì action[i, a]=reduce(AÆα) c. Neáu [S’Æ S• , $] ôû trong Ii thì action [i, $] = accept. 3. Neáu goto (Ii , A) = Ij thì phaàn töû goto [i, A] = j. 4. Taát caû caùc phaàn töû khoâng aùp duïng ñöôïc quy taéc 2 vaø 3 thì laø loãi. 5. Traïng thaùi baét ñaàu cuûa boä phaân tích cuù phaùp laø taäp thöïc theå co chöùa thöïc theå [S’Æ •S , $]. Baûng phaân tích Canonical LR cho vaên phaïm ôû thí duï 4.17. ñöôïc xaây döïng döïa vaøo giaûi thuaät 4.7. Baûng 4.10. Baûng phaân tích Canonical LR action goto c d $ S C 0 1 2 3 4 5 6 7 8 9 s3 s6 s3 r3 s6 r2 s4 s7 s4 r3 s7 r2 acc r1 r3 r2 1 2 5 8 9 Traïng thaùi Boä sinh phaân tích cuù phaùp Boä sinh phaân tích cuù phaùp Yacc Trình bieân dòch Yacc Trình bieân dòch C a.out a.out daãn xuaát Taäp tin ñaëc taû Yacc translate.y y.tab.c y.tab.c chuoãi token Hình 4.14. Taïo boä phaân tích cuù phaùp baèng Yacc. Thí duï 4.23. Chuùng ta seõ taïo taäp tin ñaëc taû vaên phaïm cho Yacc cuûa vaên phaïm G. E Æ E + T | T T Æ T * F | F F Æ (E) | digit Moâ phoûng 4.10. Taäp tin ñaëc taû vaên phaïm cho Yacc ôû thí duï 4.23. % { # include % } % token DIGIT % % line : exp ′\n′{printf (″% d\n″, $1) ;} ; exp : exp ′+′ term {$$ = $1 + $3;} : term ; term : term ′*′ factor {$$ = $1 + $3;} : factor ; factor : ′(′exp′)′ {$$ = $2;} : DIGIT ; %% yylex ( ) { int c ; c = getchar ( ) ; if (isdigit (c)) { yylval = c - ′0′ ; return DIGIT; } return c; } Phaàn ñaëc taû Phaàn caùc luaät bieân dòch: Æ | | Luaät bieân dòch trong Yacc: : {haønh vi ngöõ nghóa 1} : {haønh vi ngöõ nghóa 2} : {haønh vi ngöõ nghóa n} Phaàn caùc chöông trình con C phuï trôï