编译原理与技术课件

2023/8/2《编译原理与技术》讲义1语法制导翻译属性文法S-属性定义L-属性定义语法制导定义与翻译方案自底向上翻译S-属性定义自底向上计算自底向上计算继承属性自顶向下翻译2023/8/2《编译原理与技术》讲义1语法制导翻译属性文法2023/8/2《编译原理与技术》讲义2属性文法属性文法（AttributedGrammar）

上下文无关文法+属性+属性计算规则属性－用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。e.g.二义性表达式文法G，非终结符E有属性E.val（表达式的值）EE‘+’E|

E‘*’E|‘(‘E‘)’|number

属性计算规则（语义规则）与产生式相关联的反映文法符号属性之间关系的“规则”2023/8/2《编译原理与技术》讲义2属性文法属性文法（A2023/8/2《编译原理与技术》讲义3属性文法语法制导定义（文法＋属性＋语义规则）

语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法＋属性＋语义动作）语义规则－即语义动作，可体现若干实现的细节。2023/8/2《编译原理与技术》讲义3属性文法2023/8/2《编译原理与技术》讲义4e.g.1算术表达式的计算器

产生式 语法制导定义EE1‘+’E2E.val:=E1.val+E2.valEE1‘*’E2E.val:=E1.val*E2.valE’(‘E1‘)’E.val:=E1.valEnumberE.val:=number.lex_val2023/8/2《编译原理与技术》讲义4e.g.1算术表达式2023/8/2《编译原理与技术》讲义5e.g.1算术表达式的计算器

产生式 翻译方案EE1‘+’E2{E.val:=E1.val+E2.val}EE1‘*’E2{E.val:=E1.val*E2.val}E’(‘E1‘)’{E.val:=E1.val}Enumber{E.val:=number.lex_val}2023/8/2《编译原理与技术》讲义5e.g.1算术表达式2023/8/2《编译原理与技术》讲义6属性文法属性的分类若产生式AX1X2…Xn，与之相关的属性计算规则

b:=f(c1,c2,…)－如果属性b是产生式左部符号A的属性则称其为A的综合属性；－如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性；－c1,c2,…一般是产生式右部其它符号的(综合)属性或A的继承属性；－固有属性：终结符仅有的属性。如number.lex_val。通常由词法程序提供。2023/8/2《编译原理与技术》讲义6属性文法属性的分类2023/8/2《编译原理与技术》讲义7A.bX1.c1X2.c2Xn.cn…综合属性A.b的计算A的继承属性AX1.c1X2.c2…继承属性Xk.b的计算A的继承属性Xk.bXn.cn属性依赖图2023/8/2《编译原理与技术》讲义7A.bX1.c1X22023/8/2《编译原理与技术》讲义8e.g.2属性依赖图: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=52023/8/2《编译原理与技术》讲义8e.g.2属性依2023/8/2《编译原理与技术》讲义9语义规则的计算方法分析树方法 －为输入串建立分析树 －由语义规则建立属性依赖图（没有属性循环依赖的） －对依赖图进行拓扑排序，得到属性计算次序 －依次计算属性，得到“翻译”结果基于规则的方法 －构造编译器时，事先对产生式的语义规则进行分析，得到属性计算次序忽略规则的方法 －属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。2023/8/2《编译原理与技术》讲义9语义规则的计算方法分2023/8/2《编译原理与技术》讲义10e.g.3属性计算次序: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=5123456782023/8/2《编译原理与技术》讲义10e.g.3属性2023/8/2《编译原理与技术》讲义11S-属性定义－语义规则仅包含综合属性计算（可以有固有属性出现）。－适合自底向上计算e.g.语法树－语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。2023/8/2《编译原理与技术》讲义11S-属性定义－语义2023/8/2《编译原理与技术》讲义12SifB-exprthenS1elseS2

语法树 分析树语法树vs.分析树if-then-elseB-exprS1S2SifB-exprthenS1elseS22023/8/2《编译原理与技术》讲义122023/8/2《编译原理与技术》讲义13 a:=b*-c+b*-c

语法树分析树

语法树vs.分析树assigna+*b@c*b@cassignEEE+E*EbE@Ea赋值语句cE*EbE@c算符2023/8/2《编译原理与技术》讲义13 a2023/8/2《编译原理与技术》讲义14DAG（去除了公共子表达式的无环有向图）

a:=b*-c+b*-c

语法树vs.DAGassigna+*b@c*b@cassigna+*b@c语法树DAG2023/8/2《编译原理与技术》讲义14DAG（去除了公共2023/8/2《编译原理与技术》讲义15e.g.4构造表达式的语法树（DAG）

