Giáo trình môn học Trình biên dịch - Chương 2: Trình biên dịch đơn giản

CHÖÔNG 2 TRÌNH BIEÂN DÒCH ÑÔN GIAÛN 2.1. Toång quaùt 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 Boä phaân tích töø vöïng Boä bieân dòch tröïc tieáp cuù phaùp Chuoãi tokenChuoãi kyù töï Maõ trung gian Hình 2.1. Caáu truùc trình bieân dòch “front end” 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: stringstring string string string string Hình 2.2 Hai caây phaân tích cuûa caâu 9 – 5 + 2 + 9 5 string string - 5 string string 2 - a) 2 +9 b) 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 – exp.t ::= 9 termt ::= 9 termt.t ::= 5 termt ::= 2 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 term exp - 5 + {print (‘-‘)} term {print (‘5‘)} {print (‘+‘)} 2 {print (‘2‘)} 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 typea) typeb) array [simple] of type typec) array [simple] of type type num dotdot num array [simple] of num dotdot num Hình 2.6.Caùc böôùc xaây döïng caây phaân tích theo phöông phaùp töø treân xuoáng cho caâu: array [numdotdot num] of integer d) type simple typee) array [simple] of num dotdot num type 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 xA yA A yA A z - xyyz xyyz yyz yz yz 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ân tích cuù phaùp cho caâu xxxz khoâng thaønh coâng Luaät aùp duïng Chuoãi nhaäp S A xA A xA A xA A xxxz xxxz xxxz xxz xxz xz xz 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 xx x 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 ưu trình bieân dịch: Đ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 Hình 2.10. Nhaän daïng token cuûa boä phaân tích töø vöïng i f a b > = 0 .. t > = 0 t .. > = 0 t h .. ab>if ab> 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 3 9 id 4 15 id Daõy lexemes 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 d i v EOS m o d EOS c o u n t EOS i EOS 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 t t t pc 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 Vuøng chæ thò Choàng Vuøng döõ lieäu 1 push 5 5 + 0 1 2 rvalue 2 11 11 2 3 + a) 7 3 4 rvalue 3 4 5 ∗ 16 ∗ 6 .. 7 b) 112 c) 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: stmt→ if exp then stmt out := newlabel stmt.t ::= exp.t || ‘gotofalse’ out || stmt.t || ‘label’ out ngöõ nghóa 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 init scanner symbol parser error emit Bieåu thöùc ôû daïng trung toá 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äu toá 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 ) and (s[i] = lexemes [cp] do begin i := i + 1; cp := cp + 1; end; if 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}