《 中间代码及其翻译》由会员分享，可在线阅读，更多相关《 中间代码及其翻译（41页珍藏版）》请在金锄头文库上搜索。
1、第 6 章 中间代码及其翻译,对语法分析后的语法单位要进行语义分析，包括两个阶段：(1)静态语义审查；(2)如果静态语义正确，生成中间代码。中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的：(1) 便于进行与机器无关的代码优化；(2) 使编译程序改变目标机更容易；(3) 使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,静态语义审查,. 作用：验证语法结构合法的程序是否真正有意义,. 包含的内容：,(1) 类型检查 条件表达式的类型是不是boolean型验证指针地址访问只作用于指针 函数必须有正确的参数个数
2、和参数类型 ,(2) 控制流检查 break语句是否有转向点 ,(3) 一致性检查 在相同作用域中标识符只能说明一次 ,第 6 章 中间代码及其翻译,源语言,目标语言,两小步,一大步,6.1 常用的中间代码形式6.2 几种语法成分的四元式设计6.3 语法制导翻译6.4 语法制导翻译器的实现,【内容提要】,6.1 常用的中间代码形式, 设有赋值语句：x=a*b+c 则：,(1) 逆波兰式: xab*c+=,(2) 四元式：,(3) 三元式：,(4) 语义树 ：, 简单比较，各有所长：,逆波兰式 简单 ；四元式 清楚 ；,三元式 节省 ；语义树 直观 。,或,.表达式的四元式设计,6.2 几种语法
3、成分的四元式设计,设 quat(E),res(E)分别为表达式E的四元式和结果变量。,(1) 方框内的三个定义式 ，为四元式翻译法则；,(2) 定义式中的为 E1E2 中最后运算的算符！,则：,【注】,其中：(运算符), i运算对象(变量或常量), quat(E)= quat(E), quat(i)= 空 , res(i)= i,q( res(E1) res(E2) ti ), 基本形式 q:( o1 o2 t ), quat(E1E2)= quat(E1) quat(E2),算符，对象1，对象2，结果,. 赋值语句的四元式设计,= quat(a * (b-c) , q( = res(E) _
4、 x ),= quat(b-c),q(* a res(b-c) t), q( = res(E) _ x),= quat( b-c ),q(* a res(b-c) t),q( = res(E) _ x ),q( - b c t),q( * a res(b-c) t),q( = res(E) _ x),顺序编码,(1) ( - b c t1 ),(2) ( * a t1 t2 ),(3) ( = t2 _ x),6.2 几种语法成分的四元式设计,语句标号为转向语句提供转入语句标识，二者用标号相关联。,. 转向语句与语句标号的四元式设计,则有四元式序列：,(1) ( gt _ _ i ),(11)
5、 ( = t2 _ x ),(10) ( / t1 c t2),(8) ( lb _ _ i ),(9) ( + a b t1 ),标号后面是语句,自行练习一下！,6.2 几种语法成分的四元式设计,. 条件语句的四元式设计,(1) 文法：S - if (E) S1 else S2 ,(2) 语义结构：,可选,(3) 四元式结构：,【注】 q1：当 res(E)=false 则转向S2入口四元式；,q2：无条件转向出口四元式；,q3：条件语句出口四元式。,6.2 几种语法成分的四元式设计, 中间代码设计示例：,【例6.3】 if(ab) x=a+b;,else y=a-b;, 四元式序列：,(1
6、) ( while (E) S,(2) 语义结构：,(3) 四元式结构：,【注】 q1：while 语句的入口四元式（提供转向E参照）；,q2：当 res(E)=false 转向出口四元式；,q3：while尾（兼循环转向 E ）四元式。,6.2 几种语法成分的四元式设计, 中间代码设计示例(续1)：,【例6.4】, 四元式序列：,(1) (wh _ _ _ ),(2) ( a c t2 ),(4) ( t1 t2 t3 ),(5) ( do t3 _ _ ),(6) ( + b c t4 ),(7) ( / t4 2 t5 ),(11) (we _ _ _ ),(8) ( = t5 _ x
7、),(9) ( - a 1 t6 ),(10) ( = t6 _ a ),自行练习！,6.3 语法制导翻译,6.3.1 属性文法,【定义】 属性文法是上下文无关文法在语义上的扩展，是一种接近形式化的语义描述方法，可定义为如下三元组：,其中：,G(文法)；V(属性集)；E(语义规则集)。,(1) 属性代表与文法符号相关的信息，这里主要指语义信息(类型、种类、值和值地址)；文法产生式中的每个文法符号都附有若干个这样的属性。,(2) 属性可以进行计算和传递，语义规则就是在同一产生式中，相互关联的属性求值规则。,(3) 属性分两类（按属性求值规则区分）：,综合属性：其值由子女属性值来计算(自底向上求值
8、)；,继承属性：其值由父兄属性值来计算(自顶向下求值)。,说明, 属性文法构造示例,【例6.5】 类型说明的属性文法,属性值,已知类型说明文法G(D)：,下述属性文法用于把类型值传递给相应变量；,文法符号 X 的类型属性；,属性求值规则,【注】可以看出，X.type 属性是继承属性。,variable, 属性文法构造示例 (续1)：,(1) 属性传递路线如,(2) 由此可见，如果用此属性文法进行语法分析，,再附加一些语义处理手段，那么，标识符a,b,c获得属性值int，同时填写符号表，是很容易办到的。, 属性文法构造示例 (续2)：,【例6.6】 算术表达式的属性文法,下述属性文法用于算术表达
9、式的求值运算：,return, 属性文法构造示例 (续3)：,根据算术表达式属性文法及其相应的属性求值规则，,属性传递、属性计算过程：,6.3.2 语法制导翻译技术,【定义】语法制导翻译(syntax_directed translations)是在语法分析过程中，随着分析(推导或归约)的逐步进展，每识别出一个语法结构，根据文法的每个规则所对应的语义子程序进行翻译的方法；核心技术是构造属性翻译文法 -,在原文法产生式中插入语义动作符号(翻译子程序)，借以指明属性文法中属性求值时机和顺序。, 以算术表达式文法为例，探讨属性翻译文法的构造！, 通俗地说，所谓语法制导翻译技术，是指：, 算术表达式四
10、元式属性翻译文法设计, 假定：SEM(m) - 语义栈(属性传递、赋值场所)；,(1) PUSH(i) 压栈函数(把当前 i 压入语义栈)；,则：,其中：,QTq - 四元式区；,语义栈次栈顶、栈顶, 算术表达式四元式属性翻译文法设计, 符号串 a*(b/c-d) 的分析(翻译)过程(推导法),E = T,= T*F GEQ(*),= T*(E) GEQ(*),= T*( E-T GEQ(-) ) GEQ(*),= T*( T-T GEQ(-) ) GEQ(*),= T*( T/F GEQ(/) -T GEQ(-) ) GEQ(*), 算术表达式四元式属性翻译文法设计,a,b,c,t2,执行过
11、程,a,a b,a t1 d,a b c,a,t1,d,(3) ( * a t2 t3 ),(2) ( - t1 d t2 ),(1) ( / b c t1 ),t3,a,根据符号串 a*(b/c-d) 的以上导出序列，去掉文法符号，可得四元式动作序列：,a push(a) *( b push(b) /c push(c) GEQ(/) -d push(d) GEQ(-) ) GEQ(*),. 赋值语句四元式翻译文法：,6.3.3 各种语句四元式翻译文法设计,S - v PUSH(v) = E ASSI(=) ;,. 标号、转向语句四元式翻译文法：,S - i PUSH(i) : LABEL(i
12、) S ; S - goto i GOTO(i) ;,. 条件语句四元式翻译文法：,6.3.3 各种语句四元式翻译文法设计(续1),S - if(R) IF(if) S; else EL(el) S IE(ie),(1) SEND( if, SEMm, _ , _ );,(2) POP;,R - E E GEQ(), GEQ() - 表达式四元式生成函数；,其中的 为当前匹配的关系算符。,需要回填, 属性翻译文法应用示例,【例6.7】 已知条件语句 if (ab) a=a+1;,通过语法制导分析(属性推导树)，写出动作序列：, 属性翻译文法应用示例(续1),根据以上四元式翻译的动作序列，四元式
13、生成过程：,a,a,b,a b,(1) ( while WH(wh) (R) DO(do) S WE(we);,(1) SEND( wh, _ , _ , _ );,(1) SEND( do, SEMm ,_ , _ );,【注】文法中的 R 为 关系表达式（见条件语句四元式翻译文法）。,(2) POP ;,需要回填,6.4 语法制导翻译器的实现,语法制导翻译器的结构，可描述为：,1.自顶向下属性翻译文法的要求：,(1) 原文法应满足自顶向下分析要求(如 LL(1)文法)；,(2) 属性是自顶向下可求值的；,(3) 动作符号可插入到产生式右部任何位置。,2.自底向上属性翻译文法的要求：,(1) 原文法应满足自底向上分析要求(如 LR( )文法)；,(2) 属性是自底向上可求值的；,(3) 动作符号只能位于产生式的最右端。,其中,6.4 语法制导翻译器的实现(续1),6.4.1 递归子程序法四元式翻译器构造,2. 属性翻译文法设计,3.递归子程序的扩展, 动作符号在哪，就在哪执行之；, 主控程序( Z - E )功能增加：初始化和结果输出。,6.4.1 递归子程序法四元式翻译器构造,return,6.4.1 递归子程序法四元式翻译器构造,return,【例6.8】a*(b/c)# 四元式递归子程序翻译过程:,
