编译原理 课件chapter5.ppt

1 2 翻译的任务 首先是语义分析和正确性检查 若正确 则翻译成中间代码或目标代码 使用的方法称作语法制导翻译 基本思想是 1 根据翻译的需要设置文法符号的属性 以描述语法结构的语义 例如 一个变量的属性有类型 层次 存储地址等 表达式的属性有类型 值等 2 属性值的计算和产生式相联系 随着语法分析的进行 执行属性值的计算 完成语义分析和翻译的任务 3 属性值根据计算的依赖关系分成不相交的两类 综合属性 synthesizedattribute 和继承属性 inheritedattribute 在分析树中 一个结点的综合属性值是从其子结点的属性值计算出来的 而一个结点的继承属性值是由该结点兄第结点和父结点的属性值计算出来的 一般来说 语义翻译可按图5 1的流程处理 实际上 编译中语义翻译的实现并不是按图5 1的流程处理的 而是随语法分析的进展 识别出一个语法结构 就对它的语义进行分析和翻译 4 要求 随着语法分析 分析树逐步被构造出来 每构造一个子树 和这棵子树结点相联系的文法符号的属性值都可以根据已有结点属性值的计算出来的 一个重要的属性定义类称作 L 属性 定义 满足上述要求 5 输入符号串 分析树 依赖图 语义属性的计算 图5 1语法制导翻译概观 6 5 1语法制导定义 Syntax directeddefinitions 语法制导定义是对上下文无关文法的推广综合属性继承属性 依赖图语义规则建立了属性之间的依赖关系 这些关系可以用图来表示 这样的图称为依赖图 属性 7 5 1 1语法制导定义的形式在一个语法制导定义中 A P都有与之相关联的一套语义规则 规则形式为b f c1 c2 ck f是一个函数 而且或者1 b是A的一个综合属性并且c1 c2 ck是 中的符号的属性 或者2 b是 中的符号的一个继承属性并且c1 c2 ck是A或 中的任何文法符号的属性 在两种情况下 都说属性b依赖于属性c1 c2 ck 8 例5 1台式计算器程序的语法制导定义 表5 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 9 每个文法符号和一个属性值val联系 属性值的设置和语法结构的语义以及翻译程序的需要有关 例如 把例5 1中的类型扩充到int和real 5 1 2综合属性S 属性定义唯独只使用综合属性的语法制导定义 结点属性值的计算正好和自底向上分析建立分析树结点同步进行 例5 2输入 3 5 4n 10 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 L n 11 综合属性值的计算方法对于s 属性定义 通常使用自底向上的分析方法 在建立每一个结点处使用语义规则来计算综合属性值 即在用哪个产生式进行归约后 就执行那个产生式的s 属性定义计算属性的值 从叶结点到根结点进行计算 5 1 3继承属性继承属性值是由此结点的父结点和 或兄弟结点的某些属性值来决定的 例5 3变量说明的类性定义inta b c 12 表5 2带有继承属性L in的语法制导定义 产生式语义规则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 13 T L L id3 L id2 D id1 real 1entry 2entry 3entry 4type in5 6 in7 8 in9 10 14 5 1 4依赖图依赖图的构造方法for分析树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点 for分析树中每一个结点ndofor结点n所用产生式对应的每一条语义规则b f c1 c2 ck dofori 1tokdo从结点ci到结点b构造一条有向边 15 5 1 5计算顺序 拓扑排序一个有向非循环图的拓扑排序是图中结点的任何顺序m1 m2 mk 使得边必须是从序列中前面的结点指向后面的结点 也就是说 如果mi mj是mi到mj的一条边 那么在序列中mi必须出现在mj的前面 若依赖图中无环 则存在一个拓扑排序 它就是属性值的计算顺序 16 例5 6图5 5的拓扑排序是 1 2 3 4 5 6 7 8 9 10a4 real a5 a4 addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7 addtype id1 entry a9 17 计算语义规则的方法1 分析树法 输入串分析树依赖图计算次序2 基于规则的方法 在构造编译器时 用手工或专门的工具来分析语义规则 确定属性值的计算顺序 3 忽略语义规则的方法 在分析过程中翻译 那么计算顺序由分析方法来确定而表面上与语义规则无关 实际上 限制语法制导定义 使属性值的计算顺序能和语法分析过程同步进行 18 5 2语法树 syntaxtree 的构造 抽象语法 abstractsyntax 从具体语法中抽象出语言结构的本质性的东西 而不考虑语言的具体符号表示 从而可简化语义的形式描述 在不同的语言中赋值语句有不同的写法 x y x y y x等等 可以用抽象形式assignment variable expression 把前面各种具体形式统一起来 19 语法树表示程序层次结构的树 它把分析树中对语义无关紧要的成分去掉 是分析树的抽象形式 也称作语法结构树 或结构树 语法树是常用的一种中间表示形式 CSAGE 语法分析过程中完成翻译有许多优点 但也有一些不足 1 适于语法分析的文法可能不完全反映语言成分的自然层次结构 2 受语法分析方法限制 对分析树结点的访问序和翻译需要的访问序不一致 20 5 2 1语法树产生式S ifBthenS1elseS2的语法树if then else BS1S2赋值语句的语法树assignmentvariableexpression在语法树中 运算符号和关键字都不在叶结点 而是在内部结点中出现 21 5 2 2建立表达式的语法树建立表达式的语法树使用的函数 1 mknode op left right 建立一个运算符号结点 标号是op 两个域left和right指向运算分量结点的指针 2 mkleaf id entry 建立一个标识符结点 由标号id标识 一个域entry指向标识符符号表中相应的项 3 mkleaf num val 建立一个数结点 标号为num 域val用于存放数的值 返回新建立结点的指针 22 id toentrya num4 id toentryc 图5 6a 4 c的语法树 23 5 2 3建立语法树的语法制导定义 产生式语义规则E E1 TE nptr mknode E1 nptr T nptr E E1 TE nptr mknode E1 nptr T nptr E TE nptr T nptrT E T nptr E nptrT idT nptr mkleaf id id entry T numT nptr mkleaf num num val 24 id toentrya num4 id toentryc 图5 6a 4 c的语法树 25 1 每个非终结符号有一个语法树结点的指针属性 2 非终结符号归约未建立结点 5 2 4关于表达式的有向非循环图 有向非循环图 DirectedAcyclicGraph 简称dag 用途 提取表达式中的公共子表达式 以取得目标程序的局部优化 方法 执行mknode和mkleaf时 检查是否已有相同的结点 若有 则返回相应结点的指针 26 例5 9表达式a a b c b c d的dag d a c b 27 5 3S 属性定义及其自底向上的计算在分析栈中使用一个附加的域来存放综合属性值 下图为一个带有综合属性值域的分析栈 state val X X x Y Y y Z Z z top 28 A b f c1 c2 ck b是A的综合属性 ci 1 i k 是 中符号的属性 综合属性的值在自底向上的分析过程中 每步归约时 计算相应的属性值 A XYZA a f X x Y y Z z A a X xY yZ z 29 top state val X X x Y Y y Z Z z state val A A a top 定义式A a f X x Y y Z z 抽象 变成val ntop f val top 2 val top 1 val top 具体可执行代码 在执行代码段之前执行 ntop top r 1执行代码段后执行 top ntop r是句柄的长度 30 产生式代码段 和表5 1对比 L Enprintf val ntop E E Tval ntop val top 2 val top E TT T Fval ntop val top 2 val top T FF E val ntop val top 1 F digit 例5 10用LR分析器实现台式计算器 表5 4 31 表5 5翻译输入3 5 4n所做的移动 输入stateval使用的产生式 3 5 4n 5 4n33 5 4nF3F digit 5 4nT3T F 5 4nT 3 4nT 53 5 4nT F3 5F digit 32 4nT15T T F 4nE15E T 4nE 15 nE 415 4 nE F15 4F digit nE T15 4T F nE19E E T En19 L19L En 33 总结 采用自底向上分析 例如LR分析 首先给出S 属性定义 然后 把S 属性定义变成可执行的代码段 这就构成了翻译程序 象一座建筑 语法分析是构架 归约处有一个 挂钩 语义分析和翻译的代码段 语义子程序 就挂在这个钩子上 这样 随着语法分析的进行 归约前调用相应的语义子程序 完成相应的翻译任务 34 5 4L 属性定义在语法分析过程中进行语义分析和翻译 属性的计算顺序受到语法分析建立分析树结点顺序的限制 一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序 它适应多种自底向上和自顶向下的翻译方法 L 属性定义可用于按深度优先顺序计算属性值 35 深度优先顺序计算属性PROCEDUREdfvisit n node BEGINFORn的每个子结点m 从左至右DOBEGIN计算m的继承属性 dfvisit m END 计算n的综合属性END 36 5 4 1L 属性定义 定义一个语法制导定义是L 属性定义 如果 A X1X2 Xn P 其每一个语义规则中的每一个属性或是一个综合属性 或是Xj 1 j n 的一个继承属性 这个继承属性仅依赖于1 产生式中Xj的左边符号X1 X2 Xj 1的属性 2 A的继承属性 每一个S 属性定义都是L 属性定义 37 表5 6非L 属性的语法制导定义 产生式 语义规则 A LMA QR L i l A i M i m L s A s f M s R i r A i Q i q R s A s f Q s 表5 6的语法制导定义不是L 属性定义 文法符号Q的继承属性依赖于它右边文法符号R的属性 38 5 4 2翻译模式 定义翻译模式是语法制导定义的一种便于翻译的书写形式 其中属性与文法符号相对应 语义规则或语义动作用花括号 括起来 可被插入到产生式右部的任何合适的位置上 这是一种语法分析和语义动作交错的表示法 他表达在按深度优先遍历分析树的过程中何时执行语义动作 翻译模式给出了使用语义规则进行计算的顺序 可看成是分析过程中翻译的注释 39 例5 12一个简单的翻译模式E TRR addopT print addop lexeme R1 T num print num val 把语义动作看成终结符号 输入9 5 2 其分析树如图5 10 当按深度优先遍历它 执行遍历中访问的语义动作 将输出95 2 它是输入表达式9 5 2的后缀式 40 E T 9 T Pt 9 R Pt Pt R 5 Pt 5 T 2 Pt 2 R 图5 109 5 2的带语义动作的分析树 41 设计翻译模式 根据语法制导定义 条件 语法制导定义是L 属性定义保证语义动作不会引用还没有计算的属性值 1 只需要综合属性的情况 为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 例如 T T1 FT val T1 val F valT T1 F T val T1 val F val 42 2 既有综合属性又有继承属性产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 一个动作不能引用这个动作右边符号的综合属性 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算 计算这种属性的动作通常可放在产生式右端的未尾 43 下面的翻译模式不满足要求 S A1A2 A1 in 1 A2 in 2 A a print A in 例5 13从L 属性制导定义建立一个满足上面要求的翻译模式 使用文法产生的语言是数学排版语言EQN 里如 Esub1 val编排结果 E 1 val 44 B ps 10S ht B htB1 ps B psB2 ps B psB ht max B1 ht B2 ht B1 ps B psB2 ps shrink B ps B ht disp B1 ht B2 ht B ht text h B ps S BB B1B2B B1subB2B text 产生式 语义规则 表5 7盒子的大小和高度的语法制导定义 45 B是编排单元 B BB表示俩个编排单元的并置 B BsubB表示第二个编排单元是第一个编排单元的下标 ps是继承属性 影响编排单元的位置 text h可根据text的性质查表得到 shrink把B2的尺寸缩小30 disp把B2向下偏置 46 S B ps 10 B S ht B ht B B1 ps B ps B1 B2 ps B ps B2 B ht max B1 ht B2 ht B B1 ps B ps B1sub B2 ps shrink B ps B2 B ht disp B1 ht B2 ht B text B ht text h Bps 图5 12从表5 7构造的翻译模式 47 5 5自顶向下的翻译用翻译模式构造自顶向下翻译 5 5 1从翻译模式中消除左递归对于一个翻译模式 若采用自顶向下分析 必须消除左递归和提取左公因子 在改写基本文法时考虑属性值的计算 例5 14图5 13的带左递归的文法的翻译模式被转换成图5 14的带右递归的文法的翻译模式 48 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 图5 13带左递归的文法的翻译模式 49 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 图5 14经过转换的带有右递归文法的翻译模式 50 E val 6 T val 9 R i 9 R s 6 9 T val 5 5 R i 4 R s 6 T val 2 R i 6 R s 6 2 图5 15表达式9 5 2的计算 51 关于左递归翻译模式的一般化讨论左递归翻译模式A A1Y A a g A1 a Y y A X A a f X x 5 2 每一个文法符号都有一个综合属性 用相应的小写字母表示 g和f是任意函数 消除左递归 文法转换成A XRR YR 5 3 52 再考虑语义动作 翻译模式变为 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 5 4 经过转换的翻译模式与图5 14中一样 使用R的继承属性i和综合属性s 5 2 和 5 4 的结果是一样的 为什么 53 A a g g f X x Y1 y Y2 y A a g f X x Y1 y A a f X x Y2 Y1 X a 输入 XY1Y2 54 A R i f X x R i g f X x Y1 y R i g g f X x Y1 y Y2 y Y2 Y1 X b 55 例5 15表达式建立语法树的翻译模式 E E1 T E nptr mknode E1 nptr T nptr E E1 T E nptr mknode E1 nptr T nptr E T E nptr T nptr 从翻译模式中消除左递归 变成图5 17的翻译模式 56 E T R i T nptr R E nptr R s R T R1 i mknode R i T nptr R1 R s R1 s R T R1 i mknode R i T nptr R1 R s R1 s R R s R i T E T nptr E nptr T id T nptr mkleaf id id entry T num T nptr mkleaf num num val 57 使用继承属性构造语法树 E i R s T id R T num i R T id id num4 id toentryfora toentryforc nptr nptr nptr 58 5 5 2预测翻译器的设计算法5 1预测语法制导翻译器的建立输入 一个带有适合预测分析的基础文法的语法制导翻译模式 输出 一个语法制导翻译器的代码 方法 在预测分析器中加入语义动作代码 1 A VN 建立一个可递归调用的函数过程A 为A的每一个继承属性都设置一个形式参数 函数的返回值是A的综合属性值 2 函数过程A的代码 指用符号形式表示的数据和程序 要根据当前的输入符号来决定使用哪一个产生式 59 3 与每一个产生式有关的代码 从左到右根椐产生式右部是单词符号 非终结符号还是语义动作 分别是 a 对于带有综合属性x的单词符号X x存放在X x中 Match X b 对于B VN 编写一个赋值语句c B b1 b2 bk 其中 b1 b2 bk是继承属性 c是综合属性 c 对于每个动作 把动作的代码抄进翻译器中 用代表属性的变量来代替对属性的每一次引用 60 例5 16 R addopT R1 i mknode addop lexeme R i T nptr R1 R s R1 s R R s R i 5 5 递归下降构造语法树functionR in syntax tree node syntaX tree node varnptr i1 s1 s syntax tree node addoplexeme char 61 IFlookahead addopTHEN 产生式R addopTR addoplexeme lexval match addop nptr T i1 mknode addoplexeme in nptr s1 R i1 s s1 ELSEs in 产生式R return s 62 5 8类型分析每个程序设计语言都有自己的类型机制 包括类型说明和使用 类型分析是编译器语义分析的重要组成部分 编译器首先根据类型说明 确定每一个变量和常量的类型 计算其使用存储空间的大小 从而建立其到存储空间的映射 进而 编译器要确定每个语言结构的类型 以完成下面的主要任务 1 判定重载算符 函数 在程序中代表是那一个运算 2 进行类型转换 3 对语言结构进行类型检查 63 5 8 1类型表达式5 8 1 1类型表达式定义语言结构的类型由类型表达式指称 类型表达式依赖于程序语言的类型体制 类型表达式或者是简单类型表达式 或者是构造符作用在类型表达式上得到的类型表达式 类型表达式的定义如下 1 类型名和基本类型是类型表达式 integer char real boolean是基本类型 所以它们是类型表达式 另外 void表示 无类型 type error表示 出错类型 它们也是类型表达式 64 2 类型构造符作用于类型表达式的结果仍然是类型表达式 类型构造符包括 a 数组构造符ARRAY 若T是类型表达式 则ARRAY I T 是类型表达式 b 笛卡儿乘积 若T1 T2是类型表达式 则T1 T2是类型表达式 且 是左结合 c 记录类型构造符RECORD 若有标识符N1 N2 Nn与类型表达式T1 T2 Tn 则RECORD N1 T1 N2 T2 Nn Tn 是一个类型表达式 它指称一个记录类型 65 d 指针类型构造符POINTER 若T是类型表达式 则POINTER T 是类型表达式 它指称一个指针类型 e 函数类型构造符 若D1 D2 Dn和R是类型表达式 则D1 D2 Dn R是类型表达式 其中 优先于 它指称从定义域类型D1 D2 Dn到值域类型R的映射 3 类型表达式中可出现类型变量 变量值是类型表达式 66 例5 23设有Pascal程序片段 TYPEstype RECORDname ARRAY 1 8 OFchar score integerEND VARtable ARRAY 1 50 OFstype p stype 则stype绑定的类型表达式RECORD name ARRAY 1 8 char score integer 和table绑定的类型表达式ARRAY 1 50 stype 和P绑定的类型表达式POINTER stype 67 例5 24设有下面的函数定义FUNCTIONf P1 T1 P2 T2 Pn Tn T BEGIN END 和f绑定的类型表达式T1 T2 Tn T例5 25在函数式语言中可如下定义恒等函数funf x xx可以是任何类型的语言结构 因此x可以是任何类型 f的类型表达式为 为类型变量 其值是任何类型表达式 68 类型表达式的表达方法1 树 内部结点是类型构造符 叶结点是基本类型 类型名或类型变量 例如 FUNCTIONf a b char integer char char pointer integer pointer integer char char 69 2 位串 对类型表达式作某些限制 例如 考虑由POINTER 和ARRAY作为构造符的类型表达式 Pointer t 表示指向类型为t的指针 freturns t 表示若干变元的函数 其中t为函数返回对象的类型 而函数变元的类型则存放在其它地方 ARRAY t 表示元素类型为t的数组 而数组元素的个数保存在其它地方 这样 构造符都成为一元算符 它们作用于基本类型形成的类型表达式有非常统一的结构 70 类型构造符编码pointer01array10freturns11基本类型编码boolean0000char0001integer0010real0011类型表达式编码char0000000001freturns char 0000110001pointer freturns char 0001110001array pointer freturns char 1001110001 71 5 8 1 2类型表达式的等价根据语言的类型体制和类型表达式的表示方法 分结构等价和名字等价 结构等价两个类型表达式结构等价 当且仅当它们完全相同 图5 30是测试两个类型表达式结构等价的算法 假设类型构造符仅有数组 笛卡儿积 指针和函数 这个算法递归地比较两个类型表达式的结构 FUNCTIONeq s t boolean BEGINIFs和t是相同的基本类型THENreturn true 72 ELSEIF s ARRAY s1 s2 and t ARRAY t1 t2 THENreturn eq s1 t1 andeq s2 t2 ELSEIF s s1 s2 and t t1 t2 THENreturn eq s1 t1 and eq s2 t2 ELSEIF s POINTER s1 and t POINTER t1 THENreturn eq s1 t1 ELSEIF s s1 s2 and t t1 t2 THENreturn eq s1 t1 andeq s2 t2 ELSEreturn false END 73 类型表达式中的名字类型可以命名 例如 TYPELink cell VARnext Link 5 9 Last Link P cell q r cell 所谓名字等价 是指两个等价类型有同一个名字 也就是说 两个类型名表示不同的类型 在结构等价中 在类型表达式中的所有名字被它们代表的类型表达式替换后 两个类型表达式等价即是结构等价 74 例5 26下面给出和声明 5 9 中的5个变量相联系的类型表达式 变量类型表达式nextLinklastLinkpPointer cell qPointer cell rPointer cell 在名字等价下 变量next和last有同样的类型 next和p的类型不相同 在结构等价下 所有五个变量都有同样的类型 75 不同的语言中 通过声明变量标识符和类型联系的规则是不同的 在解释这些规则时 结构等价和名字等价是两个有用的概念 例5 27在一些Pascal的实现中 用隐含的类型名和每个声明的变量标识符相联系 如果说明中出现没有名字的类型表达式 就建立一个隐含的类型名 TYPEVARLink cell next link np cell last link nqr cell p np q r nqr 76 典型的实现是构造一张类型图 每当遇到类型构造符和基本类型 就建立一个新结点 但要记住类型名所命名的类型表达式 在这种方法中 如果两个类型表达式用类型图中同样的结点表示 那么 它们等价 link pointer pointer pointer cell next last p q r 图5 31 77 类型表示中的环链表和树结构经常是递归定义的 它们的结点通常定义成一个记录 记录中含有指向同类型记录的指针 设链表中的结点含有一个整型信息和一个指向下一个结点的指针 实现链表的类型定义 TYPElink node node RECORDinfo integer next linkEND 78 类型表达式用图表示如下 Node record infointeger nextpointer node Node record next infointeger pointer a 无环 b 有环 79 5 8 2类型分析5 8 2 1变量标识符和类型表达式的绑定程序说明部分建立计算环境 其中说明了每个变量标识符以及与之绑定的类型 语法 5 10 是一个简单的程序语言语法 假设数组的下标从1开始 文法G P 产生式如下 5 10 P D ED D D id TT char integer ARRAY num OFT TE num id Emode E E E E E 80 语义分析程序首先处理类型说明 建立类型表达式 然后处理变量说明 建立变量和类型表达式的绑定 具体实现是把变量标识符的类型信息记录在其符号表的表项中 过程addtype id enery T type 完成这个任务 其翻译模式由图5 32给出 81 P D ED D DD id T addtype id enery T TYPE T char T type char T integer T type integer T T1 T type POINTER T1 type T ARRAY num OFT1 T type ARRAY num val T1 type 图5 32建立变量标识符和类型属性绑定的翻译模式 82 5 8 2 2类型检查借助于符号表中变量和类型属性的绑定信息 分析确定每个语言结构的类型表达式 类型检查是在编译时做的静态类型检查 表达式的类型检查检查对象之间类型是否满足相容条件 函数lookup e 取符号表中保存在条目e中的类型 E num E type integer E id E type lookup id entry E E1MODE2 E type IF E1 type integer AND E2 type integer THENintegerELSEtype error 83 E E1 E2 E type IF E2 type integer AND E1 type ARRAY s t THENtELSEtype error E E1 E type IFE1 type POINTER t THENtELSEtype error 图5 33表达式的类型检查的翻译模式语句的类型检查指派给语句的类型是基本类型void 如果在语句中发现类型错误 指派给语句的类型是type error 84 S id E S type IFid type E typeTHENvoidELSEtype error S IFETHENS1 S type IFE type booleanTHENS1 typeELSEtype error S WHILEEDOS1 S type IFE type booleanTHENS1 typeELSEtype error S S1 S2 S type IF S1 type void AND S2 type void THENvoidELSEtype error 图5 34检查语句类型的翻译模式 85 函数引用的类型检查对说明部分的分析 应该能知道被引用函