产生式 语义规则EE1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)EE1-E2E.nptr:=mknode(‘-’,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)EE1/E2E.nptr:=mknode(‘/’,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.nptrE-E1E.nptr:=mknode(‘@’,E1.nptr,－)EnumberE.nptr:=mkleaf(‘NUM’,number.lex_val)EidE.nptr:=mkleaf(‘ID’,id.entry)2023/8/2《编译原理与技术》讲义15e.g.4构造表2023/8/2《编译原理与技术》讲义16e.g.4构造表达式的语法树（DAG）

E.nptr

－E的语法树（根结点指针）

mknode(op,left,right)－建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。如果建成DAG，则需要检查是否已存在相应内部结点op，其左右运算对象分别是left和right。若没有则新建一个。

mkleaf(‘NUM’,number.lex_val)－

mkleaf(‘ID’,id.entry)－ 建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。2023/8/2《编译原理与技术》讲义16e.g.4构造表2023/8/2《编译原理与技术》讲义17e.g.4构造表达式a+b*-4的属性结构树

E.nptrE.nptrE.nptr+E.nptrE.nptr*ab@E.nptr4IDaIDbNUM4@

-*

+

2023/8/2《编译原理与技术》讲义17e.g.4构造表2023/8/2《编译原理与技术》讲义18e.g.4构造表达式a+b*-4的语法树（DAG）

+

IDa*

IDb@

-NUM42023/8/2《编译原理与技术》讲义18e.g.4构造表2023/8/2《编译原理与技术》讲义19L-属性定义－如果产生式AX1X2…Xn的语义规则只计算

1）A的综合属性，或者

2）Xi的继承属性，且该属性仅依赖于产生式右部Xi的左边符号Xj（j<i）的（综合）属性或A的继承属性；－S-属性定义均为L-属性定义－可按深度优先次序计算 －一种自然的属性计算次序 －在分析期间完成翻译。属性计算与结点建立有联系；适合于自顶向下和自底向上分析方法。2023/8/2《编译原理与技术》讲义19L-属性定义－如果2023/8/2《编译原理与技术》讲义20深度优先次序

proceduredfvisit(n:node) begin foreachchildmofn,fromlefttorightdo begin evaluateinheritedattributesofm;

dfvisit(m); end; evaluatesynthesizedattributesofn; end2023/8/2《编译原理与技术》讲义20深度优先次序 pr2023/8/2《编译原理与技术》讲义21e.g.5非L-属性定义的语法制导定义

产生式 语义规则

ALM L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) AQR R.i:=r(A.i)

Q.i:=q(R.s) A.s:=f(Q.s)2023/8/2《编译原理与技术》讲义21e.g.5非L-2023/8/2《编译原理与技术》讲义22翻译方案中的动作－语义动作可放在产生式右端任何位置；这也就显式地给出了动作的执行时刻。（可认为是在深度优先遍历中的执行时刻）e.g.6将含有+和-运算的中缀表达式翻译为后缀形式：

ETR RaddopT{print(addop.lex_val)}R|

Tnumber{print(number.lex_val)}2023/8/2《编译原理与技术》讲义22翻译方案中的动作－2023/8/2《编译原理与技术》讲义23e.g.6中缀翻译为后缀：9-4+5ETR9print(9)-Tprint(‘-’)R4print(4)+Tprint(‘+’)5print(5)R123452023/8/2《编译原理与技术》讲义23e.g.6中缀2023/8/2《编译原理与技术》讲义24翻译方案中的动作－设计翻译方案时，必须保证动作所引用的属性值是可用的。 －只有综合综合属性时（S-属性定义），动作放在产生式末尾； －若有继承属性时，动作的放置须保证： －（产生式右部）符号的继承属性必须在 此符号前计算； －动作不要引用其右边符号的综合属性； －左部非终结符的综合属性一般放在产生式末 尾（确保它引用的属性均已计算完且可用）2023/8/2《编译原理与技术》讲义24翻译方案中的动作－2023/8/2《编译原理与技术》讲义25e.g.7翻译方案的书写 SA1A2{A1.in:=1;A2.in:=2} Aa{print(A.in)}改写为：

S

{A1.in:=1}A1{A2.in:=2}A2

Aa{print(A.in)}2023/8/2《编译原理与技术》讲义25e.g.7翻译方2023/8/2《编译原理与技术》讲义26e.g.8类型说明的语法制导定义（0）

产生式 语义规则

DTL L.in:=T.typeTint T.type:=integerTreal T.type:=realLL1,id L1.in:=L.in

