SETHI (1131564)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

8.6. � á¯à¥¤¥«¥­¨¥ ॣ¨áâ஢ ¯à¨ ¢ëç¨á«¥­¨¨ à¨ä¬¥â¨ç¥áª¨å ¢ëà ¦¥­¨©

Ž¤­®© ¨§ ¢ ¦­¥©è¨å § ¤ ç ¯à¨ £¥­¥à 樨 ª®¤ ï¥âáï à á¯à¥¤¥«¥­¨¥ ॣ¨áâ஢. � áᬮâਬ å®à®è® ¨§¢¥áâ­ãî â¥å­¨ªã à á¯à¥¤¥«¥­¨ï ॣ¨áâ஢ ¯à¨ âà ­á«ï樨 à¨ä¬¥â¨ç¥áª¨å ¢ëà ¦¥­¨©, ­ §ë¢ ¥¬ãî «£®à¨â¬®¬ ‘¥â¨-“«ì¬ ­ .

�ãáâì á¨á⥬ ª®¬ ­¤ ¬ è¨­ë ¨¬¥¥â ­¥®£à ­¨ç¥­­®¥ ç¨á«® ã­¨¢¥àá «ì­ëå ॣ¨áâ஢, ¢ ª®â®àëå ¢ë¯®«­ïîâáï à¨ä¬¥â¨ç¥áª¨¥ ª®¬ ­¤ë. � áᬮâਬ, ª ª ¬®¦­® ᣥ­¥à¨à®¢ âì ª®¤, ¨á¯®«ì§ãï ¤«ï ¤ ­­®£® à¨ä¬¥â¨ç¥áª®£® ¢ëà ¦¥­¨ï ¬¨­¨¬ «ì­®¥ ç¨á«® ॣ¨áâ஢.

|

/ \

R1 /\ \

-- /\

R2 /\ \

-- /\

Rn /\ \

-- \

/\LR

L/\/\R

----

�¨á. 8.13

�।¯®«®¦¨¬ á­ ç « , çâ® à á¯à¥¤¥«¥­¨¥ ॣ¨áâ஢ ®áãé¥á⢫ï¥âáï ¯® ¯à®á⥩襩 á奬¥ á«¥¢ -­ ¯à ¢®, ª ª ¨§®¡à ¦¥­® ­ à¨á. 8.13. ’®£¤ ª ¬®¬¥­âã £¥­¥à 樨 ª®¤ ¤«ï ¯®¤¤¥à¥¢ LR § ­ïâ® n ॣ¨áâ஢. �ãáâì ¯®¤¤¥à¥¢® L âॡã¥â n_l ॣ¨áâ஢, ¯®¤¤¥à¥¢® R - nr ॣ¨áâ஢. …᫨ n_l=n_r, â® ¯à¨ ¢ëç¨á«¥­¨¨ L ¡ã¤¥â ¨á¯®«ì§®¢ ­® nl ॣ¨áâ஢ ¨ ¯®¤ १ã«ìâ ⠡㤥⠧ ­ïâ n+1-© ॣ¨áâà. …é¥ n_r (=n_l) ॣ¨áâ஢ ¡ã¤¥â ¨á¯®«ì§®¢ ­® ¯à¨ ¢ëç¨á«¥­¨¨ R. ’ ª¨¬ ®¡à §®¬, ®¡é¥¥ ç¨á«® ¨á¯®«ì§®¢ ­­ëå ॣ¨áâ஢ ¡ã¤¥â à ¢­® n+n_l+1.

…᫨ n_l>n_r, â® ¯à¨ ¢ëç¨á«¥­¨¨ L ¡ã¤¥â ¨á¯®«ì§®¢ ­® n_l ॣ¨áâ஢. �ਠ¢ëç¨á«¥­¨¨ R ¡ã¤¥â ¨á¯®«ì§®¢ ­® n_r<n_l ॣ¨áâ஢, ¨ ¢á¥£® ¡ã¤¥â ¨á¯®«ì§®¢ ­® ­¥ ¡®«¥¥ 祬 n+n_l ॣ¨áâ஢.

…᫨ n_l<n_r, â® ¯®á«¥ ¢ëç¨á«¥­¨ï L ¯®¤ १ã«ìâ ⠡㤥⠧ ­ïâ ®¤¨­ ॣ¨áâà (¯à¥¤¯®«®¦¨¬ n+1-©) ¨ n_r ॣ¨áâ஢ ¡ã¤¥â ¨á¯®«ì§®¢ ­® ¤«ï ¢ëç¨á«¥­¨ï R. ‚ᥣ® ¡ã¤¥â ¨á¯®«ì§®¢ ­® n+n_r+1 ॣ¨áâ஢.

