Giáo trình môn học Trình biên dịch - Chương 3: Phân tích từ vựng

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 if then ralation num id literal const if then , = , > = 3.14, 2.5, 7.6 abc, ou, bc1 ‘abcef’ const if then caùc toaùn töû quan heä haèng soá baát kyø chuoãi goàm kyù töï chöõ vaø soá, baét ñaàu laø kyù töï chöõ laø chuoãi kyù töï baát kyø naèm giöõa 2 daá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 Boä phaân tích töø vöïng Baûng danh bieåu Boä phaân tích CP Chöông trình nguoàn token yeâu caàu token 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 * X EOF - 2 EOF 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û 0 7 8 Baét ñaàu > = other 2 3 Start < = return (relop, LE) 6 7 8 > return (relop, NE) 4 return (relop, LT) 5 = return (relop, EQ) > other 6 Hình 3.4. Sô ñoà dòch cho >= vaø = 0 1 = other (relop, EQ) 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àn cho NFA ôû hình 3.10 Kyù hieäu nhaäp Traïng thaùi a b 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 30 a 0 a b b1 1 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. 0start ∈ 1 10 4∈ a b b a 2 8 3 5 6 7 9 ∈ ∈ ∈ Hình 3.13. NFA nhaän daïng (a | b)* abb b 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 2. Vôùi a thuoäc Σ, xaây döïng NFA start i f ∈ start i f a 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) i start f ∈N(s) N(t) ∈∈ ∈ - Vôùi bieåu thöùc st, xaây döïng NFA hoãn hôïp N (st) start i f N(t)N(s) - 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 Hình 3.16. Caây phaân raõ cuûa bieåu thöùc gia toá (a| b )* abb# a 3 b 4 # 6b 5 a 1 b 2 * • • • • 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} Astart ∈ B F 2∈ a # b a 1 4 C D F 3 6 ∈ ∈ ∈ b4 ba ∈ ∈ ∈ 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 laø ∈ true n laø nuùt coù teân laø vò trí i false {i} {i} nullable(c1) or nullable(c2) firstpos(c1) ∪ firstpos(c2) lastpos(c1) ∪ lastpos(c2) nullable(c1) and nullable(c2) if nullable(c1) then firstpos(c1) ∪ firstpos(c2) else firstpos(c1) if nullable(c2) then lastpos(c1) ∪ lastpos(c2) else lastpos(c2) true firstpos(c1) lastpos(c1) n c2c1 | c2c1 ° n c1 ∗ n 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át caû vò trí trong first(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}a {1} {2}a {2} # {6} ∗ {1,2} {1,2} {1,2} {1,2} {5}a{5} {4}a{4} {3}a{3} {1,2,3} {1,2,3} {1,2,3} {1,2,3} {3} {4} {5} {6} {6} 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 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 0 – 0 1 0000 222222222 0 – 0 3 0 – 0 0 1 2 3 4 4 0 0 -1 3 1 -1 1 1 -1 2 1 5 2 2 -1 -1 2 5 3 3 -1 -1 2 -1 4 4 -1 -1 -2 -1 5 4 -1 -1 4 -1 0 1 2 3 yrmap y next 2. Neùn caëp Hình 3.22. Baûng truyeàn neùn theo phöông phaùp neùn caëp 0 • 7 ‘0’,3 ‘0’,1 ‘1’,1 ‘2’,1 ‘3’,1 ‘4’,2 ‘5’,2 ynext 0 1 • 0 -1-112-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 ynext 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 Hình 3.23. Trình bieân dòch Lex vaø Boä phaân tích töø vöïng Chöông trình moâ phoûng FA vaø baûng truyeànTrình bieân dòch Lex a) Chöông trình moâ phoûng FA Baûng truyeàn b) Ñaëc taû lex Boä ñeäm nhaäp 1. Maãu so truøng treân cô sôû NFA Hình 3.24. NFA ñöôïc tao ra töø söï ñaëc taû LEX so N(pi) ∈ ∈ N(p1) N(pn) ∈