【编译原理】语义检查

水深无声 2023-09-23 17:09 118阅读 0赞

### 语义检查 ###

*  编译器构造
 *  目标
 *  语义检查
 *  静态类型检查
 *  动态类型检查
 *  类型检查的范围
 *   *  无类型检查（No Type Checking）
     *  弱类型语言（Weakly-Typed Lanaguages）
     *  强类型语言（Strongly-Typed languages）
 *  语义检查的种类
 *   *  简单类型等效
     *  类型转换
     *  类型检查: 结构等效
     *  类型检查：两种检查方法
     *  名称和结构等效
     *  名称和结构等效检查机制例子
     *  其他语义检查
 *  如何表达语义属性
 *  语法制导定义（Syntax-Directed Definition）
 *   *  SDD示例
     *  SDT示例
     *  SDD中的属性
     *  具有合成属性的SDD
 *  主要掌握内容

# 编译器构造 #

![在这里插入图片描述][4098278425fd4c928f9dbb9e2330d7e5.png]

# 目标 #

关注核心问题：**类型检查**（type checking）。

我们可以在编译器内和编译时**静态地**进行类型检查，也可以**动态地**（在运行时）进行检查。

我们专注于**静态检查**。

我们研究具有强大数据结构建模能力的问题语言——当前类型检查。

我们研究**名称**和**结构等效性**。

# 语义检查 #

程序源文本语义分析的主要问题是**类型检查**。

我们需要检查所有标识符和常量的使用是否符合语言的类型规则。

我们需要检测隐式类型转换的情况（如果语言允许）并插入适当的转换代码。

# 静态类型检查 #

语义检查确定合法语法结构是否有意义。

类型检查：

1.  条件表达式是否为布尔值
2.  验证指针地址在指针上的作用
3.  函数必须具有正确的参数数量和类型

控制流检查  
断句：循环

重合性（Coincidence）检查：  
标识符只应在同一域中声明一次

# 动态类型检查 #

某些语言具有动态类型检查。

任何变量都保存有关其当前值类型的信息。

语言的（运行时）操作识别其操作数的类型，并应用适当版本的操作（或报告错误）。

多态性

# 类型检查的范围 #

1.  None
2.  Weak
3.  Strong

## 无类型检查（No Type Checking） ##

某些语言**没有类型检查**。

任何类型的值都可以在语法允许的任何位置使用。

**汇编语言**尤其如此。

问题是，大多数错误都是在运行时而不是编译时发现的，这是一种更加困难和昂贵的情况。

1.  **完全自由**  
    编译器会按照你的要求做任何事情。
2.  **完全负责**  
    编译器会按照你的要求做任何事情。
3.  **在系统编程中，这可能非常有用：**  
    1）内存的特定部分的使用可以根据系统的状态而改变，而不是程序的语义（您不再处于沙盒中）。  
    2）对程序员意思的任何解释都不能消除“翻译错误”的可能性。

## 弱类型语言（Weakly-Typed Lanaguages） ##

这里很容易覆盖语言的类型检查。

例如，在C中，字符可以被视为整数，我们可以调用函数而不匹配数字或类型中的形式参数。

如果我们知道自己在做什么，这是可以的，但这可能会导致一些晦涩的错误。  
![在这里插入图片描述][e62abd2436134c208d16d384d9bcbac2.png]

## 强类型语言（Strongly-Typed languages） ##

在这里，类型检查在语言的所有领域都是强制的，任何类型转换都必须明确表示（没有强制机制）。

标准示例是Ada，我们避免了某些类型的错误，但编程中可能存在灵活性。

![在这里插入图片描述][09f3465d7dec4b14bdd6bea161f88b73.png]

# 语义检查的种类 #

这里我们关注的是**静态类型检查**（static type checking），即编译器在编译时执行的检查。

我们对**类型等价**（type equivalence）感兴趣：  
也就是说，两个实体何时具有相同的类型（例如，赋值的左侧和右侧的表达式）。

## 简单类型等效 ##

**对于简单类型，没有问题：**

1.  我们在符号表中保存每个变量的类型
2.  我们希望可以从常量（字面）的形式推断出它是什么类型
3.  我们知道每个运算符的操作数必须是什么类型，结果类型是什么
4.  我们可以在构建解析树时应用测试

## 类型转换 ##

有时我们可能希望将值从一种类型转换为另一种类型（如果可能的话）。

我们可能需要程序员用有时被称为强制转换的方式来明确指出这一点。  
![在这里插入图片描述][fec542bf218344c99c54226b151c6661.png]  
或者可以通过类型强制隐式完成。

如果一个运算符需要一个浮点数，而我们有一个整数，那么编译器可以自动插入代码来进行转换。

## 类型检查: 结构等效 ##

符号表条目中的**类型字段**（type field）现在是指向此表单结构的**指针**。

我们通过遍历两个类型树并递归检查匹配（或允许的类型转换）来检查类型等价性。

【注意】为了节省空间，此结构可能包含对其他结构的引用——因此，在树上行走可能会变得非常昂贵。（时间/内存权衡）

## 类型检查：两种检查方法 ##

