Модуль (программный или реализации) +------------+ | Среда |<----- Свой модуль определений |------------|<----- Импорт из других | Объявления | модулей определений +------------+ |^ | Импорт || | Видимость +--------+| +-----------+ | +-------+ | v |Экспорт v +------------------+ +-----------+ | Локальный модуль | | Процедура | |------------------| |-----------| | ................ | | ......... | | | | | +------------------+ +-----------+ Рис. 6.3 Env ^ ^ / \ Env Env ^^ ^^ / \ / \ Env Env Env Env Рис. 6.4 +--------------------+ | | | Block | Env<--------+ | | | | | | | Dec_List | | | | | | | | Declaration | | | \ | | | \ | | | Block | | +---------+---------->Env | v | | | +-----> Imp_Set | Mod_Head | Exp_Set<-+ | | \ | | | \ | | Imp_List \ | | | \ | | +--------------+ Export | | | | | | | Import Import |--------+ | | /| Imp_Set | | | | | / | ^ | | | | | From | | | Ident Ident | | | | | | | | | | | | | | v v | |<--Ident | | | ---------------+ | +-------+ | +--------+ | | | | | | | Ident Ident | Ident Ident | | | | | | | v v | | | | -----------+ v v +------------------------------ Рис. 6.5 +---------------------------------------+ | | |---------------------------------------| | s | o | r | t | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | a | | | | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | r | e | a | d | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | i | | | | | | | | | |<---- |---------------------------------------| | | +---------------------------------------+ Рис. 7.1 +------------------------------------- | +------------------ | | +---------- | | | +----- | | | | | | | +--------------+ | | | | v v v v ----------------------------------------------------------+ | s | o | r | t |EOS| a |EOS| r | e | a | d |EOS| i |EOS| ----------------------------------------------------------+ Рис. 7.2 +---+ 0 | | |---| |...| |---| +----------+ +--------+ 9 | --+-->| Idenp |--+-->| | x | |---| +----------+ +--------+ |---| v v |...| Указатели на идентификаторы |---| +------------+ 20 | --+-->| Idenp | x | |---| +------------+ |---| v |...| Указатель на идентификатор |---| +--------+ +--------+ +-------+ 32 | --+-->| | -+-->| | -+-->| | x | |---| +--------+ +--------+ +-------+ |...| v v |---| Указатели на идентификаторы 210 | | Рис. 7.3 |--| +------+ +------+ H----->| -+-x---->| |----->| |-----> |--| | +-->+------+ +------+ | | | | |--| | +------------+ | +------+ | +---| |---+ P-------->+------+ Рис. 7.4. +---------------+ TP --->| | | -+--->Ident +-/----\--------+ / \ v v Left Right Рис. 7.6 A(-2,n+3) B(0,n+2) /\ /\ / \ / \ / \ / \ B(-1,n+2)/ \ / \ /\ \C(n) D(n+1)/ \A(0,n+1) / \ /\ /\ /\ D(n+1)/E(n)\ / \ / \ / \ /\ /\ ---- ---- E(n)/ \ C(n) / \ / \ /\ /\ ---- ---- / \ / \ | (а) ---- ---- Новая вершина (б) Рис. 7.7 A(-2,n+3)) E(0,n+2) /\ / \ / \ / \ / \ / \ B(1,n+2)/\ \C(n) / \ / \ /\B(0,n+1) /\ /\A(1,n+1) D(n)/ \ / \ / \ / \ /\E(-1,n+1)/\ ---- D(n)/ \F(n) G(n-1)/ \C(n) / \ / \ /\ /\ /\ /\ ---- F(n) / \G(n-1) / \ / \ / \ / \ /\ /\ ---- ---- ---- ---- / \ / \ б) ---- ---- | а) Новая вершина Рис. 7.8 A(-2,n+3) E(0,n+2) /\ /\ / \ / \ / \ / \ B(1,n+2) / \ \C(n) B(-1,n+1)/ \A(0,n+1) / \ \ / \ / \ /\ /\ /\ D(n) / E(1,n+1)\ / \ / \ / \ /\ /\ ---- D(n)/F(n-1)\ G(n)/ \C(n) / \ / \ /\ /\ /\ /\ ---- F(n-1)/ \G(n) / \ / \ / \ / \ /\ /\ ---- ---- ---- ---- / \ / \ ---- ---- | Новая вершина а) б) Рис. 7.9 A(-2,2) E(1,0) / /\ B(1,1)/ / \ \ / \ \ B(0,0) A(0,0) E(0,0) | Новая вершина Рис. 7.10 +------+ +------+ +-------+ -------->| | -+----->| | -+---->| | | +------+ +------+ +-------+ T1 T2 Tn Рис. 7.11 PROCEDURE P1; +----+ VAR V1; P2 | V2 | PROCEDURE P2; |----| VAR V2; |....| BEGIN P2; |----| V1:=... P2 | V2 | V2:=... |----| END P2; P1 | V1 | BEGIN P2; +----+ END P1; Рис. 8.1 Рис. 8.2 Минимальный адрес +-----------------+<---------+ | Сохраненные | | | регистры | | |-----------------| | Текущий | Локальные |<--+ |Область статический |-----------------| |Disp |последней уровень +--| Предыдущий BP |<--+- BP |вызванной | |-----------------| | |процедуры | | Точка возврата | |Disp | | |-----------------| | | | | Факт. параметры |<--+ | ||-+-----------------+-|<-------+ | | Сохраненные | | | регистры | | |-----------------| LP +-+--| Предыдущий LP |<----+D | | |-----------------| |e Предыдущий | | | Локальные | |l статический| | | | |t уровень | | |-----------------| |a | +->| Предыдущий BP |-----+ v +-----------------+ ................. Максимальный адрес Рис. 8.3 +---------------+ |Точка возврата |<---SP |---------------| |Факт. параметры| |+---------------+--| |Сохраненные | |регистры | |---------------| LP +--|Предыдущий LP |<------- | |---------------| Предыдущий | |Локальные | статический| | | уровень | |---------------| BP | |Предыдущий BP |<---- v |---------------| |...............| Рис. 8.4 +------------------+ | Точка возврата | |------------------| | Факт. параметры | |--+------------------+--| | Сохраненные | | регистры | |------------------| LP +---| Предыдущий LP |<---+ | |------------------| D | Предыдущий | | | e | статический | | Локальные | l | уровень | | | t | | |------------------| a | | | Предыдущий BP |<---+ v |------------------| | ................ | Рис. 8.5 +-----------------+<--SP Текущий | Локальные | уровень |-----------------| | Предыдущий BP |<--BP |-----------------| +------------------+ | Точка возврата | | Точка возврата |<---SP |-----------------| |------------------| | Факт. параметры | | Факт. параметры | |-----------------------| +------------------+ ................. .................. Рис. 8.6 Рис. 8.7 Минимальный адрес <------+ | Сохраненные | | Область | регистры | | последней |------------------| | вызванной Текущий | Локальные | | процедуры статический |------------------| | уровень +--| Предыдущий BP |<-- BP <-+ | |------------------| | | | | Точка возврата | | | | |------------------| | | | | Факт. параметры | | | | |------------------|<------+ | DISPLAY[i] | | Сохраненные | | ---------+ | | регистры | +------* | | |------------------| ---------+ | | предыдущий | | | DISPLAY[i] | | |------------------| Предыдущий | | Локальные | статический | | | уровень | |------------------| +->| Предыдущий BP | |------------------| |..................| Рис. 8.8 |----------------------|<-------------------------+ | Локальные | Область активации | |----------------| текущей процедуры | | Регистры | | |----------------| BP | +-----| Предыдущий BP |<----- | | |----------------| BP предыдущего статического | | | x---+---------> уровня | | | Дисплей .......| BP 1-го статического уровня | | | x---+---------> | | |----------------| | | | Точка возврата | | | |----------------| | | | Фактические | | | |--+----------------+--|<-------------------------+ | | Локальные | | |----------------| | | Регистры | | |----------------| +---->| Предыдущий BP | |----------------| | Дисплей | |----------------| | Точка возврата | |----------------| |--+ Фактические +--| Рис. 8.9. DeclPart | Size <----------+ /|\ | / | \ | / | \ | / | \ | / | \ | Decl Decl Decl | Disp----->Disp--------->Disp + Size + Size + Size ^ ^ ^ | | | Рис. 8.10 VarTail | Disp---------------+ | | / \ | / \ | / \ | +--------Number VarTail | Disp <--+ | ^ | Table | | |-------| | +----------->| Disp |----------------+ |-------| Рис. 8.11 Тип адресации VarTail левой части: IndPre or Direct (IndPost or Abs) or IndexReg=NO ((Direct or IndPre) & (IndexReg<>NO)) --------------------------------------------------------- ElSize<3>= | AddrDisp<4>:= |AddrDisp<4>:= 1,2,4,8 | AddrDisp<0> |-Left<2>*ElSize<3> AddrMode<3>=D | -Left<2>*ElSize<3> |AddrMode<4>:=IndPost | Addreg<4>:=Addreg<0>|Addreg<4>:= | IndexReg<4>:= |if Addreg<0> рабочий | Addreg<3> |then Addreg<0> | AddrMode<4>:=IndPost|else GetAddr | Scale<4>:=ElSize<3> |IndexReg<4>:= | | Addreg<3> | |Scale<4>:=ElSize<3> | |------------------- | |LEA Address<0>, | | Address<4> --------------------------------------------------------- --------------------------------------------------------- ElSize<3> | AddrDisp<4>:= | AddrDisp<4>:= <>1,2,4,8 | AddrDIP<0>- | -Left<2>*ElSize<3> AddrMode<3>=D| Left<2>*ElSize<3> | AddrMode<4>:=IndPost | Addreg<4>:=Addreg<0>| Addreg<4>:= | IndexReg<4>:= | if Addreg<0> рабочий | Addreg<3> | then Addreg<0> | Scale<4>:=1 | else GetAddr | AddrMode<4>:=IndPost| IndexReg<4>:= |---------------------| Addreg<3> | MUL ElSize<3>, | Scale:=1 | Addreg<3> |------------------- | | LEA Address<0>, | | Address<4> | | MUL ElSize<4>, | | IndexReg<4> --------------------------------------------------------- --------------------------------------------------------- ElSize<3>= |AddrDisp<4>:= | AddrDisp<4>:= 1,2,4,8 |AddrDisp<0>- | -Left<2>*ElSize<3> AddrMode<3><>D|Left<2>*ElSize<3> | AddrMode<4>:=IndPost |Addreg<4>:=Addreg<0>| Addreg<4>:= |IndexReg<4>:=GetFree| if Addreg<0> рабочий |AddrMode<4>:=IndPost| then Addreg<0> |Scale<4>:=ElSize<3> | else GetAddr |--------------------| IndexReg<4>:=GetFree |MOVE Address<3>, | Scale<4>:=ElSize<3> | IndexReg<4> |------------------- | | LEA Address<0>, | | Address<4> | | MOVE Address<3>, | | IndexReg<4> -------------------------------------------------------- --------------------------------------------------------- ElSize<3> |AddrDisp<4>:= | AddrDisp<4>:= <>1,2,4,8 |AddrDisp<0>- | -Left<2>*ElSize AddrMode<3><>D|Left<2>*ElSize<3> | AddrMode<4>:=IndPre |Addreg<4>:=Addreg<0>| Addreg<4>:= |IndexReg<4>:=GetFree| if Addreg<0> рабочий | AddrMode<4>:=IndPre| then Addreg<0> | Scale<4>:=ElSize<3>| else GetAddr |--------------------| IndexReg<4>:=GetFree |MOVE Address<3>, | Scale<4>:=1 | IndexReg<4> |---------------- | MUL ElSize<3>, | LEA Address<0>, | IndexReg<4> | Address<4> | | MOVE Address<3>, | | IndexReg<4> | | MUL ElSize<3>, | | IndexReg<4> -------------------------------------------------------- Правый операнд А2 R V +-----------------------------+ Левый | R | ADD A1,A2 | ADD A2,A1 | операнд |-----+-----------+-----------| A1 | V | ADD A1,A2 | MOVE A1,R | | | | ADD A2,R | +-----------------------------+ Рис. 8.12 | / \ R1 /\ \ -- /\ R2 /\ \ -- /\ Rn /\ \ -- \ /\LR L/\/\R ---- Рис. 8.13 | | R R / \ / \ | | / \ / \ ll/ \lr ll/ \lr 0 /\ /\ 1 / \ / \ / \ / \ R+1 R R R+1 ---- ---- а) б) а) ll=lr Рис. 8.14 Рис. 8.15 R R R R | | | | / \ / \ / \ / \ / \R R / \ R/ \R+1 R+1/ \R X /\ /\ X /\ /\ /\ /\ (0) -- -- (1) -- -- -- -- а) б) а) б) Рис. 8.16 Рис. 8.17 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. | ^ | | Label / \ / \ / \ Left=0 /Label-->Left\ /\ /\ Reg<0>:=if (Left<0>=Label<0>) / \ / \ &(Left<0>#0) / \ / \ then Label<0>+1 / \ /\ /\ else Label<0> / \ / \ / \ ---------- ---- ---- Рис. 8.19. TrueLab TrueLab FalseLab\ FalseLab\ / | \\ /| \\ / / \ \\ // \ \\ / / & \ \\ // V \ \\ / / \ \\ // \ \\ FalseLab / \ \TrueLab TrueLab/ \ \TrueLab / \FalseLab / \ FalseLab TrueLab<-------NodeLabel FalseLab<---NodeLabel Рис. 8.20. F V ( F & T & T ) V T | FalseLab=False 1 TrueLab=True / TrueLab=True / V \ FalseLab=2 / \ FalseLab=False F 2 TrueLab=True / \ TrueLab=True / V \ FalseLab=3 / \ / \ 4 3 / \ | TrueLab=5 / & \ T FalseLab=3 / \ TrueLab=True / \ FalseLab=3 F 5 / \ TrueLab=6 / & \ 1: GOTO 2 FalseLab=3 / \ TrueLab=True 2: / \ FalseLab=3 4: GOTO 3 T 6 5: GOTO 6 | 6: GOTO True T 3: GOTO True Рис. 8.21 Рис. 8.22 | FalseLab0 | TrueLab0 / \ / & \ FalseLab1=FalseLab0 / \ FalseLab2=FalseLab0 TrueLab1=NodeLab2 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- 147 | FalseLab0 | TrueLab0 / \ / V \ FalseLab1=NodeLab2 / \ FalseLab2=FalseLab0 TrueLab1=TruLab0 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- Рис. 8.23 false | true | false | true | or or and and /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ true false true true false false false true true | false | | | not not | | | | false true Рис. 8.24 |<-----| op |<-------| / \ / \ / \ / \ +---->/\ /\<-----+ +-----/\ /\---+ | / \ / \ | | / \ / \ | | ---- ---- | | ---- ---- | | +-+---------------+ +--------------------+ Рис.8.27 |<------------|<-------------|<---------| | Op / \ / \ / \ OpTable / \ / \ / \ /\ /\ /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ ---- ---- ---- ---- ---- ---- Рис. 8.28 := | ------------- / \ + + / \ / \ / \ / \ const(a) const(x) @ const(5) | | + / \ / \ + @ / \ | / \ | const(b) const(y) + / \ / \ const(i) const(z) Рис. 8.29 +------------------------------------------------------+ |Но-| Образец |Машинная команда |Стоимость| |мер| |Правило грамматики| | |---+---------------------+----------------------------| | 1 | const(c) | MOV #c,Ri | 2 | | | | Reg->Const | | |---+---------------------+-----------------------+----| | 2 | := | MOV Rj,c(Ri) | 4 | | | / \ | | | | | / \ | | | | | + reg(j) | | | | | / \ | Stat->':=' '+' Reg | | | |reg(i) const(c) | Const Reg | | |---+---------------------+-----------------------+----| | 3 | @ | MOV c(Rj),Ri | 4 | | | | | | | | | + | | | | | / \ | | | | | / \ |Contents -> '@' '+' Reg| | | | reg(j) const(c) | Const | | |---+---------------------+-----------------------+----| | 4 | + | ADD #c,Ri | 3 | | | / \ | | | | | / \ | | | | | reg(i) const(c) |Reg -> '+' Reg Const | | |---+---------------------+-----------------------+----| | 5 | + | ADD Rj,Ri | 2 | | | / \ | | | | | / \ | | | | | reg(i) reg(j) | Reg -> '+' Reg Reg | | |---+---------------------+-----------------------+----| | 6 | + | ADD c(Rj),Ri | 4 | | | / \ | | | | | / \ | | | | |reg(i) @ | | | | | | | Reg -> '+' Reg '@' | | | | + | '+' Reg Const | | | | / \ | | | | | reg(j) const(c) | | | |---+---------------------+-----------------------+----| | 7 | @ | MOV (R),R | 2 | | | | | | | | | Reg | Reg -> Contents | | +------------------------------------------------------+ Рис. 8.30 ----------[stat]---------------------------------- |2 := | | / \ | | + \ | | / \ \ | |reg(Ra) const(x) \ | |const(a) \ | | ------------------[reg(Rb)]------------------ | | | 4 + | | | | / \ | | | | / const(5) | | | | / | | | | ---------------[reg(Rb)]------------------ | | | | | 7 @ | | | | | | | | | | | | | -------------[reg(Rb)]---------------- | | | | | | |6 + | | | | | | | | / \ | | | | | | | | / \ | | | | | | | | ------[reg(Rb)]---- \ | | | | | | | | |4 + | @ | | | | | | | | | / \ | | | | | | | | | | | / \ | | | | | | | | | | | reg(Rb) const(y)| + | | | | | | | | | const(b) | / \ | | | | | | | | ------------------- / \ | | | | | | | | / \ | | | | | | | | reg(Ri) const(z) | | | | | | | | const(i) | | | | | | | -------------------------------------- | | | | | ------------------------------------------ | | | ---------------------------------------------- | -------------------------------------------------- Рис. 8.31 r[i]={A->aiV1...Vm} | /\ | / \ | 1 /\ /\m | / \ / \ |---------|----------------|-----| ai l[i] Рис. 8.32 +-----------------------------+ |Операция|Длина| Правила | | | | (стоимость) | |--------+-----+--------------| | := | 14 | 2(22) | | + | 2 | 4(5) 5(6) | | a | 0 | 1(2) | | x | 0 | 1(2) | | + | 9 | 4(16) 5(17)| | @ | 8 | 7(13) | | + | 7 | 5(15) 6(11)| | + | 2 | 4(5) 5(6) | | b | 0 | 1(2) | | y | 0 | 1(2) | | @ | 3 | 3(6) 7(7) | | + | 2 | 4(5) 5(6) | | i | 0 | 1(2) | | z | 0 | 1(2) | | 5 | 0 | 1(2) | +-----------------------------+ Рис. 8.33 M=<':=' '+' R C R> := P= | ------------- M=<<'+' R C>, / \ <'+' R R>, + + <'+' R <'@' '+' R C>> / \ / \P= / \ / \ const(a) const(x) @ const(5) M= M=> '+' R C>> | P= P= P= | | |M=<<'@' '+' R C, M=<'+' R C>, | <'@' R>> <'+' R R>, |P= <'+' R <'@' '+' R C>>| P= + / \ / \ M=<<'+' R C> / \ M=<<'@' '+' R C, <'+' R R> + @ <'@' R>> <'+' R <'@' / \ | P= '+' R C>> / \ | P= / \ | const(b) const(y) | M=<<'+' R C>, M= M=, P= <'@''+'R C>>+ <'+' R <'@' '+' R C>> P= / \P= / \ const(i) const(z) M= M=> P= P= Рис. 8.34 +---+ | A |<---------------+ +---+ | | | +------------------------------+ | | | | | | v v v v | +---+ +---+ +---+ +---+ +---+ | +---+ ->| B |-->| X |-->| X |-->...-->| X |-->| X |--->| C |- +---+ +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ ^ | | | | | +-------------------------------------+ Рис. 9.1