第6章 语法制导翻译.ppt

6语法制导翻译 内容提要语法制导翻译属性文法自顶向下翻译自底向上翻译 要求目标程序须和源程序的语义等同 也就是说 尽管它们的语法结构完全不同 但它们所表达的结果应完全相同 方式1由语法分析程序直接调用相应的语义子程序进行语义处理 2首先生成分析树或该结构的某种表示 再进行语义处理 语义处理的功能1审查每个语法结构的静态语义 即验证语法结构合法的程序是否真正有意义 类型检查 控制流检查 一致性检查 上下文相关性检查 名字的作用域分析2如果静态语义正确 语义处理则要执行真正的翻译 即要么生成程序的中间代码表示 要么生成机器语言或汇编语言的目标代码 直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译 而中间代码的优点是使编译结构在逻辑上更为简单明确 特别是使目标代码的优化比较容易实现 6 1语法制导翻译 动机语义形式化是个专门的研究课题 目前有各种各样的方法和记号不断推出 例如操作语义学 公理语义学 指称语义学和代数语义学等 不论哪种方法 其本身的符号系统比较繁杂 其描述文本不易读 尚不便借助这些形式系统自动完成语义处理任务 现在有很多编译系统采用语法制导翻译方法 这仍不是一种形式系统 但是比较接近形式化 这种方法使用属性文法为工具来说明程序设计语言的语义 语法制导翻译在语法分析的每一步中 通过执行每个产生式所对应的语义子程序 或语义规则描述的语义动作 进行翻译的方法 在语法分析过程中 当一个产生式获得匹配 对于自顶向下分析 或用于归约 对于自底向上分析 时 此产生式相应的语义子程序就进入工作 完成既定的翻译任务 分类自底向上语法制导翻译自顶向下语法制导翻译 语法制导定义使用上下文无关文法描述输入的语法结构 并且每一个文法符号和一个属性集合相关联 每一个产生式和一个语义规则集合相关联 语法制导定义说明程序设计语言中各种结构的翻译 属性程序设计语言结构的类型 目标代码中第一条指令的位置 生成的指令个数等信息 语义规则规定怎样计算与产生式中出现的文法符号相关联的属性的值的规则 文法和语义规则集合构成了语法制导定义 属性分类继承属性 用于 自顶向下 传递信息 继承属性的值由相应分析树中结点的父结点及兄弟结点的属性值计算得到 继承属性可以很方便地用来表示程序语言上下文结构的依赖性 综合属性 用于 自底向上 传递信息 综合属性的值由相应分析树中结点的子结点的属性值计算得到 其传递方向与继承属性相反 即沿分析树向上传递 从分枝结点到根结点 语法制导定义的形式在语法制导定义中 每个产生式A 与一个形如b f c1 c2 ck 的语义规则集合相关联 其中f是函数 并且满足下面两种情况之一 1 b是A的一个综合属性 且c1 c2 ck是该产生式文法符号的属性 2 b是产生式右部某个文法符号的一个继承属性 且c1 c2 ck也是该产生式文法符号的属性 这两种情况都称属性b依赖于属性c1 c2 ck 例6 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 FT val F val 6 F E F val E val 7 F iF val i lexval其中 属性皆为综合属性 并且可以认为第一条语义规则定义了S的一个虚综合属性 例6 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 其中 T type为综合属性 其值由声明中的关键字来确定 L in为继承属性 其值由分析树中左边的兄弟节点或父节点的属性值计算得到 属性信息传递情况示意 6 2属性文法 属性文法是一个语法制导定义 其中语义规则中的函数不能有副作用 语义规则中的函数通常被写成表达式的形式 有时 语法制导定义中某个规则的目的就是为了产生副作用 这种语义归则一般被写成过程调用或程序段 在这种情况下 可以把它看作是定义产生式左部非终结符的虚综合属性 但这种语义规则中的虚属性和符号 都不给出来 6 2 1S 属性文法 S 属性文法只含有综合属性的属性文法S 属性文法的翻译器通常可借助LR分析器实现 把LR分析器的能力加以扩大 使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作 每个产生式的语义子程序执行之后 某些结果 语义信息 必须作为此产生式的左部符号的语义值暂时保存下来 以便以后语义子程序引用这些信息 原LR分析器的分析栈也加以扩充 存放三类信息 分析状态 文法符号及文法符号对应的语义值 扩充后的LR分析栈 例6 3考虑下面的语法制导定义产生式语义规则 0 S Eprintval top 1 E E 1 E 2 val ntop val top val top 2 2 E E 1 E 2 val ntop val top val top 2 3 E E 1 val ntop val top 1 4 E ival ntop lexval其中 lexval为i的整型内部值 由词法分析给出 top和ntop分别是归约前和归约后的栈顶指针 表达式7 9 5 的语义分析和计值过程 6 2 2L 属性文法 在语法分析过程中进行语义分析和翻译 属性的计算顺序受到语法分析建立分析树结点顺序的限制 一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序 它适应多种自底向上和自顶向下的翻译方法 L 属性文法可用于按深度优先顺序计算属性值 L 属性文法一个属性文法称为L 属性文法 如果对于每个产生式A X1X2 Xn 其中每条语义规则中的每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 X1 X2 Xj 1的属性 2 A的继承属性S 属性文法一定是L 属性文法L 属性文法允许一次遍历就计算出所有属性值 例6 4非L 属性的语法制导定义 翻译模式翻译模式是语法制导定义的一种便于翻译的书写形式 其中属性与文法符号相对应 语义规则或语义动作用花括号 括起来 可被插入到产生式右部的任何合适的位置上 一种语法分析和语义动作交错的表示法 表达在按深度优先遍历分析树的过程中何时执行语义动作 翻译模式给出了使用语义规则进行计算的顺序 可看成是分析过程中翻译的注释 例6 5一个简单的翻译模式 把中缀表达式翻译成后缀表达式 E TRR opT print op lexeme R 1 T num print num val 把语义动作看成终结符号 输入9 5 2 按深度优先遍历分析树 执行遍历中访问的语义动作 将输出表达式9 5 2的后缀式95 2 9 5 2的带语义动作的分析树 设计翻译模式 根据语法制导定义 语法制导定义是L 属性文法保证语义动作不会引用还没有计算的属性值 只需要综合属性的情况为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 例如 T T 1 FT val T 1 val F valT T 1 F T val T 1 val F val 既有综合属性又有继承属性产生式右边的符号的继承属性的值必须在这个符号以前的动作中计算出来 一个动作不能引用这个动作右边符号的综合属性 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算 计算这种属性的动作通常可放在产生式右端的未尾 例如 下面的翻译模式不满足要求 S A 1 A 2 A 1 in 1 A 2 in 2 A a print A in 例6 6从L 属性制导定义建立一个满足上面要求的翻译模式 数学排版语言EQN 例如 Esub1 val编排结果 E 1 val 大小和高度的语法制导定义 6 5自顶向下的翻译 在预测分析中实现L 属性文法使用翻译模式而不是语法制导定义 更加明确语义动作的顺序和属性计算的顺序 算法6 1预测语法制导翻译器的建立输入 一个带有适合预测分析的基础文法的语法制导翻译模式 输出 一个语法制导翻译器的代码 1 对每个非终结符A 建立一个可递归调用的函数过程A 为A的每一个继承属性都设置一个形式参数 函数的返回值是A的综合属性值 出现在以A为左部的产生式中的每一个文法符号的每一个属性定义一个相应的局部变量 2 函数过程A的代码 指用符号形式表示的数据和程序 要根据当前的输入符号来决定使用哪一个产生式 3 与每一个产生式有关的代码 从左到右根椐产生式右部是终结符 单词符号 非终结符号还是语义动作 分别处理 a 对于带有综合属性x的单词符号X x存放在X x中 Match X b 对于非终结符B 编写一个赋值语句c B b1 b2 bk 其中 b1 b2 bk是继承属性 c是综合属性 c 对于每个语义动作 把动作的代码抄进翻译器中 用代表属性的变量来代替对属性的每一次引用 例6 7表达式的预测翻译器E T R i T val R E val R s intE intE val intT val R i R s T val T R i T val R s R R i E val R s returnE val R T R 1 i R i T val R 1 R s R 1 s R T R 1 i R i T val R 1 R s R 1 s R R s R i intR intR i intR s intT val R1 s R1 i if lookahead match T val T R1 i R i T val R1 s R R1 i R s R1 s if lookahead match T val T R1 i R i T val R1 s R R1 i R s R1 s returnR s T E T val E val T num T val num val intT intT val intE val if lookahead match E val E T val E val if lookahead match elseerror elseif lookahead num match num T val num val elseerror returnT val 6 4自底向上的翻译 从翻译模式中去掉嵌入的语义动作在自底向上的翻译方法中 需要把所有的翻译动作都放在产生式右端末尾 在基础文法中插入形如M 的新产生式 其中M是一个新的起标记 marker 作用的非终结符 标记非终结符M用来代替嵌入在产生式中的动作 并把这个动作放到产生式M 的末尾 例如E TRR T print R T print R T num print num val 使用标记非终结符M和N改写为E TRR TMR TNR T num print num val M print N print 分析栈中的继承属性考虑产生式A XY X有综合属性X s Y有继承属性Y i 在自底向上的分析中 按照该产生式进行归约的时候 依次把Y和X出栈 如果继承属性Y i是由复写规则Y i X s决定的 那么Y i的值就等于分析栈中存储的X s的值 例6 8变量声明语句的翻译器D T L in T type LT int T type int T double T type double L L 1 in L in L 1 id addtype id entry L in L id addtype id entry L in 声明语句intp q r的自底向上分析过程 模拟继承属性的计算要想从栈中找到继承属性的值 当且仅当文法允许属性值在栈中的存放位置可以预知 例6 9不能预知属性值在栈中的存放位置S aACC i A sS bABCC i A sC cC s g C i 当按照C c归约时 C i的值不能确定在val top 1 处还是在val top 2 处 解决办法 插入标记非终结符S aACC i A sS bABMCM i A s C i M sC cC s g C i M M s M i插入标记非终结符M后C i的值可以在val top 1 处找到 标记非终结符也可以用于模拟不是复写规则的语义规则S aACC i f A s 计算C i的规则不是复写规则 因此C i的值不在栈中 S aANCN i A s C i N sN N s f N i 算法5 2带有继承属性的自底向上的语法制导翻译输入 基础文法是LL 1 文法的L 属性文法输出 一个计算所有属性值的翻译器对于每个产生式A X1 Xn 引入n个新的标记非终结符M1 Mn 用产生式A M1X1 MnXn代替它 综合属性Xj s与Xj关联 继承属性Xj i与Mj关联 1 如果按照Mj 进行归约 此时Xj 1 i和Xj 1 s分别位于val top