‚¨¤­®, çâ® ¤«ï ¤¥à¥¢ì¥¢, ᮢ¯ ¤ îé¨å á â®ç­®áâìî ¤® ¯®à浪 ¯®â®¬ª®¢ ª ¦¤®© ¢¥à設ë, ¬¨­¨¬ «ì­®¥ ç¨á«® ॣ¨áâ஢ ¯à¨ à á¯à¥¤¥«¥­¨¨ ¨å á«¥¢ -­ ¯à ¢® ¤®á⨣ ¥âáï ­ ¤¥à¥¢¥, ã ª®â®à®£® ¢ ª ¦¤®© ¢¥à設¥ á«¥¢ à ᯮ«®¦¥­® ¡®«¥¥ "á«®¦­®¥" ¯®¤¤¥à¥¢®, âॡãî饥 ¡®«ì襣® ç¨á« ॣ¨áâ஢.

’ ª¨¬ ®¡à §®¬, ¥á«¨ ¤¥à¥¢® â ª®¢®, çâ® ¢ ª ¦¤®© ¢­ãâ७­¥© ¢¥à設¥ ¯à ¢®¥ ¯®¤¤¥à¥¢® âॡã¥â ¬¥­ì襣® ç¨á« ॣ¨áâ஢, 祬 «¥¢®¥, â®, ®¡å®¤ï ¤¥à¥¢® á«¥¢ ­ ¯à ¢®, ¬®¦­® ®¯â¨¬ «ì­® à á¯à¥¤¥«¨âì ॣ¨áâàë.

�¥§ ¯¥à¥áâனª¨ ¤¥à¥¢ íâ® ®§­ ç ¥â, çâ® ¥á«¨ ¢ ­¥ª®â®à®© ¢¥à設¥ ¤¥à¥¢ á¯à ¢ à ᯮ«®¦¥­® ¡®«¥¥ á«®¦­®¥ ¯®¤¤¥à¥¢®, â® á­ ç « ᣥ­¥à¨à㥬 ª®¤ ¤«ï ­¥£®, § ⥬ 㦥 ¤«ï «¥¢®£® ¯®¤¤¥à¥¢ .

€«£®à¨â¬ à ¡®â ¥â á«¥¤ãî騬 ®¡à §®¬. ‘­ ç « ®áãé¥á⢫ï¥âáï à §¬¥âª ᨭ⠪á¨ç¥áª®£® ¤¥à¥¢ ¯® á«¥¤ãî騬 ¯à ¢¨« ¬.

�à ¢¨« à §¬¥âª¨:

1) ¥á«¨ ¢¥à設 - ¯à ¢ë© «¨áâ ¨«¨ ¤¥à¥¢® á®á⮨⠨§ ¥¤¨­á⢥­­®© ¢¥à設ë, ¯®¬¥ç ¥¬ íâã ¢¥à設ã ç¨á«®¬ 1, ¥á«¨ ¢¥à設 - «¥¢ë© «¨áâ, ¯®¬¥ç ¥¬ ¥¥ 0 (à¨á. 8.14).

| | R R

/ \ / \ | |

/ \ / \ ll/ \lr ll/ \lr

0 /\ /\ 1 / \ / \

/ \ / \ R+1 R R R+1

---- ----

) ¡) ) ll<lr ¡) ll>=lr

�¨á. 8.14 �¨á. 8.15

2) ¥á«¨ ¢¥à設 ¨¬¥¥â ¯àï¬ëå ¯®â®¬ª®¢ á ¬¥âª ¬¨ l1 ¨ l2, â® ¢ ª ç¥á⢥ ¬¥âª¨ í⮩ ¢¥àè¨­ë ¢ë¡¨à ¥¬ ¡®«ì襥 ¨§ ç¨á¥« l1 ¨«¨ l2 «¨¡® ç¨á«® l1+1, ¥á«¨ l1=l2.

�â à §¬¥âª ¯®§¢®«ï¥â ®¯à¥¤¥«¨âì, ª ª®¥ ¨§ ¯®¤¤¥à¥¢ì¥¢ âॡã¥â ¡®«ì襣® ª®«¨ç¥á⢠ॣ¨áâ஢ ¤«ï ᢮¥£® ¢ëç¨á«¥­¨ï.

‡ ⥬ ®áãé¥á⢫ï¥âáï à á¯à¥¤¥«¥­¨¥ ॣ¨áâ஢ ¤«ï १ã«ìâ ⮢ ®¯¥à 権.

