RevisionCFG

+

Synthesized

Attribute+Restricted

Inherited

AttributeTranslation

SchemeL-Attributed

DefinitionrepresentTop

DownBottom

UpAttribute

calculatedby

its

childrenAttributescalculated

byparent

and

siblings1/33AttributeSynthesizedEliminating

left

recursionGrammarrewriteInherited4.3 Top

Down

Calculation

of

L-Attributed

DefinitionEx

Inherited

Attributes

caused

by

eliminating

lefProduction Semantic

ruleE

fi

E1

+

T E.nptr

:=

mknode(

‘+’,

E1.nptr,

T.nptr)E

fi

T E.nptr

:=

T.nptrT

fi

T1*F T.nptr

:=

mknode(

‘*’,

T1.nptr,

F.nptr)T

fi

F T.nptr

:=

F.nptrF

fi

(E)

F.nptr

:=

E.nptrF

fi

id

F.nptr

:=

mkleaf

(id,

id.entry)F

fi

num

F.nptr

:=

mkleaf

(num,

num.val)4.3 Top

Down

Calculation

of

L-Attributed

Definition{R.i

:=

T.nptr}

T

+

T

+

T

+

…{E.nptr

:=

R.s}{R.s

:=

R1.s}{R.s

:=

R.i

}{W.i

:=

F.nptr}{T.nptr

:=

W.s}E

fi

TRR

fi

+TR1R

fi

eT

fi

FWW

fi

*FW1W

fi

e{W1.i

:=

mknode

(

‘*’,

W.i,

F.nptr)}{W.s

:=

W1.s}{W.s

:=

W.i

}Production

rules

after

eliminating

leftrecursionR

RR{R1.i

:=

mknode

(

‘+’,

R.i,

T.nptr)}+T.nptr？TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中b

的入口id

num

5指向符號(hào)表中a

的入口i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionT

fi

F

{W.i

=

F.nptr}

W