许多语言允许我们命名新类型，以便我们可以通过它们的名称而不是重复它们的定义引用这些类型（例如，在声明中）。

但这意味着现在有两种检查类型等价性的方法。

## 名称和结构等效 ##

**名称等效性**：我们在符号表中存储对类型名称的引用，并通过简单地检查两个名称的等效性来检查两个变量的兼容性。

**结构等效性**：我们使用类型名称来访问类型定义，并遍历两个树来检查等价性。

**这两种机制可能产生不同的结果**

## 名称和结构等效检查机制例子 ##

例如，如果我们声明：  
**类型someArray是整数的数组\[1…100\]；  
array1 : someArray;  
array2 : array \[1…100\] of integer**

然后，在结构等价下，两个数组具有相同的类型，但在名称等价下，这两个数组没有相同的类型

第二个数组被称为具有匿名类型

语言设计可以（应该）指定使用哪种类型的等效

## 其他语义检查 ##

在讨论语义检查时，我们将重点放在类型检查上。

我们可能需要检查的其他事项是**声明检查**（我们可能希望在使用变量之前强制执行（如果合适）声明）。

我们还需要正确处理变量的范围；例如，包体中的变量在包外部可能不可见。

**控制检查流程**（Flow of control checks）：  
某些类型的语句只能出现在某些构造中（例如，在Ada中，“exit”语句必须位于循环中）

这可以通过语法约束来实现，但通常作为单独的“语义”检查更容易实现：

1.  为了支持这一点，除了基本类型之外的元数据可能还必须包含在范围结构中
2.  这是什么类型的范围
3.  此位置的哪些操作合法/有效
4.  此处对访问/操作的任何其他限制

# 如何表达语义属性 #

**语法导向翻译** (Syntax-directed translation)

1.  为语法符号设置语义属性，以表达语法组件的语义信息
2.  即，对于变量：它是什么类型，它有什么值，它的值存储在哪里
3.  如何计算属性(通过生成表示符号的语法规则)  
    ![在这里插入图片描述][5e95960504c347b6a168741729c3437a.png]

# 语法制导定义（Syntax-Directed Definition） #

SDD是CFG的扩展

1.  将每个语法符号与语义属性相关
2.  将每个产生式与一组语义规则相关联，这些规则用于计算产品中每个符号的属性值

如果X是一个符号，a是X的一个属性，则用X.a表示

## SDD示例 ##

![在这里插入图片描述][dff743f87063446380fe4408c4460ba5.png]

## SDT示例 ##

SDT：语法导向翻译，是将一段程序嵌入产生式右侧中的CFG。程序的这些部分称为语义动作。  
![在这里插入图片描述][40b8ca98e339493c88192eff0a53cdb6.png]  
计算符号（即T）的右侧值后。

我们可以计算左侧值（即D）。

## SDD中的属性 ##

**语法符号的属性**  
合成属性（Synthesized attribute）  
![在这里插入图片描述][c7a14f072d724f1d9f4818c8a47e6ab1.png]

继承属性 （Inherited attribute）  
![在这里插入图片描述][0950ebf53fde4540b7969f990cadba1b.png]

## 具有合成属性的SDD ##

![在这里插入图片描述][332176309de2485b89546620d18e3d81.png]

# 主要掌握内容 #

了解语义检查的概念以及编译器如何支持这一点。

我们专注于类型等价，因此您应该了解类型检查的范围，了解动态类型检查，了解类型等价和显式/隐式强制。

理解结构和命名等效之间的区别。

***Thanks to Dr. John: Some contents are from their slides.***

[4098278425fd4c928f9dbb9e2330d7e5.png]: https://img-blog.csdnimg.cn/4098278425fd4c928f9dbb9e2330d7e5.png
[e62abd2436134c208d16d384d9bcbac2.png]: https://img-blog.csdnimg.cn/e62abd2436134c208d16d384d9bcbac2.png
[09f3465d7dec4b14bdd6bea161f88b73.png]: https://img-blog.csdnimg.cn/09f3465d7dec4b14bdd6bea161f88b73.png
[fec542bf218344c99c54226b151c6661.png]: https://img-blog.csdnimg.cn/fec542bf218344c99c54226b151c6661.png
[5e95960504c347b6a168741729c3437a.png]: https://img-blog.csdnimg.cn/5e95960504c347b6a168741729c3437a.png
[dff743f87063446380fe4408c4460ba5.png]: https://img-blog.csdnimg.cn/dff743f87063446380fe4408c4460ba5.png
[40b8ca98e339493c88192eff0a53cdb6.png]: https://img-blog.csdnimg.cn/40b8ca98e339493c88192eff0a53cdb6.png
[c7a14f072d724f1d9f4818c8a47e6ab1.png]: https://img-blog.csdnimg.cn/c7a14f072d724f1d9f4818c8a47e6ab1.png
[0950ebf53fde4540b7969f990cadba1b.png]: https://img-blog.csdnimg.cn/0950ebf53fde4540b7969f990cadba1b.png
[332176309de2485b89546620d18e3d81.png]: https://img-blog.csdnimg.cn/332176309de2485b89546620d18e3d81.png