�à ¢¨« à á¯à¥¤¥«¥­¨ï ॣ¨áâ஢.

1) Š®à­î ­ §­ ç ¥âáï ¯¥à¢ë© ॣ¨áâà.

2) …᫨ ¬¥âª «¥¢®£® ¯®â®¬ª ¬¥­ìè¥ ¬¥âª¨ ¯à ¢®£®, â® «¥¢®¬ã ¯®â®¬ªã ­ §­ ç ¥âáï ॣ¨áâà ­ ¥¤¨­¨æã ¡®«ì訩, 祬 ¯à¥¤ªã, ¯à ¢®¬ã - á ⥬ ¦¥ ­®¬¥à®¬ (á­ ç « ¢ëç¨á«ï¥âáï ¯à ¢®¥ ¯®¤¤¥à¥¢® ¨ ¥£® १ã«ìâ â ¯®¬¥é ¥âáï ¢ ॣ¨áâà R). …᫨ ¦¥ ¬¥âª «¥¢®£® ¯®â®¬ª ¡®«ìè¥ ¨«¨ à ¢­ ¬¥âª¥ ¯à ¢®£® ¯®â®¬ª , â® ­ ®¡®à®â, á­ ç « ¢ëç¨á«ï¥âáï «¥¢®¥ ¯®¤¤¥à¥¢® ¨ ¥£® १ã«ìâ â ¯®¬¥é ¥âáï ¢ ॣ¨áâà R (à¨á. 8.15). �®á«¥ í⮣® ä®à¬¨àã¥âáï ª®¤ ¯® á«¥¤ãî騬 ¯à ¢¨« ¬.

�à ¢¨« £¥­¥à 樨 ª®¤ :

1) ¥á«¨ ¢¥à設 - ¯à ¢ë© «¨áâ á ¬¥âª®© 1, â® ¥© ᮮ⢥âáâ¢ã¥â ª®¤ LOAD X,R, £¤¥ R - ॣ¨áâà, ­ §­ 祭­ë© í⮩ ¢¥à設¥, X - ¤à¥á ¯¥à¥¬¥­­®©, á¢ï§ ­­®© á ¢¥à設®© (à¨á. 8.16.¡);

2) ¥á«¨ ¢¥à設 ¢­ãâ७­ïï ¨ ¥¥ «¥¢ë© ¯®â®¬®ª - «¨áâ á ¬¥âª®© 0, â® ¥© ᮮ⢥âáâ¢ã¥â ª®¤

Š®¤ ¯à ¢®£® ¯®¤¤¥à¥¢

Op X,R

£¤¥ á­®¢ R - ॣ¨áâà, ­ §­ 祭­ë© í⮩ ¢¥à設¥, X - ¤à¥á ¯¥à¥¬¥­­®©, á¢ï§ ­­®© á ¢¥à設®©, Op - ®¯¥à æ¨ï, ¯à¨¬¥­¥­­ ï ¢ ¢¥à設¥ (à¨á. 8.16. );

3) ¥á«¨ ­¥¯®á।á⢥­­ë¥ ¯®â®¬ª¨ ¢¥àè¨­ë ­¥ «¨áâìï ¨ ¬¥âª ¯à ¢®© ¢¥àè¨­ë ¡®«ìè¥ ¬¥âª¨ «¥¢®©, â® ¢¥à設¥ ᮮ⢥âáâ¢ã¥â ª®¤

Š®¤ ¯à ¢®£® ¯®¤¤¥à¥¢

Š®¤ «¥¢®£® ¯®¤¤¥à¥¢

Op R+1,R

£¤¥ R - ॣ¨áâà, ­ §­ 祭­ë© ¢­ãâ७­¥© ¢¥à設¥, ¨ ®¯¥à æ¨ï Op, ¢®®¡é¥ £®¢®àï, ­¥ ª®¬¬ãâ ⨢­ ï (à¨á. 8.17 ¡)).

R R R R

| | | |

/ \ / \ / \ / \

/ \R R / \ R/ \R+1 R+1/ \R

X /\ /\ X /\ /\ /\ /\

(0) -- -- (1) -- -- -- --

) ¡) ) ¡)

�¨á. 8.16 �¨á. 8.17

…᫨ ¬¥âª ¯à ¢®© ¢¥àè¨­ë ¬¥­ìè¥ ¨«¨ à ¢­ ¬¥âª¥ «¥¢®© ¢¥à設ë, â® ¢¥à設¥ ᮮ⢥âáâ¢ã¥â ª®¤

Š®¤ «¥¢®£® ¯®¤¤¥à¥¢

Š®¤ ¯à ¢®£® ¯®¤¤¥à¥¢

