ch6 语义分析和中间代码生成.ppt

第六章属性文法 第六章语义分析与中间代码生成 6 1语义分析的任务6 2语法制导翻译6 2 1属性文法的定义6 2 2基于属性文法的处理方法6 2 3S 属性文法的自下而上计算6 2 4L 属性文法和自顶向下翻译 6 3中间代码生成 6 1语义分析的任务 源程序经过词法分析 语法分析后 表明该源程序书写正确 符合程序语言所规定的语法 但语法分析并未对程序内部的逻辑含义加以分析 因此编译程序接着进行语义分析 即审查每个语法成分的静态语义 如果静态语义正确 则生成与该语言成分等效的中间代码 或直接生成目标代码 6 1语义分析的任务 语义分析进行的语义检查有两类 动态语义检查和静态语义检查 动态语义检查需生成相应的目标代码 在运行时进行 静态语义检查在编译时进行 6 1语义分析的任务 静态语义检查涉及以下几个方面 1 类型检查 如运算操作数的类型应相容 2 控制流检查 用以保证控制语句有合法的转向点 如C语言中不允许goto语句转入case语句流 break语句需寻找包含它的最小switch while或for语句方可找到转向点 3 一致性检查 如在相同作用域中标识符只能说明一次 6 2语法制导翻译 程序语言的词法和语法结构可分别用正规式和上下文无关文法来描述 已建立成熟的形式化描述方法 由于语义是上下文有关的 因此语义的形式化描述非常困难 目前较常见的是用属性文法作为描述语义的工具 并采用语法制导翻译法完成对语法成分的翻译 该方法在语法分析的同时进行语义分析 6 2 1属性文法的定义 要利用语法制导的翻译方法 就需要在一个上下文无关文法的基础之上赋予每个文法符号以一定的属性 并规定文法的每个产生式对相关属性的运算规则 这种附加了一组属性和运算规则的文法称为属性文法 例如 对一个算数表达式进行翻译 不仅要知道各个运算符的先后次序 而且还要知道表达式中各个变量和常量的数据类型 内存地址或值 哟啊知道中间结果存放的内存地址和值 这些信息被称为语义信息 也称为属性 6 2 1属性文法的定义 属性文法是在上下文无关文法的基础上为每个文法符号 终结符或非终结符 配备若干个相关的 值 称为属性 这些属性代表与文法符号相关的信息 例如它的类型 值 代码序列 符号表内容等等 属性和变量一样 可以进行计算和传递 依据则是语义规则 属性的表示 在属性文法中 文法符号X的属性t常用X t来表示 例如 X val X type X addr分别表示X的值 类型和地址 例如 对于算数表达式文法G E 如果只想计算表达式的值 则只需关心各文法符号的值属性 因此对每个非终结符都有一个整数值的属性 分别为E val T val F val i的属性为i lexval 其他终结符 都代表语义动作 将在语义规则中反映 E E T TT T F FF E i 语义规则的表示 一个产生式对应的语义规则是根据产生式所蕴涵的语义操作所建立的 并与语义分析的目标有关 例如文法G E 已表达式求值为目标构造各产生式的语义规则如下 E E T TT T F FF E i 语义规则 EE1 T ET TT1 F TF F E Fdigit E val E1 val T val E val T val T val T1 val F val T val F val F val E val F val digit lexval 产生式 6 2 2基于属性文法的处理方法 用属性描述语义信息 用语义规则描述属性间的关系 将语义规则与语法规则相结合 在语法分析的过程中通过执行语义动作 计算语义属性的值 从而完成预定的翻译工作 这就是语法制导翻译的思想 语法制导的定义 属性一般分为两类 综合属性和继承属性 简单的说 综合属性用于 自下而上 传递信息 而继承属性用于 自上而下 传递信息 语法制导的定义 综合属性 在语法树中 一个结点的综合属性的值由其子结点的属性值确定 因此 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 继承属性 在语法树中 一个结点的继承属性由此结点的父结点和 或兄弟结点的某些属性确定 用继承属性来表示程序语言结构中的上下文依赖关系很方便 语法制导的定义 在一个属性文法中 对应于每个产生式A 都有一套与之相关联的语义规则 每条语义规则的形式为 b f c1 c2 ck 这里f是一个函数 或者 1 b是A的一个综合属性并且c1 c2 ck是产生式右边文法符号的属性 2 b是产生式右边某个文法符号的一个继承属性并且c1 c2 ck是A或产生式右边任何文法符号的属性在这两种情况下 我们都说属性b依赖于属性c1 c2 ck 语法制导的定义 要特别强调的是 1 终结符只有综合属性 它由词法分析器提供 2 非终结符既可以有综合属性也可以有继承属性 但文法开始符号没有继承属性 例6 1台式计算器程序的语法制导定义 产生式语义规则 L Enprint E val E E1 TE val E1 val T valE TE val T valT T1 FT val T1 val F valT FT val F valF E F val E valF digitF val digit lexval 每个文法符号和一个属性值val联系 属性值的设置和语法结构的语义以及翻译程序的需要有关 例如 把左例中的类型扩充到int和real 综合属性S 属性定义唯独只使用综合属性的语法制导定义 结点属性值的计算正好和自底向上分析建立分析树结点同步进行 上例中输入串为3 5 4n的带注释的语法树 每个节点的属性值都标注出来的分析树叫做注释分析树 digit lexval 3 F val 3 T val 3 digit lexval 5 F val 5 T val 15 E val 15 digit lexval 4 F val 4 T val 4 E val 19 输入 3 5 4n L EnE E1 TE TT T1 FT FF E F digit 例6 2 已知文法如下 构造个产生式的语义规则 将每个变量名及其类型信息填入符号表 产生式语义规则D TLL in T typeT intT type integerT realT type realL L1 idL1 in L inaddtype id entry L in L idaddtype id entry L in 表6 2带有继承属性L in的语法制导定义 上例文法定义了一种说明语句 该说明语句的形式由关键字int或real开头 后跟一个标识符表 每个标识符间有逗号隔开 非终结符号T有一个综合属性type 它的值由关键字int或real决定 与产生式D TL相联的语义L in T type将L in的属性值置为该说明语句指定的类型 属性L in将沿着语法树传递到下边的结点使用 与L产生式相联的规则里使用了它 过程addtype的功能是把每个标识符的类型信息登录在符号表中相关项中 下面给出句子realid1 id2 id3带注释的语法树 T type L in real L in i3 entry L in i2 entry i1 entry 基于属性文法的处理方法 从概念上讲 基于属性文法的处理过程通常是这样的 对单词符号串进行语法分析 构造语法分析树 然后根据需要遍历语法树 并在语法树的各结点处按语义规则进行计算 输入串 语法树 依赖图 语义规则计算次序 基于属性文法的处理方法 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法 语义规则的计算可能产生代码 在符号表中存放信息 给出错误信息或执行任何其它动作 对输入串的翻译也就是根据语义规则进行计算得出结果 依赖图 描述语法树中结点属性之间的相互依赖关系的有向图 为包含过程调用的语义规则引入一个虚综合属性b 这样把每个语义规则都写成b f c1 c2 ck 的形式 依赖图中为每一个属性设置一个结点 如果属性b依赖属性c 则从属性c的结点有一条有向边连到属性b的结点 例如 假设A a f X x Y y 是对应于产生式A XY的语义规则 这条语义规则确定了依赖于属性X x和Y y的综合属性A a 如果在语法树中应用这个产生式 那么在依赖图中会有三个结点A a X x 和Y y 由于A a依赖X x 所以有一条有向边从X x到A a 由于A a也依赖于Y y 所以还有一条有向边从Y y连到A a 如果与产生式A XY对应的语义规则还有 X i g A a Y y 那么 图中还应有两条有向边 一条从A a连到X i 另一条从Y y连到X i 因为X i依赖于A a和Y y 例6 3 当下面的产生式应用于语法树时 我们就把有向边加到依赖图中 产生式语义规则E E1 E2E val E1 val E2 val 例6 4 下页的图是例6 2带注释语法树的依赖图 如果一属性文法不存在属性之间的循环依赖关系 那么该文法为良定义的 为了设计编译程序 我们只处理良定义的属性文法 属性的计算次序一个有向非循环图 DAG 的拓扑序是图中结点的任何顺序m1 m2 mk 使得边必须是从序列中前面的结点指向后面的结点 也就是说 如果mi mj是mi到mj的一条边 那么在序列中mi必须出现在mj之前 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 从依赖图的拓扑排序中可以得到计算语义规则的顺序 用这个顺序来计算语义规则就得到输入符号串的翻译 例 上例中的一个拓扑排序可以从低序号到高序号顺序给出 从该拓扑排序可得到下列程序 a4 real a5 a4 addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7 addtype id1 entry a9 树遍历的属性计算方法设语法树已经建立起了 并且树中已带有开始符号的综合属性和终结符的综合属性 然后以某种次序遍历语法树 直至计算出所有属性 最常用的遍历方法是深度优先 从左到右的遍历方法 如果需要的话 可使用多次遍历 或称遍 一遍扫描的处理方法与树遍历的属性计算文法不同 一遍扫描的处理方法是在语法分析的同时计算属性值 而不是语法分析构造语法树之后进行属性的计算 而且并无需构造实际的语法树 如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话 所谓语法制导翻译法 直观上说是为文法中每个产生式配上一组语义规则 并且在语法分析的同时执行这些语义规则 在自上而下的语义分析中 若一个产生式匹配输入串成功 或者在自下而上分析中 当一个产生式被用于进行归约时 此产生式相应的语义规则就被计算 完成有关语义分析和代码生成的工作 6 3S 属性文法的自下而上计算 S 属性文法 只含有综合属性的属性文法 S 属性文法的翻译器可借助于LR分析器实现 在分析栈中使用一个附加的域来存放综合属性值 当第i个state对应的符号为A时 val i 中就存放语法树中与结点A对应的属性值 设当栈顶由指针top指示 我们假设综合属性是刚好在每次归约前计算的 假设语义规则A a f X x Y y Z z 是对应于产生式A XYZ的 在把XYZ归约成A以前 属性Z z的值放在val top 中 Y y的值放在val top 1 中 X x的值放在val top 2 中 如果一个符号没有综合属性 那么数组val中相应的元素就不定义 归约后 top值减2 A的状态存放在state top 中 也就是X的位置 综合属性A a的值存放在val top 中 例 下表台式计算器的属性文法 在自底向上分析输入串2 3 5n时 分析器在每次规约前执行表中的代码段 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 假定输入串为2 3 4n LR分析器的工作过程 步骤状态符号语义栈输入串 1 0 2 3 4 05 2 2 3 4 03 F 2 3 4 02 T 2 3 4 5 01 E 2 3 4 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 假定输入串为i i i LR分析器的工作过程 步骤状态符号语义栈输入串016 E 2 3 4 0165 E 3 2 3 4 0163 E F 2 3 4 0169 E T 2 3 4 10 01697 E T 2 3 4 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 假定输入串为i i i LR分析器的工作过程 步骤状态符号语义栈输入串016975 E T 4 2 3 4 01697 10 E T F 2 3 4 13 0169 E T 2 12 14 01 E 14 15 接受 L 属性文法 如果每个产生式A X1X2 Xn 其每个语义规则中的每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 产生式Xj的左边符号X1 X2 Xj 1的属性 2 A的继承属性 S 属性文法一定是L 属性文法 6 4L 属性文法和自顶向下翻译 例 请判断下表所示属性文法是不是L 属性文法 6 4 1翻译模式用属性文法计算时必须先确定计算的顺序 为了使用户从确定翻译顺序的工作中解脱出来 可以使用翻译模式 在翻译模式中 和文法符号相关的属性和语义规则用花括号 括起来 插入到产生式右部的合适位置上 这样翻译模式给出了使用语义规则进行计算的顺序 例 下例是一个翻译模式 它将带加号和减号的中缀表达式翻译成相应的后缀表达式 每个语义动作都作为相应产生式左部符号节点的儿子 我们把它看作是终结符 表示在什么时候应该执行那些动作 这样我们深度优先执行后得到后缀表达式95 2 左图是关于输入串9 5 2的语法树 如何建立翻译模式1 只有综合属性为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 例如 假设有下面的产生式和语义规则 产生式语义规则TT FT val T1 val F val建立其对应的翻译模式如下 TT F T val T1 val F val 2 既有综合属性又有继承属性 1 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 2 一个动作不能引用这个动作右边符号的综合属性 3 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算 计算这种属性的动作通常可放在产生式右端的末尾 例 6 4 2自顶向下翻译为使更多的文法可以使用自顶向下分析 采用消除基本文法左递归时 同时考虑属性计算的变换 例 带左递归的算术表达式的文法翻译模式E E1 T E val E1 val T val E E1 T E val E1 val T val E T E val T val T E T val E val T num T val num val 消除左递归后的翻译模式E T R i T val R E val R s R T R1 i R i T val R1 R s R1 s R T R1 i R i T val R1 R s R1 s R R s R i T E T val E val T num T val num val 对于自顶向下分析 我们假设动作是在处于相同位置上的符号被完全展开 匹配成功 时执行的 转换左递归翻译模式方法的一般化 设有下列翻译模式 A A1Y A a g A1 a Y y A X A a f X x 消除左递归后的翻译模式 A X R i f X x R A a R s R Y R1 i g R i Y y R1 R s R1 s R R s R i 消除左递归前 后的翻译模式等价 R s R i 中间语言 源程序的一种内部表示 不依赖目标机的结构 便于优化 便于移植 中间语言形式 后缀式 三地址代码 包括三元式 四元式 间接三元式 AST DAG图表示 6 5中间语言 6 5 1后缀式 逆波兰式 将运算对象写在前面 运算符写在后面 例 a b ab a b c ab c a b c abc a b c b d abc bd 一个表达式E的后缀形式可以如下定义 1 若E是变量或常量 则E1的后缀式是E 2 若E是E1opE2形式的表达式 则E的后缀式为E1 E2 op 其中E1 E2 分别为E1和E2的后缀式 3 若E是 E1 形式的表达式 则E1的后缀式就是E的后缀式 后缀表示法不需要括号 如 a b c表示为ab c 把表达式翻译成后缀式的语义规则描述 注 E code表示E的后缀表达式 op表示任意二元操作符 表示后缀形式的连接 例 把下述产生式定义的算术表达式映射到后缀波兰表示 确定输入a a a的输出 E E E T ET T T TT F T FT a T aT a T F aTF a F F aFF a a F aaF a a a aaa 后缀式的最大优点是易于计算机处理处理过程 利用一个栈 自左向右扫描逆波兰式 碰到运算对象 把它推进栈 碰到运算符 若是双目运算符 则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈 若是单目运算符 对栈顶元素 执行该运算 将运算结果代替该元素进栈 最后结果即栈顶元素 例 表达式 b c d的后缀式buminuscd 的计值过程 t1 b t2 c d t3 t1 t2 逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围例如 6 5 2图表示法图表示法包括 包括DAG和AST DFG 无循环有向图 与AST相同 DAG为每个子表达式设一个结点 内部结点代表操作符 孩子结点为操作数 DAG中公共子表达式结点具有多个父结点 而AST中公共子表达式表示为重复的子树 抽象语法树 语法树作为一种合适的中间语言形式 我们可以通过对它的遍历完成属性的计算 为了获得更有小的源程序中间表示 需要在语法树中去掉那些对翻译不必要的信息 这种经变换后的语法树称为抽象语法树 AST 表达式的语法树被定义为具有下述性质的一棵树 1 根与内部节点由表达式中的操作符或关键字标记 2 叶子由表达式中的操作数标记 3 用于改变运算优先级和结合性的括弧 被隐含在语法树的结构中 例如 句子 id id 和句型ifCthens1elses2 id id S ifCthenS1elseS2 例 画出a a b c b c d的抽象语法树 画出a b c b c 如何建立抽象语法树建立表达式的抽象语法树 我们通过为每个运算分量或运算符号都建立一个结点来为子表达式建立子树 抽象语法树中的每一个结点可以由包含几个域的记录来实现的 在一个运算符号对应的结点中 一个域标识运算符号 其它域包含指向运算分量的结点的指针 运算符号通常叫做这个结点的标号 当我们进行翻译时 抽象语法树中的结点可能会用附加域来存放结点的属性值 或指向属性的指针 用下列函数建立表示带有二目算符的表达式的抽象语法树中的结点 每个函数都返回一个指向新建立结点的指针 mknode op left right 建立一个运算符号结点mkleaf id entry 建立一个标识符结点mkleaf num val 建立一个数结点 建立抽象语法树的语义规则 例 下列函数调用建立表达式a 4 c的抽象语法树 p1 mkleaf id entrya p2 mkleaf num 4 p3 mknode p1 p2 p4 mkleaf id entryc id toentryforcid num4toentryforap5 mknode p3 p4 DFGDFG 无循环有向图 与AST相同 DAG为每个子表达式设一个结点 内部结点代表操作符 孩子结点为操作数 DAG中公共子表达式结点具有多个父结点 而AST中公共子表达式表示为重复的子树 抽象语法树有两种表达形式 6 5 3三地址代码一般形式为x yopz特点 每个语句的右边只有一个操作符 例 源程序语言表达式x y z可以被翻译为如下语句序列 T1 y zT2 x T1三地址码可以看成是DAG或AST的一种线性表示 例如 a b c b c的抽象语法树 T1 cT2 b T1T3 cT4 b T3T5 T2 T4a T5 AST的三地址码 a b c b c的DAG T1 cT2 b T1T5 T2 T2a T5 DAG的三地址码 三个地址 两个存放操作数 一个存放结果 三地址语句的种类 1 形如x yopz的赋值语句 其中op为二元算符或逻辑算符 2 形