addtype(id.entry,L.in) Lid addtype(id.entry,L.in)2023/8/2《编译原理与技术》讲义26e.g.8类型说2023/8/2《编译原理与技术》讲义27e.g.8类型说明的语法制导定义（0）－

属性传递DTLL，kL，jiint2023/8/2《编译原理与技术》讲义27e.g.8类型说2023/8/2《编译原理与技术》讲义28e.g.8类型说明的语法制导定义（1）改写上述类型声明文法，使得其中的T成为L的子结点（即产生式右部），可以避免继承属性的使用。修改后文法如下：

DLTintTrealLL1,idLTid2023/8/2《编译原理与技术》讲义28e.g.8类型说明2023/8/2《编译原理与技术》讲义29e.g.8类型说明的语法制导定义（2）

产生式 语义规则

DL

Tint T.type:=integerTreal T.type:=realLL1,id L.in:=L1.in

addtype(id.entry,L1.in)

LTid

addtype(id.entry,T.type); L.in:=T.type2023/8/2《编译原理与技术》讲义29e.g.8类型说明2023/8/2《编译原理与技术》讲义30e.g.8类型说明的语法制导定义（2）

属性传递DTLL，kL，jiint2023/8/2《编译原理与技术》讲义30e.g.8类型说明2023/8/2《编译原理与技术》讲义31e.g.8类型说明的语法制导定义（3）Pascal语言类型声明文法如下：

DL:TTintTrealLL1,idLid该声明文法的“问题”在于，L中声明的变量的类型T处于产生式中L的右边！若用继承属性L.in来传递类型信息T.type形成非L－属性定义。从而无法在完成L分析同时将有关类型信息填入符号表！可以考虑将T作为L的子结点（通过修改文法）来改变这种情况2023/8/2《编译原理与技术》讲义31e.g.8类型说2023/8/2《编译原理与技术》讲义32e.g.8类型说明的语法制导定义（4）

产生式 语义规则

DidL addtype(id.entry,L.in) Tint T.type:=integerTreal T.type:=realL,idL1 L.in:=L1.in

addtype(id.entry,L1.in) L:T L.in:=T.type2023/8/2《编译原理与技术》讲义32e.g.8类型说2023/8/2《编译原理与技术》讲义33e.g.9翻译方案的计算次序 EE+T{print(“1”)} ET{print(“2”)} TT*F{print(“3”)} TF{print(“4”)} F(E){print(“5”)} Fid{print(“6”)}输入串是id*(id+id)时，该翻译方案输出什么？2023/8/2《编译原理与技术》讲义33e.g.9翻译方2023/8/2《编译原理与技术》讲义34S-属性定义的自底向上计算拓广分析栈，即添加属性栈，包含文法符号的综合属性。在归约实施前，右部各符号的综合属性（若有的话）已放在与符号位置对应的属性栈上，因此，可以先计算获得左部非终结符的综合属性。然后再归约，这时从分析栈中弹出句柄，（注意，此时改变栈顶top即可）最后，将左部符号连同其属性放入由top指示的分析栈及属性栈的位置中。这种属性栈只能存放综合属性。回想YACC中如何做的？2023/8/2《编译原理与技术》讲义34S-属性定义的自底2023/8/2《编译原理与技术》讲义35如果AXYZ，相关语义规则如下：A.a:=f(X.x,Y.y,Z.z)显然，X.x在Val[top-2]Y.y在Val[top-1]Z.z在Val[top]A.a在Val[ntop]，ntop=top–|句柄长度|+1Val[ntop]:=f(val[top-2],Val[top-1],Val[top])属性栈与分析栈ZZ.zYY.yXX.x…………分析栈属性栈Valtopbottom2023/8/2《编译原理与技术》讲义35如果AXYZ，相2023/8/2《编译原理与技术》讲义36如果AB，相关语义规则如下：A.a:=B.b显然，B.b在Val[top]A.a在Val[ntop]，ntop=top–1+1=top,即归约前后栈顶top不变，也即Val[ntop]和Val[top]对应属性栈同一个单元，所以，可以省略原语义规则对应的属性栈操作：