Op R,R+1

MOVE R+1,R

�®á«¥¤­ïï ª®¬ ­¤ £¥­¥à¨àã¥âáï ¤«ï ⮣®, çâ®¡ë ¯®«ãç¨âì १ã«ìâ â ¢ ­ã¦­®¬ ॣ¨áâॠ(¢ á«ãç ¥ ª®¬¬ãâ ⨢­®© ®¯¥à 樨 ®¯¥à ­¤ë ®¯¥à 樨 ¬®¦­® ¯®¬¥­ïâì ¬¥áâ ¬¨ ¨ ¨§¡¥¦ âì ¤®¯®«­¨â¥«ì­®© ¯¥à¥á뫪¨)(à¨á. 8.17 )).

� áᬮâਬ âਡãâ­ãî £à ¬¬ ⨪ã, ॠ«¨§ãîéãî í⨠¯à ¢¨« £¥­¥à 樨 ª®¤ . ‚ í⮩ âਡãâ­®© £à ¬¬ ⨪¥ £¥­¥à æ¨ï ª®¤ ¯à®¨á室¨â ­¥ ­¥¯®á।á⢥­­® ¢ ¯à®æ¥áᥠ®¡å®¤ ¤¥à¥¢ , ª ª à ­ìè¥, ¨§-§ ­¥®¡å®¤¨¬®á⨠¯¥à¥áâ ¢«ïâì ¯®¤¤¥à¥¢ìï ª®¤ áâநâáï ¢ ¢¨¤¥ ⥪áâ á ¯®¬®éìî ®¯¥à 樨 ª®­ª ⥭ 樨. �à ªâ¨ç¥áª¨, ª®­¥ç­®, íâ® ­¥æ¥«¥á®®¡à §­®: à §ã¬­¥¥ ã¯à ¢«ïâì ®¡å®¤®¬ ¤¥à¥¢ ­¥¯®á।á⢥­­®, ®¤­ ª® ¤«ï ¯à®áâ®âë ¬ë ¡ã¤¥¬ ¯®«ì§®¢ âìáï ª®­ª ⥭ 樥©.

RULE

Expr ::= IntExpr

SEMANTICS

Reg<1>:=1; Left<1>:=true.

RULE

IntExpr ::= Term AddOp IntExpr

SEMANTICS

Left<1>:=true; Left<3>:=false;

Label<0>:=if Label<1>=Label<3>

then Label<1>+1

else Max(Label<1>,Label<3>);

Reg<1>:=if Label<1> < Label<3>

then Reg<0>+1

else Reg<0>;

Reg<3>:=if Label<1> < Label<3>

then Reg<0>

else Reg<0>+1;

Code<0>:=if Label<1>=0

then Code<3>||Code<2>

||Code<3>||","||Reg<0>

else if Label<1> < Label<3>

then Code<3>||Code<1>||Code<2>||

Reg<0>+1||","||

Reg<0>

else Code<1>||Code<3>||Code<2>||

Reg<0>||","||Reg<0>+1

||"MOVE"||Reg<0>+1

||","||Reg<0>.

IntExpr ::= Term =>

Left<1>:=Left<0>; Code<0>:=Code<1>;

Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE

Term::= Factor MultOp Term

SEMANTICS

Left<1>:=true; Left<3>:=false;

Label<0>:=if Label<1>=Label<3>

then Label<1>+1

else Max(Label<1>,Label<3>);

Reg<1>:=if Label<1> < Label<3>

then Reg<0>+1

else Reg<0>;

Reg<3>:=if Label<1> < Label<3>

then Reg<0>

else Reg<0>+1;

Code<0>:=if Label<1>=0

then Code<3>||Code<2>

||Code<3>||",""||Reg<0>

else if Label<1> < Label<3>

then Code<3>||Code<1>||Code<2>||

Reg<0>+1||","||

Reg<0>

else Code<1>||Code<3>||Code<2>||

Reg<0>||","||Reg<0>+1

||"MOVE"||Reg<0>+1

||","||Reg<0>.

RULE

Term ::= Factor

SEMANTICS

Left<1>:=Left<0>; Code<0>:=Code<1>;

Label<0>:=Label<1>; Reg<1>:=Reg<0>.

RULE

Factor ::= Ident

SEMANTICS

Label<0>:=if Left<0> then 0 else 1;

Code<0>:=if not Left<0> then

"LOAD"||Reg<0>||","||Val<1>

else Val<1>.

RULE

Factor ::= ( IntExpr )

SEMANTICS

Left<2>:=Left<0>; Code<0>:=Code<2>;

