编译原理与技术 语法制导翻译.ppt
《编译原理与技术 语法制导翻译.ppt》由会员分享,可在线阅读,更多相关《编译原理与技术 语法制导翻译.ppt(62页珍藏版)》请在三一文库上搜索。
1、2019/10/25,编译原理与技术讲义,1,编译原理与技术,语法制导翻译,2019/10/25,编译原理与技术讲义,2,语法制导翻译,属性文法 S-属性定义 L-属性定义 语法制导定义与翻译方案 自底向上翻译 S-属性定义自底向上计算 自底向上计算继承属性 自顶向下翻译,2019/10/25,编译原理与技术讲义,3,属性文法,属性文法(Attributed Grammar) 上下文无关文法+属性+属性计算规则 属性用来描述文法符号的语义特征,如 常量的“值”、变量的类型和存储位置等。 e.g. 二义性表达式文法G,非终结符E有属性E.val(表达式的值) EE + E | E * E | (
2、 E ) | number 属性计算规则(语义规则) 与产生式相关联的反映文法符号属性之间关系的“规则”,2019/10/25,编译原理与技术讲义,4,属性文法 语法制导定义(文法属性语义规则) 语义规则仅表明属性间“抽象”关系,不涉及具体翻译实现细节,如计算次序等。 翻译方案(文法属性语义动作) 语义规则即语义动作,可体现若干实现的细节。,2019/10/25,编译原理与技术讲义,5,e.g.1算术表达式的计算器,产生式 语法制导定义 EE1 + E2 E.val := E1.val + E2.val EE1 * E2 E.val := E1.val * E2.val E( E1 ) E.v
3、al := E1.val Enumber E.val := number.lex_val,2019/10/25,编译原理与技术讲义,6,e.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 ,2019/10/25,编译原理与技术讲义,7,属性文法,属性的分类 若产生式AX1X2Xn,与之相关的属性计算规则 b := f ( c1, c2, ) 如果属性b
4、是产生式左部符号A的属性则称其为A的综合属性; 如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性; c1, c2, 一般是产生式右部其它符号的(综合)属性或A的继承属性; 固有属性:终结符仅有的属性。如number.lex_val。通常由词法程序提供。,2019/10/25,编译原理与技术讲义,8,A.b,X1.c1,X2.c2,X,综合属性A.b的计算,A的继承属性,A,X1.c1,X2.c2,继承属性Xk.b的计算,A的继承属性,Xk.b,X,属性依赖图,2019/10/25,编译原理与技术讲义,9,e.g. 2 属性依赖图: 345,E. val = 23,E. val = 3
5、,+,E. val = 20,number. lex_val = 3,E. val = 4,E. val = 5,number. lex_val = 4,number. lex_val = 5,2019/10/25,编译原理与技术讲义,10,语义规则的计算方法,分析树方法 为输入串建立分析树 由语义规则建立属性依赖图(没有属性循环依赖的) 对依赖图进行拓扑排序,得到属性计算次序 依次计算属性,得到“翻译”结果 基于规则的方法 构造编译器时,事先对产生式的语义规则进行分析,得到属性计算次序 忽略规则的方法 属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时,在归约前计算。如YACC
6、中的语义动作。,2019/10/25,编译原理与技术讲义,11,e.g. 3 属性计算次序: 345,E. val = 23,E. val = 3,+,E. val = 20,number. lex_val = 3,E. val = 4,E. val = 5,number. lex_val = 4,number. lex_val = 5,1,2,3,4,5,6,7,8,2019/10/25,编译原理与技术讲义,12,S-属性定义,语义规则仅包含综合属性计算(可以有固有属性出现)。 适合自底向上计算 e.g. 语法树 语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语
7、法树。,2019/10/25,编译原理与技术讲义,13,S if B-expr then S1 else S2 语法树 分析树,语法树 vs. 分析树,if-then-else,B-expr,S1,S2,S,if,B-expr,then,S1,else,S2,2019/10/25,编译原理与技术讲义,14,a := b* -c + b * -c 语法树 分析树,语法树 vs. 分析树,assign,a,+,*,b,c,*,b,c,assign,E,E,E,+,E,*,E,b,E,E,a,赋值语句,c,E,*,E,b,E,c,算符,2019/10/25,编译原理与技术讲义,15,DAG(去除了公
8、共子表达式的无环有向图) a := b* -c + b * -c,语法树 vs. DAG,assign,a,+,*,b,c,*,b,c,assign,a,+,*,b,c,语法树,DAG,2019/10/25,编译原理与技术讲义,16,e.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
9、 := mknode(/,E1.nptr, E2.nptr) E( E1 ) E.nptr := E1.nptr E - E1 E.nptr := mknode(,E1.nptr, ) Enumber E.nptr := mkleaf(NUM,number.lex_val) Eid E.nptr := mkleaf(ID,id.entry),2019/10/25,编译原理与技术讲义,17,e.g.4 构造表达式的语法树(DAG),E.nptr E的语法树(根结点指针) mknode(op, left, right)建立一个表达式语法树结点,它的运算符为op,左、右运算对象是left和right
10、所指的语法树。如果建成DAG,则需要检查是否已存在相应内部结点op,其左右运算对象分别是left和right。若没有则新建一个。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry) 建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。,2019/10/25,编译原理与技术讲义,18,e.g.4 构造表达式a+b*-4的属性结构树,E.nptr,E.nptr,E.nptr,+,E.nptr,E.nptr,*,a,b,E.nptr,4,2019/10/25,编译原理与技术讲义,19,e.g.4 构造表达式a+b*-4的语法树(DAG),2019/1
11、0/25,编译原理与技术讲义,20,L-属性定义,如果产生式AX1X2Xn 的语义规则只计算 1)A的综合属性,或者 2)Xi的继承属性,且该属性仅依赖于产生式右部Xi的左边符号Xj(ji)的(综合)属性或A的继承属性; S-属性定义均为L-属性定义 可按深度优先次序计算 一种自然的属性计算次序 在分析期间完成翻译。属性计算与结点建立有联系;适合于自顶向下和自底向上分析方法。,2019/10/25,编译原理与技术讲义,21,深度优先次序,procedure dfvisit( n : node ) begin for each child m of n, from left to right d
12、o begin evaluate inherited attributes of m; dfvisit( m ) ; end; evaluate synthesized attributes of n; end,2019/10/25,编译原理与技术讲义,22,e.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),2019/10/25,编译原理与技术讲义,23,翻译方案中的动作,语义动作可放在产生式右端任何位
13、置;这也就显式地给出了动作的执行时刻。(可认为是在深度优先遍历中的执行时刻) e.g. 6将含有+和-运算的中缀表达式翻译为后缀形式: ET R R addop T print( addop.lex_val) R | T number print( number.lex_val) ,2019/10/25,编译原理与技术讲义,24,e.g. 6 中缀翻译为后缀 :9-4+5,E,T,R,9,print(9),-,T,print(-),R,4,print(4),+,T,print(+),5,print(5),R,1,2,3,4,5,2019/10/25,编译原理与技术讲义,25,翻译方案中的动作,
14、设计翻译方案时,必须保证动作所引用的属性值是可用的。 只有综合综合属性时(S-属性定义),动作放在产生式末尾; 若有继承属性时,动作的放置须保证: (产生式右部)符号的继承属性必须在 此符号前计算; 动作不要引用其右边符号的综合属性; 左部非终结符的综合属性一般放在产生式末 尾(确保它引用的属性均已计算完且可用),2019/10/25,编译原理与技术讲义,26,e.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 ) ,
15、2019/10/25,编译原理与技术讲义,27,e.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),2019/10/25,编译原理与技术讲义,28,e.g.8 类型说明的语法制导定义(0) 属性传递,D,T,L,L,,,k,L,,,j,i,int,2019/10/25,编译原理与技术讲义,29,e.g.8类型说明
16、的语法制导定义(1),改写上述类型声明文法,使得其中的T成为L的子结点(即产生式右部),可以避免继承属性的使用。修改后文法如下: DL Tint Treal LL1 , id LT id,2019/10/25,编译原理与技术讲义,30,e.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.entry, T.type); L.in := T.type,2019/10/2
17、5,编译原理与技术讲义,31,e.g.8类型说明的语法制导定义(2) 属性传递,D,T,L,L,,,k,L,,,j,i,int,2019/10/25,编译原理与技术讲义,32,e.g.8 类型说明的语法制导定义(3),Pascal语言类型声明文法如下: DL : T Tint Treal LL1 , id Lid,该声明文法的“问题”在于,L中声明的变量的类型T处于产生式中L的右边!若用继承属性L.in来传递类型信息T.type形成非L属性定义。从而无法在完成L分析同时将有关类型信息填入符号表!可以考虑将T作为L的子结点(通过修改文法)来改变这种情况,2019/10/25,编译原理与技术讲义,
18、33,e.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.type,2019/10/25,编译原理与技术讲义,34,e.g.9 翻译方案的计算次序,EE+T print( “1” ) ET print( “2” ) TT*F print( “3” ) TF print( “4” ) F(E) print( “5”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理与技术 语法制导翻译 编译 原理 技术 语法 制导 翻译
链接地址:https://www.31doc.com/p-4175526.html