Sinh mã

Chia sẻ: Ho Quang Trung | Ngày: | Loại File: DOC | Số trang:12

0
47
lượt xem
6
download

Sinh mã

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

1. Mục đích và nhiệm vụ - Sinh mã : là giai đoạn cuối của quá trình dịch, sinh mã tốt là rất khó và sinh mã ra thường gắn với một loại máy tính nào đó. - Tiêu chuẩn quan trọng đối với bộ sinh mã là phải tạo mã đúng, đặt tiêu chuẩn này lên hàng đầu còn giúp cho việc thiết kế xây dựng và bảo trì bộ sinh mã trở nên đinh hướng tốt hơn, dễ thực hiện hơn và tiết kiệm hơn. Trong thực tế sinh mã máy đòi hỏi nhiều kinh nghiệm, am hiểu về ngôn ngữ...

Chủ đề:
Lưu

Nội dung Text: Sinh mã

  1. III.Sinh m∙  1.Môc ®Ých vµ nhiÖm vô  ­ Sinh   m∙   :   lµ   giai   ®o¹n   cuèi   cña   qu¸   tr×nh  dÞch, sinh m∙ tèt lµ rÊt khã vµ sinh m∙ ra th­ êng g¾n víi mét lo¹i m¸y tÝnh nµo ®ã.  ­ Tiªu chuÈn quan träng ®èi víi bé sinh m∙ lµ  ph¶i t¹o m∙ ®óng, ®Æt tiªu chuÈn nµy lªn hµng  ®Çu cßn gióp cho viÖc thiÕt kÕ x©y dùng vµ b¶o  tr× bé sinh m∙ trë nªn ®inh híng tèt h¬n, dÔ  thùc hiÖn h¬n vµ tiÕt kiÖm h¬n. Trong thùc tÕ  sinh m∙ m¸y ®ßi hái nhiÒu kinh nghiÖm, am hiÓu  vÒ ng«n ng÷ lËp tr×nh vµ kyc thuËt m¸y tÝnh. Sau   khi   hoµn   thµnh   ë   møc   ph©n   tÝch,   ch¬ng  tr×nh   dÞch   chuyÓn   sang   giai   ®o¹n   sinh   m∙   víi  ®Çu vµo lµ ch¬ng tr×nh nguån ë d¹ng c©y có ph¸p  hoÆc c©y m∙ trung gian. Giai ®o¹n sinh m∙ bao gåm : + Sinh m∙ trung gian  + Tèi u m∙  + Sinh m∙ ®Ých  Ch¬ng tr×nh ®Ých mµ chóng ta t¹o ra ë ®©y lµ  ch¬ng tr×nh hîp ng÷ Assemble vµ nghiªn cøu ph­ ¬ng ph¸p sinh m∙ cho :  + LÖnh g¸n  + BiÓu thøc sè häc  + CÊu tróc ®iÒu khiÓn 2.D¹ng m∙ ba ®Þa chØ  D¹ng m∙ ba ®Þa chØ lµ lªnh cã d¹ng : x := y Operator z Trong ®ã :  x, y, z lµ c¸c biÕn hoÆc bé nhí  trung gian.                                    Operator : lµ to¸n tö  ( phÐp to¸n) ­ D¹ng m∙ ba ®Þa chØ lµ c©u lÖnh cã hai ®ịa chØ  cho to¸n h¹ng vµ mét ®Þa chØ cho to¸n tö. Nã ®­ îc sö dông ë bíc sinh m∙ trung gian. ­ Mäi biÓu thøc sè häc hoÆc c©u lÖnh ®Òu cã thÓ  ®îc biÔu diÔn díi d¹ng m∙ ba ®Þa chØ VÝ dô : Víi c©u lÖnh : A:= X + Y + Z *150
  2. M∙  ba ® Þa  chØ sÏ l  :    T1:  Z*150 µ = T2:  Y + T1 = A :  X + T2 = • C¸c c© u l nh d¹ng m ∙ Ö  ba ® Þa chØ : 1­LÖ nh : X :  Y O perator  Z : l  phÐ p to¸n  sè  = µ häc hai ng«i hoÆ c  phÐ p to¸n  l i og c VÝ dô: X : Y + Z hoÆ c : = B and C =  A 2­LÖ nh : X :  O perator Y : l  phÐ p to¸n  m ét = µ  ng«i  , l  phÐ p to¸n  l  sè © m hoÆ c ¶o og i µ Êy  ®  l c. VÝ dô: X :  ­Y hoÆ c :  Not B =  A = 3­LÖ nh : X :  Y l  phÐ p g¸n  gi  trÞ  Y cho X (X   = µ ¸ ®î  g¸n bëi Y) c 4­LÖ nh nh¸y kh«ng ® i u ki n: G o to  Nhan(Pasca l)   Ò Ö J P Nhan ( Assem bl M e) 5­LÖ nh nh¸y cã ® i u ki n :  Ò Ö   If     BT   l i     then     G ot   Nhan   (Pasca l)   og c o  J , J , J  , J , J , … (A ssem bl A B G E LE e) 6­C¸c l nh   l  l i  gäi hµm ,  gäi  thñ   tôc,  l Ö µ ê ªnh   l  chØ sè m ∙ Êy  ® Þa Êy , l  chØ con trá… 3.C¸c vÊn ®Ò cña bé sinh m∙ a.§Çu vµo : lµ v¨n b¶n ch¬ng tr×nh nguån ®∙  qua   giai   ®o¹n   ph©n   tÝch   cã   thÓ   biÓu   diÔn   díi  d¹ng c©y ph©n tÝch. b.§Çu   ra   :   Bé   m∙   cña   ch¬ng   tr×nh   ®èi   tîng  gåm: ­ Mét ch¬ng tr×nh hoµn toµn b»ng ng«n ng÷ m¸y  cã thÓ ch¹y ®îc trªn m¸y tÝnh ­ Ch¬ng tr×nh ng«n ng÷ m¸y cã thÓ ®Þnh vÞ l¹i  ®îc ( cã thÓ chÌn, thªm mét ®o¹n m∙). ­ Ch¬ng tr×nh hîp ng÷ Assemble ­ Mét ch¬ng tr×nh b»ng ng«n ng÷ lËp tr×nh kh¸c c. Qu¶n lý bé nhí ­ ViÖc   chuyÓn   ®æi   t¬ng   øng   tõ   tªn   biÕn,   tªn  h»ng trong ch¬ng tr×nh nguån thµnh ®Þa chØ d÷  liÖu trong lóc ch¹y cña ch¬ng tr×nh chÝnh ®îc  thùc hiÖn phèi hîp gi÷a c¸c phÇn tríc vµ phÇn  sinh m∙, th«ng qua b¶ng ký hiÖu cã thÓ x¸c ®Þnh  ®îc mét ®Þa chØ t¬ng ®èi trong miÒn d÷ liÖu. d.  Chän chØ thÞ lÖnh
  3. - TÝnh chÊt cña tËp c¸c chØ thÞ lÖnh x¸c ®Þnh møc ®é phøc t ¹p cña viÖc chän chØ thÞ lÖnh. - TÝnh thèng nhÊt vµ tÝnh ®Çy ®ñ lµ nh©n tè quan träng - §èi ví i mçi c©u l ªnh d¹ng m· ba ®Þa chØ ta cã thÓ th iÕt kÕ bé khung ®Ó sinh m· cho nã. §Ó khi sinh m· ta chØ viÖc sö dông bé khung nµy ®Ó t ¹o ra m·. VD: Ví i c©u lÖnh : X:= Y + Z khung m· cña nã lµ Mov AL,Y Add AL,Z Mov X,AL Khi sinh m· cho c¸c lÖnh A:= B+ C, B:= C+D Khi ®ã chØ cÇn sö dông khung m· t rªn ®Ó cã ®o¹n m·, khi ®ã ta sÏ cã Mov AL,B Mov AL,C Add AL,Z Add AL,D Mov X,AL Mov B, AL - Sau khi t ¹o ra ®o¹n míi ta ph¶i thùc hiÖn tè i u b»ng c¸ch lo ¹ i bá c¸c m· l ªnh trung gian mang tÝnh chÊt chuyÓn ® mµ kh«ng ¶nh hëng ®Õn æi ch¬ng tr×nh. e. Sö dông thanh ghi - C¸c lÖnh tÝnh to¸n ®èi ví i thanh ghi th êng nhanh h¬n vµ gän h¬n tÝnh to¸n ví i bé nhí . Do vËy, viÖc sö dông thanh ghi cã hai vÊn ®Ò : + Trong khi dïng thanh ghi ta chän tËp c¸c biÕn sÏ ® ® trong c¸c thanh ghi t¹ i mét vÞ îc Æt t rÝ cña ch¬ng tr×nh + Trong gia i ®o¹n g¸n thanh ghi ta chØ thÞ mét thanh ghi ®Ó l u gi¸ trÞ mét biÕn tr¸nh tr - êng hîp g©y t ranh chÊp xung ®ét. f . M¸y ®Ých - M¸y ®Ých lµ m¸y sÏ ch¹y ch¬ng t r×nh ®Ých mµ bé sinh m· t ¹o ra ë ® ta sö dông m¸y thùc ®Ó ©y m« t¶ vµ m· do bé sinh m· t¹o ra lµ d¹ng m· Assemble. C¸c c©u lÖnh cã d¹ng Operator §Ých, nguån
  4. Trong ®ã : Operator : lµ phÐp xö lý cã thÓ lµ Mov, Add, Sub, Cmp, Mul, Div,…. Nguån, ®Ých lµ c¸c ®Þa chØ d÷ l iÖu chÞu sù t¸c ®éng cña phÐp xö lý. §Ých vµ nguån cã thÓ lµ biÕn hoÆc h»ng. Nh ng tèi thiÓu ph¶i cã sù tham gia cña mét thanh ghi. 4.Sinh m∙ cho lÖnh g¸n vµ biÓu thøc sè häc Dùa vµo c©y có ph¸p ( lµ c©y m« t¶ lÖnh g¸n hoÆc biÓu thøc sè häc) ® x©y dùng trong qu¸ îc tr×nh ph©n tÝch có ph¸p. Tõ c©y nµy ta dÞch sacng m· ®Ých trong qu¸ tr×nh dÞch ph¶i tham kh¶o c¸c ký hiÖu trong b¶ng ký hiÖu. Ta cã thÓ xem c©y có ph¸p lµ c©y m· ch¬ng tr×nh trung gian. Mµ t¹ i nót thø n trªn c©y cã ®o¹n m· lªnh, kÝ hiÖu lµ C(n). Khi ®ã ®Ó sinh m· mét nót n cña c©y chóng ta ph¶i ghÐp c¸c ®o¹n m· con hoÆc ch¸u theo mét trËt tù nhÊt ®Þnh. TrËt tù ®ã lµ tÝnh tõ dí i lªn vµ tõ tr¸ i qua ph¶i cña c©y. Cã ba d¹ng nót trªn c©y := + * a) b) c) Trong ®ã : Ký hiÖu lµ mét nót (c©y con). Riªng nót tr¸ i cña d¹ng a lµ mét tªn biÕn VD1: Víi lÖnh g¸n A:= < id1> + + ta sÏ biÓu diÔn nh sau : n2 n1 A := n0 < d1> i < d2> i * < d3> i
  5. - Nót d¹ng a, gi¸ trÞ c©y con bªn ph¶i ® ph¸t îc cho bªn biÕn bªn tr¸ i . - Nót d¹ng b, c, m· lÖnh C(n) lµ gi¸ trÞ cña c©y con bªn tr¸ i c«ng hoÆc nh©n gi¸ trÞ c©y con bªn ph¶i. §Ó t iÖn cho viÖc sinh m· ngêi ta quy ®Þnh bËc cña c©y BËc cña nót thø n trªn c©y, ký hiÖu lµ b(n) { B(n) = 0 nÕu n lµ nót l¸ Max (b (ni) )+1 nÕu nót n cã k con n1,n2,…nk i :=1,. . , k VD2: Víi vÝ dô 1 trªn ta cã b(n0) = 1 ; b(n1) = (1+1) = 2 ; b(n2) = (2+1) = 3 a. Gi¶i thuËt sinh m· cho lÖnh g¸n Vµo: C©y m· trung gian biÓu diÔn lÖnh g¸n x©u ω Ra : m· lÖnh Qu¸ tr×nh thùc hiÖn: Thùc hiÖn bíc 1 hoÆc 2 cho nót bËc 0. Bíc 1: + nót thø j trong b¶ng ký hiÖu gi¶ sö cã tªn lµ x th× Cj = x + Nót thø j trong b¶ng ký hiÖu gi¶ sö cã gi¸ trÞ k th× Ck = k Bíc2: Nót n thuéc c¸c nót : = , +, *, - , / , cã C(n) = φ Bíc 3: nót n lµ nót d¹ng a, cã 3 con n1, n2, n3, khi ®ã : C(n) lµ : Mov Ri, C(n3) Mov C(n) , Ri Ri lµ thanh ghi nµo ®ã Bíc 4: nót n lµ nót d¹ng b, cã 3 con n1, n2, n3, Khi ®ã C(n) lµ : Mov Ri, C(n1) Add Ri , C(n3) Mov C(n) , Ri Bíc 5: Nót n lµ nót d¹ng c, cã 3 con lµ n1, n2, n3 Khi ®ã C(n) lµ : Mov Ri, C(n1),
  6. Mov Rj , C(n3) Nul Ri Mov C(n), Ri Víi Ri = Ri * Rj Ri= Work Rj= Byte VD: Sinh m· cho lÖnh g¸n A:= X + Y + Z *150 Ta cã c©y m· trung gian lµ : n3 n2 A := n1 x n0 y + Z * 150 Sinh m· : Bíc 1: + C(n01) = Z , C(n11) = Y , C(n21) = X , C(n31) = A + C(n03) = 150 , Bíc 2: C¸c nót n02, n12, n22, n32 cã m· b»ng φ Bíc 3: Nót n0  cã 3 con n01 ,n 02 ,n 03, m· lÖnh C(n0 ) lµ Mov AH,0 ; AL = C(n01) Mov AL, Z ; BL = C(n03) Mov BL, 150 Mul BL Mov Temp1, AL Bíc 4: Nót n1 cã 3 con n11, n12 , n13  m· lÖnh C(n1) lµ : Mov AL, Temp1 Add Al, Y Mov Temp2, AL Bíc 4 : Nót n2  cã 3 con n21, n22 , n23  m· lÖnh C(n) lµ Mov AL, Temp2 Add AL, X
  7. M ov Tem p3, AL Bí  5 : Nót n3 cã 3 con n31 , n32 , n33  m∙ lÖnh lµ  c Mov  AL, Temp3 Mov  A, AL VËy m∙ thu ®îc: Mov AH, 0 Mov Al,Z Mov BL, 150 Mul BL Mov Temp1, AL ;1 Mov AL, Temp1 ;2 Add AL, Y Mov Temp2, AL ; 3 Mov AL, TEMP2 ;4 Add AL,X Mov Temp3, AL ;5 Mov AL, Temp3 ;6 Mov A, AL  • Tèi u m∙ : Ta thÊy c¸c cÆp lÖnh ( 1, 2) ; (3, 4); (5, 6);  lµ d thõa v× vËy ta lo¹i bá c¸c lÖnh nµy. Ta cã m∙ lÖnh : Mov AH ,0 Mov AL, Z Mov BL, 150 Mul BL Add AL, Y Add AL, X Mov A, AL b. Gi¶i thuËt cho sinh m∙ cho biÓu thøc sè häc Vµo : X©u  ω  biÓu thøc sè häc Ra : M∙ lÖnh Assembly  CÊu tróc d÷ liÖu : D÷ liÖu 2 Stack : + 1 Stack  to¸n tö : STT +   1   Stack   to¸n   h¹ng   :  STH vµ 1 Buffer Khëi t¹o : STT vµ STH chøa $ (®¸y) Buffer chøa  ω $ Repeat {Dùa vµo viÖc ph¸t hiÖn tõ c¸n vµ quan  hÖ u tiªn}
  8. - NÕu ký hiÖu t iÕp ®Õn trong Buffer lµ to¸n h¹ng th× dÞch chuyÓn vµo STH - NÕu ký hiÖu t iÕp ®Õn trong Buffer lµ to¸n tö th× ta so s¸nh ví i to¸n tö ë ®Ønh STT. NÕu l í n h¬n th× dÞch chuyÓn vµo STT. Ngîc l ¹ i nÕu nhá h¬n th× : Repeat Gì 2 to¸n h¹ng ë ®Ønh STH Gì 1 to¸n tö ë ®Ønh STT Thùc hiÖn sinh m· cho to¸n tö vµ hai to¸n h¹ng ®ã. §Èy kÕt qu¶ ®ã vµo STH. Unt i l §é u t i ªn ë ®Ønh STT < To¸n tö t iÕp ®Õn trong Buffer dÞch chuyÓn vµo STT - NÕu gÆp ngoÆc t r¸ i th× xem biÓu thøc trong m· cïng cÊp cÇn sinh m· lµ x©u míi cÇn sinh m·, ®Èy ngoÆc tr¸ i vµo STT lµm ®¸y míi . Ví i ký hiÖu kÕt thóc x©u míi lµ ngoÆc ph¶i cïng cÊp. - NÕu Buffer rçng Repeat Gì 2 to¸n h¹ng ë ®Ønh STH Gì 1 to¸n tù ë ®Ønh STT Sinh m· cho to¸n tö vµ 2 to¸n h¹ng ®ã ®Èy kÕt qu¶ vµo STH Unt i l STT= φ ( rçng) Unt i l STT = φ VD : Sinh m· nhËp biÓu thøc ω = “ a + b * ( c + d) “ LËp b¶ng Bíc STT STH Buffer Hµnh ®éng 0 $ $ a+b*(c+ DÞch chyÓn 1 $ $a d)$ STH 2 $+ $a +b*(c+d DÞch chyÓn 3 $+ $ab )$ STT 4 $+* $ab b*(c+d) DÞch chyÓn 5 $+*( $ab $ STH 6 $+*( $abc *(c+d)$ DÞch chyÓn 7 $+*(+ $abc (c+d)$ STT 8 $+*(+ $abcd c+d)$ DÞch chyÓn +d)$ STT
  9. d)$ DÞch chuyÓn c )$ STH DÞch chyÓn+ 9 $+* $abt1 STT DÞch chyÓnd STH $ Gì d,c vµ gì + Mov AL, d Add AL, c 10 $+ $at2 Mov t1,AL Push (t1,STH) Gì T1,b; Gì * $ Mov AH, 0 Mov AL, t1 11 $ $t3 Mov BL,b M BL ul Mov t2, AX $ Push (t2, STH) Gì t2, a; gì + Mov AX t2 , Add AX, a Mov t3, AX Push (t3, STH) Dõng M· thu ® lµ îc Mov AL, d Add AL, c Mov t1, AL Mov AH, 0 Mov AL, t1 Mov BL, b Mul BL Mov t2, AX Mov AX, t2 Add AX, a
  10. Mov t3, AX • Tèi u ho¸ Mov AL, d Add AL, c Mov AH, 0 Mov BL, b Mul BL Add AX, a Mov t3, AX 5. Sinh m∙ cho c¸c cÊu tróc ®iÒu khiÓn RÏ nh¸nh : + RÏ 2 nh¸nh : - i f….. then - i f …then…..else + RÏ nhiÒu nh¸nh : - Case …of …and - Case….of….else…and LÆp : + While … do + Repeat….Unti l + For chuyÓn sang d¹ng While vµ sinh m· theo While Mét sè vÝ dô : VD1: Sinh m· cho ®o¹n ch¬ng tr×nh sau: 1). I f a>b then a: = a-b 2). I f a+b >c then a:= a+c else b:= b+c Gi¶i: 1. Mov AL, a Cmp AL, b JLE Tiep Sub AL, b Mov a, AL Tiep 2. Mov AL,a Add AL,b Cmp AL,c JLE ELSE Mov AL,a Add AL,c Mov a, AL Jmp Tiep ELSE Mov AL,b
  11. Add AL,c Mov b, AL Tiep: VD2: Sinh m· cho ®o¹n ch¬ng tr×nh sau : Case chon of 1: Begin S:= a*b; c:= (a+b)*2; End; 2: Begin S:= 3.14*R*R; c:= 2*3.14*R; End; End; Gi¶i: Mov CL,chon Cmp CL,1 JNE L1 Mov AH,0 Mov AL,a Mov BL,b Nul BL Mov S,AL Mov AL,a Add AL,b Mov BL,2 Mul BL Mov c,AL Jmp Tiep L1: Cmp CL,2 JNE Tiep Mov AL, 3.14 Mov BL,R Mul BL Mul BL Mov S,AL Mov AL, 3.14 Mul BL Mov BL,2
  12. Mul BL Mov C,AL Tiep: Bµi tËp: 1. Sinh m· cho ®o¹n ch¬ng tr×nh sau : tt := csm- csc; Case dtt of 1..100: tt := dtt*5; 101..200: tt := 500 +(dtt- 100)*6.5 Else tt := 2300+(dtt- 200)*9.5 End; 2. While ab do I f a>b then a:= a-b Else b:= b-a; USCLN := a; 3. S1:= 0 ; S2:=0; i :=1; Repeat If i mod 2 = 0 then S2:= S2+i Else S1:= S1+i; I :=i+1; Unti l i>n; 3. KT:=1; I f x
Đồng bộ tài khoản