Val[ntop]:=Val[top]属性栈与分析栈BB.b…………分析栈属性栈Valtopbottom2023/8/2《编译原理与技术》讲义36如果AB，相关2023/8/2《编译原理与技术》讲义37e.g.10计算表达式的（栈）代码产生式语义规则代码段LE‘\n’Print(E.val)Print(Val[top-1])EE1+TE.val:=E1.val+T.valVal[ntop]:=Val[top-2]+Val[top]ETE.val:=T.valTT1*FT.val:=T1.val*F.valVal[ntop]:=Val[top-2]*Val[top]TFT.val:=F.valF(E)F.val:=E.valVal[ntop]:=Val[top-1]FdigitF.val:=digit.lex_val2023/8/2《编译原理与技术》讲义37e.g.10计算2023/8/2《编译原理与技术》讲义38如何在自底向上分析中计算继承属性？ －属性栈上仅能存放综合属性 －能否将继承属性的引用转换成综合属性？分析栈中符号的继承属性 －属性copy规则 如果，AXY，有语义规则Y.i:=X.s， 翻译方案可写为：

AX{Y.i:=X.s}Y

自底向上计算继承属性2023/8/2《编译原理与技术》讲义38如何在自底向上分析2023/8/2《编译原理与技术》讲义39自底向上计算继承属性－由属性copy规则可知，Y的继承属性Y.i和X.s在属性栈上同一位置。这样对属性Y.i的引用可以转化为对X.s的引用。若计算Y的综合属性Y.s时需要引用Y.i，则此时Y.i（即X.s）就紧邻在句柄下面；如果Y的句柄形成前，它的某个右部符号需使用Y.i，这时，也可以直接使用Y.i。（Howtouse?）bottom………………XX.s（Y.i）……分析栈属性栈Valtop句柄（归约为Y）top－句柄长2023/8/2《编译原理与技术》讲义39自底向上计算继承属2023/8/2《编译原理与技术》讲义40e.g.11C声明的翻译方案DT{L.in:=T.type}L Tint{T.type:=integer}Treal {T.type:=real}L{L1.in:=L.in} L1,id

{addtype(id.entry,L.in)} Lid{addtype(id.entry,L.in)}对于输入串：intp,q,r分析过程如下：2023/8/2《编译原理与技术》讲义40e.g.11C2023/8/2《编译原理与技术》讲义41

输入串 分析栈 产生式

intp,q,r p,q,r int p,q,r T Tint ,q,r Tp ,q,r TL

Lid q,r TL, ,r TL,q

,r TL LL,id

r

TL,

TL,r

TLLL,id

D

DTL注意：每次归约成L时，T与L的位置关系－－T就在句柄的下面！2023/8/2《编译原理与技术》讲义41 输入串 2023/8/2《编译原理与技术》讲义42e.g.11C声明的“代码段”

产生式 代码段（只含综合属性）

DTL Tint val[ntop]:=integer

Treal val[ntop]:=real LL1,id addtype(val[top],val[top-3]) Lid addtype(val[top],val[top-1])L的继承属性L.in2023/8/2《编译原理与技术》讲义42e.g.112023/8/2《编译原理与技术》讲义43问题1：继承属性的位置在构造编译器时不可预知（或不固定），如e.g.12

产生式 语义规则SaAC

C.i:=A.sSbA

B

C

C.i:=A.sCc C.s:=g(C.i) …

用Cc归约时，C.i的值可能在val[top-1]或者在val[top-2]的位置上。解决办法是考虑将其统一。 引入标记非终结符M和产生式M。模拟继承属性的计算bottomccABaAb……分析栈1分析栈2top2023/8/2《编译原理与技术》讲义43问题1：继承属性的2023/8/2《编译原理与技术》讲义44产生式 语义规则SaAC

C.i:=A.sSbA

B

M

C

C.i:=M.s M.i:=A.sCc C.s:=g(C.i)M M.s:=M.i

…引入M后，C.i可从句柄c的下面(val[top-1])取得！属性传递：

A.s

M.iM.sC.iC.se.g.12引入标记非终结符bottomAMaB…A…b……分析栈1分析栈2topcc2023/8/2《编译原理与技术》讲义44产生式 2023/8/2《编译原理与技术》讲义45产生式 代码段SaAC

SbA

B

M

C

Cc val[ntop]:=g(val[top-1])Mval[ntop]:=val[top-1]…可否将M放在SaAC产生式中？M.i2023/8/2《编译原理与技术》讲义45产生式 代2023/8/2《编译原理与技术》讲义46模拟继承属性的计算问题2：语义规则不是简单的属性复写拷贝。e.g.13:将例12中的SaAC语义规则换为： 产生式 语义规则

SaAC C.i:=f(A.s)虽然在例12中引入了M使得“A.s”可在val[top-1]处找到，但在S的两个产生式中C.i的取值方式不同，导致C.s的计算嘛…这次可以考虑引入标记非终结符N和N2023/8/2《编译原理与技术》讲义46模拟继承属性的计算2023/8/2《编译原理与技术》讲义47e.g.13引入标记非终结符N

产生式 语义规则

