语法制导翻译和中间代码生成 词法分析和语法分析之后的语义分析和中间 代码生成,是编译第三、四阶段的工作。本 章介绍几种典型的中间代码形式,以及产生 它的算法。 中间代码的形式很多,如逆波兰记号、树 形表示、三元式、四元式。他们都是介于 单词流与目标指令之间的“中间产品
词法分析和语法分析之后的语义分析和中间 代码生成,是编译第三、四阶段的工作。本 章介绍几种典型的中间代码形式,以及产生 它的算法。 中间代码的形式很多,如逆波兰记号、树 形表示、三元式、四元式。他们都是介于 单词流与目标指令之间的“中间产品”
困难 解决办法 目前还不存在一种广 为每一个产生式配一个 泛接受的方式来描述 翻译子程序(语义子程 为典型程序语言产生 序、动作),在语法分 中间代码所需的邻语 析的同时执行它。这样, 言的动作。原因是代 配上语义动作之后,既 码生成依赖于对语义 指定了串的意义,同时 的解释,而语义的刻 又按这种意义规定了生 划的形式化系统尚未 成某种中间代码应作的 诞生。 基本动作
目前还不存在一种广 泛接受的方式来描述 为典型程序语言产生 中间代码所需的邻语 言的动作。原因是代 码生成依赖于对语义 的解释,而语义的刻 划的形式化系统尚未 诞生。 为每一个产生式配一个 翻译子程序(语义子程 序、动作),在语法分 析的同时执行它。这样, 配上语义动作之后,既 指定了串的意义,同时 又按这种意义规定了生 成某种中间代码应作的 基本动作
基本思想 是对上下文无关文法的一种扩充。对文法中的每一产生式 都附加一个“语义动作”或“语义子程序”,且在分析的 过程中,每当需要使用一个产生式进行推导(自上向下的 分析)或进行归约(自下而上的分析)时,语法分析程序 除执行相应的语法分析动作之外,同时也调用相应的语义 子程序,每一语义子程序都指明了相应产生式中各个符号 的具体含义,并确定了用该产生式进行分析时所采取的语 义动作(如传送信息、查填符号表、计算值以及产生中间 代码等)
基本思想 是对上下文无关文法的一种扩充。对文法中的每一产生式 都附加一个“语义动作”或“语义子程序”,且在分析的 过程中,每当需要使用一个产生式进行推导(自上向下的 分析)或进行归约(自下而上的分析)时,语法分析程序 除执行相应的语法分析动作之外,同时也调用相应的语义 子程序,每一语义子程序都指明了相应产生式中各个符号 的具体含义,并确定了用该产生式进行分析时所采取的语 义动作(如传送信息、查填符号表、计算值以及产生中间 代码等)
本章内容 ●属性文法 ●语法制导翻译 ·逆波兰表示法 ●三元式和树 ●四元式 ●简单算术表达式和赋值句到四元式的翻译 ●布尔表达式到四元式的翻译 ●控制语句的翻译 ●数组元素的引用 ●说明语句的翻译 ●自上而下分析制导翻译概说
⚫属性文法 ⚫语法制导翻译 ⚫逆波兰表示法 ⚫三元式和树 ⚫四元式 ⚫简单算术表达式和赋值句到四元式的翻译 ⚫布尔表达式到四元式的翻译 ⚫控制语句的翻译 ⚫数组元素的引用 ⚫说明语句的翻译 ⚫自上而下分析制导翻译概说
※回顾※ 语义分析是王什么的? 其任务是对语法分析所识别出的各类语法范畴,分析 其含义,并进行初步翻译。 包括两个方面的工作。 首先是对各种语法范畴进行静态语义检查,例如,变 量是否定义、类型是否正确等等。 如果语义正确,则进行中间代码的翻译。 ÷为什么我们需要属性文法? 因为语义分析依循的是语言的语义规则,通常使用属 性文法描述语义规则
※回顾※ ❖ 语义分析是干什么的? 其任务是对语法分析所识别出的各类语法范畴,分析 其含义,并进行初步翻译。 包括两个方面的工作。 首先是对各种语法范畴进行静态语义检查,例如,变 量是否定义、类型是否正确等等。 如果语义正确,则进行中间代码的翻译。 ❖ 为什么我们需要属性文法? 因为语义分析依循的是语言的语义规则,通常使用属 性文法描述语义规则
8.1 属性文法的基本概念 属性文法: (也称属性翻译文法)是Kunth在1968年首先提出的。 它是在上下文无关文法的基础上,为每个文法符号(终结 符或非终结符)配备若干相关的“值”(称为属性)。这 些属性代表与文法符号相关信息,例如它的类型、值、代 码序列、符号表内容等。属性与变量一样,可以进行计算 和传递。属性加工的过程即是语义处理的过程。 属性通常分为两类: 综合属性:“自下而上”传递信息 继承属性:“自上而下”传到信息
8.1 属性文法的基本概念 ① 属性文法: (也称属性翻译文法)是Kunth在1968年首先提出的。 它是在上下文无关文法的基础上,为每个文法符号(终结 符或非终结符)配备若干相关的“值”(称为属性)。这 些属性代表与文法符号相关信息,例如它的类型、值、代 码序列、符号表内容等。属性与变量一样,可以进行计算 和传递。属性加工的过程即是语义处理的过程。 属性通常分为两类: 综合属性: “自下而上”传递信息。 继承属性: “自上而下”传到信息
可以在复杂的处理(甚至编译程序的构造)之前确定属性。 例如,一个数的有效位数可以根据语言的定义确定(或者至少 给出一个最小值)。 属性也可以在程序执行期间才确定,如非常数)表达式 的值,或者动态分配的数据结构的位置。属性的计算及将计 算值与正在讨论的语言结构联系的过程称作属性的联编(bⅰ nding)。联编属性发生时编译执行过程的时间称作联编 时间(binding time)。不同的属性变化,甚至不同语言的相 同属性都可能有完全不同的联编时间。在执行之前联编的属 性称作静态的(static),而只在执行期间联编的属性是动 态的(dynamic)。对于编译程序编写者而言,当然对那 些在翻译时联编的动态属性感兴趣
可以在复杂的处理(甚至编译程序的构造)之前确定属性。 例如,一个数的有效位数可以根据语言的定义确定(或者至少 给出一个最小值)。 属性也可以在程序执行期间才确定,如(非常数)表达式 的值,或者动态分配的数据结构的位置。属性的计算及将计 算值与正在讨论的语言结构联系的过程称作属性的联编( b i n d i n g )。联编属性发生时编译/执行过程的时间称作联编 时间(binding time)。不同的属性变化,甚至不同语言的相 同属性都可能有完全不同的联编时间。在执行之前联编的属 性称作静态的( s t a t i c ),而只在执行期间联编的属性是动 态的( d y n a m i c )。对于编译程序编写者而言,当然对那 些在翻译时联编的动态属性感兴趣
语义规则: 对于文法的每个产生式都配备了一组属性的计算规则。 在一个属性文法中,对应于每个产生式A一>α都有一套 与之相关语义规则,每条规则的形式为 b:=f(c1,c2,...,ck) 这里,是一个函数 > b是A的一个属性,并且cL,c2,.,ck是产生式右边文法符号 的属性;或者A的其他属性,则称b是A的综合属性: >b是产生式右边某个文法符号X的一个属性,并且c1,c2,.,ck 是A或产生式右边任何文法符号的属性,则称b是文法符号X的继承属性。 在这两种情况下,我们都说属性b依赖于属性c1,c2,.,ck
② 语义规则: 在一个属性文法中,对应于每个产生式A->α都有一套 与之相关语义规则,每条规则的形式为 b:= f(c1,c2,…,ck) 这里,f是一个函数 ➢ b是A的一个属性,并且c1,c2,…,ck是产生式右边文法符号 的属性;或者A的其他属性,则称b是A的综合属性; ➢ b是产生式右边某个文法符号X的一个属性,并且c1,c2,…,ck 是A或产生式右边任何文法符号的属性,则称b是文法符号X的继承属性。 在这两种情况下,我们都说属性b依赖于属性c1,c2,…,ck。 对于文法的每个产生式都配备了一组属性的计算规则
强调 终结符只有综合属性,它们由词法分析器提供; 非终结符既可以有综合属性也可有继承属性,文法开始符 号的所有继承属性作为属性计算前的初始值 ·对出现在产生式右边的继承属性和出现在产生式左边的综 合属性都必须提供一个计算规则 冬 出现在产生式左边的继承属性和出现在产生式右边的综合 属性不由所给的产生式的属性计算规则进行计算,它们由 其他产生式的属性计算规则或者由属性计算器的参数提供
强调 ❖ 终结符只有综合属性,它们由词法分析器提供; ❖ 非终结符既可以有综合属性也可有继承属性,文法开始符 号的所有继承属性作为属性计算前的初始值 ❖ 对出现在产生式右边的继承属性和出现在产生式左边的综 合属性都必须提供一个计算规则 ❖ 出现在产生式左边的继承属性和出现在产生式右边的综合 属性不由所给的产生式的属性计算规则进行计算,它们由 其他产生式的属性计算规则或者由属性计算器的参数提供
※例一必 考虑非终结符A,B和C,其中,A有一个继承属性a和一个综合属 性b,B有综合属性c,C有继承属性d。 产生式A一>BC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c 而属性Aa和B.c在其他地方计算
※例一※ 考虑非终结符A,B和C,其中,A有一个继承属性a和一个综合属 性b ,B有综合属性c ,C有继承属性d。 产生式A->BC可能有规则 C.d := B.c + 1 A.b := A.a + B.c 而属性A.a和B.c在其他地方计算