编译原理 语法制导翻译和中间代码生成.ppt

1 一个源程序经过词法分析 语法分析之后 表明该源程序在书写上是正确的 也就是符合程序语言所规定的语法 但是语法分析并未对程序内部的逻辑含义加以分析 因此编译程序接下来的工作是语义分析 编译中的语义处理是指两个功能 第一 静态语义分析或静态审查 审查每个语法结构的静态语义 即验证语法结构合法的程序是否真正有意义 第二 翻译 如果静态语义正确 语义处理则要执行真正的翻译 即 或者将源程序翻译成程序的一种中间表示形式 中间代码 或者将源程序翻译成目标代码 第8章语法制导翻译技术和中间代码生成 2 类型检查 验证程序中执行的每个操作是否遵守语言的类型系统的过程 编译程序必须报告不符合类型系统的信息 控制流检查 控制流语句必须使控制转移到合法的位置 例如 在C语言中break语句使控制跳离包括该语句的最小while for或switch语句 如果不存在包括它的这样的语句 则就报错 一致性检查 在很多场合要求对象只能被定义一次 例如Pascal语言规定同一标识符在一个分程序中只能被说明一次 同一case语句的标号不能相同 枚举类型的元素不能重复出现等等 相关名字检查 有时 同一名字必须出现两次或多次 例如 Ada语言程序中 循环或程序块可以有一个名字 出现在这些结构的开头和结尾 编译程序必须检查这两个地方用的名字是相同的 名字的作用域分析 静态语义分析通常包括 3 中间代码 所谓中间代码 也称中间语言 是复杂性介于源程序语言和机器语言的一种表示形式 有的编译程序直接生成目标代码 有的编译程序采用中间代码 一般来说 快速编译程序直接生成目标代码 没有将中间代码翻译成目标代码的额外开销 但是为了使编译程序结构在逻辑上更为简单明确 常采用中间代码 这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理 并且可以在中间代码一级进行优化工作使得代码优化比较容易实现 4 语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述 由于语义是上下文有关的 因此语义的形式化描述是非常困难的 虽然语义的形式化工作已经有相当的进展 但由于语义的复杂性 使得语义分析不能像语法那样规范 到目前为止 语义的形式化描述并没有语法的形式化描述那样成熟 使得语义的描述处于一种自然语言的描述或者半形式化描述的状态 而没有基于数学抽象的形式化描述 就很难设计出基于数学模型的统一算法来实现语义分析器的自动生成 5 目前较为常见的是用属性文法作为描述程序语言语义的工具 并采用语法制导翻译的方法完成对语法成分的翻译工作 直观上讲 语法制导翻译法就是为每个产生式配上一个语义子程序 在语法分析过程中 在选用某个产生式的同时 执行该产生式所对应的语义子程序来进行翻译的一种办法 6 8 1属性文法1 文法的属性 属性是指与文法符号的类型和值等有关的一些信息 在编译中用属性描述处理对象的特征 例 判断变量X的类型是否匹配 要用X的数据类型来描述 判断变量X是否存在 要用X的存储位置来描述 而对变量X的运算 则要用X的值来描述 因此 语义分析阶段引入X的属性 如X type X place X val等来分别描述变量X的类型 存储位置以及值等不同的特征 7 2 属性文法 属性翻译文法 在上下文无关文法的基础上 为每个文法符号 终结符或非终结符 引入若干属性值 称为属性 这些属性代表与文法符号相关信息 属性可以是类型 值 代码序列 符号表内容 入口 等 属性可计算或传递 属性的加工过程即是语义处理的过程 对于文法的每个产生式都配备了一组属性的计算规则 称为语义规则 Knuth 克努特 在1968年首先提出属性文法 8 一个属性文法是一个三元组 A G V F 其中G表示一个上下文无关文法 V表示一个属性的有穷集 F表示属性的断言或谓词的有穷集 属性文法的形式定义 每个属性与某个文法符合X 终结符或非终结符 相关联 用 文法符合 属性 表示这种关联 每个断言与文法的某产生式相联 与一个文法规则相关联的断言也是这个文法规则式上定义的一组语义规则 9 例 一个简单表达式文法 E N 1 N 2 N 1 orN 2 N num true false可以得到关于类型检查的属性文法 E N 1 N 2 N 1 type intandN 2 type int E N 1 orN 2 N 1 type boolandN 2 type bool N num N type int N true N type bool N false N type bool 与每个非终结符N相连的有属性Type 要么是int 要么是bool 与非终结符E的产生式相联的断言指明 两个N的属性必须相同 10 输入串3 4的语法树 结点带有语义信息的语法树 11 综合属性用于 自下而上 传递信息 综合属性由相应语法分析树中结点的分枝结点 即子结点 属性计算得到 其传递方向与继承属性相反 即沿语法分析树向上传递 从分枝结点到根结点 属性分类 继承属性与综合属性 12 设A X1X2 Xn为一个产生式 这种属性叫做综合 Synthesized 属性适应 归约分析自底向上按照语义规则来计算各结点的综合属性值 A s f c1 c2 ck c1 c2 ck是X1 X2 Xn的属性A s是从其子结点的属性值计算出来的 终结符只有综合属性 由词法分析器提供 产生式左部符号的某些属性根据其右部符号的属性或自己的其它属性计算而得 13 例8 1 简单算术表达式求值的属性文法 产生式语义规则 1 S Eprint E val 2 E E 1 TE val E 1 val T val 3 E TE val T val 4 T T 1 FT val T 1 val F val 5 T T 1 T val T 1 val 6 F E F val E val 7 F digitF val digit lexval 14 上面的一组产生式中 每一个非终结符都有一个属性val来表示整型值 如E val表示E的整型值 而digit lexval则表示digit的整型内部值 与产生式关联的每一个语义规则的左部符号E T F等的属性值的计算由其各自相应的右部符号决定 这种属性也称为综合属性 与产生式S E关联的语义规则是一个函数print E val 其功能是打印E产生式的值 S在语义规则中没有出现 可以理解为其属性是一个虚属性 15 3 5 4的注释分析树 16 2 继承属性用于 自上而下 传递信息 继承属性由相应语法树中结点的父结点属性计算得到 沿语法树向下传递 由根结点到分枝 子 结点 它反映了对上下文依赖的特性 继承属性可以很方便地用来表示程序语言上下文的结构关系 17 设A X1X2 Xn为一个产生式 这种属性叫做继承 Inherited 属性 B in f c1 c2 ck B为Xi c1 c2 ck是A X1 X2 Xn的属性 在分析树中 一个节点的继承属性值是由该节点的父节点和 或 兄弟节点的属性决定的 非终结符可有综合属性也可有继承属性 但文法开始符号没有继承属性 根据依赖关系决定计算顺序 即文法产生式右部符号的某些属性根据其左部符号的属性和右部的其它符号的某些属性计算而得 18 例8 2 描述说明语句中各种变量类型信息的语义规则 产生式语义规则 1 D TLL in T type 2 T intT type int 3 T floatT type float 4 L L 1 idL 1 in L in addtype id entry L in 5 L idaddtype id entry L in 过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中 19 非终结符T有一个综合属性type 其值为int或float 语义规则L in T type表示L in的属性值由相应说明语句指定的类型T type决定 属性L in被确定后将随语法树的逐步生成而传递到下边的有关结点使用 这种结点属性称为继承属性 由此可见 标识符的类型可以通过继承属性的复写规则来传递 20 例如 对输入串inta b 根据上述的语义规则 可在其生成的语法树中看到用 表示的属性传递情况 21 8 2语法制导翻译概述 现在很多编译程序采用语法制导翻译方法 这仍不是一种形式系统 但它是比较接近形式化的 这种方法以属性文法为工具来说明程序设计语言的语义 一个属性文法包含一个上下文无关文法和一系列语义规则 这些语义规则附在文法的每个产生式上 在语法分析过程中 完成这些语义规则描述的动作 从而实现语义处理 22 我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析 在编译的许多实际应用中 属性和断言以多种形式出现 也就是说 与每个文法符号相联的可以是各种属性 断言 以及语义规则 或者某种程序设计语言的程序段等等 23 语法制导翻译技术分为自底向上和自顶向下语法制导翻译 我们重点介绍自底向上语法制导翻译 假定有一个自下而上的LR分析器 我们可以把这个LR分析器的能力加以扩大 使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作 每个产生式的语义子程序执行之后 某些结果 语义信息 必须作为此产生式的左部符号的语义值暂时保存下来 以便以后语义子程序引用这些信息 24 作为一个例子 考虑下面的文法及语义动作所执行的程序 E E E E E E digit 25 1 为文法的规则设计相应的语义子程序 产生式语义子程序1 E E 1 E 2 E val E 1 val E 2 val 2 E E 1 E 2 E val E 1 val E 2 val 3 E E 1 E val E 1 val 4 E digit E val digit lexval 26 产生式语义动作1 E E 1 E 2 val TOP val TOP val TOP 2 2 E E 1 E 2 val TOP val TOP val TOP 2 3 E E 1 val TOP val TOP 1 4 E digitval TOP digit lexval 27 2 文法的LR分析表 28 此外 原LR分析器的分析栈也加以扩充 以便能够存放与文法符号相对应的语义值 这样 分析栈可以存放三类信息 分析状态 文法符号及文法符号对应的语义值 扩充后的分析栈如图所示 3 扩充分析栈 29 扩充分析栈工作的总控程序功能 使其在完成语法分析的同时也能完成语义分析工作 这时的语法分析栈已成为语义分析栈 即在用某一个规则进行归约之后 调用相应的语义子程序完成与所用产生式相应的语义动作 并将每次工作后的语义值保存在扩充后的 语义值 栈中 4 扩充总控程序的功能 30 算术表达式7 8 5 的语法树及各结点值 语义分析和计值过程 32 8 3中间语言 编译程序所使用的中间代码有多种形式 常见的有逆波兰记号 三元式 四元式和树形表示 33 8 3 1逆波兰式 后缀式 逆波兰记号是最简单的一种中间代码表示形式 早在编译程序出现之前 它就用于表示算术表达式 是波兰逻辑学家卢卡西维奇 Lukasiewicz 发明的 这种表示法将运算对象写在前面 把运算符号写在后面 比如把a b写成ab 把a b写成ab 用这种表示法表示的表达式也称做后缀式 34 后缀表示法表示表达式 其最大的优点是易于计算机处理表达式 常用的算法是使用一个栈 自左至右扫描算术表达式 后缀表示 每扫描到运算对象 就把它推进栈 扫描到运算符 若该运算符是二目的 则对栈顶部的两个运算对象实施该运算 并将运算结果代替这两个运算对象而进栈 若是一目运算符 则对栈顶元素执行该运算 并以运算结果代替该元素进栈 最后的结果留在栈顶 35 例 逆波兰式ab c 的处理 a b T1 T1 c T2 36 逆波兰式的形式定义 37 后缀表示中 操作数出现的顺序与原来一致 而运算符则按运算先后的顺序放入相应的操作数之后 即运算符先后的顺序发生了变化 这种表示已不再需要用括号来规定运算的顺序了 后缀表示中的计值用栈实现非常方便 一般的计值过程是自左至右扫描后缀表达式 每碰到运算量就把它推进栈 每碰到K目运算符就把它作用于栈顶的K个运算量 并用运算的结果 即一个运算量 来取代栈顶的K个运算量 38 例 39 只要遵守运算对象后直接紧跟它们的运算符的规则即可 逆波兰表示很容易扩充到表达式以外的范围 比如 把转语句GOTOL写为 Ljump 运算对象L为语句标号 运算符jump表示转到某个标号 比如 条件语句ifEthenS1elseS2可表示为 ES1S2 把ifthenelse看成三目运算符 用 来表示 又如 数组元素A 下标表达式1 下标表达式n 可表示为 下标表达式1 下标表达式2 下标表达式n Asubs 运算符Subs表示求数组的下标 40 8 3 2三元式和树形表示1 三元式 每个三元式由三个主要部分和一个序号组成 i op arg1 arg2 其中 算符op 第一运算对象arg1和第二运算对象arg2 运算对象可能是源程序中的变量 也可能是某个三元式的结果 用三元式的编号表示 三元式出现的先后次序与表达式的计算顺序一致 对于一目算符op 只需选用一个运算对象 不妨规定只用arg1 至于多目算符 可用若干个相继的三元式表示 41 例 表达式A B c的三元式表示 1 B 是单目运算符 使B取反 2 1 C 3 A 2 42 例 a b c b d的三元式表示 1 b c 2 b d 3 1 2 4 3 a 与后缀式不同 三元式中含有对中间计算结果的显式引用 比如三元式 1 表示的是b c的结果 三元式 3 中的 1 和 2 分别表示第一个三元式和第二个三元式的结果 43 在三元式表示中 每个语句的位置同时有两个作用 一是可作为该三元式的结果被其它三元式引用 二是三元式位置顺序即为运算顺序 三元式的序号 在代码优化阶段 调整三元式的运算顺序时会遇到困难 这是因为三元式中的arg1 arg2也可以是指向某些三元式位置的指针 当这些三元式的位置顺序发生变化时 含有指向这些三元式位置指针的相关三元式也需随之改变指针值 因此 变动一张三元式表是很困难的 44 2 树形表示 抽象语法树也称图表示 是一种较为流行的中间语言表示形式 在抽象语法树表示中 每一个叶结点都表示诸如常量或变量这样的运算对象 而其它内部结点则表示运算符 45 一个表达式中的简单变量或常量的树形表示就是该变量或常量自身 如果e1和e2的树分别为E1 E2 则 e1 e1 e2 e1 e2的树形表示如下 E1 E1 E2 E1 E2 定义 46 多目运算符的树形表示 二目运算对应二叉子树 多目运算对应多叉子树 不过 为了便于安排存储空间 一棵多叉子树可以通过引进新结点而表示成一棵二叉子树 例如 条件语句ifEthenS1elseS2可以看成一个三目运算 运算符 定义为ifthenelse E S2 S1 E New S1 S2 引入一个新节点 使其转化为二叉树 47 8 3 3四元式和三地址代码 四元式是由四部分组成 i op arg1 arg2 result 其中 op为运算符 arg1 arg2为运算对象 result为运算结果 运算对象和运算结果可以是用户自己定义的变量也可以是编译程序引进的临时变量 我们约定 凡只需一个运算量的算符一律使用arg1 48 例 表达式 c和赋值语句X a的四元式 i C Ti j a X 49 例 表达式X a b c d的四元式 1 a b T1 2 c d T2 3 T1 T2 T3 4 T3 X 50 如果op是一个算术或逻辑运算符 则result总是一个新引进的临时变量 它用来存放运算结果 四元式出现的顺序与表达式计值的顺序是一致的 四元式之间的联系是通过临时变量实现的 四元式由于其表示更接近程序设计的习惯而成为一种普遍采用的中间代码形式 51 三地址代码的形式 三地址代码语句的一般形式为X aopb其中 X a和b为变量或编译时产生的临时变量 a b还可以为常量 op为运算符 如浮点算符和逻辑运算符等 三地址代码的每条语句通常包含三个地址 两个用来存放运算对象 一个用来存放运算结果 在实际实现中 用户定义的名字将由指向符号表中该名字项的指针所取代 52 由于三地址语句只含有一个运算符 因此多个运算符组成的表达式必须用三地址语句序列来表示 如表达式X a b c d的三地址代码为 1 T1 a b 2 T2 c d 3 T3 T1 T2 4 X T3 53 四元式 1 C D T1 2 B T1 T2 3 A T2 T3 4 C D T4 5 T4 N T5 6 E T5 T6 7 T3 T6 T7 三元式 1 C D 2 B 1 3 A 2 4 C D 5 4 N 6 E 5 7 3 6 举一个例子 用几种中间代码的形式来表示A B C D E C D N 54 8 4简单赋值语句的翻译 简单算术表达式是一种仅含简单变量的算术表达式 简单变量是指普通变量和常数 但不含数组元素及结构引用等复合型数据结构 简单算术表达式的计值顺序与四元式出现的顺序相同 因此很容易将其翻译成四元式形式 这些翻译方法稍加修改也可用于产生三元式形式 55 翻译一般采取的步骤 分析文法的特点 设置一系列语义变量 定义语义过程 语义函数 修改文法 写出每一规则的语义子程序 扩充LR分析栈 构造LR分析表 56 考虑以下文法G S S id EE E E E E E E id 非终结符S代表 赋值语句 文法G S 虽然是一个二义文法 但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生 为了实现由表达式到四元式的翻译 需要给文法加上语义子程序 以便在进行归约的同时执行对应的语义子程序 语义子程序所涉及的语义变量 语义过程及函数说明如下 57 语义子程序所涉及的语义变量 语义过程及函数说明 对非终结符E定义语义变量E place 即用E place表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码 定义语义函数newtemp 即每次调用newtemp 时都将回送一个代表新临时变量的整数码 临时变量名按产生的顺序可设为T1 T2 定义语义过程emit T arg1oparg2 emit的功能是产生一个四元式并填入四元式表中 定义语义函数lookup id name 其功能是审查id name是否出现在符号表中 是则返回id name在符号表的入口指针 否则返回nil 其中id name表示id代表的名字本身 58 文法G S 中的每一个产生式的语义子程序 1 S id E p lookup id name if p nil error elseemit p E place 2 E E 1 E 2 E place newtemp emit E place E 1 place E 2 place 3 E E 1 E 2 E place newtemp emit E place E 1 place E 2 place 4 E E 1 E place newtemp emit E place uminus E 1 place 5 E E 1 E place E 1 place 6 E id p lookup id name if p nil E place p elseerror 59 例 试分析赋值语句X B C D 的语法制导翻译过程 60 61 算术表达式和赋值语句中的类型检查 实际上 在一个表达式中可能会出现各种不同类型的变量或常数 而不是假定为都是同一类型 也就是说 编译程序还应执行这样的语义动作 对表达式中的运算对象应进行类型检查 如不能接受不同类型的运算对象的混合运算 则应指出错误 如能接受混合运算 则应进行类型转换的语义处理 约定 当两个不同类型的量进行运算时 必须首先将整型量转换为实型量 62 例 设x y为实型 i j为整型 则表达式x y i j的三地址码是 T1 iint jT3 inttorealT1T2 yreal T3x T2 为进行类型转换的语义处理 增加语义变量 用E type表示E的类型信息 E type的值或为int或为real 此外 为区别整型加 乘 和实型加 乘 把 分别写作int 和real 把 分别写作int 和real 用一目算符inttoreal表示将整型运算对象转换成实型 63 E E1 E2的带语义检查的三地址码的语义动作 E place newtemp ifE1 type intandE2 type intthenbeginemit E place E1 place int E2 place E type int endelseifE1 type realandE2 type realthenbeginemit E place E1 place real E2 place E type real endelseifE1 type intandE2 type realthenbeginu newtemp emit u inttoreal E1 place emit E place u real E2 place E type real endelseifE1 type realandE2 type intthenbeginu newtemp emit u inttoreal E2 place emit E place E1 place real u E type real endelseE type type error 64 8 5布尔表达式的翻译 有的语言 如PL 1 允许更通用的表达式 其中 对布尔运算 关系运算 算术运算的运算对象的类型可不区分布尔型或算术型 假定不同类型的变换工作将在需要时强制执行 65 优先级 关系运算符的优先级相同 其运算优先级低于任何算术运算符 布尔运算符的运算顺序一般为 且 和 服从左结合 布尔算符的运算优先级低于任何关系运算符 注意 此处的运算优先级约定不同于C语言 66 1 布尔表达式的翻译方法 布尔表达式的作用 1 计算逻辑值 2 用做改变控制流语句中的条件表达式 如在if then if then else 或是while do语句中那样 67 讨论下述文法G E 生成的布尔表达式 E E E E E E E i iropi 计算布尔表达式的值一般有两种方法 数值表示法 仿照算术表达式的计算 按照布尔表达式的运算顺序 步步计算出各部分的真假值 最后计算出整个表达式的值 假设逻辑值true用1表示 false用0表示采取某种优化措施 只计算部分表达式 例如要计算A B 若计算出A的值为1 那么B的值就无需再计算了 因为不管B的值为何结果 A B的值都为1 同理 在计算A B时若发现A值为0 则B值也无需计算 A B的值一定为0 68 上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的 但是 假若一个布尔式中含有布尔函数调用 并且这种函数调用引起副作用 如有对全局量的赋值 时 这两种方法未必等价 采用哪种方法取决于程序设计语言的语义 有些语言规定 函数过程调用应不影响这个调用处环境的计值 或者说 函数过程的工作不许产生副作用 在这种规定下 可以任选其中一种 副作用的考虑 69 数值表示法 布尔表达式1or 0andnot0 and1的计算过程是 1or 0andnot0 and1 1or 0and1 and1 1or0and1 1or0 1 70 布尔表达式a b c翻译成的四元式序列为 1 t1 c 2 t2 b t1 3 t3 a t2对于像a b这样的关系表达式 可看成等价的条件语句ifa bthen1else0 它翻译成的四元式序列为 1 ifa bgoto 4 2 t 0 3 goto 5 4 t 1 5 其中用临时变量t存放布尔表达式a b的值 5 为后续的四元式序号 例 71 数值表示法 nextstat给出输出序列中下一四元式序号 emit过程每被调用一次 nextstat增加1 E E1 E2 E place newtemp emit E place E1 place E2 place E E1 E2 E place newtemp emit E place E1 place E2 place E E1 E place newtemp emit E place E1 place E E1 E place E1 place E i1ropi2 E place newtemp emit if i1 placeropi2 place goto nextstat 3 emit E place 0 emit goto nextstat 2 emit E place 1 E id E place id place 72 例 根据数值表示法对布尔表达式a b c d e f翻译为三地址代码 100ifa bgoto103101T1 0102goto104103T1 1104ifc dgoto107105T2 0106goto108107T2 1108ife fgoto111109T3 0110goto112111T3 1112T4 T2 T3113T5 T1 T4 73 采取某种优化措施 用if then else来解释布尔运算 A B解释为ifAthenBelsefalseA B解释为ifAthentrueelseB A解释为ifAthenfalseelsetrue 74 2 控制语句中布尔表达式的翻译 现在讨论出现在ifthen ifthenelse和whiledo等语句中的布尔表达式E的翻译 这三种语句的语法为 S ifEthenS1S ifEthenS1elseS2S whileEdoS1这时表达式不仅仅是计算值 而且值还决定了程序控制流的转向 75 真 假 76 出现在语句ifEthenS1elseS2中的布尔表达式 它们的作用仅在于控制语句的选择 只要能够完成这个使命 E的值就无需最终保留在某个临时单元中 因此作为转移条件的布尔表达式E 可以赋予它两个 出口 一是 真 出口 它指向E为真时的指向 出向S1一是 假 出口 它指向E为假时的指向 出向S2 77 定义一组控制转向的四元式 1 ifEgotoLi 表示当E为真时 执行标号为Li的四元式 Li是布尔表达式E的 真 出口 2 ifE 1 ropE 2 gotoLi 表示当E 1 ropE 2 为真时 执行标号为Li的四元式 3 gotoLj 表示无条件转向标号为Lj的四元式 通常用来表示当E为假时程序流的转向 因此又称为 假 出口 78 例 语句ifa bthens 1 ifa bgotoLi 2 gotoLj 3 Li S的第一个四元式 79 分析语句ifa b cthenS1elseS2 1 ifa bgoto 5 2 goto 3 3 ifcgoto 5 4 goto p 1 5 关于S1的四元式序列 p goto q p 1 关于S2的四元式序列 q 后继四元式 5 是真出口 但在生成 1 和 3 时 这个值是未知的 p 1 是假出口 但在生成 4 时 这个值也是未知的 什么时候可以确定 真 出口这个值 什么时候可以确定 假 出口这个值 处理到then处理到else 80 语句whileEdoS 1 ifEgoto 3 2 goto p 1 3 关于S的四元式序列 p goto 1 p 1 后继四元式 p 1 是假出口 但在生成 2 时 这个值是未知的 81 在有多个因子组成的布尔表达式中 可能有多个因子的真出口和假出口的转移去向相同 但又不能立刻知道它们的具体转移位置 在这种情况下 需要把这些转移方向相同的四元式链在一起 一旦发现转移目标就可以回填 在生成用做控制条件的布尔表达式E时 就有两条链需要回填 1条是E的真出口 用E true表示1条是E的假出口 用E false表示 82 83 语句ifa b cthenS1elseS2的回填描述 1 ifa bgoto 0 E的一个真出口 有待回填 2 goto 3 回填E的第一个假出口 3 ifcgoto 1 3 是E的真出口链头 4 goto 0 E的一个假出口 有待回填 5 关于S1的四元式序列 此时回填真出口 p goto 0 有待回填 p 1 关于S2的四元式序列 此时回填假出口 q 后继四元式 此时回填q 1 E true E false 1 ifa bgoto 0 3 ifcgoto 1 4 goto 0 84 它应该有下面的代码序列 E 1 codeE 1 false E 2 code 考虑表达式E E 1 E 2 若E 1 为真 则立即知道E也为真 因此 E 1 的真出口也就是整个E的真出口 若E 1 为假 则E 2 必须被计值 此时E 2 的第一个四元式就是E 1 的假出口 当然 E 2 的真假出口也就是整个E的真假出口 E true E 1 true E 2 trueE false E 2 falseE 1 false E 2 第一个四元式 85 它应该有下面的代码序列 E 1 codeE 1 true E 2 code 考虑表达式E E 1 E 2 若E 1 为假 则立即知道E也为假 因此 E 1 的假出口也就是整个E的假出口 若E 1 为真 则E 2 必须被计值 此时E 2 的第一个四元式就是E 1 的真出口 当然 E 2 的真假出口也就是整个E的真假出口 E false E 1 false E 2 falseE true E 2 trueE 1 true E 2 第一个四元式 86 考虑表达式E E 1 若E 1 为假 则E为真 因此 E 1 的假出口是E的真出口 若E 1 为真 则E为假 因此 E 1 的真出口是E的假出口 E false E 1 trueE true E 1 false 87 需要的公共变量 过程 函数 四元式指针nextstat 始终指向下一条将要产生的四元式的地址 序号 其初值为1 每当执行一次emit语句后 nextstat自动增1 设置非终结符E的语义变量E codebegin 表示非终结符E的第一个四元式标号 回填过程Backpatch p t 把链首p所链接的每个四元式的第四区段 即result 都改写为地址t 链接函数merge p1 p2 把以p1和p2为链首的两条链合并为一条以p2为链首的链 即返回链首值p2 88 每个规则的语义子程序 1 E i E true nextstat E false nextstat 1 E codebegin nextstat emit ifi placegoto0 emit goto0 2 E i 1 ropi 2 E true nextstat E false nextstat 1 E codebegin nextstat emit ifi 1 placeropi 2 placegoto0 emit goto0 3 E E 1 E true E 1 true E false E 1 false E codebegin E 1 codebegin 4 E E 1 E true E 1 false E false E 1 true E codebegin E 1 codebegin 89 5 E E 1 E 2 Backpatch E 1 false E 2 codebegin E codebegin E 1 codebegin E true merge E 1 true E 2 true E false E 2 false 6 E E 1 E 2 Backpatch E 1 true E 2 codebegin E codebegin E 1 codebegin E true E 2 true E false merge E 1 fasle E 2 false 90 E E 1 E 2 的分析 当E 1 为假时 计算E 2 所以E 2 的第一个四元式地址E 2 codebegin回填为E 1 的假链值 Backpatch E 1 false E 2 codebegin 当E 1 为真时 无需计算E 2 应该去执行S1的第一个四元式 但此时尚未扫描到then 因此 保留E 1 true 若E 2 为真 其转移地址同E 1 所以将E 1 和E 2 回填真链E 1 true和E 2 true合并为一条链 E true merge E 1 true E 2 true 新链首作为E true的值 91 当E 1 为假时 计算E 2 E 2 也为假 此时 这个布尔表达式为假 E 2 false就是E false 尽管有两个变量E 1 和E 2 参加运算 但按扫描顺序 首先生成E 1 的四元式 因此E 1 的第一个四元式也就是整个布尔表达式的第一个四元式 所以E codebegin E 1 codebegin 92 例 表达式A B D的翻译 nextstat 1赋初值1 扫描到A 用E i进行归约 执行相应语义子程序 E true nextstat E false nextstat 1 E codebegin nextstat emit ifi placegoto0 emit goto0 E true 1 E false 2 E codebegin 1 四元式 1 ifAgoto0 2 goto0 nextstat的值为3 93 2 继续扫描 栈内符号串为E B D 栈顶形成句柄B D 用E i 1 ropi 2 进行归约 执行相应语义子程序 E true nextstat E false nextstat 1 E codebegin nextstat emit ifi 1 placeropi 2 placegoto0 emit goto0 E true 3 E false 4 E codebegin 3 四元式 3 ifB Dgoto0 4 goto0 nextq的值为5 94 3 继续归约 栈内符号串为E E 形成句柄 用E E 1 E 2 进行归约 执行相应语义子程序 Backpatch E 1 false E 2 codebegin E codebegin E 1 codebegin E true merge E 1 true E 2 true E false E 2 false E bcode 3 E true 3 E false 4 95 1 ifAgoto0 E 1 false 2 goto0 3 3 ifB Dgoto0 4 goto0 回填操作Backpatch E 1 false E 2 codebegin E 1 true 1 ifAgoto0 2 goto3 E 2 true 3 ifB Dgoto0 1 4 goto0 合并操作E true merge E 1 true E 2 true 这是翻译结果 96 8 4 3控制语句的翻译 在源程序中 控制语句用于实现程序流程的控制 一般程序流程控制可分为下面三种基本结构 1 顺序结构 一般用复合语句实现 2 选择结构 用if和case等语句实现 3 循环结构 用for while do 即repeat 等语句实现 97 控制语句的文法 考虑ifthen ifthenelse和whiledo语句文法G S 定义这些语句 G S 1 S ifEthenS 2 S ifEthenSelseS 3 S whileEdoS 4 S A 5 L L S 6 L S其中各非终结符号的意义是 S 语句L 语句串A 赋值句E 布尔表达式 98 条件语句if的翻译 按下面的条件语句if的模式进行讨论 ifEthenS1elseS2布尔表达式E的作用仅在于控制对S1和S2的选择 因此可将作为转移条件的布尔式E赋予两种 出口 一是 真 出口 出向S1 一是 假 出口 出向S2 99 非终结符E具有两项语义值E true和E false 它们分别指出了尚待回填真假出口的四元式串 E的 真 出口只有在扫描完布尔表达式E后的 then 时才能知道 E的 假 出口则需要处理过S1之后并且到 else 时才能明确 这就是说 必须把E false的值传下去 以便到达相应的else时才进行回填 S1语句执行完就意味着整个if then else语句也已执行完毕 因此 在S1的编码之后应产生一条无条件转移指令 这条转移指令将导致程序控制离开整个if then else语句 100 但是 在完成S2的翻译之前 这条无条件转移指令的转移目标是不知道的 甚至在翻译完S2之后仍无法确定 这种情形是由语句的嵌套性所引起的 例如下面的语句 ifE1thenifE2S1thenelseS2elseS3在S1代码之后的那条无条件转移指令不仅应跨越S2 而且应跨越S3 这也就是说 转移目标的确定和语句所处的环境密切相关 因此仿照处理布尔表达式的办法 让非终结符S 和L 含有一项语义值S CHAIN 和L CHAIN 也是一条链 它把所有那些四元式串在一起 这些四元式期待在翻译完S L 之后回填转移目标 真正的回填工作将在处理S的外层环境的某一适当时候完成 101 条件语句if的文法和语义子程序的设计 条件语句if的文法G S 如下 G S S ifEthenS 1 S ifEthenS 1 elseS 2 为了在扫描条件语句过程中不失时机地处理和回填有关信息 可将G S 改写为如下的G S G S 1 S CS 1 2 C ifEthen 3 S TPS 2 4 TP CS 1 else 102 E的 真 出口的处理 首先用产生式 2 C ifEthen进行归约 这时E的真出口即为E所生成四元式序列后的下一个地址 因此 将 then 后的第一个四元式地址 即nextstat 回填至E的真出口地址 E的 假 出口的处理 E的假出口地址则作为待填信息放在C的语义变量C chain中 语义子程序C ifEthen Backpatch E true nextstat C chain E false C ifEthen的翻译 103 接下来用产生式 1 S CS 1 继续向上归约 这时已经处理到S ifEthenS 1 由于归约时E的真出口已经处理 而E的假出口 即语句S的出口 同时是语句S 1 的出口 但此时语句S的出口地址未定 故将C chain和S 1 chain一起作为S的待填信息链用函数merge链在一起保留在S的语义值S chain中 即有S CS 1 S chain merge C chain S 1 chain 如果此时条件语句为不含else的条件句 则在产生式 1 2 归约为S后即可以用下一个将要产生的四元式地址 即S的出口地址 来回填S的出口地址链 即S chain 如果此时条件语句为if tnen else形式 则继续用产生式 4 TP CS 1 else归约 S CS 1 的翻译 104 Tp CS 1 else的翻译 用Tp CS 1 else归约时首先产生S 1 语句序列之后的一个无条件转移四元式 以便跳过S 2 该四元式的地址保留在q中 以便待获知要转移的地址后再进行回填 也即 i S 1 的第一个四元式 E的真出口 q 1 S 1 的最后一个四元式 q goto0 转移地址有待回填 q 1 S 2 的第一个四元式 E的假出口 105 此时q的出口也就是整个条件语句的出口 因此应将其与S chain链接后挂入链头为Tp chain的链中 此外 emit产生四元式q后nextstat自动加1 即为q 1 其地址即为else后 也即S 2 的第一个四元式地址 它也是E的假出口地址 因此应将此地址回填到E false即C chain中 即有 TP CS 1 else q nextstat emit goto0 Backpatch C chain nextstat TP chain merge S chain q 106 S TPS 2 的翻译 当S 2 语句序列处理完后继续翻译if语句之后的后继语句 这时就有了后继语句的四元式地址 该地址也是整个if语句的出口地址 它与S 2 语句序列的出口一致 由于S 2 的出口待填信息在S 2 chain中 故将TP chain与S 2 chain链接后挂入链头为S chain的链中 即S TPS 2 S chain merge TP chain S 2 chain 107 循环语句while的文法和语义子程序设计 给出及时处理和回填的循环语句while的文法G S 如下 G S 1 S WdS 1 2 Wd WEdo 3 W while 108 W while的翻译 根据while语句的扫描加工顺序 首先用产生式 3 W while进行归约 这时nextstat即为E的第一个四元式地址 将其保留在W codebegin中 3 W while W codebegin nextstat 109 Wd WEdo的翻译 然后继续扫描并用Wd WEdo归约 即扫描完do后可以用Backpatch E true nextstat 回填E true值 而E false则要等到S 1 语句序列全部产生后才可能回填 因此E false为待填信息用Wd chain E false传下去 2 Wd WEdo Backpatch E true nextstat Wd chain E false Wd codebegin W codebegin 110 S WdS 1 的翻译 当用产生式 1 S WdS 1 归约时 S 1 语句序列的全部四元式已经产生 此时应无条件返回到E的第一个四元式继续对条件E进行再次测试 即形成四元式 goto Wd codebegin 所以需要用Backpatch S 1 chain Wd codebegin 回填E的入口地址到S 1 语句序列中所有需要该信息的四元式中 在无条件转移语句 goto Wd codebegin 之后即为while语句的后继语句 而这个后继语句中的第一个四元式地址即为while语句E的假出口 保存在Wd chain中 考虑到嵌套情况 将Wd chain信息作为整个while语句的出口保留在S chain中 以便适当时机回填 111 3 S WdS 1 Backpatch S 1 chain Wd codebegin emit goto Wd codebegin S chain Wd chain 112 例 whileA B6 thenX X 1elseY X 1 100ifAgoto104101goto102102ifB6goto106105goto109106T1 X 1107X T1108goto111109T2 X 1110Y T2111goto100112 E false E true 113 三种基本控制结构的翻译 基本控制结构的文法G S 1 S CS 2 S TPS 3 S WdS 4 S L 5 S A A代表赋值语句 6 L LsS 7 L S 8 C ifEthen 9 TP CSelse 10 Wd WEdo 11 W while 12 LS L 114 G S 中各产生式对应的语义子程序 1 S CS 1 S chain merge C chain S 1 chain 2 S TPS 2 S chain