SaA

N

C C.i:=N.s

N.i:=A.s

N

N.s:=f(N.i)

(其他产生式和语义规则不变）

(代码段略）

2023/8/2《编译原理与技术》讲义47e.g.13引入2023/8/2《编译原理与技术》讲义48

产生式 语义规则

SB B.ps:=10 S.ht:=B.ht BB1B2 B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) BB1subB2 B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) Btext B.ht:=text.h×B.pse.g.14文字排版的语法制导定义2023/8/2《编译原理与技术》讲义48 产生式 2023/8/2《编译原理与技术》讲义49S：S.ht，综合属性；待排公式的整体高度B：B.ps，继承属性；公式（文本）中字体“点”的大小

B.ht，综合属性；公式排版高度text：text.h，文本高度max：求两个排版公式的最大高度shrink(B)：将点大小缩小为B的30％disp(B1.ht，B2.ht)：向下调整B2的位置文字排版中的符号属性E1Val2023/8/2《编译原理与技术》讲义49S：S.ht，2023/8/2《编译原理与技术》讲义50文字排版的翻译方案（0） S {B.ps:=10} B {S.ht:=B.ht} B {B1.ps:=B.ps} B1 {B2.ps:=B.ps} B2 {B.ht:=max(B1.ht,B2.ht)} B {B1.ps:=B.ps} B1 sub {B2.ps:=shrink(B.ps)} B2 {B.ht:=disp(B1.ht,B2.ht)} Btext {B.ht:=text.h×B.ps}2023/8/2《编译原理与技术》讲义50文字排版的翻译方案2023/8/2《编译原理与技术》讲义51文字排版中引入标记符号为了自底向上计算：Btext {B.ht:=text.h×B.ps}必须确定继承属性B.ps的（“属性栈”）位置。为此引入标记非终结符L、M和N及其属性，包括相应的空产生式和有关属性规则。这样B.ps即可在紧靠“句柄”text下方的位置上找到。(L的综合属性置为B.ps的初值)SL

BBB1MB2BB1subNB2texttext.hLL.s=10分析栈属性栈topbottom2023/8/2《编译原理与技术》讲义51文字排版中引入标记2023/8/2《编译原理与技术》讲义52SL {B.ps:=L.s} L{L.s:=10} B {S.ht:=B.ht}B {B1.ps:=B.ps} M{M.s:=M.i} B1 {M.i:=B.ps}

M {B2.ps:=M.s} B2 {B.ht:=max(B1.ht,B2.ht)}B {B1.ps:=B.ps} B1 sub {N.i:=B.ps} N{N.s:=shrink(N.i)}

N {B2.ps:=N.s} B2 {B.ht:=disp(B1.ht,B2.ht)}Btext {B.ht:=text.h×B.ps}文字排版的翻译方案（1）2023/8/2《编译原理与技术》讲义52SL2023/8/2《编译原理与技术》讲义53

产生式 代码段SL

B val[ntop]:=val[top]BB1M

B2val[ntop]:=max(val[top-2],val[top])BB1subNB2val[ntop]:=disp(val[top-3],val[top])Btext val[ntop]:=val[top]×val[top-1]L val[ntop]:=10M val[ntop]:=val[top-1]N val[ntop]:=shrink(val[top-2])2023/8/2《编译原理与技术》讲义53产生式 代2023/8/2《编译原理与技术》讲义54（L-属性定义）自顶向下翻译删除翻译方案中的左递归

AA1Y{A.a:=g(A1.a,Y.y)} AX{A.a:=f(X.x)}

消除左递归：

AX {R.i:=f(X.x)}//传递“左”运算量

R{A.a:=R.s} RY {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s} R

{R.s:=R.i}//返回结果2023/8/2《编译原理与技术》讲义54（L-属性定义）自2023/8/2《编译原理与技术》讲义55输入串XY1Y2的翻译XA.a:=f(X.x)A.a:=g(f(X.x),y1.y)y1A.a:=g(g(f(X.x),y1.y),y2.y)y2A.aXR.i:=f(X.x)Y1R.i:=g(f(X.x),Y1.y)Y2R.i:=g(g(f(X.x),Y1.y),Y2.y)R.sR.sR.s2023/8/2《编译原理与技术》讲义55输入串XY1Y2的2023/8/2《编译原理与技术》讲义56e.g.15删除翻译方案中左递归EE1+T{E.nptr:=mknode(‘+’,E1.nptr,T.nptr)}EE1-T{E.nptr:=mknode(‘-’,E1.nptr,T.nptr)}ET{E.nptr:=T.nptr}T(E){T.nptr:=