Giáo án Trình Biên dịch

359 trang huongle 6480

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo án Trình Biên dịch", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_an_trinh_bien_dich.pdf

Nội dung text: Giáo án Trình Biên dịch

MOÂN HOÏC TRÌNH BIEÂN DÒCH
MUÏC LUÏC CHƯƠNG I CHƯƠNG 6 Giớithiệuvề trình bieân dòch Xử lí ngữ nghĩa CHƯƠNG 2 CHƯƠNG 7 Trình bieân dòch ñơngiản Quảnlíbộ nhớ trong thời CHƯƠNG 3 gian thựcthi Phaân tích từ vựng CHƯƠNG 8 CHƯƠNG 4 Tổ chứcbảng danh biểu Phaân tích cuù phaùp CHƯƠNG 9 CHƯƠNG 5 Sinh maõ ñoái töôïng Trình bieân dịch trựctiếpcuù CHƯƠNG 10 phaùp Toái öu maõ
TAØI LIEÄU THAM KHAÛO 1) Alfred V.Aho, Jeffrey D.Ullman (1986). Compilers, Principles techniques, and tools. Addison – Wesley Publishing Company. 2) Alfred V.Aho, Jeffrey D.Ullman (1972). The theory of parsing, translation and compiling. Prentice – Hall, inc. 3) Terrence W. Pratt. Programming Languages: design and implementation second edition. Prebtice – Hall International editions. 4)Allen I. Holub. Compiler design in C. Prentice – Hall International editions. 5) D. Gries (1976). Compiler construction. Springger – Verlag. 6) Jeffrey D. Ullman (1977). Fundamental concepts of programming system. Addion - Wesley Publsihing Company. 7) Döông Tuaán Anh (1986) Giaùo trình Trình bieân dòch. Ñaïi hoïc Baùch Khoa TP. Hoà Chí Minh. 8) Nicklaus Wirth (1976), Algorithms + Data Structure = program. Prentice – Hall International editions. 9) Alfred V.Aho, Jeffrey D. Ullman (1977). Principles of compiler design. Addison – Wesley, Reading, Mass. 10) Leâ Hoàng Sôn, Luaän vaên toát nghieäp “Xaây döïng giaûi thuaät toái öu maõ trung gian cuûa trình bieân dòch” – Khoa CNTT Tröôøng ÑH Baùch khoa 2002. 11) Phan Thò Töôi (2001). Trình Bieân Dòch. Ñaïi hoïc Baùch Khoa TP. Hoà Chí Minh
YEÂU CAÀU Phaàn Lyù thuyeát: SV hoïc 42 tieát lyù thuyeát Phaàn Thöïc haønh: SV tham döï thöïc haønh – thöïc hieän Baøi taäp Moân hoïc 14t (1 Baøi taäp Moân hoïc / 1 SV) Hình thöùc ñaùnh giaù: Kieåm tra Baøi taäp Moân hoïc Æ Ñieåm TH Thi vieát Lyù thuyeát cuoái kyø Æ Ñieåm LT Caùch tính ñieåm: Ñieåm toång keát moân = LT * 60% + BTTH * 40%
CHÖÔNG 1 GIÔÙI THIEÄU VEÀ TRÌNH BIEÂN DÒCH 1.1. Ngoân ngöõ laäp trình 1. Giôùi thieäu Phaân loaïi Chöông trình dòch - Trìnhbieândòch Döõ lieäu Chöông Trình Chöông Maùy tính Keát quaû trình nguoàn bieân dòch trình ñích thöïc thi Hình 1.1. Chöông trình thöïc thi theo cô cheá dòch cuûa trình bieân dòch
- Trình thoâng dòch Chöông trình Trình thoâng Keát quaû nguoàn dòch Döõ lieäu Hình 1.2. Chöông trình thöïc thi theo cô cheá dòch cuûa trình thoâng dòch Ñaëc taû ngoân ngöõ laäp trình 1. Taäp caùc kyù hieäu caàn duøng trong caùc chöông trình hôïp leä 2. Taäp caùc chöông trình hôïp leä 3. Nghóa cuûa chöông trình hôïp leä - Phöông phaùp thöù nhaát laø ñònh nghóa baèng pheùp aùnh xaï. Söû duïng pheùp toaùn haøm: haøm Lamda. - Phöông phaùp thöù hai: Maùy tröøu töôïng. - Phöông phaùp thöù ba: Taäp (x,y) laø söï bieân dòch.
2. Cuù phaùpvaø ngöõ nghóa - AÙnh xaï cuù phaùp (syntactic mapping) the pig is the pen Hình 1.3 Caáu truùc caây cuûa caâu tieáng Anh: the pig is in the pen
- AÙnh xaï cuù phaùp + ∗ a b c Hình 1.4. Caây cuù phaùp cuûa bieåu thöùc soá hoïc a + b * c
1.2. Trình bieân dòch 1. Caùc thaønh phaàn cuûa trình bieân dòch 1. Phaân tích töø vöïng Nhaän daïng token. Token: danh bieåu, haèng, töø khoùa, caùc toaùn töû pheùp toaùn, caùc kyù hieäu phaân caùch, khoaûng traéng, caùc kyù hieäu ñaëc bieät Ví duï: COST := ( PRICE + TAX )*65 Ñaàu ra cuûa boä phaân tích töø vöïng: ( ) := ( ( ) + ( ) ) * ( ,4) Vieát goïn : id1 := (id2 + id3) * num4 Boä phaân tích töø vöïng thao taùc tröïc tieáp Boä phaân tích töø vöïng thao taùc khoâng tröïc tieáp
2. Baûng danh bieåu Ví duï: COST := (PRICE + TAX) * 65 Baûng 1.1 Baûng danh bieåu Chæ soá token lexeme Caùc thoâng tin khaùc 1 id COST bieán thöïc 2 id PRICE bieán thöïc 3 id TAX bieán thöïc 4 num 65 haèng soá nguyeân 3. Phaùt hieän vaø thoâng baùo loãi 4. Phaân tích cuù phaùp Ví duï: COST := (PRICE + TAX) * 65 Keát quaû phaân tích töø vöïng: id1 := ( id2 + id3 )* num4
Keát quaû phaân tích cuù phaùp: n3 id n2 1 := n1 num * 4 id2 + id3 Hình 1.6. Caây cuù phaùp cuûa phaùt bieåu 5. Phaân tích ngöõ nghóa n3 n id1 := 2 n 2 * intoreal (65) id2 + id3 65.0 PRICE TAX Hình 1.7. Caây cuù phaùp coù xöû lyù ngöõ nghóa
6. Sinh maõ trung gian temp1 := intoreal (65) temp2 := id2 + id3 temp3 := temp2 * temp1 id1 := temp3 7. Toái öu maõ trung gian temp1 := id2 + id3 id1 := temp1 + 65.0 8. Sinh maõ ñoái töôïng movF id2, R1 movF id3, R2 addF R2, R1 multF # 65.0, R1 movF R1, id1
COST := (PRICE + TAX) * 65 Boä phaân tích töø vöïng id := (id2 + id3) * num4 Boä phaân tích cuù phaùp n1 id n2 1 := n3 * num4 id2 + id3 Boä phaân tích ngöõ nghóa n1 n2 id1 := n3 * intoreal (65) id2 + id3
Boä sinh maõ trung gian temp1 := intoreal (65) temp2 := id3 + id3 temp3 := temp2 * temp1 id1 := temp3 Boä toái öu trung gian temp1 := id2 + id3 id1 := temp1 * 65.0 Boä sinh maõ ñoái töôïng movF id2 , R1 movF id3 , R2 ADDF R2 . R1 mulF # 65.0, R 1 Hình 1.8. Bieân dòch phaùt bieåu movF R1 ,id1
1.3. Caùc moái lieân quan vôùi trình bieân dòch 1. Boä tieàn xöû lyù - Xöû lyù macro (macro processing) - Cheâm taäp tin (file inclusion) - Boä xöû lyù hoaø hôïp (rational processor) - Môû roäng ngoân ngöõ (language extension) Thí duï veà xöû lyù macro: - Heä thoáng maùy ñaùnh chöõ typesetting: \define { } Thí duï macro ñònh nghóa veà söï trích daãn cuûa taïp chí ACM: \define\JACM # 1; #2; #3 {{\S1J.ACM}{\bf #1}: #2, pp.#3} Khi duøng macro: \JACM 17; 4; 715-728 Seõ ñöôïc hieåu nhö sau: J.ACM 17 : 4 , pp. 715-728
2. Trình bieân dòch hôïp ngöõ Phaùt bieåu gaùn b := a + 2 ñöôïc dòch ra maõ hôïp ngöõ MOV a, R1 ADD #2 , R1 MOV R1, b 3. Trình bieân dòch hôïp ngöõ hai chuyeán - Chuyeán thöù nhaát: ñoïc maõ hôïp ngöõ vaø taïo baûng danh bieåu Danh bieåu Ñiaï chæ töông ñoái a 0 b 4 - Chuyeán thöù hai: ñoïc maõ hôïp ngöõ vaø dòch sang maõ maùy khaû ñònh vò ñòa chæ: MOV a, R1 0001 010000000000* ADD #2, R1 0010 0110 00000010 (1.6) MOV R1, b 0100 010000000100*
4. Boä caát lieân keát soaïn thaûo Loader laø chöông trình thöïc hienä hai nhieäm vuï: caát vaø soaïn thaûo lieân keát. Quaù trình caát bao goàm laáy maõ maùy khaû ñònh vò tính laïi thaønh ñòa chæ tuyeät ñoái. Nhö ôû ví duï phaàn 3: Giaû söû maõ maùy ñöôïc caát trong boä nhôù trong taïi ñòa chæ L = 00001111; ñòa chæ tuyeät ñoái cuûa a, b laø 00001111 vaø 00010011. Ba chæ thò (1.6) ñöôïc vieát laïi döôùi daïng maõ maùy tuyeät ñoái: 0001010000001111 0011011000000010 (1.7) 0010010000010011 Link-editor cho pheùp taïo moät chöông trình duy nhaát töø nhieàu taäp tin ôû daïng maõ maùy khaû ñònh vò cuûa nhöõng laàn bieân dòch rieâng bieät vaø töø caùc taäp tin thö vieän do heä thoáng cung caáp.
Chöông trình nguoàn vieát taét Boä tieàn xöû lyù Chöông trình nguoàn Trình bieân dòch Chöông trình ñoái töôïng trong maõ hôïp ngöõ Trình bieân dòch hôïp ngöõ Chöông trình trong maõ maùy khaû ñònh vò Thö vieän heä thoáng, caùc taäp tin ñoái töôïng Boä caát/ lieân keát – soaïn thaûo khaû ñònh vò ñòa chæ Chöông trình maõ maùy ñòa chæ tuyeät ñoái Hình 1.19. Heä thoáng xöû lyù ngoân ngöõ
1.4. Nhoùm caùc giai ñoaïn cuûa trình bieân dòch - Giai ñoaïn tröôùc vaø giai ñoaïn sau (front end and back end) - Caùc chuyeán - Thu giaûm soá löôïng caùc chuyeán Thí duïï: goto L : goto L : L : a = b + c
CHÖÔNG 2 TRÌNH BIEÂN DÒCH ÑÔN GIAÛN 2.1. Toång quaùt Chuoãi kyù töï Boä phaân tích Chuoãi token Boä bieân dòch tröïc Maõ trung gian töø vöïng tieáp cuù phaùp Hình 2.1. Caáu truùc trình bieân dòch “front end” 2.2. Ñònh nghóa cuù phaùp Vaên phaïm phi ngöõ caûnh (PNC) ñöôïc ñònh nghóa: G2 = (Vt, Vn, S, P) P : A →α1 |α2 | |αn Thí duï 2.1. Cho vaên phaïm G: P: list → list + digit | list – digit | digit digit → 0 |1| 2 | |9
Thí duï 2.2. Vaên phaïm mieâu taû phaùt bieåu hoãn hôïp begin end cuûa Pascal P : block → begin opt_stmts end opt_stmts → stmt_list |€ stmt_list → stmt_list ; stmt | stmt - Caây phaân tích Söï khoâng töôøng minh Thí duï 2.3. Vaên phaïm G sau ñaây laø khoâng töôøng minh: P : string → string + string | string – string | 0 | 1 | |9 Caâu 9 – 5 + 2 cho hai caây phaân tích: string string string + string string - string string - string 2 9 string + string 9 5 5 2 a) b) Hình 2.2 Hai caây phaân tích cuûa caâu 9 – 5 + 2
Söï keát hôïp cuûa caùc toaùn töû Möùc öu tieân cuûa caùc toaùn töû: * vaø / coù möùc öu tieân hôn + , - . Döïa vaøo nguyeân taéc treân chuùng ta xaây döïng cuù phaùp cho bieåu thöùc soá hoïc: exp → exp + term | exp – term | term term → term * factor | term / factor | factor factor → digit | ( exp ) Löu yù: pheùp toaùn luõy thöøa vaø pheùp gaùn trong C laø pheùp toaùn keát hôïp phaûi. Vaên phaïm cho pheùp gaùn nhö sau: right → letter = right | letter letter → a | b | | z 2.3. Söï bieân dòch tröïc tieáp cuù phaùp (Syntax-Directed Translation) 1. Kyù hieäu haäu toá 1) Neáu E laø bieán hoaëc haèng soá thì kyù hieäu haäu toá cuûa E chính laø E. 2) Neáu E laø bieåu thöùc coù daïng E1 op E2 vôùi op laø toaùn töû hai ngoâi thì kyù hieäu haäu toá cuûa E laø E1’E2’ op. 3) Neáu E laø bieåu thöùc coù daïng (E1) thì kyù hieäu haäu toá cuûa E1 cuõng laø kyù hieäu haäu toá cuûa E.
Löu yù: Khoâng caàn coù daáu ñoùng, môû ngoaëc trong kyù hieäu haäu toá. 2. Ñònh nghiaõ tröïc tieáp cuù phaùp (Syntax-directed definition) Vaên phaïm phi ngöõ caûnh vaø taäp luaät ngöõ nghiaõ seõ thieát laäp ñònh nghóa tröïc tieáp cuù phaùp. Bieân dòch laø pheùp aùnh xaï töø nhaäp → xuaát. Daïng xuaát cuûa chuoãi nhaäp x ñöôïc xaùc ñònh nhö sau: 1. Xaây döïng caây phaân tích cho chuoãi x. 2. Giaû söû nuùt n cuûa caây phaân tích coù teân cuù phaùp X, X.a laø trò thuoäc tính a cuûa X, ñöôïc tính nhôø luaät ngöõ nghóa. Caây phaân tích coù chuù thích caùc trò thuoäc tính ôû moãi nuùt ñöôïc goïi laø caây phaân tích chuù thích Toång hôïp thuoäc tính (synthesized attributes) Thí duï 2.4. Cho vaên phaïm G coù taäp luaät sinh P: Taäp luaät sinh Taäp luaät ngöõ nghóa exp → exp + term exp.t ::= exp.t || term.t || ‘+’ exp → exp – term exp.t ::= exp.t || term.t || ‘-’ exp → term exp.t ::= term.t term → 0 term.t ::= ‘0’ term → 9 term.t ::= ‘9’
exp.t ::= 95 – 2 + exp.t ::= 95 – termt ::= 2 exp.t ::= 9 termt.t ::= 5 termt ::= 9 9 - 5 + 2 Hình 2.3. Caây phaân tích chuù thích cho ñònh nghóa tröïc tieáp cuù phaùp Löôïc ñoà dòch Löôïc ñoà dòch laø vaên phaïm PNC, trong ñoù caùc ñoaïn chöông trình goïi laø haønh vi ngöõ nghiaõ ñöôïc nhuùng vaøo veá phaûi cuûa luaät sinh. Thí duï 2.5. Löôïc ñoà dòch cuûa vaên phaïm G:
Taäp luaät sinh Taäp luaät ngöõ nghóa exp → exp + term exp → exp + term { print (‘+’)} exp → exp – term exp → exp – term {print (‘-’)} exp → term exp → term term → 0 term → 0 {print (‘0’)} . term → 9 term → 9 {print {‘9’)} exp exp + term {print (‘+‘)} exp - term {print (‘-‘)} { } term 2 print (‘2‘) 5 {print (‘5‘)} 9 {print (‘9‘)} Hình 2.4. Löôïc ñoà dòch cuûa caâu 9 – 5 + 2
Moâ phoûng 2.1. Giaûi thuaät depth- first traversals cuûa caây phaân tích Procedure visit (n: node); begin for vôùi moãi con m cuûa n, töø traùi sang phaûi do visit (m); tính trò ngöõ nghiaõ taïi nuùt n end; 2.4. Phaân tích cuù phaùp 1. Phaân tích cuù phaùp töø treân xuoáng Thí duï 2.6. Cho vaên phaïm G: type → simple ⏐↑ id ⏐ array [ simple] of type simple → integer ⏐char ⏐num dotdot num Haõy xaây döïng caây phaân tích cho caâu: array [num dotdot num] of integer
a) type b) type array [simple] of type c) type array [simple] of type Hình 2.6.Caùc num dotdot num böôùc xaây döïng d) type caây phaân tích array theo phöông [simple] of type phaùp töø treân num dotdot num simple xuoáng cho caâu: array e) type [numdotdot array [simple] of type num] of integer num dotdot num simple integer
2. Söï phaân tích cuù phaùp ñoaùn nhaän tröôùc Daïng ñaëc bieät cuûa phaân tích cuù phaùp töø treân xuoáng laø phöông phaùp ñoaùn nhaän tröôùc. Phöông phaùp naøy seõ nhìn tröôùc moät kyù hieäu nhaäp ñeå quyeát ñònh choïn thuû tuïc cho kyù hieäu khoâng keát thuùc töông öùng. Thí duï 2.8. Cho vaên phaïm G: P: S → xA A → z | yA Duøng vaên phaïm G ñeå phaân tích caâu nhaäp xyyz Baûng 2.1. Caùc böôùc phaân tích cuù phaùp cuûa caâu xyyz Luaät aùp duïng Chuoãi nhaäp S xyyz xA xyyz yA yyz A yz yA yz A z z z - -
Thí duï 2.9. Cho vaên phaïm vôùi caùc luaät sinh nhö sau : S → A | B A → xA | y B → xB | z Baûng 2.2. Phaântíchcuùphaùpchocaâuxxxzkhoângthaønhcoâng Luaät aùp duïng Chuoãi nhaäp S xxxz A xxxz xA xxxz A xxz xA xxz A xz xA xz A z
- Ñieàu kieän 1 : A Æ ξ1 |ξ2 | |ξn - Ñònh nghóa: first (ξi) = {s | s laø kyù hieäu keát thuùc vaø ξ⇒s } Ñieàu kieän 1 ñöôïc phaùt bieåu nhö sau : A →ξ1 |ξ2 | |ξn first (ξi) ∩ first (ξj) = ∅ vôùi i ≠ j Löu yù: 1. first (aξ ) = {a} 2. Neáu A →α1 |α2 | |αn; thì first (Aξ) = first (α1) ∪ first (α2) ∪ first (αn) Thí duï 2.11. Cho vaên phaïm G coù taäp luaät sinh: S → Ax A → x |∈ vôùi ∈ laø chuoãi roãng Baûng 2.3. Phaân tích caâu nhaäp : x Luaät Chuoãi nhaäp A x xx x x -
Söï phaân tích thaát baïi - Ñieàu kieän 2: first (A) ∩ follow (A) = ∅ Vôùi A →ξ1 |ξ2 | |ξn |∈ Follow (A) ñöôïc tính nhö sau: Vôùi moãi luaät sinh Pi coù daïng X →ξAη thì follow (A) laø first (η ). ÔÛ thí duï 2.11 first (A) ∩ follow (A) = {x} Löu yù vaên phaïm coù ñeä quy traùi seõ vi phaïm ñieàu kieän 1. Thí duï: A → B | AB (2.1) Vaäy first (A) = first (B) ; first (AB) = first (A) = first (B). first (B) ∩ first (AB) ≠∅ vi phaïm ñieàu kieän 1. Neáu söûa luaät (2.1) thaønh A →∈|AB thì seõ vi phaïm ñieàu kieän 2. Thí duï 2.12. Cho vaên phaïm nhö ôû thí duï 2.6, chuùng ta duøng phöông phaùp phaân tích ñoaùn nhaän tröôùc ñeå phaân tìch caâu array[num dot dot num] of integer (töï xem ôû trang 41). Caùc thuû tuïc ñöôïc goïi khi sinh caây phaân tích cho caùc caâu thuoäc vaên phaïm ôû thí duï 2.12.
2.5. Trình bieân dòch cho bieåu thöùc ñôn giaûn Thí duï: exp → exp + term {print (‘+’)} (2.5) exp → exp – term {print (‘-’)} exp → term term → 0 {print (‘0’} . term → 9 {print (‘9’} Loaïi boû ñeä quy traùi: exp → term rest exp.t ::= term.t || rest.t rest → + exp rest.t ::= exp.t || ‘+’ rest → - exp rest.t ::= exp.t || ‘-’ rest →∈ term → 0 term.t ::= ‘0’ rest →∈
term → 0 term.t ::= ‘0’ term → 9 term.t ::= ‘9’ Vaên phaïm naøy khoâng phuø hôïp cho bieân dòch tröïc tieáp cuù phaùp. Löôïc ñoà dòch: exp → exp + term {print (‘+’)} exp → exp –term {print (‘-’)} exp → term term → 0 {print (‘0’)} term → 9 {print (‘9’)} Loaïi boû ñeä quy traùi cho löôïc ñoà dòch: exp → term rest rest→ + term {print (‘+’)}| - term {print (‘-’)}|∈ term → 0 {print (‘0’) } . term → 9 {print (‘9’)}
Caây phaân tích chuù thích cho caâu: 9-5 = 2 ôû tr.44 Chöông trình bieân dòch bieåu thöùc töø daïng trung toá sang daïng haäu toá: procedure exp; procedure match ( t : token ); begin if lookahead = t then lookahead := nexttoken else error end; procedure term ; begin if lookahead = num then begin write ( num); match (lookahead); end else error end; procedure rest; begin
if lookahead = ‘ +‘ then begin match (‘+‘); term; write (‘+’); end else if lookahead = ‘-’ then begin match (‘-’); term; write(‘-’); end; end; begin term; rest; end; Toái ưutrinh̀ bieân dich:̣ Đeå taêng toác doä bieân dòch ta thöïc hieân gôõ ñeä quy cuûa thuû tuïc rest: procedure exp; procedure term; begin
: end; begin term; repeat if lookahead = ‘+’ then begin match (‘+’); term; write(‘+’); end else if lookahead = ‘-’ then begin match(‘-’); term; write(‘-’) end; until (lookahead ‘+’) and (lookahead ‘-’); end;
Hoaøn chænh chöông trình: Chöông trình naøy bao goàm caû chöông trình ñoïc chuoãi nhaäp. procedure exp; procedure match (t : char); begin if lookahead = t then lookahead := readln (c); else error end; procedure term; begin val (i,lookahead,e); if e = 0 then begin write (i); match (lookahead ); end else error; end;{term} begin
term; repeat if lookahead = ‘+’ then begin match (‘+’); term; write(‘+’); end else if lookahead = ‘-’ then begin match (‘-’); term; write(‘-’); end; until (lookahead ‘+’ ) and (lookahead ‘-’); end; {exp } begin readln( c); lookahead := c; exp; end;
2.6. Söï phaân tích töø vöïng 1. Loaïi boû khoaûng traéng vaø chuù thích 2. Nhaän bieát caùc haèng 3. Nhaän bieát danh bieåu vaø töø khoùa Giao tieáp vôùi boä phaân tích töø vöïng if ab>=0 t >=0 t >=0 t h if ab> ab> Hình 2.10. Nhaän daïng token cuûa boä phaân tích töø vöïng
2.7. Söï hình thaønh baûng danh bieåu 1. Giao tieáp vôùi baûng danh bieåu Hai thao taùc vôùi baûng danh bieåu: insert (s,t) vaø lookup (s). 2. Löu giöõ töø khoùa 3. Hieän thöïc baûng danh bieåu Baûng danh bieåu goàm coù baûng symtable vaø daõy lexemes. Baûng symtable lexptr token caùc thuoäc tính khaùc 0 1 1 div 2 5 mod 39 id 415 id
Daõy lexemes d i v EOS m o d EOS c o u n t EOS i EOS Hình 2.11. Baûng danh bieåu Moâ phoûng 2.2. Giaûi thuaät phaân tích töø vöïng Procedure lexan; var lexbuf array [0 100] of char; c : char; ngöng : boolean; begin repeat read (c ); ngöng := true; if (c = blank ) or (c = tab) then ngöng := false else if c = newline then begin line := lineno + 1 ngöng := false; end else if c laø chöõ soá then
begin val (i, c, e); tokenval := 0; while e = 0 do begin tokenval := tokenval * 10 + i; read (c); val (i, c, e); end; typetoken := num; end {laø soá} else if c laø chöõ then begin p := 0; b := 0; while c laø chöõ hoaëc soá do begin lexbuf [b] := c; read (c);
b := b + 1; if b => b_size then error end; /* b size laø kích thöôùc toái ña cuûa lexbuf*/ lexbuf [b] := eos; p := lookup (lexbuf); if p = 0 then p = insert (lexbuf, ID); tokenval := p; typetoken := symtable [p]. token; end else if c = eof then begin tokenval := none; typetoken := done; {heát chöông trình nguoàn} end else begin tokenval := none; typetoken := c;
end until ngöng; end; 2.8. Maùy tröøu töôïng kieåu choàng Vuøng chæ thò Choàng Vuøng döõ lieäu 1push 5 5 + 0 1 2 rvalue 2 11 t 11 2 3+ a) 73 4rvalue3 4 5 ∗ pc 16 ∗ 6 7 t b) 112 t c) Hình 2.12. Maùy tröøu töôïng kieåu choàng vôùi vieäc thöïc thi bieåu thöùc (5 + 11) * 7
1. Chæ thò soá hoïc 2. Lvalue vaø Rvalue Thí duï: i := i + 1 3. Thao taùc vôùi choàng Caùc chæ thò: Lvalue, Rvalue, push v, pop, copy, := 4. Bieân dòch cho bieåu thöùc Thí duï: Bieân dòch phaùt bieåu gaùn: day := (53*y) div 4 + (273 * m + 2) div 5 + d chuyeån sang kyù hieäu haäu toá day 53y * 4 div 273 m * 2 + 5 div + d + := dòch sang maõ maùy tröøu töôïng 5. Chæ thò ñieàu khieån trình töï Caùc chæ thò bao goàm: label l, goto l, gotofalse l, gototrue l, halt. 6. Söï bieân dòch caùc phaùt bieåu Thí duï: Phaùt bieåu if: ngöõ nghóa stmt→ if exp then stmt out := newlabel stmt.t ::= exp.t || ‘gotofalse’ out || stmt.t || ‘label’ out
vuøng chæ thò Ñoaïn maõ cho exp gotofalse out Ñoaïn maõ cho stmt label out Ñoaïn maõ cuûa phaùt bieåu sau phaùt bieåu if Hình 2.13. Maõ maùy tröøu töôïng cuûa phaùt bieåu if 7. Giaûi thuaät cuûa trình bieân dòch caùc phaùt bieåu procedure stmt; var out : integer; begin if lookahead = id then begin emit (‘lvalue’, tokenval); match (id); match (‘ := ‘); exp; emit (‘:=‘, tokenval) end
else if lookahead = ‘if’ then begin match (‘if’); exp; out := newlabel; emit (‘gotofalse’, out); match (‘then’); stmt; emit (‘label’,out) end else error end; 2.9. Thieát keá trình bieân dòch ñôn giaûn 1. Ñaëc taû trình bieân dòch start→ list eof list→ exp ; list |∈ exp → exp + term {print (‘+’)} lexp – term {print (‘-’)} | term term → term * factor {print (‘*’)}
| term / factor {print(‘/’)} | term div factor {print (‘div’)} | term mod factor {print (‘mod’)} | factor factor → (exp) | id | num Bieåu thöùc ôû daïng trung toá init scanner symbol parser error emit Bieåu thöùc ôû daïng haäu toá Hình 2.14. Sô ñoà cuûa trình bieân dòch cho bieåu thöùc töø daïng trung toá sang daïng haäutoá
2. Nhieäm vuï cuûa caùc chöông trình con cuûa trình bieân dòch scanner: phaân tích töø vuïng; parser: phaân tích cuù phaùp; emit: taïo daïng xuaát cuûa token; symbol: xaây döïng baûng danh bieåu vaø thao taùc vôùi baûng danh bieåu baèng insert vaø lookup; init: caát caùc töø khoùa vaøo baûng danh bieåu; error: thoâng baùo loãi. Moâ phoûng 2.3. Löôïc ñoà dòch tröïc tieáp cuù phaùp cuaû G sau khi ñöôïc boû ñeä quy traùi: start → list eof list → exp ; list |∈ exp → term Rest1 Rest1 → + term {print (‘+’)} Rest1 |∈ | -term {print (‘-’-)}|∈ term → factor Rest2 Rest2 →*factor {print (‘*’)} Rest2 l/ factor {print (‘/’)} Rest2 | div factor {print (div’)} Rest2 |∈ | mod factor {print (mod’)} Rest2 |∈ factor → (exp) | id {print (id.lexeme)} | num {print(num.value)}
3. Giaûi thuaät cuûa trình bieân dòch const bsize = 128; |para = 40; none = ‘#’; plus = 43; num = 256; minus = 45; div = 257; star = 42; mod = 258; slash = 47; id = 259; done = 260; strmax = 999; symax = 100; type entry = record lexptr : integer; token : integer; end; str = string; var tokenval : integer; lineno : integer; lookahead : char;
symtable : array [1 100] of entry; lexbuf : string [bsize]; typetoken : integer; lexemes: array[1 strmax] of char; lastentry : integer; lastchar : integer; procedure scanner; var t: char; p, b, i: integer; begin read (t); if (t = ‘ ‘ ) or (t = \t’) then repeat read (t); until (t ‘ ‘) and (t ‘\t’); else if t = ‘\t’ then begin lineno := lineno + 1; read ( t ); end
else if t in [‘0’ ’9’] then begin val ( i,t,e); tokenval := 0; while e = 0 do begin tokenval := tokenval *10 + I; read (t); val (i,t,e); end; typetoken := num; end else if t in [ ‘A’ ’Z’,’a’ ’z’] then begin p:= 0; b := 0; while t in [‘0’ ’9’,’A’ ’Z’,’a’ ’z’] do begin lexbuf [b] := t; read (t); b := b + 1; if (b > = bsize) then
error end; lexbuf [b] := eos; p := lookup (lexbuf); if p = 0 then p := insert ( lexbuf, id); tokenval := p; typetoken := symtable[p].token; end else if t = eof then typetoken := done else begin typetoken := ord (t); read (t) end; tokenval := none; end; end; {scanner} /* */ procedure parser;
procedure exp; var t : integer; procedure term; var t : integer; procedure factor; begin case lookahead of |para : begin match ( lpara); exp; match(rpara); end; num : begin emit (num, tokenval); match (num) end; id : begin emit (id, tokenval ); match (id) end; else error (‘ loãi cuù phaùp’, lineno); end; {case} end; {factor} /* */
begin {term} factor; while lookahead in [star, slash, div, mod] do begin t := lookahead; match (lookahead); factor; emit (t, none); end; end; {term} begin {exp} term; while (lookahead = plus) or (lookahead = minus) do begin t := lookahead ; match (lookahead); term; emit (t, none); end; end; begin {parser} scanner; lookahead := typetoken;
while lookahead done do begin exp; match (semicolon); end; end; {parser} /* */ procedure match (t : integer); begin if lookahead = t then begin scanner; lookahead := typetoken ; end else error (‘ loãi cuù phaùp’, lineno); end; procedure emit (t : integer; tval : integer); begin case t of plus, minus, star, slash : writeln (chr (t )); div : writeln (‘div’); mod : writeln (‘mod’); num : writeln (tval);
id : wrteln (symtable[tval].lexptr^); else writeln (chr (t). tval); end; end; {emit} fuction strcmp (cp : integer; s: str) : integer; var i, l : integer; begin i := t; l := length (s); while ( I l then strcmp := 1 else strcmp := 0 end; {strcmp} procedure strcopy (cp : integer; t : str); var i : integer; begin
for i := 1 to length (t) do begin lexemes [cp] := t [i] cp := cp + 1; end; lexemes [cp] := eos; end; {Strcopy} function lookup (s : string) : integer; var I, p: integer; begin p := lastentry; while (p > 0) and (Strcmp (symtable [p].lexptr ^ , s) = 0) do p := p – 1;
lookup := p; end; {lookup} /* */ function insert (s : str; typetoken : integer) : integer; var len: integer; begin len := length (s ); if (lastentry + 1 > = symax ) then error (‘baûng danh bieåu ñaày’, lineno); if (lastchar + len + 1 > = strmax ) then error (‘daõy lexemes ñaày, lineno); lastentry := lastentry + 1; symtable [ lastentry].token := typyetoken; symtable [latsentry].lexptr := @lexemes[lastchar + 1]; lastchar := lastchar + len + 1;
strcopy (symtable [latsentry].lexptr ^, s) insert := lastentry; end; {insert} /* */ procedure init; var keyword : array[1.3] of record lexeme : string [10] token : integer; end; r, i : integer; begin keyword [i].lexeme := ‘div’; keyword [1].token := div; keyword [2].lexeme:= ‘mod’; keyword [2].token := mod; keyword [3].lexeme := ‘0’; keyword [3].token := 0; r := 3;
for i := 1 to r do p := insert (keyword [i].lexem, keyword [i].token); end; /* */ procedure error (m : str; lineno : integer); begin writeln (m, lineno); stop; end; /* */ begin {main} lastentry := 0; lineno := 0; tokenval := -1; lastchar := 0; init; parser; end; {main}
CHÖÔNG 3 PHAÂN TÍCH TÖØ VÖÏNG 3.1. Vai troø cuaû boä phaân tích töø vöïng 1. Token, maãu, trò töø vöïng Baûng 3.1 Baûng danh bieåu cuûa token Token Trò töø vöïng YÙ nghóa cuûa maãu const const const if if if then then then ralation , = , > = caùc toaùn töû quan heä num 3.14, 2.5, 7.6 haèng soá baát kyø id abc, ou, bc1 chuoãi goàm kyù töï chöõ vaø soá, baét ñaàu laø kyù töï chöõ literal ‘abcef’ laø chuoãi kyù töï baát kyø naèm giöõa 2 daáu ‘
Chöông trình token nguoàn Boä phaân tích Boä phaân töø vöïng tích CP yeâu caàu token Baûngdanhbieåu Hình 3.1. Söï giao tieáp giöõa boä phaân tích töø vöïng vaø boä phaân tích cuù phaùp 3.2. CAÙC TÍNH CHAÁT CUÛA TOKEN 3.3. CHÖÙA TAÏM CHÖÔNG TRÌNH NGUOÀN 1. Caëp boä ñeäm Caáu taïo
A : = B * . - 2 eof p1 p2 Hình 3.2. Caëp boä ñeäm Quy trình hoaït ñoäng Giaûi thuaät: if p2 ôû ranh giôùi moät nöûa boä ñeäm then begin laáp ñaày N kyù hieäu nhaäp môùi vaøo nöûa beân phaûi p2 := p2 + 1; end else if p2 ôû taän cuøng beân phaûi boä ñeäm then begin laáp ñaày N kyø hieäu nhaäp vaøo nöûa beân traùi boä ñeäm chuyeån p2 veà kyù töï taän cuøng beân traùi cuûa boä ñeäm end else p2 := p2 + 1;
2. Phöông phaùp caàm canh A:=B*XEOF -2EOF EOF N kyù töï N kyù töï p1 p2 Hình 3.3. Caëp boä ñeäm theo phöông phaùp caàm canh Giaûi thuaät: p2 := p2 + 1; if p2 ^ eof then if p2 ôû ranh giôùi moät nöûa boä ñeäm then begin chaát ñaày N kyø hieäu nhaäp vaøo nöûa beân phaûi boä ñeäm; p2 := p2 + 1 end
else if p2 ôû taän cuøng beân phaûi boä ñeäm then begin laáp ñaày N kyù hieäu vaøo nöû beân traùi boä ñeäm; chuyeån p2 veà ñaàu boä ñeäm end else /* döøng söï phaân tích töø vöïng */ 3.4. Ñaëc taû token Caùc quy taéc ñònh nghiaõ bieåu thöùc chính quy 1. ∈ laø bieåu thöùc chính quy, bieåu thò cho taäp {∈} 2. a laø kyù hieäu thuoäc Σ, bieåu thò cho taäp {a} 3. r vaø s laø hai bieåu thöùc chính quy, bieåu thò cho L (r) vaø L (s) thì: ø a) (r) | (s) laø bieåu thöùc chính quy, bieåu thò cho L(r) ∪ L(s). b) (r) (s) laø bieåu thöùc chính quy, bieåu thò cho L(r) L(s). c) (r)* laø bieåu thöùc chính quy, bieåu thò cho (L(r))*. d) r laø bieåu thöùc chính quy, bieåu thò cho L(r).
Thí duï 3.1. Cho Σ = {a, b} 1. a|b 2. (a| b) | (b| a) 3. a* Hai bieåu thöùc chính quy töông ñöông r vaø s, kyù hieäu r = s. 2. Ñònh nghóa chính quy Neáu Σ laø taäp kyù hieäu caên baûn, thì ñònh nghiaõ chính quy laø chuoãi ñònh nghiaõ coù daïng: d1 → r1 dn → rn Thí duï 3.2. letter → A | B | |Z | a| b | | z digit → 0 |1| | 9 id → letter ( letter | digit)* Thí duï 3.3. digit → 0 | 1 | | 9 digits → digit digit* optional_fraction → .digits |∈ optional_exponent → (E (+| - |∈) digits) |∈
3.5. Nhaän daïng token Thí duï 3.4. Cho vaên phaïm G: stmt → if exp then stmt | if exp then stmt else stmt |∈ exp → term relop term | term term → id | num Ñònh nghóa chính quy if → if then → then else → else relop → | >= | <> | = id → letter (letter | digit)* num → digit+ (.digit+ |∈) ( E ( + | - |∈) digit+ |∈) delim → blank | tab | newline ws → delim+ Töø ñònh nghóa chính quy ta xaây döïng baûng maãu cho token nhö ôû baûng 3.3 trang 74.
3.6. Sô ñoà dòch 1. Mieâu taû > = Baét ñaàu 0 6 7 Hình 3.4. Sô ñoà dòch cho >= vaø = * other 8 Start 3 return (relop, NE) other * 4 return (relop, LT) = 5 return (relop, EQ) > = 6 7 (relop, EQ) other * 8 return (relop, EQ) Hình 3.5. Sô ñoà dòch nhaän daïng token relop
Löu yù: - Phaàn khai baùo bao goàm khai baùo haèng, bieán bieåu thò vaø caùc ñònh nghóa chính quy. - Phaàn quy taéc bieân dòch laø caùc phaùt bieåu coù daïng: p1 →{haønh vi ngöõ nghóa 1} p2 →{haønh vi ngöõ nghóa 2} pn →{haønh vi ngöõ nghóa n} 3.8. Automat höõu haïn 1. Automat höõu haïn khoâng taát ñònh (NFA) Thí duï: Cho NFA: Taäp traïng thaùi S = {0, 1,2, 3}; Σ = {a, b}; Traïng thaùi baét ñaàu so = 0; Taäp traïng thaùi keát thuùc F = {3}.
Baûng 3.4. Baûng truyeànchoNFA ôû hình 3.10 Kyù hieäu nhaäp Traïng thaùi ab 0 {0, 1}{0} 1-{2} 2-{3} NFA chaáp nhaän moät chuoãi nhaäp x neáu vaø chæ neáu toàn taïi moät ñöôøng naøo ñoù trong sô ñoà töø traïng thaùi baét ñaàu ñeán traïng thaùi keát thuùc sao cho taát caû teân cuûa caùc caïnh con ñöôøng cho chuoãi x. NFA chaáp nhaän chuoãi aabb. 2. Automat höõu haïn taát ñònh (DFA) DFA laø tröôøng hôïp ñaëc bieät cuûa NFA, noù khoâng coù: i) Söï truyeàn roãng. ii) Vôùi moãi traïng thaùi s vaø kyù hieäu nhaäp a chæ toàn taïi nhieàu nhaát moät caïnh coù teân a xuaát phaùt tö øs.
Giaûi thuaät 3.1. Moâ phoûng hoaït ñoäng cuûa DFA treân chuoãi nhaäp x. Thí duï 3.5 start a a b b 0 0 1 1 3 Hình 3.12. DFA nhaän daïng ngoân ngöõ (a | b)*abb 3. Chuyeån NFA sang DFA Giaûi thuaät 3.2. Xaây döïng taäp con (Taïo DFA töø NFA). Nhaäp: Cho NFA goïi laø N. Xuaát: DFA goïi laø D, nhaän daïng cuøng ngoân ngöõ nhö NFA. Phöông phaùp: Xaây döïng baûng truyeàn cho D. Moãi traïng thaùi cuûa D laø taäp traïng thaùi cuûa N. D moâ phoûng ñoàng thôøi moïi chuyeån ñoäng cuûa N treân chuoãi nhaäp cho tröôùc baèng caùc taùc vuï: ∈-closure (s); ∈-closure (T); move (T, a)
Moâ phoûng 3.2. Xaây döïng taäp con Giaûi thuaät: Tính ∈-closure Ñaåy taát caû caùc traïng thaùi trong T leân stack; Khôûi taïo ∈-closure (T) cho T. Moâ phoûng 3.3. Tính ∈-closure Thí duï 3.6. (H.3.13 ) laø NFA nhaän daïng ngoân ngöõ (a | b )* abb. Chuùng ta duøng giaûi thuaät 3.2 ñeå xaây döïng DFA töông ñöông. a ∈ 2 3 ∈ start ∈ a b b 0 1 6 7 8 9 10 ∈ b 4 5 ∈ Hình 3.13. NFA nhaän daïng (a | b)* abb
3.9. Töø bieåu thöùc chính quy ñeán NFA Xaây döïng NFA töø bieåu thöùc chính quy Giaûi thuaät 3.3. Xaây döïng NFA töø bieåu thöùc chính quy (Caáu truùc Thompson’) Nhaäp: Bieåu thöùc chính quy r treân Σ. Xuaát: NFA nhaän daïng ngoân ngöõ L (r). Phöông phaùp: Quy taéc: 1. Vôùi ∈ , xaây döïng NFA start ∈ i f 2. Vôùi a thuoäc Σ, xaây döïng NFA start a i f
3. Giaû söû N( s ) vaøN( t ) laø NFA cho bieåu thöùc chính quy s vaø t - Vôùi s | t xaây döïng NFA hoãn hôïp N (s| t) ∈ N(s) ∈ start i f ∈ ∈ N(t) - Vôùi bieåu thöùc st, xaây döïng NFA hoãn hôïp N (st) start N(s) N(t) i f
- Vôùi bieåu thöùc s* , xaây döïng NFA N (s*) ∈ start ∈ ∈ i f ∈ - Bieåu thöùc s thì N (s) laø NFA nhaän daïng L (s) Caùc tính chaát cuaû NFA xaây döïng theo caáu truùc Thompson’ Thí duï 3.7. Giaûi thuaät 3.4. Moâ phoûng NFA Nhaäp: NFA goïi laø N ñöôïc xaây döïng theo giaûi thuaät 3.3, chuoãi nhaäp x. X ñöôïc keát thuùc baèng eof, N coù traïng thai baét ñaàu s0 vaø taäp traïng thaùi keát thuùc F. Xuaát: Giaûi thuaät traû lôøi ñuùng neáu N chaáp nhaän x, ngöôïc laïi traû lôøi sai Phöông phaùp: Giaûi thuaät: Moâ phoûng 3.4.
Thí duï 3.8. Giaû söû ta coù NFA ôû (H.3.13 ), x laø chuoãi nhaäp chöùa a. Duøng giaûi thuaät 3.4 xeùt xem NFA coù chaáp nhaän x ?. Keát quûa giaûi thuaät traû lôøi sai ( nghiaõ laø a khoâng thuoäc ngoân ngöõ do NFA nhaän daïng Thôøi gian vaø khoâng gian caàn thieát cho vieäc nhaän daïng moät chuoãi nhaäp: - Ñoái vôùi DFA: khoâng gian O (2 ( )) vaø thôøi gian O (|x | ). - Ñoái vôùi NFA: khoâng gian O (|r | ) vaø thôøi gian O (| r | * | x | ). 3.10. Xaây döïng DFA tröïc tieáp töø bieåu thöùc chính quy vaø vaán ñeà toái öu hoùa vieäc so truøng maãu 1. Traïng thaùi quan troïng cuûa NFA Traïng thaùi quan troïng laø töø noù coù söï truyeàn khaùc roãng. Nhö vaäy neáu hai taäp traïng thaùi coù cuøng soá traïng thaùi quan troïng thì chuùng ñöôïc ñoàng nhaát. NFA ñöôïc xaây döïng theo caáu truùc Thompson’ coù traïng thaùi keát thuùc khoâng coù söï truyeàn ra, nhö vaäy noù khoâng phaûi laø traïng thaùi quan troïng ( nhöng thöïc söï noù laïi raát quan troïng ). Ñeå traùnh tình traïng naøy ngöôøi ta theâm kyù hieäu # vaøo sau bieåu thöùc chính quy, vaø traïng thaùi keát thuùc coù söï truyeàn treân kyù hieäu #. Khi xaây döïng taäp con hoaøn taát thì traïng thaùi naøo coù söï truyeàn treân # laø traïng thaùi chaáp nhaän.
- Bieåu thöùc r# ñöôïc goïi laø bieåu thöùc chính quy gia toá. Vaên phaïm cuûa bieåu thöùc chính quy: exp → exp | term exp → term term → term • factor term → factor factor → factor* factor → ( exp ) factor → a factor → b • • • • # b 6 * b 5 a 4 3 a b 1 2 Hình 3.16. Caây phaân raõ cuûa bieåu thöùc gia toá (a| b )* abb#
∈ a 1 C ∈ ∈ ∈ start ∈ a a b b # A B F 3 4 4 6 F ∈ b 2 D ∈ ∈ Hình 3.17. NFA ñöôïc xaây döïng töø ( a| b )* abb# Löu yù: - Caùc traïng thaùi ñöôïc kyù hieäu baèng soá laø traïng thaùi quan troïng; Caùc traïng thaùi ñöôïc kyù hieäu baèng chöõ laø traïng thaùi khoâng quan troïng. - ÔÛ thí duï 3.6 traïng thaùi A vaø C coù cuøng soá traïng thaùi quan troïng laø 2,4,7 , trong (H 3.17) laø 1,2,3: A = {0,1,2,4,7} C = {1,2,4,5,7}
Baûng 3.6. Caùc quy taéc ñeå tính ba haøm nullable, firstpos, lastpos Nuùt n nullable (n) firstpos (n) lastpos (n) n laø nuùt coù teân true laø ∈ n laø nuùt coù teân false {i}{i} laø vò trí i | n nullable(c1) or firstpos(c1) ∪ lastpos(c1) ∪ nullable(c2) firstpos(c2) lastpos(c2) c1 c2 if nullable(c ) if nullable(c ) ° n 1 2 nullable(c1) and then firstpos(c1) ∪ then lastpos(c1) nullable(c2) firstpos(c2) ∪ lastpos(c2) c1 c2 else firstpos(c1) else lastpos(c2) ∗ n true firstpos(c1) lastpos(c1) c1
Caùc quy taéc tính haøm followpos (n): 1. Neáu nuùt n laø nuùt cat vôùi con beân traùi laø c1, con beân phaûi laø c2 vaø i laø vò trí trong lastpos(c1), thìtaátcaûvòtrítrongfirst(c2) seõ cho vaøo followpos(i). 2. Neáu n laø nuùt star vaø i laø vò trí trong lastpos(n) thì taát caû caùc vò trí trong firstpos(n) seõ cho vaøo followpos(i). Thí duï 3.10. Ta xaùc ñònh DFA cho bieåäu thöùc (a | b)* abb {1,2,3} {1,2,3} {6} {1,2,3} {5} { } { } {1,2,3} 4 6 # {6} { } 3 {5}a{5} { } ∗ 1,2 {1,2} {4}a{4} {3}a{3} {1,2} {1,2} {1}a {1} {2}a {2} Hình 3.19. Tính caùc haøm nullable, firstpos, lastpos cho caùc nuùt treân caây phaân tích cuûa bieåu thöùc ( a| b )* abb
Sau ñoù ta tính haøm followpos. Baûng 3.7. caùc trò followpos cuûa caùc nuùt treân caây ôû (H.3.19) Nuùt followpos 1 {1,2,3} 2 {1,2,3} 3 {4} 4 {5} 5 {6} 6 _ Giaûi thuaät 3.5. Xaây döïng DFA töø bieåu thöùc chính quy Nhaäp: Bieåu thöùc chính quy r. Xuaát: DFA goïi laø D, nhaän daïng ngoân ngöõ L( r) Phöông phaùp :1. Xaây döïng caây phaân tích cho BTCQ gia toá r#. 2. Tính caùc haøm nullable, firstpos, lastpos vaø followpos cho caùc nuùt treân caây phaân tích 3. Xaây döïng caùc traïng thaùi, haøm truyeàn vaø baûng truyeàn cho D baèng thuû tuïc ôû (moâ phoûng 3.5).
Thuû tuïc taïo taäp con laø caùc traïng thaùi cuûa DFA: Luùc ñaàu D chæ coù moät traïng thaùi baét ñaàu laø firstpos(root) , chöa ñöôïc ñaùnh daáu. Moâ phoûng 3.5. Thuû tuïc taïo taäp con while coù traïng thaùi T chöa ñöôïc ñaùnh daáu, trong taäp traïng thaùi cuûa D do begin ñaùnh daáu T; for vôùi moãi kyù hieäu nhaäp a do; begin vôùi U laø taäp caùc vò trí trong followpos (p), p laø vò trí trong T, sao cho kyù hieäu taïi vò trí p laø a; if U khoâng roãng vaø chöa coù trong taäp traïng thaùi cuûa D then begin theâm U vaøo taäp traïng thaùi cuûa D vaø laø traïng thaùi chöa ñöôïc ñaùnh daáu; D[T, a] := U; end; end; end; Löu yù: traïng thaùi keát thuùc cuûa D coù chöùa vò trí cuûa y.
Thí duï 3.10. Xaây döïng DFA töø btcq ( a| b )* abb. (trang 103 -104) 3. Toái thieåu soá traïng thaùi cuûa DFA - Khaùi nieäm DFA ñaày ñuû, traïng taùi cheát d. - Chuoãi w phaân bieät traïng thaùi s vôùi traïng thaùi t. Thí duï: DFA ôû (H.3.14, tr. 90), neáu xuaát phaùt töø C ñeå nhaän daïng w=bb thì khoâng ñi ñöôïc ñeán traïng thaùi chaáp nhaän, ngöôïc laïi töø B thì ñi ñeán E laø traïng thaùi chaáp nhaän. Giaûi thuaät 3.6. Toái thieåu soá traïng thaùi cuûa DFA. Nhaäp: DFA, goïi laø M coù S, Σ, s0, F. M laø DFA ñaày ñuû. Xuaát: DFA, goïi laø M’ chaáp nhaän ngoân ngöõ nhö M, vôùi soá traïng thaùi nhoû nhaát. Phöông phaùp: 1.Taïo Π khôûi ñaàu coù 2 nhoùm: caùc traïng thaùi keát thuùc F, vaø caùc traïng thaùi khoâng keát thuùc S – F. 2. AÙp duïng thuû tuïc (moâ phoûng 3.6) ñeå taïo Πnew . 3. Neáu Πnew = Π thì Πfinal = Π, tieáp tuïc böôùc 4, ngöôïc laïi laëp laïi böôùc 2, vôùi Π = Πnew
4. Chuùng ta choïn moãi nhoùm 1 traïng thaùi ñaïi dieän vaø ñoù laø traïng thaùi cuûa M’ . 5. Neáu M’ coù traïng thaùi cheát d thì loaïi noù ra khoûi M’. Taát caû caùc söï truyeàn ñeán traïng thaùi d ñeàu khoâng xaùc ñònh. Moâ phoûng 3.6. Giaûi thuaät taïo Πnew for vôùi moãi nhoùm G cuûa Π do begin - chia G thaønh caùc nhoùm nhoû hôn sao cho hai traïng thaùi s vaø t cuûa G seõ ôû cuøng moät nhoùm nhoû hôn neáu vaø chæ neáu caùc söï truyeàn treân taát caû caùc kyù hieäu nhaäp a töø s vaø t ñeàu ñi ñeán caùc traïng thaùi keá tieáp ôû trong cuøng moät nhoùm cuûa Π; - ta thay G baèng caùc nhoùm nhoû hôn vöøa ñöôïc taïo neân, cho chuùng vaøo Πnew ; end; Thí duï 3.11. Cho DFA nhö ôû (H. 3.14, tr. 90). Caùch giaûi ôû tr. 106 – 107.
4. Caùc phöông phaùp neùn baûng truyeàn FA 1. Thu giaûm haøng vaø coät dö thöøa 0 – 0 1 0000 222222222 0 – 0 3 0 – 0 y next yrmap 00 -131-10 11 -12151 2 2 -1 -1 2 5 2 3 3 -1 -1 2 -1 3 4 4 -1 -1 -2 -1 4 5 4 -1 -1 4 -1 4 0123 Hình 3.21. Baûng truyeàn ñöôïc neùn baèng phöông phaùp thu giaûm haøng vaø coät dö thöøa
2. Neùn caëp ynext 0 • 7 ‘0’,3 ‘0’,1 ‘1’,1 ‘2’,1 ‘3’,1 ‘4’,2 ‘5’,2 ynext 0 1 • 0 -1-1 12-1 1111111111-1 -1 5-1 ynext 1 2 • 6 ‘0’,2 ‘1’,2 ‘2’,3 ‘3’,4 ‘4’,1 ‘5’,1 ynext 2 3 • 7 ‘0’,1 ‘1’,1 ‘2’,2 ‘3’,2 ‘4’,2 ‘5’,2 ‘6’,2 ynext 3 4 • 7 ‘0’,4 ‘1’,4 ‘2’,4 ‘3’,2 ‘4’,2 ‘5’,2 ‘6’,2 ynext 4 5 • 6 ‘0’,2 ‘1’,2 ‘2’,2 ‘3’,2 ‘4’,1 ‘5’,1 ynext 5 Hình 3.22. Baûng truyeàn neùn theo phöông phaùp neùn caëp
Moâ phoûng 3.7. Giaûi thuaät tìm traïng thaùi keá tieáp treân baûng truyeàn ñaõ ñöôïc neùn row := ynext [t]; I := row^[0], /* row^ laø ma traän 1 chieàu ynext t */ if I = 0 then begin c := ord (a) s := row^[c]; /* s laø traïng thaùi keá tieáp */ end else begin while (a row^ [i]. chart) and (i < I) do i := i + 1; if a = row^[i]. chart then s := row^[i]. State else writen (‘sai – loãi töø vöïng’); end;
3.11. Thieát keá boä sinh boä phaân tích töø vöïng Chöông trình moâ phoûng FA vaø Ñaëc taû lex Trình bieân dòch baûng truyeàn Lex a) Boä ñeäm nhaäp Chöông trình moâ phoûng FA Baûng truyeàn b) Hình3.23. TrìnhbieândòchLexvaøBoäphaântíchtöøvöïng
1. Maãu so truøng treân cô sôû NFA N(p1) ∈ ∈ so N(pi) ∈ N(pn) Hình 3.24. NFA ñöôïc tao ra töø söï ñaëc taû LEX
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: chovaênphaïmG. 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 Ad c Ad ab a a) b) 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 Æ X1X2 Xn , 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, X3 Xn.
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’ + TE’ 4 5 E: 0 1 2 3 6 ∈ FT’ E’: T: 7 8 9 ∗ T’ ( ∈ ) T’: 10 11 F’ 12 1 14 15 16 1 3 7 ∈ F: id Hình 4.5. Sô ñoà dòch cuûa caùc kyù hieäu khoâng keát thuùc cuûa G
+ ∗ T ∈∈F ( E ) E: 0 3 6 T: 7 10 13 F: 14 15 16 17 id 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;
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 Xuaát X Chöông trình ñieàu khieån Y Z $ Baûng phaân tích M 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 if M [X, a] = X Æ X1X2 Xk then begin - ñaåy X ra khoûi stack; -ñaåyXkXk-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 khoâng Kyù hieäu nhaäp keát thuùc id + * ( ) $ E E Æ TE’ E Æ TE’ E’ E Æ E’ Æ ∈ E’ Æ ∈ +TE’ 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 $Eid+ id ∗ id $ $E’T’Fid∗ id $ T Æ FT’ $E’Tid+ id ∗ id $ E Æ TE’ $E’T’id id ∗ id $ F Æ id $E’T’Fid+ 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’Fid$ $E’ + id ∗ id $ T’ Æ ∈ $E’T’id id $F Æ id $E’T++id ∗ id $ E’ Æ +TE’ $E’T’ $ $E’Tid∗ 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. Caùc Kyù hieäu nhaäp kyù hieäu khoâng ab e i t$ KT S S Æ aS Æ iEtSS’ S’ S’ Æ ∈ S’ Æ ∈ S’ Æ eS 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 Kyù hieäu nhaäp 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. 1 2r -1n S = γ0 ⇒γ1 ⇒γ2 ⇒ ⇒γn-1 ⇒γn = w rm rm rm rm rm 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.
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 Xuaát 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
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* SSR SR R R RR R R id RR R SR * SS + SS ( SS ) RR R R = SS $ 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 Xnlaøluaätsinhnaøocoùveáphaûidaø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 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öôønghôïp1: Y laø kyù hieäu keát thuùc Tröôønghôïp2: 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 $ boä ñeäm nhaäp Stack Sm Xm Chöông trình xuaát Sm–1 ñieàu khieån Xm–1 $ action goto baûng phaân tích 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 Traïng thaùi id + * ( ) $ E T F 0 s5 s4 12 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 82 3 5 r6 r6 r6 r6 6 s5 s4 93 7 s5 s4 10 8 s6 s11 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5
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ùptínhclosure 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 Traïng thaùi cd$SC 0 s3 s4 12 1 acc 2 s6 s7 5 3 s3 s4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2
Boä sinh phaân tích cuù phaùp Boä sinh phaân tích cuù phaùp Yacc y.tab.c Taäp tin ñaëc taû Trình bieân dòch Yacc translate.y Yacc y.tab.c Trình bieân dòch C a.out chuoãi token a.out daãn xuaát 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ôï
CHÖÔNG 5 BIEÂN DÒCH TRÖÏC TIEÁP CUÙ PHAÙP Coù hai khaùi nieäm veà caùc luaät ngöõ nghóa coù lieân quan ñeán luaät sinh: ñònh nghóa tröïc tieáp cuù phaùp vaø löôïc ñoà dòch. - Ñònh nghóa tröïc tieáp cuù phaùp. - Löôïc ñoà dòch. Chuoãi nhaäp → caây phaân tích → ñoà thò phuï thuoäc → → ñaùnh giaù thöù töï caùc luaät ngöõ nghóa. Hình 5.0. Khaùi nieäm veà dòch tröïc tieáp cuù phaùp
Khaùi nieäm toång quan cuûa bieân dòch tröïc tieáp cuù phaùp 5.1. Ñònh nghóa tröïc tieáp cuù phaùp Laø vaên phaïm phi ngöõ caûnh maø trong ñoù moãi kyù hieäu vaên phaïm coù taäp thuoäc tính. Taäp thuoäc tính naøy coù hai loaïi: thuoäc tính toång hôïp vaø thuoäc tính keá thöøa. Caây cuù phaùp coù giaù trò thuoäc tính ôû moãi nuùt ñöôïc goïi laø caây phaân tích chuù thích. Daïng cuûa ñònh nghóa tröïc tieáp cuù phaùp Moãi luaät sinh coù daïng A →αñeàu coù moät taäp luaät ngöõ nghóa coù daïng b:= f (c1, c2, , ck) vôùi f laø haøm soá vaø: 1. b laø thuoäc tính toång hôïp cuûa A vaø c1, c2, , ck laø caùc thuoäc tính cuûa kyù hieäu vaên phaïm cuûa luaät sinh, hoaëc 2. b laø thuoäc tính keá thöøa cuûa moät trong caùc kyù hieäu vaên phaïm beân veá phaûi cuûa luaät sinh vaø c1, c2, , ck laø caùc thuoäc tính cuûa caùc kyù hieäu vaên phaïm cuûa luaät sinh.
Thí duï 5.1. Ñònh nghóa tröïc tieáp cuù phaùp ôû baûng 5.1. Baûng 5.1. Ñònh nghóa tröïc tieáp cuù phaùp cho baûng tính ñôn giaûn Luaät sinh Luaät ngöõ nghóa L → En Print (E.val) E → E1 + T E.val: = E1.val + T.val E → TE.val: = T.val E.val: = T.val T → T1* F T.val: = T.val x F.val T → FT.val: = F.val T.val: = F.val F → (E) F.val: = E.val F → digit F.val: = digit . lexval Thuoäc tính toång hôïp Ñònh nghóa tröïc tieáp cuù phaùp duøng caùc thuoäc tính toång hôïp goïi laø ñònh nghóa thuoäc tính S. Thuoäc tính S cuûa moät nuùt coù theå ñöôïc töø caùc thuoäc tính ôû moãi nuùt töø döôùi leân.
Thí duï 5.2. Ñònh nghóa thuoäc tính S ôû thí duï 5.1 L n E.val = 19 E.val = 15 + T.val = 4 T.val = 15 F.val = 4 T.val = 3 * F.val = 5 digit.lexval = 4 F.val = 3 digit.lexval = 5 digit.lexval = 3 Hình 5.1. Caây phaân tích chuù thích 3 * 5 + 4n
Thuoäc tính keá thöøa Thuoäc tính keá thöøa laø thuoäc tính maø giaù trò cuûa noù ôû moät nuùt treân caây phaân tích ñöôïc xaùc ñònh bôûi thuoäc tính cha meï vaø/hoaëc anh chò cuûa nuùt ñoù. Thí duï 5.3. Söï khai baùo ñöôïc taïo bôûi kyù hieäu khoâng keát thuùc D trong ñònh nghóa tröïc tieáp cuù phaùp ôû (baûng 5.2). Baûng 5.2. Ñònh nghóa tröïc tieáp cuù phaùp vôùi thuoäc tính keá thöøa L.in. Luaät sinh Luaät ngöõ nghóa D → TL L.in: = T.type T → int T.type: = integer T → real T.type: = real L → L1, id L1.in: = L.in L → id Addtype (id.entry, L.in)
Hình 5.2 laø caây phaân tích chuù thích cho caâu real id1, id2, id3. D L.in = real T.type = real L.in = real , id3 real L.in = real , id2 id1 Hình 5.2. Caây phaân tích vôùi thuoäc tính keá thöøa in ôû moãi nuùt coù nhaõn L.
Ñoà thò phuï thuoäc Caùc söï phuï thuoäc trung gian: thuoäc tính keá thöøa vaø toång hôïp treân caùc nuùt cuûa caây phaân tích coù theå ñöôïc mieâu taû baèng ñoà thò coù höôùng ñöôïc goïi laø ñoà thò phuï thuoäc (dependency graph). Caây phuï thuoäc cuûa moät caây phaân tích cho tröôùc, ñöôïc xaây döïng nhö sau: for vôùi moãi nuùt n treân caây phaân tích do for vôùi moãi thuoäc tính a cuûa kyù hieäu vaên phaïm taïi nuùt n do - xaây döïng nuùt treân ñoà thò phuï thuoäc cho a; for vôùi moãi nuùt n treân caây phaân tích do for vôùi moãi luaät ngöõ nghóa b:= f (c1, c2, , ck) töông öùng vôùi luaät sinh ñöôïc duøng taïi nuùt n for i := 1 to k do xaây döïng caïnh ñi töø nuùt cuûa c1 ñeán nuùt b.
Thí duï 5.4. Khi ta duøng luaät sinh E → E1 + E2 treân caây phaân tích, chuùng ta theâm caùc caïnh sau vaøo (H.5.3) chuùng ta seõ ñöôïc ñoà thò phuï thuoäc. Luaät sinh Luaät ngöõ nghóa E → E1 + E2 E.val := E1.val + E2.val E val E 1 E 2 val val + Hình 5.3. Ñoà thò phuï thuoäc cuûa caây phaân tích cho E Æ E1+ E2
Thí duï 5.5. (H.5.4) laø ñoà thò phuï thuoäc cho caây phaân tích cuûa (H.5.2). Ñaùnh giaù thöù töï Trong saép xeáp logic topo, caùc thuoäc tính phuï thuoäc c1, c2, , ck trong luaät ngöõ nghóa b:= f (c1, c2, , ck) ñöôïc ñaùnh giaù tröôùc f. D 5 L 6 4 in T type 3 entry 7 L8 id3 real 2 entry 9 in L 10 id2 1 id1 entry Hình 5.4. Ñoà thò phuï thuoäc cho caây phaân tích ôû (H.5.2).
Thí duï 5.6. Moãi moät caïnh cuûa ñoà thò phuï thuoäc ôû (H.5.4.) ñi töø soá thaáp ñeán soá cao cuûa caùc nuùt. Töø thöù töï logic topo chuùng ta seõ coù chöông trình. Chuùng ta vieát an cho thuoäc tính lieân quan ñeán nuùt ñöôïc ñaùnh soá n. treân ñoà thò phuï thuoäc. a4 := real a5 := a4 addtype (id3.entry, a5); a7 := a5 addtype (id2.entry, a7); a9 := a7 addtype (id1.entry, a9); Moät soá phöông phaùp ñöôïc ñeà nghò cho vieäc ñaùnh giaù caùc luaät ngöõ nghóa 1. Phöông phaùp caây phaân tích (parse-tree method) 2. Phöông phaùp cô sôû luaät (rule-based method) 3. Phöông phaùp roõ raøng
5.2. Caáu truùc cuûa caây phaân tích Caây cuù phaùp: laø daïng thu goïn cuûa caây phaân tích, ñöôïc duøng ñeå bieåu dieãn cho caáu truùc ngoân ngöõ. Caây phaân tích ôû (H.5.1) seõ ñöôïc veõ laïi thaønh caây cuù phaùp. + ∗ 4 3 5 Xaây döïng caây cuù phaùp cho bieåu thöùc Chuùng ta seõ duøng caùc haøm ñeå taïo caùc nuùt cho caây cuù phaùp cuûa bieåu thöùc vôùi pheùp toaùn hai ngoâi. Moãi haøm traû veà con troû chæ ñeán nuùt môùi ñöôïc taïo ra. 1. mknode(op, left, right). 2. mkleaf(id, entry). 3. mkleaf(num, val).
Thí duï 5.7. Moät chuoãi caùc haøm ñöôïc goïi ñeå taïo caây cuù phaùp cho bieåu thöùc a – 4 + c ôû (H.5.5). (1) p1 := mkleaf(id, entry a); (4) p4 := mkleaf(id, entry c); (2) p2 := mkleaf(num, 4); (5) p5 := mknode(‘+’, p3, p4)’ (3) p3 := mknode(‘-‘, p1, p2) + − id chæ ñeán vò trí cuûa c id Num 4 chæ ñeán vò trí cuûa a Hình 5.5. Caây cuù phaùp cho bieåu thöùc a – 4 + c
Ñònh nghóa tröïc tieáp cuù phaùp vaø caáu truùc caây cuù phaùp Thí duï ôû baûng 5.3 laø ñònh nghóa thuoäc tính S duøng ñeå xaây döïng caây cuù phaùp cho bieåu thöùc soá hoïc coäng (+) vaø tröø (-). Baûng 5.3. Ñònh nghóa tröïc tieáp cuù phaùp cho caáu truùc caây cuù phaùp cuûa bieåu thöùc Luaät sinh Caùc luaät ngöõ nghóa E → E1 + T E. nptr: = mknode(‘+’, E1 .nptr, T. nptr) E → E1 – T E. nptr: = mknode(‘-‘, E1 .nptr, T.nptr) E → T E. nptr: = T. nptr T → (E) T. nptr: = E. nptr T → id T. nptr: = mkleaf(id, id, entry) T → num T. nptr: = mkleaf(num, num, val)
Thí duï 5.8. Caây phaân tích chuù thích duøng ñeå mieâu taû caây cuù phaùp cho bieåu thöùc a - 4 + c ñöôïc trình baøy ôû (H.5.6). E E nptr nptr E T nntr T+ − nptr nptr T num + id − − id id con troû chæ ñeán c num 4 trong baûng danh bieåu con troû chæ ñeán a trong baûng danh Hình 5.6. Toå chöùc cuûa caây cuù phaùp cho bieåu thöùc bieåu a – 4 + c
Ñoà thò coù höôùng khoâng laëp voøng mieâu taû bieåu thöùc Ñoà thò coù höôùng khoâng laëp voøng (directed acyclic graph) goïi taét laø dag. + + ∗ ∗ a − d b c Hình 5.7. Dag cho bieåu thöùc a + a * (b – c) + (b – c) * d.
Baûng 5.4. Caùc leänh ñeå taïo DAG ôû (H.5.7) Haøng Leänh Haøng Leänh 1 p1 := mkleaf(id, a) 8 p8 := mkleaf(id, b) 2 p2 := mkleaf(id, a) 9 p9 := mkleaf(id, c) 3 p3 := mkleaf(id, b) 10 p10 := mknode(’ −‘, p8, p5) 4p4 := mkleaf(id, c) 11 p11 := mkleaf(id, d) 5p5 := mknode(‘−‘, p3, p4)12p12 := mknode(‘*’, p10, p11) 6p6 := mknode(‘*’, p2, p5)13p13 := mknode(‘+’, p7, p12) 7p7 := mknode(‘+’, p1, p6)
Maãu tin töôïng tröng cho nuùt ñöôïc löu chöùa trong daõy nhö ôû (H.5.8). Pheùp gaùn Dag i := i + 10 Bieåu dieãn caáu truùc döõ lieäu := 1idChæ ñeán danh bieåu i 2num 10 + 3+ 1 2 4:= 1 3 i 10 5 Giaûi thuaät 5.1. Phöông phaùp soá trò cho vieäc taïo nuùt cuûa dag. Giaû söû moãi nuùt laø moät phaàn töû cuûa daõy ôû (H.5.8). Nhaäp: nhaõn op, nuùt 1 vaø nuùt r. Xuaát: nuùt vôùi kyù hieäu Phöông phaùp
5.3. Ñaùnh giaù töø döôùi leân cho ñònh nghóa thuoäc tính S Thuoäc tính toång hôïp treân stack cuûa boä phaân tích. Boä bieân dòch cho ñònh nghóa thuoäc tính S coù theå ñöôïc thöïc hieän döïa theo boä sinh boä phaân tích cuù phaùp LR. Baûng 5.5. Stack cuûa boä phaân tích coù vuøng löu chöùa caùc thuoäc tính toång hôïp state val . . . XX.x YY.y top ZZ.z .
Baûng 5.6. Hieän thöïc baûng tính baèng boä phaân tích cuù phaùp LR Luaät sinh Ñoaïn maõ L → En Print (val [top]) E → E1 + T val [ntop]: = val [top - 2] + val [top] E → T T → T1 * F val [ntop]: = val [top - 2] x val [top] T → F F → (E) val [ntop]: = val [top - 1] F → digit
Baûng 5.7. Quaù trình bieân dòch cho chuoãi nhaäp 3 * 5 + 4n. Chuoãi nhaäp Traïng thaùi Trò val Luaät aùp duïng 3 * 5 + 4n −− * 5 + 4n 3 3 * 5 + 4n F 3 F Æ digit * 5 + 4n T 3 T Æ F 5 + 4n T * 3 − + 4n T * 5 3 − 5 + 4n T * F 3 – 5 F Æ digit + 4n T 15 T Æ T * F + 4n E 15 E Æ T 4n E + 15 − n E + 4 15 – 4 n E + F 15 – 4 F Æ digit n E + T 15 – 4 T Æ F nE19E Æ E + T En 19 L19L Æ En
5.4. Ñònh nghóa thuoäc tính L Moâ phoûng 5.1. Thöù töï ñaùnh giaù depth – first cho caùc thuoäc tính treân caây phaân tích procedure dfvisit (n: node); begin for vôùi moãi nuùt m laø con cuûa nuùt n, töø traùi sang phaûi do begin ñaùnh giaù thuoäc tính keá thöøa cuûa m dfvisit (m) end ñaùnh giaù thuoäc tính toång hôïp cuûa n end; Chuùng ta trình baøy lôùp cuûa ñònh nghóa tröïc tieáp cuù phaùp, ñöôïc goïi laø ñònh nghóa thuoäc tính L nhö sau: thuoäc tính L luoân ñöôïc ñaùnh giaù theo thöù töï depth – first. Ñònh nghóa thuoäc tính L bao goàm taát caû caùc ñònh nghóa tröïc tieáp cuù phaùp, ñöôïc döïa treân cô sôû vaên phaïm LL (1).
Ñònh nghóa thuoäc tính L Ñònh nghóa tröïc tieáp cuù phaùp, ñöôïc goïi laø ñònh nghóa thuoäc tính L, neáu moãi thuoäc tính keá thöøa cuûa xj vôùi 1 < j ≤ n maø xj naèm ôû veá phaûi luaät sinh A → x1x2 xn, chæ phuï thuoäc vaøo: 1. Caùc thuoäc tính cuûa caùc kyù hieäu x1, x2, , xj-1 ôû phía traùi cuûa xj trong luaät sinh. 2. Thuoäc tính keá thöøa cuûa kyù hieäu A. Baûng 5.8. Ñònh nghóa tröïc tieáp cuù phaùp khoâng phaûi thuoäc tính L. Luaät sinh Luaät ngöõ nghóa A → LM L.i : = l (A.i) M.i := m (L.s) A.s : = f (M.s) A → QR R.i : = r (A.i) Q.i : = q (R.s) A.s : = f (Q.s)
Löôïc ñoà dòch Moâ phoûng 5.2. Löôïc ñoà dòch ñôn giaûn cho bieåu thöùc soá hoïc E → TR R → addop T {print (addop. Lexeme)} R⏐∈ T → num {print (num. val)} Tröôøng hôïp ñôn giaûn nhaát neáu haønh vi chæ caàn thuoäc tính toång hôïp. Nhö vaäy chuùng ta seõ xaây döïng löôïc ñoà dòch baèng caùch taïo ra haønh vi laø pheùp gaùn cho moãi luaät ngöõ nghóa vaø gaén haønh vi naøy vaøo taän cuøng cuûa veá phaûi luaät sinh. Thí duï: ta coù luaät sinh vaø luaät ngöõ nghóa sau: Luaät sinh Luaät ngöõ nghóa T Æ T1 * F T.val:= T1.val x F.val ta ñöa luaät ngöõ nghóa ‘nhuùng’ vaøo luaät sinh vaø ñöôïc: T Æ T1 * F {T.val:= T1.val x F.val} Neáu caùc haønh vi caàn caû thuoäc tính toång hôïp vaø keá thöøa thì chuùng ta phaûi löu yù:
1. Thuoäc tính keá thöøa cuûa moät kyùhieäu naèm ôû veá phaûi luaät sinh phaûi ñöôïc tính tröôùc trong haønh vi ñöùng tröôùc kyùhieäu ñoù. 2. Haønh vi khoâng ñöôïc tham khaûo ñeán thuoäc tính toång hôïp cuûa kyù hieäu naèm ôû beân phaûi haønh vi ñoù. 3. Thuoäc tính toång hôïp cuûa kyù hieäu khoâng keát thuùc ôû veá traùi luaät sinh chæ coù theå ñöôïc tính sau taát caû caùc thuoäc tính maø noù tham khaûo tôùi. 5.5. Bieân dòch töø treân xuoáng Loaïi boû ñeä quy traùi cho löôïc ñoà dòch Moâ phoûng 5.3. Löôïc ñoà dòch vôùi vaên phaïm coù ñeä quy traùi. E → E1 + T {E.val := E1.val + T. val⏐} E → E1 – T {E.val := E1.val - T. val⏐} E → T {E.val := T. val⏐} T → E {T.val := E. val⏐} T → num {T.val := num. val⏐}
E R.i = 9 T.val = 9 − T.val = 5 R.i = 4 num. val = 9 num. val = + T.val = 5 5 num. val = 2 ∈ Hình 5.10. Ñaùnh giaù bieåu thöùc 9 – 5 + 2.
Moâ phoûng 5.4. Löôïc ñoà dòch chuyeån ñoåi vôùi vaên phaïm ñeä quy traùi. E → T {R.i := T.val⏐} R {E.val := R.s} R → + T {R1.i := R.i + T.val⏐} R1 {R.s := R1.s} R → - T {R1.i := R.i - T.val⏐} R1 {R.s := R1.s} R →∈ {R.s := R.i} T → ( E {T.val := E.val⏐} ) T → num {T.val := num.val⏐}
Giaû söû chuùng ta coù löôïc ñoà dòch sau (vôùi thuoäc tính toång hôïp): A → A1Y {A.a := g (A1.a, Y.y} A → X {A.a := f (X.x)} (5.1) Sau khi loaïi boû ñeä quy traùi chuùng ta coù vaên phaïm töông ñöông; A → X {R.i := f (X.x)} R {A.a := R.s} R → Y {R1.i := g (R.i, Y.y)} (5.3) R1 {R.i := R1.s} R →∈ {R.s := R.i} Thí duï 5.13. Ñònh nghóa tröïc tieáp cuù phaùp ôû baûng 5.3. duøng ñeå xaây döïng caây cuù phaùp ñöôïc chuyeån thaønh löôïc ñoà dòch. E → E1 + T {E.nptr := mknode (‘+’, E1.nptr, T.nptr)} E → E1 – T {E.nptr := mknode (‘-’, E1.nptr, T.nptr)} (5.9) E → T {E.nptr := T.nptr}
A.a = g(g(f(X.x), Y1, y), Y2, y) A X R.i = f(X.x) Y2 A.a = g(f(X.x), Y1, y) Y1 Y A.a = f(X.x) 1 Y2 R.I = g(g(f(X.x), Y1, y), Y2,y) X ∈ Hình 5.11. Hai caùch tính giaù trò thuoäc tính.
Moâ phoûng 5.5. Löôïc ñoà dòch chuyeån ñoåi cho caáu truùc caây cuù phaùp. E → T {Rj := T.nptr} R {E.nptr := R.s} R → + T {R1j := mknode (‘+’, Rj.T.nptr)} R1 {R.s := R1.s} R →− T {R1j := mknode (‘-’, Rj.T.nptr)} R1 {R.s := R1.s} R →∈ {R.s := Rj} T → ( E ) {T.nptr := E.nptr} T → id {T.nptr := mkleaf (id.id.entry)} T → num {T.nptr := mkleaf (num.num.val)}
Hình 5.12. bieåu dieãn toaøn boä caùc haønh vi trong moâ phoûng 5.5. cho caáu truùc caây cuù phaùp cuûa caâu a – 4 + c. Thieát keá boä dòch ñoaùn nhaän tröôùc E R R T•nptr i i R s − T•nptr = •nptr + ∈ id num id + − id c id num 4 a Hình 5.12. Duøng caùc thuoäc tính keá thöøa ñeå xaây döïng caây cuù phaùp.
Giaûi thuaät 5.2: xaây döïng trình bieân dòch tröïc tieáp cuù phaùp ñoaùn nhaän tröôùc. Nhaäp: cho löôïc ñoà dòch tröïc tieáp cuù phaùp vôùi vaên phaïm cô sôû phuø hôïp cho phaân tích ñoaùn nhaän tröôùc. Xuaát: maõ cho trình bieân dòch tröïc tieáp cuù phaùp. Phöông phaùp: 1. Vôùi moãi kyù hieäu khoâng keát thuùc A, xaây döïng haøm, thoâng soá laø thuoäc tính keá thöøa cuûa A, traû veà giaù trò cuûa caùc thuoäc tính toång hôïp cuûa A. 2. Maõ cho kyù hieäu khoâng keát thuùc A seõ quyeát ñònh luaät sinh naøo seõ ñöôïc duøng treân cô sôû kyù hieäu nhaäp ñang ñöôïc ñoïc. 3. Maõ cho moãi luaät sinh seõ ñöôïc taïo ra: i) Vôùi moãi token X vôùi thuoäc tính toång hôïp x, caát giaù trò x vaøo bieán X.x. Taïo ra leänh goïi chöông trình con ñeå so truøng token X vôùi kyù hieäu nhaäp ñöôïc ñoïc. ii) Vôùi B, taïo ra phaùt bieåu gaùn C1 = B (b1, b2, , bk), b1, b2, , bk laø caùc bieán chöùa caùc thuoäc tính keá thöøa cuûa B vaø C laø bieán chöùa thuoäc tính toång hôïp cuûa B.
iii) Vôùi moãi haønh vi, haõy cheùp maõ vaøo cho boä phaän tích, thay moãi tham chieáu ñeán caùc thuoäc tính baèng bieán chöùa caùc thuoäc tính ñoù. Thí duï 5.14. Vaên phaïm ôû moâ phoûng 5.5 laø LL (1), noù phuø hôïp cho vieäc phaân tích töø treân xuoáng. function E: ↑ nuùt caây cuù phaùp function R: (i: ↑ nuùt caây cuù phaùp): ↑ nuùt caây cuù phaùp; function T: ↑ nuùt caây cuù phaùp; Keát hôïp hai luaät sinh R ôû moâ phoûng 5.5. R → addop T {R1.i :=mknode (addop.lexeme, R.i, T.nptr)} R1 {R.s := R1.s} R →∈{R.s := R.i}
Moâ phoûng 5.6. Thuû tuïc phaân tích cuù phaùp cho caùc luaät sinh R: R → addop TR |∈ Procedur R: begin if lookahead = addop then begin match (addop): T; R; end else begin /*khoâng laøm gì caû*/ end Moâ phoûng 5.7. Caây cuù phaùp ñeä quy ñi xuoáng function R (i: ↑ nuùt caây cuù phaùp): ↑ nuùt caây cuù phaùp; var nptr. ll, sl, s: ↑ nuùt caây cuù phaùp; addoplexeme: char; begin if lookahead = addop then begin /* luaät sinh R → addop TR*/ addoplexeme := lexval; match (addop);
il := mknode (addoplexeme, i, nptr); sl := R (il); s := sl; end else s := i; /* luaät sinh R →∈*/ return s end; 5.6. Ñaùnh giaù thuoäc tính keá thöøa töø döôùi leân Loaïi boû haønh vi ñöôïc nhuùng trong löôïc ñoà dòch Ví duï: chuùng ta coù löôïc ñoà dòch E → TR R → + T {print (‘+’)} R ⏐ -T {print (‘−‘)} R⏐∈ T → num {print (num.val)}
Taïo ra löôïc ñoà dòch vôùi vieäc duøng caùc kyù hieäu ñaùnh daáu khoâng keát thuùc môùi N, M. E → TR R → + T MR ⏐-TNR ⏐∈ T → num {print (num.val)} M →∈{print (‘+’) } N →∈{print (‘−’) } Thuoäc tính keá thöøa treân stack cuûa boä phaân tích Thí duï 5.15. Quaù trình ñaùnh giaù thuoäc tính keá thöøa baèng boä phaân tích töø döôùi leân cho caâu nhaäp real p, q, r ôû (H.5.13). D → T {L.in := T.type} T → int {T.type := integer} T → real {T.type := real} L →{L1.in := L.in} L1, id {add type (id.entry, L.in)} L → id {add type (id.entry, L.in)}
D L T in in in L r • real L q , p Hình 5.13. Taïi moãi nuùt L coù L.in := T.type.
Baûng 5.9. Baát cöù luùc naøo veá phaûi cuûa L ñöôïc thu giaûm thì T luoân ôû treân veá phaûi ñoù. Nhaäp Traïng thaùi Luaät ñöôïc aùp duïng Real p, q, r - p, q, r real p, q, r T T → real , q, r Tp , q, r TL L → id , q, r TL, , r TL, q , r TL L → L, id r TL, TL, r TL L → L, id D D → TL
Baûng 5.10. Giaù trò cuûa T.type ñöôïc duøng ôû vò trí L.in. Luaät sinh Ñoaïn maõ D Æ TL T Æ int val [ntop] := integer T Æ real val [ntop] := real L Æ L, id addtype (val[top], val[top – 3]) L Æ id addtype (val[top], val[top – 1]) Ñaùnh giaù caùc thuoäc tính keá thöøa Thí duï 5.16. Ñaây laø ví duï veà tröôøng hôïp khoâng theå ñoaùn nhaän tröôùc vò trí cuûa thuoäc tính trong löôïc ñoà dòch. Luaät sinh Luaät ngöõ nghóa S Æ aAC C.i:= A.s (5.4) S Æ aABC C.i := A.s C Æ c C.i := g (C.i)
Luaät sinh Luaät ngöõ nghóa S Æ aAC C.i := A.s S Æ bABMC M.i := A.s ; C.i := M.s C Æ c C.i := g(C.i) M Æ ∈ M.S := M.i S S b b C C A B M i A s siB i a) b) ∈ Hình 5.14. Sao cheùp thuoäc tính thoâng qua kyù hieäu M. a) Luaät sinh chöa bieán ñoåi; b) Luaät sinh ñaõ ñöôïc bieán ñoåi.
Kyù hieäu khoâng keát thuùc N cuõng coù theå ñöôïcduøng ñeå moâ phoûng cho luaät ngöõ nghóa maø noù khoâng phaûi laø luaät sao cheùp. Ví duï ta coù luaät sinh vaø luaät ngöõ nghóa: Luaät sinh Luaät ngöõ nghóa S Æ aAC C.i := f(A.s) (5.5) Luaät sinh Luaät ngöõ nghóa S Æ aANC N.i := A.s ; C.i := N.s N Æ ∈ N.s := f(N.i) (5.6) Giaûi thuaät 5.3. Phaân tích töø döôùi leân vaø söï bieân dòch vôùi caùc thuoäc tính keá thöøa. Nhaäp: ñònh nghóa thuoäc tính L vôùi vaên phaïm cô sôû LL (1). Xuaát: boä phaân tích cuù phaùp tính caùc giaù trò cuûa taát caû caùc thuoäc tính treân stack cuûa boä phaân tích. Phöông phaùp: giaû söû moãi kyù hieäu khoâng keát thuùc A coù moät thuoäc tính keá thöøa A.i vaø moãi kyù hieäu vaên phaïm X coù moät thuoäc tính toång hôïp X.x.
Vôùi moãi luaät sinh A Æ X1 Xn, seõ coù n kyù hieäu khoâng keát thuùc ñaùnh daáu M1 Mn, seõ thay luaät treân thaønh luaät sinh A Æ M1X1 MnXn. Ñeå nhaän thaáy caùc thuoäc tính coù theå ñöôïc tính trong quaù trình phaân tích töø döôùi leân, haõy xeùt hai tröôøng hôïp. Tröôøng hôïp thöù nhaát neáu ta thu giaûm veà kyù hieäu Mj ta phaûi bieát luaät sinh A → Mj X1 MnXn maø Mj coù trong ñoù. Chuùng ta phaûi bieát caùc vò trí cuûa caùc thuoäc tính maø thuoäc tính keá thöøa Xj.i caàn ñeå tính giaù trò cho noù. A.i ôû val[top – 2j + 2], X1.i ôû val[top – 2j + 3], X1.s ôû taïi val[top – 2i + 4], X2.i ôû val[top – 2j + 5] Tröôøng hôïp thöù hai seõ xuaát hieän khi ta thu giaûm veà moät kyù hieäu khoâng keát thuùc cuûa vaên phaïm giaû söû baèng luaät sinh A → M1X1 MnXn, vaø giaû söû ta chæ tính A.s, coøn A.i ñaõ ñöôïc sinh vaø naèm treân stack ôû vò trí treân vò trí cuûa A. Caùc thuoäc tính caàn thieát ñeå tính A.s ñaõ saün saøng treân stack, ñaõ ñöôïc bieát, ñoù chính laø caùc vò trí cuûa caùc Xj trong quaù trình thu giaûm.
Thay theá thuoäc tính keá thöøa baèng thuoäc tính toång hôïp Chuùng ta coù theå traùnh duøng thuoäc tính keá thöøa baèng vieäc thay ñoåi vaên phaïm cô sôû. Trong ngoân ngöõ cuûa Pascal cho pheùp khai baùo moät chuoãi caùc bieán vaø sau ñoù laø kieåu döõ lieäu cuûa chuùng. Thí duï: m, n: integer. D → L : T T → integer ⏐ char L → L, id ⏐ id D → id L L → ,id Ll:T T → integer ⏐ char
CHÖÔNG 6 XÖÛ LYÙ NGÖÕ NGHÓA Xöû lyù ngöõ nghóa coù hai caùch: kieåm tra tónh (static check) vaø kieåm tra ñoäng (dynamic check). Trong chöông naøy chuùng ta chæ baøn ñeán kieåm tra ngöõ nghóa tónh. Xöû lyù ngöõ nghóa tónh bao goàm: 1. Truyeàn thuoäc tính 2. Kieåm tra kieåu 3. Kieåm tra trình töï ñieàu khieån 4. Kieåm tra tính duy nhaát 5. Kieåm tra moái lieân heä cuûa teân 6. Xöû lyù caùc phaùt bieåu goto tham khaûo tröôùc.
chuoãi caây caây maõ Boä phaân Boä xöû lyù Sinh maõ token tích cuù phaùp cuù phaùp ngöõ nghóa cuù phaùp trung trung gian gian Hình 6.1. Vò trí cuûa boä xöû lyù ngöõ nghóa. 6.1. Truyeàn thuoäc tính 1. Maõ trung gian Maõ trung gian coù nhieàu loaïi: maõ cambridge, maõ Balan ngöôïc, maõ boä tam (triple code), maõ boä töù (quadruple code). Boä töù cho bieåu thöùc soá hoïc Daïng toång quaùt: ( , , ) Moät caùch bieåu thò bieán taïm ôû baûng danh bieåu: Teân:roãng Loaïi: 4 Kieåu döõ lieäu: tuøy theo kieåu cuûa caùc toaùn haïng tham gia pheùp toaùn. Ñòa chæ : ñòa chæ töông ñoái. Ñòa chæ naøy ñöôïc gaùn khi sinh maõ.
Moät soá maõ boä töù cho caùc pheùp toaùn hoïc JMP (i, 0, 0) nhaûy ñeán boä töù coù chæ soá i JPG (i, p1, p2) nhaûy ñeán boä töù i neáu toaùn haïng thöù nhaát lôùn hôn toaùn haïng hai as1 (p1, p2, 0) gaùn trò p1 cho p2. p2 laø bieán ñôn FLT (p1, p2, 0) Ñoåi trò cuûa p1 thaønh soá thöïc, gaùn sang p2 FIX (p1, p2, 0) Ñoåi trò cuûa p1 thaønh soá nguyeân, gaùn sang p2 6.2. Xöû lyù ngöõ nghóa vôùi phaân tích cuù phaùp töø döôùi leân 1. Vaán ñeà truyeàn thuoäc tính Thí duï 6.1. Chuùng ta coù vaên phaïm G. → id := → + | → * | → id | ( )
n12 n11 n10 n9 n8 n 2 n 5 n7 n n 4 1 n6 n3 + id ) id1 := id2 * ( id3 4 Hình 6.2. Caây cuù phaùp A := X * (R + Q).
Baûng danh bieåu Token Trò töø vöïng Kieåu döõ lieäu 1 id A thöïc 2 id X thöïc 3 id R thöïc 4 id Q thöïc - Truyeàn thuoäc tính - Sinh ra bieán taïm khi thu giaûm 2. Phöông phaùp thöïc hieän söï truyeàn thuoäc tính Ñeå thöïc hieän xöû lyù ngöõ nghóa trong quaù trình phaân tích cuù phaùp, chuùng ta seõ duøng moät stack ñaëc bieät goàm caùc phaàn: A: kyù hieäu vaên phaïm (töôïng tröng cho moät danh hieäu) B: coù trò 0 hoaëc 1 (kyù hieäu 1 laø bieán taïm) C: con troû chæ ñeán baûng danh bieåu (thöïc chaát laø vò trí cuûa danh bieåu ôû trong baûng danh bieåu
Thí duï 6.2. Cho vaên phaïm G nhö ôû thí duï 6.1. → id := → + | → * | → id | ( ) 3. Nguyeân taéc xöû lyù ngöõ nghóa Khi coù moät chuoãi con x = x1x2 xn saép ñöôïc thu giaûm veà KHKKT U (vôùi luaät sinh U Æ x1, x2 xn) thì haønh vi xöû lyù ngöõ nghóa taïi nuùt V laø haøm cuûa: 1) Luaät sinh U Æ x1x2 xn 2) Caùc xöû lyù ngöõ nghóa cuûa caùc nuùt xi, töùc laø caùc nuùt con cuûa V coù theå laø: i) Tra cöùu baûng danh bieåu ii) Taïo ra bieán taïm iii) Sinh maõ trung gian iv) Truyeàn thuoäc tính töø x veà V
6.3. Kieåm tra kieåu döõ lieäu 1. Heä thoáng kieåu Ñònh nghóa bieåu thöùc kieåu 1. Kieåu döõ lieäu cô baûn 2. Khi bieåu thöùc kieåu ñöôïc ñaët teân 3. Boä kieán thieát kieåu bao goàm: 1) Daõy (array): array (I, T). 2) Tích soá (product): tích soá cartesian T1 x T2. 3) Baûn ghi (record): kieåu cuûa baûn ghi laø tích soá cuûa bieåu thöùc kieåu caùc thaønh phaàn cuûa noù. Thí duï: type row = record address : integer; lexeme : array [1 15] of char; end; var table : array [1 10] of row; Kieåu row ñöôïc bieåu dieãn baèng bieåu thöùc kieåu: record ((address x integer) x (lexeme x array (1 15, char))).
4) Con troû (pointer): pointer (T). 5) Haøm (function): D Æ R. Thí duï: trong Pascal coù khai baùo: function f (a, b : char) : ↑ integer; Bieåu thöùc kieåu cuûa f laø: char x char Æ pointer (integer) 4. Bieåu thöùc kieåu chöùa caùc bieán maø trò cuûa chuùng laø bieåu thöùc kieåu. Ñeå bieåu dieãn bieåu thöùc kieåu ta duøng ñoà thò. (H.6.4) laø caây vaø dag, bieåu thò cho bieåu thöùc kieåu char x char Æ pointer (integer). Heä thoáng kieåu x pointer x pointer char char interger char interger Hình 6.4. Caây vaø dag, bieåu thò cho bieåu thöùc char x char Æ point (interger)
Kieåm tra kieåu tónh vaø kieåm tra kieåu ñoäng Phaùt hieän loãi 2. Ñaëc taû boä kieåm tra kieåu ñôn giaûn Ngoân ngöõ ñôn giaûn Chuùng ta coù ngoân ngöõ ñôn giaûn ñöôïc sinh ra töø vaên phaïm G P → D ; E D → D ; D | id : T T → char | integer | array [num] of T |↑T E → literal | num | id |E mod E |[E]|E ↑ Moâ phoûng 6.1. Sô ñoà bieân dòch duøng ñeå löu giöõ kieåu cuûa caùc danh bieåu P → D ; E D → D ; D D → id : T {addtype (id. entry, T. type)} T → char { T. type := char} T → integer {T. type := integer} T →↑T1{T. type := pointer (T1. type)} T → array [num] of T1{T. type = array (num. val, T1 . type)}
Kieåm tra cho bieåu thöùc 1. Kieåu token laø literal vaø num thí coù kieåu laø char vaø integer. E → literal {E. type := char} E → num {E. type := integer} 2. E → id {E. type := lookup (id. Entry)} 3. E → E1 mod E2 {E. type := if (E1 . type = integer) and (E2. type := integer) then integer else type - error} 4. E → E1 {E2}{E. type := if (E1 . type = integer) and (E1. type E2 = array (s, t)) then t else type – error} 5. E → E1 ↑{E. type := if E1. type = pointer (t) then t else type – error} Kieåm tra kieåu döõ lieäu cho caùc phaùt bieåu Moät chöông trình bao goàm caùc khai baùo, sau ñoù laø caùc phaùt bieåu, ñieàu naøy ñöôïc bieåu thò baèng luaät sinh P Æ D; S.
Moâ phoûng 6.2. Sô ñoà bieân dòch cho kieåu döõ lieäu cuûa caùc phaùt bieåu P → D; S S → id := E {S.type := if id. type = E. type then void else type - error} S → if E then S1 {S.type := if E. type = boolean then S1. type else type - error} S → while E do S1 {S.type := if E. type = boolean then S1. type else type - error} S → S1; S2 {S.type := if (S1. type = void) and (S2. Type = void) then void else type - error} Kieåm tra kieåu cuûa haøm E Æ E (E) Ñeå dieãn taû kieåu cho bieåu thöùc kieåu ta duøng kyù hieäu T vaø theâm luaät sinh T Æ T1’ Æ ‘T2 {T. type := T1. type Æ T2. type}
Quy taéc kieåm tra kieåu cuûa haøm laø E Æ E1 (E2) {E. type := if (E2. type = s) and (E1. type = s Æ t) then t else {type - error} T1 x T2 x x Tn Thí duï: root Æ (real Æ real) x real Æ real Chuùng ta seõ hieåu laø coù khai baùo: function root (functionf (real) : real; x : real) : real 3. Söï töông ñöông cuûa bieåu thöùc kieåu • Söï töông ñöông caáu truùc cuûa bieåu thöùc kieåu • Giaûi thuaät kieåm tra töông ñöông caáu truùc cuûa caùc bieåu thöùc kieåu
Moâ phoûng 6.3. Kieåm tra töông ñöông caáu truùc cuûa hai bieåu thöùc kieåu s vaø t. function sequiv (s, t): boolean; begin if s vaø t cuøng moät kieåu cô baûn then true else if s = array (s1, s2) and t = array (t1, t2) then return sequiv (s1, s2) and sequiv (s2, t2) else if s = s1 x s2 and t = t1 x t2 then return sequiv (s1, t1) and sequiv (s2, t2) else if s = pointer (s1) and t = pointer (t1) then return sequiv (s1, t1) else if s = s1→ s2 and t = t1→ t2 then return sequiv (s1, t1) and sequiv (s2, t2) else return false; end; Thí duï 6.3. Chuùng ta seõ giôùi thieäu caùch maõ hoaù caùc bieåu thöùc kieåu cuûa trình bieân dòch C do D.M. Ritchie vieát.
Moâ phoûng 6.4. Caùc thí duï veà bieåu thöùc kieåu. char freturns (char) pointer (freturns (char)) array (pointer (freturns (char)) Boä kieán thöùc kieåu Maõ hoùa pointer 01 array 10 freturns 11 Caùc kieåu cô baûn cuûa ngoân ngöõ C ñöôïc John (1979) maõ hoùa baèng 4 bit Kieåu cô baûn Maõ hoùa boolean 0000 char 0001 integer 0010 real 0011
Moâ phoûng 6.5. Maõ hoùa bieåu thöùc kieåu ôû moâ phoûng 6.4. Bieåu thöùc kieåu Maõ hoùa char 000000 0001 freturns (char) 000011 0001 pointer (freturns (char)) 0111 0001 array (pointer (freturns (char)) 100111 0001 - Teân cho bieåu thöùc kieåu Sau ñaây laø moät ñoaïn khai baùo kieåu trong Pascal: type link = ↑ cell; var next : link; last : link; p : ↑ cell; q, r : ↑ cell;
Thí duï 6.4. Bieán Bieåu thöùc kieåu next link last link p pointer (cell) q pointer (cell) r pointer (cell) Hình 6.11. Bieán vaø caùc bieåu thöùc kieåu töông öùng 6.4. Chuyeån ñoåi kieåu Thí duï kyù hieäu haäu toá cuûa bieåu thöùc a + i sau khi thöïc hieän haønh vi chuyeån ñoåi kieåu: a i intereal real + - AÙp ñaët toaùn töû (Coercion) Thí duï 6.5.
Moâ phoûng 6.6. Quy taéc kieåm tra kieåu cho vieäc aùp ñaët toaùn töû ñeå ñoåi trò toaùn haïng töø soá nguyeân sang soá thöïc. Luaät sinh Luaät ngöõ nghóa E → num E. type := integer E → num. num E. type := real E → id E. type := lookup (id. entry) E → E1 op E2 E. type := if (E1. type = integer) and (E2. type = integer) then integer else if (E1. type = integer) and (E2. type = real) then real else if (E1. type = real) and (E2. type = integer) then real else if (E1. type = real) and (E2. type = real) then real else type - error
Löu yù: for | := 1 to N do x [i] := 1 (1) for | := 1 to N do x [i] := 1.0 (2) 6.5. Xöû lyù ngöõ nghóa cho phaùt bieåu goto tham khaûo tröôùc Thí duï 6.6. Giaû söû chuùng ta coù ñoaïn chöông trình goto L (10) JMP (0,0,0) goto L (50) JMP (10,0,0) goto L (90) JMP (50,0,0) L: x := x + 1 (120)
Baûng 6.2. Baûng löu giöõ teân phaùt bieåu vaø chæ soá ñaàu danh saùch lieân keát Teân p/b Ñòa chæ Ñònh nghóa L90 0 Baûng 6.3. Ñieàn chæ soá cuûa teân L vaøo caùc leänh nhaûy Teân p/b Ñòa chæ Ñònh nghóa L 120 1 (10) JMP (120,0,0) (50) JMP (120,0,0) (90) JMP (120,0,0)
CHÖÔNG 7 QUAÛN LYÙ BOÄ NHÔÙ TRONG THÔØI GIAN THÖÏC THI 7.1. Caùc phaàn töû yeâu caàu caáp phaùt boä nhôù trong thôøi gian thöïc thi Taát caû caùc phaàn töû caàn ñöôïc caáp phaùt boä nhôù, bao goàm: 1. Ñoaïn maõ cuûa chöông trình ñöôïc bieân dòch. 2. Caùc chöông trình heä thoáng caàn thieát trong thôøi gian thöïc thi. 3. Caáu truùc döõ lieäu vaø haèng do ngöôøi söû duïng ñònh nghóa. 4. Caùc ñieåm trôû veà cuûa chöông trình con. 5. Moâi tröôøng tham khaûo. 6. Caùc vò trí nhôù taïm cho vieäc tính trò bieåu thöùc. 7. Nhaäp, xuaát boä ñeäm. 8. Caùc baûng, traïng thaùi thoâng tin. Ngoaøi döõ lieäu vaø caùc chöông trình ñöôïc bieân dòch, caùc taùc vuï cuõng caàn boä nhôù: 1) Goïi chöông trình con vaø caùc taùc vuï trôû veà. 2) Khôûi taïo vaø huûy boû caáu truùc döõ lieäu. 3) Taùc vuï theâm vaøo hoaëc loaïi boû caùc phaàn töû.
7.2. Caùc vaán ñeà veà ngoân ngöõ nguoàn Chöông trình con Moâ phoûng 7.1. Chöông trình Pascal ñoïc vaø saép xeáp thöù töï caùc soá nguyeân (1) program sort (input, output); (2) var a: array [0 10]; (3) procedure readarray; (4) var i: integer; (5) begin (6) for i := 1 to 9 do read (a [1]); (7) end; (8) function partition (y, z: integer): integer; (9) var i, j, x, v: integer; (10) begin (11) end; (12) procedure quicksort (m, n: integer);
(13) var i: integer; (14) begin (15) if (n > m) then begin (16) i := partition (m, n); (17) quicksort (m, i – 1); (18) quicksort (i + 1, n); (19) end; (20) end; (21) begin (22) a[0] := -9999; a[10] := 9999; (23) readarray; (24) quicksort (1, 9); (25) end
Caây hoaït ñoäng (activation tree) Caây hoaït ñoäng duøng ñeå mieâu taû con ñöôøng maø söï ñieàu khieån ñi vaøo vaø ñi ra khoûi caùc hoaït ñoäng cuûa chöông trình. Moät soá tính chaát cuûa caây hoaït ñoäng: 1. Moãi nuùt cuûa caây töôïng tröng cho moät hoaït ñoäng cuûa chöông trình con. 2. Nuùt goác (root) töôïng tröng cho hoaït ñoäng cuûa chöông trình chính. 3. Nuùt a laø cha cuûa nuùt b neáu vaø chæ neáu doøng ñieàu khieån ñi töø söï hoaït ñoäng a sang söï hoaït ñoäng b. 4. Nuùt a ôû beân traùi nuùt b neáu vaø chæ neáu thôøi gian soáng cuûa a xuaát hieän tröôùc thôøi gian soáng cuûa b.
Moâ phoûng 7.2. Caùc phaùt bieåu in cuûa chöông trình ôû moâ phoûng 7.1 mieâu taû söï thöïc thi cuûa noù. Söï thöïc thi chöông trình baét ñaàu vaøo readarray ra khoûi readarra vaøo quicksort (1,9) vaøo partition (1,9) ra khoûi partition (1,9) vaøo quicksort (1,3) ra khoûi quicksort (1,3) vaøo quicksort (5,9) ra khoûi quicksort (5,9) ra khoûi quicksort (1,9) Söï thöïc thi keát thuùc
Thí duï 6.1. s: vieát taét cho sort p: vieát taét cho partition r: vieát taét cho readarray q: vieát taét cho quicksort S r q(1,9) q(5, 9) p(1,9) q(1,3) q(7,9) p(5,9) q(5,5) p(1,3) p(7,9) q(7,7) q(1,0) q(2,3) p(2,3) q(2,1) q(3,3) Hình 7.1. Caây hoaït ñoäng ñöôïc xaây döïng töø chuoãi xuaát ôû moâ phoûng 7.2.
Stack ñieàu khieån (Control stack) S r q(1,9) p(1,9) q(1,3) q(2.3) p(1,3) q(1,0) Hình 7.2. Stack ñieàu khieån bao goàm caùc nuùt treân con ñöôøng töø s ñeán q (2,3) vaø trôû veà
• Taàm vöïc cuûa söï khai baùo Khai baùo coù theå töôøng minh, Var I: integer nhöng coù theå laø khai baùo ngaàm nhö Fortran, khi ta duøng teân bieán i maø khoâng khai baùo, Fortran maëc nhieân hieåu i laø bieán nguyeân. Taàm aûnh höôûng cuûa caùc khai baùo ñöôïc quy taéc taàm vöïc quyeát ñònh. • Söï raøng buoäc cuûa teân Moâi tröôøng laø teân cuûa haøm, aùnh xaï teân ñeán vò trí nhôù vaø traïng thaùi laø haøm aùnh xaï töø vò trí nhôù ñeán trò maø noù löu giöõ. teân vò trí nhôù trò Hình 7.3. Pheùp chieáu hai möùc töø teân ñeán trò Söï raøng buoäc chính laø baûn sao ñoäng cuûa khai baùo, trong thôøi gian thöïc thi.
Baûng 7.1. Caùc khaùi nieäm tónh vaø ñoäng cuûa chöông trình con Khaùi nieäm tónh Baûn sao ñoäng Ñònh nghóa chöông trình con Söï hoaït ñoäng cuûa chöông trình con Khai baùo teân Söï raøng buoäc teân vôùi vò trí nhôù Taàm vöïc yù nghóa cuûa khai baùo Thôøi gian soáng cuûa söï raøng buoäc teân 7.3. Toå chöùc kyù öùc Söï phaân chia boä nhôù trong thôøi gian thöïc thi Trong thôøi gian dòch, trình bieân dòch ñaõ tính toaùn kích thöôùc boä nhôù daønh cho chöông trình ñoái töôïng, noù bao goàm: 1. Maõ cuûa chöông trình ñoái töôïng. 2. Caùc ñoái töôïng döõ lieäu. 3. Moät phaàn trong stack ñieàu khieån (stack trung taâm) löu giöõ baûn ghi hoaït ñoäng cuûa chöông trình con.