{T.nptr

=

W.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionT

fi

F

{W.i

=

F.nptr}

W

{T.nptr

=

W.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionW

fi

*F

{W1.i

=

mkNode

(‘*’,W.i,

F.nptr)}W1{W.s

=

W1.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionW

fi

*F

{W1.i

=

mkNode

(‘*’,W.i,

F.nptr)}W1{W.s

=

W1.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionW

fi

*F

{W1.i

=

mkNode

(‘*’,W.i,

F.nptr)}W1{W.s

=

W1.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionW

fi

*F

{W1.i

=

mkNode

(‘*’,W.i,

F.nptr)}W1{W.s

=

W1.s}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

RecursionW

fi

e

{W.s

=

W.i

}TF.nptrF.nptridi

W*idnumid**指向符號(hào)表中a

的入口指向符號(hào)表中b

的入口id

num

5i

W

si

W*

F.nptrea*5*b略去了E

TR

T

部分E

fi

TRR

fi

+TR1R

fi

eT

fi

F

WW

fi

*FW1W

fi

eInherited

Attributes

Caused

by

Eliminating

Left

Recursion4.3 Top

Down

Calculation

of

L-Attributed

Definition4.3.3

Recursive

Descent

Predictive

TranslationGeneralize

LL

Parser

to

support

translation

schemParsing

for

R

fi

+TR

|

eprocedure

R;beginif

lookahead

=

‘+’

then

beginmatch

(

‘+’

);

T;

Rendelse

begin /*

do

nothing

*/endend5/334.3 Top

Down

Calculation

of

L-function

R

(i

:?syntax_tree_node)

:?syntax_tree_node;varbeginnptr

,

i1,

s1,

s

:

?

syntax_tree_node;addoplexeme

:

char;if

lookahead

=

‘+’ then

begin/*

R

fi

+T

R

*/addoplexeme

:=

lexval;match(

‘+’

);nptr

:=

T;i1

:=

mknode(addoplexme,

i

,

nptr)

;s1

:=

R

(i1

);s

:

=

s1endelse

s

:=

i;

/*

R

fi

e*/return

send;R

fi

+T

{R1.i

:=

mknode

(

‘+’,

R.i,

T.nptr)}R1

{R.s

:=

R1.s}Translation

sAchtetmreibfourRtefid+DTRe|feinition4.3 Top

Down

Calculation

of

L-Attributed

Definition4.3.4

Replace

inherited

attributes

withSynthesized

attributes

(via

grammar

rewrite)Declaration

for

Pascal,

e.g.,

m,

n

:

integerD

fi

L

:TT

fi

integer

|charL

fi

L,id|id,LidintegerDL

:

Tid4.3 Top

Down

Calculation

of

L-Attributed

Definition4.3.4

Replace

inherited

attributes

withSynthesized

attributesD

fi

L

:TT

fi

integer

|charL

fi

L,id|idUse

right

to

left

reductionD

fi

id

LL

fi

,

id

L

|

:TT

fi

integer

|char4.3 Top

Down

Calculation

of

L-Attributed

Definition4.3.4

Replace

inherited

attributes

withSynthesized

attributesD

fi

L

:TT

fi

integer

|charL

fi

L,id|idUse

right

to

left

reductionD

fi

id

LL

fi

,

id

L

|

:TT

fi

integer

|charD:L,idintegerTAddtype(id.entry,

L.type)Addtype(id.entry,

L.type)id

L4.3 Top

Down

Calculation

of

L-Attributed

DefinitionD

fi

id

L

L

fi

,

id

L1{

addtype

(id.

entry,

L.

type)}{L.

type

:=

L1.

Type;addtype

(id.

entry,

L1.

type)}L

fi:

T{L.

type

:=

T.

type}T

fiinteger{T.

type

:=

integer}T

fi

real{T.

type

:=

real}D:L,idid

LintegerT10/334.4

Bottom

Up

Calculation

ofL-AttributedDefinitionIn

top-down

analysis,

it

is

possible:To

realize

any

LL(1)

based

L-attributeddefinitionsTo

realize

many

(but

not

all)

LR(1)

basedL-attributed

definitions4.4

Bottom

Up

Calculation

ofL-AttributedDefinition.

.

..

.

.YY.

yXX.x.

.

..

.

.Stack

state

valtopProblem

to

tackleA

X

Y

{Z.i

=

X.x}ZZ

abC..

{C.c

=

Z.i

*

10}A

state

(symbol)

isassociated

with

asynthesized

attribute.

Itsattribute

value

is

availableafter

processing

the

symbol.Before

processing

Z,

theinherited

attribute

Z.i

has

no

entryEliminate

inherited

attributein

the

stack4.4

Bottom

Up

Calculation

ofL-AttributedDefinition4.4.1

Special

Case

1：Removing

embeddedactions

in

the

translation

schemeEfi

TRR

fi

+

T

{print

(‘+’)}R1

|

-

T

{print

(‘-’)}R1

|

eT

fi

num

{print

(num.val)}Introduce

a

production

that

derives.

Represent

theembedded

actions

with

the

introduced

production,

andput

the

action

in

the

productionEfi

TRRfi

+

TM

R1

|-

TNR1

|eT

fi

num

{print

(num.val)}M

fi

e{print

(‘+’)}Nfi

e

{print

(‘-’)}4.4

Bottom

Up

Calculation

ofL-attributed

Definitions4.4.2

Special

Case

2:

The

inheritedattribute

in

the

stack

is

predictableEx

int

p,

q,

rD

fi

T

{L.in

:=

T.type}LTfi

int {T.

type

:=

integer}Tfi

real

{T.

type

:=

real}Lfi

{L1.in

:=

L.in

}L1,

id

{addtype

(id.entry,

L.in

)}Lfi

id {addtype

(id.entry,

L.in

)}4.4

Bottom

Up

Calculation

ofL-4.4.2

SpecAiatltCriabsuet2e:dThDeeinfihneirtiitoednattributeD,rLqintT

?typeL,inin

?in

?

LStateInputProduction-int

p,q,rintp,q,rTp,q,rT

intTp,q,rTL,q,rL

idTL,q,rTL,q,rTL,rL

L,idTL,rTL,rTLL

L.idDD

TLpL.in

=

T.typeLfi

id

{addtype

(id.entry,

L.in

)}Lfi{L1.in

:=

L.in

}L1,

id

{addtype

(id.entry,

L.in

)}Lfi{L1.in

:=

L.in

}L1,

id

{addtype

(id.entry,

L.in

)}15/33in

the

stack

is

pFroerLd

iicd,tLa

bL1l,eid,when

using

L.in

we

canfind

it

at

(T.type)4.4

Bottom

Up

Calculation

ofL-Attributed

DefinDitionTr,

qint?typein

?

Lpin

?

Lin

?

L

,ProductionCodeDfi

TLTfi

intval[top]

:=

integerTfi

realval[top]

:=

realLfi

L1,

idaddtype(val[top],val[top-3])Lfi

idaddtype(val[top],val[top-1])4.4

Bottom

Up

Calculation

ofL-AttributedDefinitionS

fi

aAC

S

fi

bABCC

fi

cC.i

:=

A.sC.i

:=

A.sC.s

:=

g(C.i)Introduce

marker

nonterminal

MS

fi

aACS

fi

bABMCC

fi

cM

fi

eC.i

:=

A.sM.i

:=

A.s;

C.i

:=

M.sC.s

:=

g(C.i)M.s

:=

M.iS

aACS

bABMCC

cval

[top]=g(val

[top-1])M

eval

[top+1]=val

[top-1]Unpredictable

Attribute

locationC

c could

be

obtainedfrom

two

productions,yet

the

locations

aredifferent4.4

Bottom

Up

Calculation

ofL-AttributedDefinition4.4.3

General

Case：Simulating

thecalculation

of

inherited

attributeInherited

attribute

is

a

function

of

somesynthesized

attributeSfiaACC.i

:=

f(A.s)C

ficC.s

:=

g(C.i)4.4

Bottom

Up

CalculationAttributedDefinitionof

L-ofsome4.4.3

Simulating

the

calculationinherited

attributeInherited

attribute

is

a

function

ofsynthesized

attributeS

fi

aACC

fi

cIntroduce

markerC.i

:=

f

(A.s)C.s

:=

g(C.i)nonterminal,and

move

thecalculation

of

f(A.s)

to

the

reduction

of

themarker

nonterminalS

fi

aANCN

fi

eC

fi

cN.i

:=

A.s;

C.i

:=

N.sN.s

:=

f

(N.i)C.s

:=

g(C.i)Wheneverusinginheritedattributes,theyappearunder

thecurrentsymbol

inthe

stackEx.

EQNSfi

{B.ps

:=

10

}B

{S.ht

:=

B.ht

}Bfi

{B1.ps

:=

B.ps

}B1

{B2.ps

:=

B.ps

}B2

{B.ht

:=

max(B1.ht,

B2.ht

)

}Bfi

{

B1.ps

:=B.ps

}B1sub {

B2.ps

:=

shrink(B.ps)

}B2

{B.ht

:=

disp

(B1.ht,

B2.ht

)

}B

fi

text

{B.ht

:=

text.h

·

B.ps

}在計(jì)算文本的字體和高度的時(shí)候，無(wú)法確定所依賴(lài)的繼承屬性值的位置。例如：棧頂元素可能是text =>

BB

text =>

B

BB

sub

text =>

B

sub

BproductionSemantic

rulesS

fi

LBB.ps

:=

L.s;

S.ht

:=

B.htL

fi

eL.s

:=

10B

fi

B1

MB2B1.ps

:=

B.ps;

M.i

:=

B.ps;B2.ps

:=

M.s;B.ht

:=max(B1.ht,

B2.ht

)M

fi

eM.s

:=

M.iB

fi

B1

subNB2B1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp(B1.ht,

B2.ht

)N

fi

eN.s

:=

shrink(N.i)S

fiL{

B.ps

:=

L.s

}B{

S.ht

:=

B.ht

}LfiB

fie{

L.s

:=

10

}{

B1.ps

:=

B.ps}B1

{

M.i

:=

B.ps}M

{

B2.ps

:=

M.s

}B2

{

B.ht

:=

max(B1.ht,B2.ht)

}M

fi

e

{

M.s

:=

M.i

}B

fi

{

B1.ps

:=B.ps

}B1sub {

N.i=

B.ps}N

{

B2.ps

:=

shrink(N.s)}B2

{

B.ht

:=

disp

(B1.ht,

B2.ht)

}N

fi

e

{

N.s

:=

N.i}B

fitext

{

B.ht:=

text.h

·

B.ps

}舉例說(shuō)明textesubetext1L

s=10stexth=E.hEEh=E.h

htpBsiN

sh=1.hpsB

htpsB

hte

psBht

MiS

htpsB

htproductionSemantic

RuleL.s

:=

10B1.ps

:=

B.ps;

M.i

:=

B.ps;B2.ps

:=

M.s;

B.ht

:=

max(B1.ht,

B2.ht

)S

fi

LBL

fi

eB

fi

B1MB2M

fi

eM.s

:=

M.iB1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp

(B1.ht,

B2.ht

)N.s

:=

shrink(N.i)B

fi

B1sub

NB2N

fi

eB

fi

textB.ht

:=

text.h

·

B.ps棧

state

valB

htB.ps

:=

L.s;

S.ht

:=

B.ht

LstopproductioncodeS

fi

LBval[top-1]

:=

val[top]topLsL

fi

eL.s

:=

10B

fi

B1MB2B1.ps

:=

B.ps;

M.i

:=

B.ps;B2.ps

:=

M.s;

B.ht

:=

max(B1.ht,

B2.ht

)M

fi

eM.s

:=

M.iB

fi

B1sub

NB2B1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp

(B1.ht,

B2.ht

)N

fi

eN.s

:=

shrink(N.i)B

fi

textB.ht

:=

text.h

·

B.psodeval[top-1]

:=

val[top]val[top+1]

:=

10B1.ps

:=

B.ps;

M.i

:=

B.ps;B2.ps

:=

M.s;

B.ht

:=

max(B1.ht,

B2.ht

)productionS

fi

LBL

fi

eB

fi

B1MB2M

fi

eM.s

:=

M.iB1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp

(B1.ht,

B2.ht

)N.s

:=

shrink(N.i)B

fi

B1sub

NB2N

fi

eB

fi

textB.ht

:=

text.h

·

B.psB

htcM

sB

htL

stopproductioncodeval[top-1]

:=

val[top]max(val[top-2],val[top+1]

:=

10val[top-2]

:=val[top])S

fi

LBL

fi

eB

fi

B1MB2M

fi

eM.s

:=

M.iB1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp

(B1.ht,B2.ht

)B

fi

B1sub

NB2N

fi

eN.s

:=

shrink(N.i)B

htL

stopcodeval[top-1]

:=

val[top]max(val[top-2],val[top+1]

:=

10val[top-2]

:=val[top])productionS

fi

LBL

fi

eB

fi

B1MB2M

fi

eval[top+1]

:=

val[top-1]B1.ps

:=B.ps;

N.i

:=

B.ps;B2.ps

:=

N.s;

B.ht

:=

disp

(B1.ht,B2.ht

)B

fi

B1sub

NB2N

fi

eN.s

:=

shrink(N.i)B

htN

ssubB

htL

stopodeproductioncsubBhtS

fi

LBval[top-1]

:=

val[top]LsL

fi

eval[top+1]

:=

10B

fi

B1MB2val[top-2]

:=

max(val[top-2],

val[top])M

fi

eval[top+1]

:=

val[top-1]B

fi

B1sub

NB2val[top-3]:=

disp

(val[top-3],

val[top]

)N

fi

eN.s

:=

shrink(N.i)B

fi

textB.ht

:=

text.h

·

B.pscodeproductiontexthS

fi

LBval[top-1]

:=

val[top]LsL

fi

eval[top+1]

:=

10B

fi

B1MB2val[top-2]

:=

max(val[top-2],

val[top])M

fi

eval[top+1]

:=

val[top-1]B

fi

B1sub

NB2val[top-3]:=

disp

(val[top-3],

val[top]

)N

fi

eval[top+1]

:=

shrink(val[top-2])B

fi

textB.ht

:=

text.h

·

B.psproductioncodeS

fi

LBval[top-1]

:=

val[top]L

fi

eval[top+1]

:=

10B

fi

B1MB2val[top-2]

:=

max(val[top-2],

val[top])M

fi

eval[top+1]

:=

val[top-1]B

fi

B1sub

NB2val[top-3]:=

disp

(val[top-3],

val[top]

)N

fi

eval[top+1]

:=

shrink(val[top-2])B

fi

textval[top]

:=

val[top]

·

val[top-1]SummaryTwo

ways

of

describing

semantic

rules:

syntaxdirecteddefinitionand

translation

schemeHow

todesignsimple

syntax

directeddefinitionsand

translationrulesBottom

upcalculation

ofS-Attributes(alongparsing)Bottom

upcalculation

ofL-Attributes(alongparsing)Top

downcalculation