编译原理与技术课件

《编译原理与技术课件》由会员分享，可在线阅读，更多相关《编译原理与技术课件（61页珍藏版）》请在金锄头文库上搜索。

1、2022/8/26编译原理与技术讲义1语法制导翻译属性文法lS-属性定义lL-属性定义l语法制导定义与翻译方案自底向上翻译lS-属性定义自底向上计算l自底向上计算继承属性自顶向下翻译2022/8/26编译原理与技术讲义2属性文法属性文法（Attributed Grammar）上下文无关文法上下文无关文法+属性属性+属性计算规则属性计算规则 属性用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。e.g.二义性表达式文法G，非终结符E有属性E.val（表达式的值）EE+E|E*E|(E)|number 属性计算规则（语义规则）与产生式相关联的反映文法符号属性之间关系的“规则”20

2、22/8/26编译原理与技术讲义3属性文法语法制导定义（文法属性语义规则）语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法属性语义动作）语义规则即语义动作，可体现若干实现的细节。2022/8/26编译原理与技术讲义4e.g.1算术表达式的计算器 产生式 语法制导定义EE1+E2 E.val :=E1.val+E2.valEE1*E2 E.val :=E1.val*E2.valE(E1)E.val :=E1.valEnumber E.val :=number.lex_val2022/8/26编译原理与技术讲义5e.g.1算术表达式的计算器 产生式 翻译方案E

3、E1+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 2022/8/26编译原理与技术讲义6属性文法属性的分类若产生式AX1X2Xn，与之相关的属性计算规则b:=f(c1,c2,)如果属性b是产生式左部符号左部符号A的属性的属性则称其为A的的综合属性；综合属性；如果属性b是产生式右部符号右部符号Xi的属性的属性则称其为Xi的继承属性；的继承属性；c1,c2,一般是产生式右部其它符号的(综合)属性或A的继承属性；固有属性：终结符仅有的属

4、性。如number.lex_val。通常由词法程序提供。2022/8/26编译原理与技术讲义7A.bX1.c1X2.c2X综合属性A.b的计算A的继承属性AX1.c1X2.c2继承属性Xk.b的计算A的继承属性Xk.bX属性依赖图2022/8/26编译原理与技术讲义8e.g.2 属性依赖图:345E.val=23E.val=3+E.val=20number.lex_val=3E.val=4E.val=5number.lex_val=4number.lex_val=52022/8/26编译原理与技术讲义9语义规则的计算方法分析树方法 为输入串建立分析树 由语义规则建立属性依赖图（没有属性循环依赖

5、的）对依赖图进行拓扑排序，得到属性计算次序 依次计算属性，得到“翻译”结果基于规则的方法 构造编译器时，事先对产生式的语义规则进行分析，得到属性计算次序忽略规则的方法 属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。2022/8/26编译原理与技术讲义10e.g.3 属性计算次序:345E.val=23E.val=3+E.val=20number.lex_val=3E.val=4E.val=5number.lex_val=4number.lex_val=5123456782022/8/26编译原理与技术讲义11S-属性定义语义规则仅包含综

6、合属性计算（可以有固有属性出现）。适合自底向上计算e.g.语法树语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。2022/8/26编译原理与技术讲义12 S if B-expr then S1 else S2语法树 分析树语法树 vs.分析树if-then-elseB-exprS1S2Sif B-expr then S1else S22022/8/26编译原理与技术讲义13 a:=b*-c+b*-c 语法树 分析树 语法树 vs.分析树assigna+*bc*bcassignEEE+E*EbEEa赋值语句cE*EbEc算符2022/8/26编译原理与技术讲义

