Sinh mã trung gian - 1 -
SINH MÃ TRUNG GIAN
ằ ể ữ ư ự ế ư ư ể
t k t ng ph n Tuy r ng có th sinh mã tr c ti p, nh ng sinh mã trung gian có nh ng u đi m nh sau: - - ộ ứ ạ c mã đ c l p v i t ng máy tính c th . T đó làm gi m đ ph c t p ế ế ừ ượ ụ ể ừ ả ớ ừ
- ụ ấ ị
ư ệ ượ ể ộ ư ể ễ ể ị ỉ ượ ữ ộ ượ ộ ả ặ ằ ỉ ụ ậ ng tr ng và ư ộ ng tr ng bi u di n cho ch m c c a m t ỉ ụ ủ mã trung gian. Các ch m c th c s có th ể ự ự t khác ho c b ng k thu t đi n sau ề ỹ ặ ằ
d thi ầ ễ sinh đ ộ ậ c a sinh mã th c s . ự ự ủ i u mã d t ễ ố ư Sau đây ta xét lo i mã trung gian thông d ng nh t là mã ba đ a ch . ạ ỉ 1. Mã ba đ a ch ỉ ị Mã ba đ a ch h i gi ng nh mã assembly. Các câu l nh có th có nhãn t ỉ ơ ị ố các câu l nh đi u khi n dòng. M t nhãn t ề ệ câu l nh ba đ a ch trong m t m ng ghi gi ệ c thay vào các nhãn, ho c b ng m t l đ ượ (backpatching). D i đây là m t s câu l nh ba đ a ch thông d ng: ệ ộ ố ướ ụ ỉ ố ọ x := y op z, trong đó op là m t phép toán s h c ộ ị ạ ệ hai ngôi ho c phép toán logic. 1. Các câu l nh gán có d ng ặ x := op y, trong đó op là phép toán m t ngôi. Các phép ộ ộ ừ ủ ị ể 2. Các phép gán có d ng ạ ủ ế ể x := y, gán y vào x. ạ L là câu ệ goto L. Câu l nh ba đ a ch có nhãn ệ ị ỉ ệ ế ệ l nh đ ệ ệ ệ ệ ư if x relop y goto L. Câu l nh này th c hi n ự L n u quan toán m t ngôi ch y u là phép tr , phép ph đ nh logic, phép chuy n đ i ổ ki u, phép d ch bít. ệ ả ề c th c hi n ti p theo. ượ ề ệ ự ệ ế ạ ẽ ự ế ế ệ ủ ụ ệ return y đ trể ả 1,x2,...,xn) thì s sinh các ủ ụ ẽ x và y, th c hi n câu l nh có nhãn ệ i s th c hi n câu l nh ti p theo. ệ param x và call p,n dùng đ g i th t c. Còn l nh ể ọ y. Ví d đ g i th t c p(x ụ ể ọ ng ng nh sau: ư ỉ ươ ứ ị ư ị
ị 3. Các câu l nh sao chép d ng 4. L nh nh y không đi u ki n ự 5. Các l nh nh y có đi u ki n nh ệ ả m t phép toán quan h cho ộ h này là đúng, n u trái l ệ 6. Câu l nh ệ v m t giá tr l u trong ề ộ câu l nh ba đ a ch t ệ param x1 param x2 . . . param xn call p, n 7. Các phép gán ch s có d ng ỉ ố ạ i v trí i sau y ị ạ ị ng t x := y[i] có ý nghĩa là gán cho x giá tr t t ươ 8. Phép gán đ a ch và con tr có d ng x := &y, x := *y, *x := y ự ố ớ ỉ ị đ i v i x[i] := y ỏ ạ
ỉ ng c a mã trung gian. Trong m t ch ị ộ ạ ặ ệ ộ ừ ượ ộ c cài đ t nh các c u trúc v i các tr 2. Cài đ t các câu l nh ba đ a ch ệ M t câu l nh ba đ a ch là m t d ng tr u t ị trình d ch, nh ng câu l nh này có th đ ể ượ ỉ ệ ữ ị ươ ng ườ ng ủ ặ ư ấ ớ
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Sinh mã trung gian - 2 -
và toán h ng. Nh ng bi u di n đó là b t ( ộ ứ quadruple) và b baộ ữ ể ễ ạ ử
ng, đ t là là m t c u trúc b n ghi v i b n tr ả c g i l n l ượ ọ ầ ượ ườ op, arg1, arg2 và ớ ố x := y + z thì op là +, arg1 là y, arg2 là z và result ch aứ ệ m t ngôi thì không dùng arg2. ử ộ ch a các toán t ứ (triple) B tộ ứ B t ộ ấ ộ ứ result. Ví d , đ i v i câu l nh ụ ố ớ x. Đ i v i toán t ố ớ Ví d câu l nh ụ ệ
ị ạ ỉ ư s đ ẽ ượ
nh sau: và đ a := -b * (c+d) c chuy n thành đo n mã ba đ a ch nh sau: ể t1 := - b t2 := c+d t3 := t1 * t2 a := t3 c bi u di n b ng b t ể ộ ứ ư ễ ằ ượ arg2
d t2 op uminus + * assign arg1 b c t1 t3 result t1 t2 t3 a 0 1 2 3
ờ ệ ể ị ạ ế ệ ạ ủ ể ế ế ả ư ằ ế ệ ế c bi u di n b ng m t c u trúc ch g m có ba ộ ấ ệ ỏ ứ ộ ể ỉ ẽ ượ ị ế ị ủ ễ ỉ ồ ệ ằ
B baộ Đ tránh ph i đ a các tên t m th i vào b ng ký hi u, chúng ta có th tham chi u đ n ế ể ả m t giá tr t m b ng v trí c a câu l nh dùng đ tính nó (tham chi u đ n câu l nh đó ộ chính là tham chi u đ n con tr ch a b ba c a câu l nh đó). N u chúng ta làm nh ư v y, câu l nh mã ba đ a ch s đ ậ tr ườ Ví d trên s đ c chuy n thành b ba nh sau: ng op, arg1 và arg2. ẽ ượ ụ ư ể ộ
arg2
op uminus + * assign arg1 b c (0) a d (1) (2) 0 1 2 3
arg1 và tham s trong arg2 và toán t ố ả ệ ặ ế làử
ặ ỏ ỉ ế ộ ấ ễ ộ ệ ượ ự ể ễ ằ arg1 và arg2 có th đ ể ượ ụ ả ạ ng op ho c đ a thêm m t s tr i các lo i m c ghi khác nhau trong ng khác. ặ ư ộ ố ườ ư ượ c ư ụ ế ấ ộ Chú ý, câu l nh sao chép đ t k t qu trong assign. Các s trong ngo c tròn bi u di n các con tr ch đ n m t c u trúc b ba, còn con tr ỏ ố ể c bi u di n b ng chính các tên. Trong th c hành, thông tin ch đ n b ng ký hi u đ ỉ ế ả c mã hoá c n đ di n gi ể ễ ầ vào tr ườ Chú ý, phép toán ba ngôi nh x[i] := y c n đ n hai m c trong c u trúc b ba nh đ ầ ch ra nh sau: ư ỉ
op arg1 arg2
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Sinh mã trung gian - 3 -
(0) (1) []= assign x (0) i y
ng t đ i v i phép toán ba ngôi x := y[i] t ươ ự ố ớ
(0) (1) op []= assign arg1 y x arg2 i (0)
ề ỉ 3. Cú pháp đi u khi n sinh mã ba đ a ch ể Đ i v i m i ký hi u X, chúng ta ký hi u: ố ớ ỗ ệ ơ ể ứ ị ệ ị ế ả ế ẽ - X.place là n i đ ch a mã ba đ a ch sinh ra b i X (dùng đ ch a các k t qu ể ứ ỉ ộ newtemp dùng đ sinh ra m t ể ộ ị ế ạ ế ể ở trng gian). Vì th s có m t hàm đ nh nghĩa là bi n trung gian (bi n t m) đ gán cho X.place. ỉ ủ X ứ ị th t c - X.code ch a đo n mã ba đ a ch c a ạ - ị ủ ụ gen đ sinh ra câu l nh ba đ a ch . ỉ ể ệ Sau đây, chúng ta xét ví d sinh mã ba đ a ch cho m t s d ng câu l nh ộ ố ạ ụ ệ ị ỉ
Sinh mã ba đ a ch cho bi u th c s h c: ứ ố ọ ể ỉ ị
S n xu t ấ ả Lu t ng nghĩa ữ ậ
S -> id := E
E -> E1 + E2
E -> E1 * E2
E -> - E1
E -> ( E1 )
E -> id S.code := E.code || gen(id.place ‘:=’ E.place) E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘+’ E2.place) E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘+’ E2.place) E.place := newtemp; E.code := E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place) E.place := E1.place E.code := E1.code E.place := id.place E.code := ‘’
Ví d :ụ
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Sinh mã trung gian - 4 -
hãy sinh mã ba đ a ch cho câu l nh sau “x := a + ( b * c )” ệ ị ỉ
S => x := E => x := E1 + E2 => x := a + E2 => x := a + ( E3 ) => x := a + ( E4 * E5 ) => x := a+ ( b * E5 ) => x := a + ( b * c )
E5.place := c E5.code := ‘’ E4.place := b E4.code := ‘’ E3.place := t1 E3.code := t1 := b * c E2.place := t1 E2.code := t1 := b * c E1.place := a E1.code := ‘’ E1.place := a E1.code := ‘’ E.place := t2 E.code := t1 := b * c || t2 := a + t1 S.code := t1 := b * c || t2 := a + t1 || x := t2
ỉ ị ể ứ ộ ộ ố ớ
ỉ ệ ả ệ
ề
ệ
ể ẽ ề ộ ơ ể
ố ớ
ệ
i n u E đúng, và i n u E sai. ể
E.true, n i quy n đi u khi n s chuy n
ề
ể ớ ế ơ Sinh mã ba đ a ch cho bi u th c Boole:
Đ i v i m t bi u th c Boole E, chúng ta s d ch E thành m t dãy các câu l nh ba đ a
ị
ẽ ị
ứ
ch , trong đó đ i v i các phép toán logic s sinh ra các l nh nh y có đi u ki n và
ẽ
không có đi u ki n đ n m t trong hai v trí:
ề
ị
ế
t
E.false, n i quy n đi u khi n s chuy n t
ớ ế
ề
Ví d E có d ng
ụ ể ẽ
ề
a if a
Ví d đo n l nh sau: ụ ạ ệ if a>b then a:=a-b; else b:=b-a; đ c chuy n thành mã ba đ a ch nh sau: ượ ỉ ư ể L1: L2: ị
if a>b goto L1
goto L2
t1 := a –b
a := t1
goto Lnext
t2 := b-a
b := t2 Lnext: Sinh mã trung gian - 5 - Trong đo n mã ba đ a ch trên thì E.true = L1 và E.false = L2 ạ ị ỉ ộ ố ẽ ề ể ị ỉ ể
Sau đây chúng ta s xem xét m t s cú pháp đi u khi n sinh mã ba đ a ch cho các bi u
th c Boole.
Đ sinh ra các nhãn, chúng ta s d ng th t c ủ ụ newlable đ sinh ra m t nhãn m i. ử ụ ứ
ể ể ộ ớ S n xu t
ấ ả Lu t ng nghĩa
ữ ậ E -> E1 or E2 E -> E1 and E2 E -> not E1 E -> ( E1 ) E -> id1 relop id2 E -> true E1.true := E.true;
E1.false := newlable;
E2.true := E.true;
E2.false := E.false;
E.code := E1.code || gen(E1.false ‘:’) || E2.code
E1.true := newlable;
E1.false := E.false;
E2.true := E.true;
E2.false := E.false;
E.code := E1.code || gen(E1.true ‘:’) || E2.code
E1.true := E.false;
E1.false := E.true;
E.code := E1.code;
E1.true := E.true;
E1.false := E.false;
E.code := E1.code;
E.code := gen(‘if’ id1.place relop.op id2.place
‘goto’ E.true) || gen(‘goto’ E.false)
E.code := gen(‘goto’ E.true) E -> false E.code := gen(‘goto’ E.false) ng trình sau: Ví d : sinh mã ba đ a ch cho đo n ch
ị ụ ạ ỉ ươ if a>b and c>d then
x:=y+z else x:=y-z i: L i gi
ờ ả ư ậ ứ ế ạ ở ươ ng trình có d ng: nh v y n u coi E là bi u th c logic
a>b and c>d thì đo n ch
ể
if E then x:=y+z , khi đó mã ba đ a ch cho đo n ch
ỉ ươ ạ ị ng trình trên tr thành
ạ E.code {
if E=true goto E.true
goto E.false } Sinh mã trung gian - 6 - E.true: t1:= y+z
x := t1; E.false : t2 := y-z
x :=t2 ả ư ậ ễ ấ ủ ệ ể
ứ
i thích t i sao chúng ta l ề ả ạ ạ ữ ư ả
ậ ụ ạ ị ỉ ị
ỉ
trên là: ng trình ngu n Nh v y chúng ta ph i phân tích bên trong c a bi u th c E, và d th y các l nh nh y
ả
ậ
i có các lu t
bên trong E chính là E.true và E.false, đi u đó gi
ng nghĩa nh b ng trên.
Áp d ng các lu t sinh mã ba đ a ch trong b ng trên chúng ta có đo n mã ba đ a ch cho
ả
đo n ch
ạ ồ ở ươ L1: L2: L3: if a>b goto L1
goto L3
if c>d goto L2
goto L3
t1 := y+z
x := t1
goto L4
t2 := y-z
x := t2 L4: ỉ ị ể ộ ố ệ ề ể ể ự ể ệ ể ứ
ẽ ầ ệ ợ ệ
ự
ị ể
ể ể
ể ệ
ệ ị ể
ố ệ ố ớ ộ ứ
ứ
ủ ụ newlable. M t khác
S.next đ i v i kh i l nh sinh
ệ ặ
ủ ớ
ệ ế ị ị Sinh mã ba đ a ch cho m t s l nh đi u khi n:
ề
Trong các câu l nh đi u khi n có đi u ki n, chúng ta d a vào bi u th c logic E đ
ề
ệ
i v trí thích h p. Do đó ta s c n hai nhãn: nhãn
chuy n vi c th c hi n các câu l nh t
ớ ị
ệ
i khi bi u th c logic E là đúng, và nhãn
E.true đ xác đ nh v trí câu l nh chuy n t
ể ớ
ị
E.false đ xác đ nh v trí câu l nh chuy n t
i khi bi u th c logic E là sai. Đ sinh ra
ể ớ
ị
m t nhãn m i, chúng ta dùng th t c
ra b i ký hi u S là nhãn xác đ nh v trí ti p theo c a các l nh sau S.
Đ i v i câu l nh ở
ố ớ ệ S -> while E do S1 ế ầ ả ộ ỗ S.begin đ xác đ nh v trí b t đ u kh i l nh này. chúng ta c n có m t nhãn b t đ u c a kh i l nh này đ nh y đ n m i khi E đúng, vì
ố ệ
v y c n nhãn
ắ ầ
ậ ầ ắ ầ ủ
ị ể
ố ệ ể ị S n xu t
ấ ả Lu t ng nghĩa
ữ ậ S -> if E then S1 S -> if E then S1 else S2 E.true := newlable;
E.false := S.next;
S1.next := S.next;
S.code := E.code || gen(E.true ‘:’) || S1.code
E.true := newlable;
E.false := newlable;
S1.next := S.next;
S2.next := S.next;
S.code := E.code || gen(E.true ‘:’) || S1.code || Sinh mã trung gian - 7 - S -> while E do S1 gen(‘goto’ S.next) || gen(E.false ‘:’) || S2.code
S.begin := newlable;
E.true := newlable;
E.false := S.next
S1.next := S.begin;
S.code := gen(S.begin ‘:’) || E.code ||
gen(E.true ‘:’) || S1.code || gen(‘goto’ S.begin) Ví d 1:ụ sinh đo n mã ba đ a ch cho đo n mã ngu n sau: ạ ạ ồ ị ỉ while a<>b do if a>b then a:=a-b else b:=b-a :
i L i gi
ờ ả L1: L2: L3: L4: if a<>b goto L2
goto Lnext
if a>b goto L3
goto L4
t1 := a-b
a := t1
goto L1
t2 := b-a
b := t2
goto L1 Lnext: ị ệ ể ư ồ ư ậ
ị ữ
ậ ệ ệ
ể ể
ả ả
ng trình ngu n là t p l nh ba đ a ch và b ng ký hi u qu n lý các
ch
ỉ ừ ươ ả ủ
ả ệ ỉ ng đ i đ l u giá
ố ể ư ề ể ỉ ươ ư ị ng đ i c a các đ n danh; m i s interger ỗ ố ệ ị s hàm enter dùng đ ể ứ ị
ứ ố ủ
ỏ ứ ả ử ố
ề ể ể
ụ ướ
i ộ ị ố ị Các khai báo.
ng ng trong mã ba
Đ i v i các khai báo đ nh danh, chúng ta không sinh ra mã l nh t
ố ớ
ươ ứ
đ a ch mà dùng b ng ký hi u đ l u tr . Nh v y có th hi u là k t qu c a sinh mã
ế
ỉ
ị
ba đ a ch t
ị
đ nh danh.
ị
V i m i đ nh danh, chúng ta l u các thông tin v ki u và đ a ch t
ỗ ị
ớ
tr cho đ nh danh đó.
ị
ị
Ví d :ụ
s ký hi u offset đ ch a đ a ch t
Gi
ỉ ươ
ả ử
chi m 4 byte, s real ch a 8 byte và m i con tr ch a 4 byte; gi
ế
ỗ
nh p thông tin v ki u và đ a ch t
ng đ i cho m t đ nh danh, chúng ta có ví d d
ậ
đây mô ta vi c sinh thông tin vào b ng ký hi u cho các khai báo. ỉ ươ
ả ệ ệ Sinh mã trung gian - 8 - S n xu t
ấ ả Lu t ng nghĩa
ữ ậ P -> D offset := 0 D -> D ; D D -> id : T T -> interger T -> real
T -> array [ num ] of T1 T -> ^T1 enter(id.name,T.type, offset) ;
offset := offset + T. width
T.type := interger;
T. width := 4
T.type := real; T. width := 8
T.type := array(num.val,T1.type);
T.width := num.val * T1. width
T.type := pointer(T1.type)
T. width := 4 ị ỉ ề ậ ả ạ
ệ ẽ
ng ng đ s d ng trong
ể ử ụ ỉ ươ ứ ế
ị ư ậ
ế
ế
ệ ề ể
ể ở ệ ả ng đ i c a m t ph n t ị
c tính b ng đ a
ằ ượ ụ ả ị . Nh v y, trong các đo n mã ba đ a ch , khi đ c p đ n m t tên, chúng ta s tham
ộ
chi u đ n b ng ký hi u đ l y thông tin v ki u, đ a ch t
ể ấ
các câu l nh. Hay nói cách khác chúng ta có th thay m t đ nh danh b i ch m c c a
ỉ ụ ủ
ộ ị
đ nh danh đó trong b ng ký hi u.
ị
Chú ý: đ a ch t
ộ
ỉ ươ
ch c a x c ng v i i l n đ dài c a m i ph n t
ớ trong m ng, ví d x[i] đ
ầ ử ố ủ
ộ
ầ ầ ử
ỗ ỉ ủ ủ ộ : Hãy chuy n các câu l nh ho c đo n ch ể ệ ạ ặ ươ ị
ng trình sau thành đo n mã ba đ a ạ Bài t p 1ậ
ch :ỉ ng trình C 1) a * - (b+c)
2) đo n ch
ươ
ạ
main ()
{ int i; int a[100]; i=1;
while(i<=10)
{ a[i]=0;
i=i+1; } }Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
Tập bài giảng CTD Lê Anh Cường – Khoa Công Nghệ, ĐHQG HN
