编译原理3——语法制导翻译&中间代码生成

第五章 语法制导翻译

语法制导翻译：

• 语法分析
• 语义分析
• 中间代码生成

语义翻译：

• 语义分析
• 中间代码生成

语法制导定义（SDD）

• 将每个文法符号和一个语义属性集合相关联
• 将每个产生式和一组语义规则相关联，用于计算该产生式中各文法符号的属性值。

语法制导翻译方案（SDT）

• 在产生式右部嵌入了程序片段的CFG，这些程序片段被称为语义动作（语义动作放在花括号内）
• 一个语义动作在产生式中的位置决定了这个动作的执行时间

文法符号的属性

• 综合属性
  • 只能通过子节点或本身的属性值定义
  • 终结符可以具有综合属性（有词法分析器提供的词法值）
• 继承属性
  • 只能通过父节点、兄弟节点或本身的属性值定义
  • 终结符没有继承属性
• 注释分析树：每个节点都带有属性值的分析树
• 副作用
• 属性文法：一个没有副作用的SDD又是也称为属性文法
  • 属性文法的规则仅仅通过其他属性值和常量来定义一个属性值
• 依赖图：描述分析树种节点属性间依赖关系的有向图
  • 分析树中每个标号为x的节点的每个属性a都对应着依赖图中的一个节点
  • 如果X.a的值依赖着 Y.b的值，则存在后者节点指向前者节点的有向边。

两类SDD

• S属性定义（S-SDD）
  • 仅仅使用综合属性
  • 可按照任意一个自底向上的顺序计算属性值
• L属性定义（L-SDD）
  • 每个属性要么是综合属性，要么是满足如下条件的继承属性：
    • 假设存在一个产生式 $A \rightarrow X_1X_2X_3…X_{i-1}$，其右部符号的继承属性仅依赖于下列属性：
    • A的继承属性
    • 产生式中该符号左边的属性
    • 该符号本身的属性，但是其全部属性不能在依赖图中形成环路

SDT

• 语法制导翻译方案是在产生式右部中嵌入了程序片段（被称为语义动作）的CFG。

• 可以看作是SDD的具体实施方案

• 两种SDT可在语法分析过程中实现的情况：

  • LL分析+L属性SDD
  • LR分析+S属性SDD

• S-SDD转换为SDT的方法：每个语义动作放在产生式的最后

  • SDT实现：在LR语法分析过程中当规约发生时执行相应的语义动作
  • 在分析站中使用一个附加的域来存放综合属性值
  • 将语义动作中的抽象定义式改写成具体可执行的栈操作

• L-SDD转化成SDT：

  • 将计算某个非终结符号A的继承属性的动作插入到产生式右部仅靠A本次出现之前的位置上
  • 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

• L属性定义的SDT实现：

  • 在非递归的预测分析过程中进行语义翻译

    • 扩展语法分析栈
    • 分析栈中的每一个记录都对应这一段执行代码
    • 综合记录出栈时，要将综合属性值赋值给后面特定的语义动作
    • 变量展开时，如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作

  • 在递归的预测分析过程中进行语义翻译

    • 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的的综合属性值。
    • 对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
    • 非终结符A的代码根据当前的输入决定使用哪个产生式
    • 与每个产生式有关的代码，从左到右考虑产生式右部的词法单元、非终结符及语义动作
      • 对于带有综合属性x的词法单元X，把x的值保存在局部变量X.x中额案后产生一个匹配X的调用，并继续输入
      • 对于非终结符B，产生又不带有函数调用的赋值语句
      • 对于每个语义动作，直接转移到语法分析器中

  • 在LR分析的过程中进行语义翻译（自底向上）

    

第六章 中间代码生成

声明语句的翻译

• 主要任务：收集标识符的类型等属性信息，并为每一个名字分配一个相对地址
• 类型表达式
  • 基本类型（integer、real、char、boolean、type_error、void）
  • 为类型表达式命名，类型名也是类型表达式
  • 将类型构造符作用域类型表达式可以构成新的类型表达式
    • eg：array（数组构造符）、pointer（指针构造符）、$\times$（笛卡尔积构造符）、$\rightarrow$（函数构造符）、record（记录构造符）
• 局部变量的存储分配
  • 从类型表达式可知该类型在运行时所需的存储单元数量——类型的宽度
  • 在编译时刻，可以使用类型的宽度为每个名字分配一个相对地址
  • 名字的类型和相对地址信息保存在相应的符号表里

赋值语句的翻译

• 简单赋值语句的翻译

  • 主要任务：生成对表达式求值的三地址码

  

  • 增量翻译
    • 在增量方法中，gen()指令不仅要构造新的三地址指令，还要将其添加到迄今为止已经生成的指令序列之后

• 数组引用的翻译

  • 主要问题：却低估数组元素的存放地址（数组元素的寻址）

  • 数组元素寻址：

    • 一维数组：每个数组元素的宽度时w，则a[i]的相对地址是 $base + iw$

    • k维数组：$base + i_1w_1+ i_2w_2+ … +i_kw_k$

      

控制语句的翻译

布尔表达式的翻译

• 在跳转代码中，逻辑运算符&&，||和！被翻译成跳转指令，运算符本身不出现在代码中。布尔表达式的值是通过代码序列中的位置来表示的。

回填

• 基本思想

  • 生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都放入由跳转指令组成的列表中。同一个列表的所有跳转指令具有相同的目标标号，确定时进行填充。

• 非终结符的综合属性

  • B.truelist
    • 指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是B为真时应该转向的标号
  • B.falselist

• 函数

  • $makelist(i)$

    • 创建一个只包含 i 的列表，i 是跳转指令的标号，函数返回指向新创建列表的指针。

  • $merge(p_i,p_2)$

    • 将两者指向的列表进行合并，返回合并后列表的指针

  • $backpatch(p,i)$

    • 将i作为目标标号插入到p指向列表的所有指令中

switch语句的翻译

过程调用语句的翻译

语义分析中的错误检测

• 变量或者过程未声明就使用
• 变量或过程名重复声明
• 运算分量类型不匹配
• 操作符与操作数之间的类型不匹配
  • 数组下标不是整数
  • 非数组变量使用数组访问操作符
  • 非过程名使用过程调用操作符
  • 过程调用的参数类型或者数目不匹配
  • 函数返回类型有误