7、14DAG（去除了公共子表达式的无环有向图）a:=b*-c+b*-c 语法树 vs.DAGassigna+*bc*bcassigna+*bc语法树DAG2022/8/26编译原理与技术讲义15e.g.4 构造表达式的语法树（DAG）产生式 语义规则EE1+E2 E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1-E2 E.nptr:=mknode(-,E1.nptr,E2.nptr)EE1*E2 E.nptr:=mknode(*,E1.nptr,E2.nptr)EE1/E2 E.nptr:=mknode(/,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.

8、nptrE-E1 E.nptr:=mknode(,E1.nptr,)Enumber E.nptr:=mkleaf(NUM,number.lex_val)Eid E.nptr:=mkleaf(ID,id.entry)2022/8/26编译原理与技术讲义16e.g.4 构造表达式的语法树（DAG）E.nptr E的语法树（根结点指针）mknode(op,left,right)建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。如果建成DAG，则需要检查是否已存在相应内部结点op，其左右运算对象分别是left和right。若没有则新建一个。mkleaf(NU

9、M,number.lex_val)mkleaf(ID,id.entry)建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。2022/8/26编译原理与技术讲义17e.g.4 构造表达式a+b*-4的属性结构树 E.nptrE.nptrE.nptr+E.nptrE.nptr*abE.nptr4ID aID bNUM4 -*+2022/8/26编译原理与技术讲义18e.g.4 构造表达式a+b*-4的语法树（DAG）+ID a*ID b -NUM42022/8/26编译原理与技术讲义19L-属性定义如果产生式AX1X2Xn 的语义规则只计算1）A的综合属性，或者2）Xi的继承属性，且该属

10、性仅依赖于产生式右部Xi的左边符号Xj（ji）的（综合）属性或A的继承属性；S-属性定义均为L-属性定义可按深度优先次序计算 一种自然的属性计算次序 在分析期间完成翻译。属性计算与结点建立有联系；适合于自顶向下和自底向上分析方法。2022/8/26编译原理与技术讲义20深度优先次序procedure dfvisit(n:node)beginfor each child m of n,from left to right do begin evaluate inherited attributes of m;dfvisit(m);end;evaluate synthesized attribut

11、es of n;end2022/8/26编译原理与技术讲义21e.g.5 非L-属性定义的语法制导定义产生式语义规则ALML.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)AQRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)2022/8/26编译原理与技术讲义22翻译方案中的动作语义动作可放在产生式右端任何位置；这也就显式地给出了动作的执行时刻。（可认为是在深度优先遍历中的执行时刻）e.g.6将含有+和-运算的中缀表达式翻译为后缀形式：ET RR addop T print(addop.lex_val)R|T number print(number.lex_

12、val)2022/8/26编译原理与技术讲义23e.g.6 中缀翻译为后缀：9-4+5ETR9print(9)-Tprint(-)R4print(4)+Tprint(+)5print(5)R123452022/8/26编译原理与技术讲义24翻译方案中的动作设计翻译方案时，必须保证动作所引用的属性值是可用的。只有综合综合属性时（S-属性定义），动作放在产生式末尾；若有继承属性时，动作的放置须保证：（产生式右部）符号的继承属性必须在此符号前计算；动作不要引用其右边符号的综合属性；左部非终结符的综合属性一般放在产生式末 尾（确保它引用的属性均已计算完且可用）2022/8/26编译原理与技术讲义25e

13、.g.7 翻译方案的书写S A1 A2 A1.in:=1;A2.in:=2 A a print(A.in)改写为：S A1.in:=1 A1 A2.in:=2 A2 A a print(A.in)2022/8/26编译原理与技术讲义26e.g.8 类型说明的语法制导定义（0）产生式语义规则 DT L L.in:=T.type Tint T.type:=integer Treal T.type:=real LL1,id L1.in:=L.in addtype(id.entry,L.in)Lid addtype(id.entry,L.in)2022/8/26编译原理与技术讲义27e.g.8 类型说

14、明的语法制导定义（0）属性传递DTLL，kL，jiint2022/8/26编译原理与技术讲义28e.g.8类型说明的语法制导定义（1）改写上述类型声明文法，使得其中的T成为L的子结点（即产生式右部），可以避免继承属性的使用。修改后文法如下：DL Tint Treal LL1,id LT id2022/8/26编译原理与技术讲义29e.g.8类型说明的语法制导定义（2）产生式语义规则 D L Tint T.type:=integer Treal T.type:=real LL1,id L.in:=L1.in addtype(id.entry,L1.in)LT id addtype(id.entr

15、y,T.type);L.in:=T.type2022/8/26编译原理与技术讲义30e.g.8类型说明的语法制导定义（2）属性传递DTLL，kL，jiint2022/8/26编译原理与技术讲义31e.g.8 类型说明的语法制导定义（3）Pascal语言类型声明文法如下：DL:T Tint Treal LL1,id Lid该声明文法的“问题”在于，L中声明的变量的类型T处于产生式中L的右边！若用继承属性L.in来传递类型信息T.type形成非L属性定义。从而无法在完成L分析同时将有关类型信息填入符号表！可以可以考虑将考虑将T作为作为L的子结点（通过修的子结点（通过修改文法）来改变这种情况改文法）

16、来改变这种情况2022/8/26编译原理与技术讲义32e.g.8 类型说明的语法制导定义（4）产生式语义规则 D id L addtype(id.entry,L.in)Tint T.type:=integer Treal T.type:=real L,id L1 L.in:=L1.in addtype(id.entry,L1.in)L:T L.in:=T.type2022/8/26编译原理与技术讲义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)时，该翻译方案输出什么？2022/8/26编译原理与技术讲义34S-属性定义的自底向上计算拓广分析栈，即添加属性栈，包含文法符号的综合属性。在归约实施前，右部各符号的综合属性（若有的话）已放在与符号位置对应的属性栈上，因此，可以先计算获得左部非终结符的综合属性。然后再归约，这时从分析栈中弹出句柄，（注意，此时改变栈顶注意，此时改变栈顶top即可即可）最后，将左部符号