Label<0>:=Label<2>; Reg<2>:=Reg<0>.

RULE

AddOp ::= '+'

SEMANTICS

Code<0>:="ADD".

RULE

AddOp ::= '-'

Code<0>:="SUB".

RULE

MultOp ::= '*'

SEMANTICS

Code<0>:="MUL".

RULE

MultOp ::= '/'

SEMANTICS

Code<0>:="DIV".

Expr

|

IntExpr

/ | \ Left=true

/ | \Label=2

/ | \Reg=1

Term AddOp IntExpr

/ | \ Left=true| / | \ Left=false

/ | \Label=1 | / | \Label=2

/ | \Reg=2 | / | \

/ | \ + / | \

Factor MultOp Term Factor MultOp Term

|Left=true | |Left=false |Left=true | |Left=false

|Label=0 | |Label=1 |Label=0 | |Label=1

|Reg=2 * |Reg=3 |Reg=1 * |Reg=1

Ident Ident Ident Factor

A B C | Left=false

| Label=1

----------------- Reg=1

/|\

( | )

IntExpr

/ | \ Left=false

/ | \Label=1

/ | \Reg=1

Term AddOp IntExpr

|Left=true | | Left=false

|Label=0 | | Label=1

|Reg=2 + | Reg=1

Factor Term

|Left=true | Left=false

|Label=0 | Label=1

|Reg=2 | Reg=1

Ident Factor

D | Left=false

| Label=1

| Reg=1

Ident

E

�¨á. 8.18.

€âਡãâ¨à®¢ ­­®¥ ¤¥à¥¢® ¤«ï ¢ëà ¦¥­¨ï A*B+C*(D+E) ¯à¨¢¥¤¥­® ­ à¨á. 8.18. �ਠí⮬ ¡ã¤¥â ᣥ­¥à¨à®¢ ­ á«¥¤ãî騩 ª®¤:

LOAD E,R1

ADD D,R1

MUL C,R1

LOAD B,R2

MUL A,R2

ADD R2,R1

�ਢ¥¤¥­­ ï âਡãâ­ ï á奬 âॡã¥â ¤¢ãå ¯à®å®¤®¢ ¯® ¤¥à¥¢ã ¢ëà ¦¥­¨ï. � áᬮâਬ ⥯¥àì ¤àã£ãî âਡãâ­ãî á奬ã, ¢ ª®â®à®© ¤®áâ â®ç­® ®¤­®£® ®¡å®¤ ¤«ï £¥­¥à æ¨ï ¯à®£à ¬¬ë ¤«ï ¢ëà ¦¥­¨© á ®¯â¨¬ «ì­ë¬ à á¯à¥¤¥«¥­¨¥¬ ॣ¨áâ஢ [9].

�ãáâì ¬ë ¯à®¨§¢¥«¨ à §¬¥âªã ¤¥à¥¢ à §¡®à â ª ¦¥, ª ª ¨ ¢ ¯à¥¤ë¤ã饬 «£®à¨â¬¥. � §­ 祭¨¥ ॣ¨áâ஢ ¡ã¤¥¬ ¯à®¨§¢®¤¨âì ¢ ᮮ⢥âá⢨¨ á® á奬®© à¨á. 8.19.

‹¥¢®¬ã ¯®â®¬ªã ¢á¥£¤ ­ §­ ç ¥âáï ॣ¨áâà, à ¢­ë© ¥£® ¬¥âª¥, ¯à ¢®¬ã - ¥£® ¬¥âª¥, ¥á«¨ ®­ ­¥ à ¢­ ¬¥âª¥ ¥£® «¥¢®£® ¡à â , ¨ ¬¥âª¥ +1, ¥á«¨ ¬¥âª¨ à ¢­ë. �®áª®«ìªã ¡®«¥¥ á«®¦­®¥ ¯®¤¤¥à¥¢® ¢á¥£¤ ¢ëç¨á«ï¥âáï à ­ìè¥ ¡®«¥¥ ¯à®á⮣®, ¥£® ॣ¨áâà १ã«ìâ â ¨¬¥¥â ¡®«ì訩 ­®¬¥à, 祬 «î¡®© ॣ¨áâà, ¨á¯®«ì§ã¥¬ë© ¯à¨ ¢ëç¨á«¥­¨¨ ¡®«¥¥ ¯à®á⮣® ¯®¤¤¥à¥¢ , çâ® £ à ­â¨àã¥â ¯à ¢¨«ì­®áâì ¨á¯®«ì§®¢ ­¨ï ॣ¨áâ஢.

| ^

| | Label

/ \

/ \

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)