Semantic

發表於   |   分類於

前面

最近又翻了翻之前编译课上写的代码，大致看了一下语法分析部分跟语义分析部分。

Java写的，最后生成的代码并非汇编，也不是JVM的ByteCode，而是C代码，生成的程序自然使用GCC编译链接而成，因此也就没有什么链接器——当然，即便如此也应当有一个自定义的链接部分，但由于只要求用单个文件就能表示整个程序代码，于是就没有了。至于中间代码用C来表示的问题，事实上只要能用三地址类型表示出来，中间代码的具体形式是没什么影响的（龙书里面出现的中间代码一样是类似C的代码）。生成的代码额外加了一个GC的过程，这个会在后面说。

几个概念：Top-Down的递归下降子程序语法解析、完美打印（Pretty Print）以及符号表、类型。语法解析以及完美打印涉及到的抽象语法树前面已经讨论过了（抽象语法树的论述过于简短，但这个东西走一遍就能够理解了），这里主要说明一下剩下的也是语义分析需要的两个重要的部分：符号表、类型。

正文

类型

先从经常接触的类型开始。

类型可以看作内存中某一块数据的表现形式，用来通知程序：“对于内存中的这一块数据，你应当这么认为……然后你可以……去使用它”。

在绝大部分高级语言中，对于类型的检查都是很严格的，如果只是使用过Java/C#等强调OO的语言，则可能会认为这是天经地义的一件事。但有过C代码经验的人却不能忽视一个事实：在C中，内存数据可以以几乎任何类型解释，即便是是风马牛不相及的两块数据，它们的类型同样可以相互转换——而在强调OO的语言中，类型之间是不能随意转换的，除非两种类型有继承关系。

这之间的区别在于：对于C而言，类型更强调数据的size；对于强调OO的语言，类型除了表示数据的size，更是为了告诉并规范程序员数据应当如何进行使用——所谓更安全即是因此而来。

类型检查

这里只说一下我自己写相关代码时采用的方案。

对于基本类型，例如int/float/string/user-defined。可以赋予一个唯一标识符。如果有可以转换的情况，例如 int->string，那么就将赋值操作的右部分表达式的最终结果使用一个int->string的过程表示出来；至于int/float/bool之间的相互转换，直接生成对应的C代码。例如下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 源代码
class Main
{
  int main(int argc,string[] argv)
  {
    int f2i = 18.9;
    string f2i2s =  f2i;
    return 0;
  }
}

// 对应生成的C代码
int main(int argc, char** argv)
{
  int f2i = 18.9f;
  // 示例。用一个过程来表示int->string
  char f2i2s[256];
  int f2i2sn = sprintf(f2i2s,"%d",f2i);
  f2i2s[f2i2sn] = '\0';
  //
  return 0;
}

由于采用了一些OO特性，支持了单继承，因此用户定义的类型可能会具有基类形。故而，用户定义类型表示如下：

1
2
3
4
5
6
7
8
9
10
11
struct Type
{
  std::string m_uid; // 使用字符串作为类型的标识
};

struct UserDefinedType : public Type
{
  UserDefine* m_base; // 基类类型
  std::vector<Type*> m_dataMembers; // 数据成员类型
  std::vector<Type*> m_derived; // 继承自此类型的类型
};

那么，根据m_base与m_derived就可以得到一个静态的继承关系树（如果我没有记错的话MFC里面的RUNTIME_CLASS使用的就是这个方法，是用static对象实现的）。

如果不去显式说明继承关系，又该如何？

首先，回顾一下C++中的构造函数，其中有一种方式被称为初始化列表的构造方式。在大多数的C++书籍中，都会明确告诉读者：数据成员在初始化列表中的顺序与其真正的初始化顺序无关，只与它们在类中的定义顺序有关。也就是说，对于一个类，它的类型不仅仅与它包含哪些成员相关，还与它的成员的定义顺序有关。

实际上，下面的两个类是不同的类型，虽然它们包含相同的成员，在内存中占有的大小也相同：

1
2
3
4
5
6
7
8
9
10
11
struct SA
{
  int a;
  char b;
};

struct SB
{
  char b;
  int a;
};

这样定义不是没有道理的：无论是按照何种对齐方式，它们在内存中的第一个字节的意义始终是无法相同的。

那么继承的情况又如何呢？

1
2
3
4
5
6
7
8
9
struct Base
{
  int base;
};

struct Derived : public Base
{
  int derived;
};

很显然，我们知道Derived实际上是这样的：

1
2
3
4
5
struct Derived
{
  int base;
  int derived;
};

于是，如果我们希望能够动态的判定Base与Derived的继承关系，需要从两个方面来判定：首先是宽度（也就是成员数目），宽度小的类有可能是宽度大的类的父类；其次是深度：宽度小的类包含的成员，必须按顺序从头到尾依次出现在宽度比较大的类中的同样位置，并且类型要相同。很显然的，类型相同包含了是否包含相同的成员数目、包含的成员类型以及定义顺序是否相同——这是一个递归过程。

不难发现，上面的判断方法仅对单继承有好的支持，而对于多继承则力有不逮，不如通过语法强制显式声明来的好。

符号表

符号表在整个编译链接生成代码的过程中占有重要地位，居于核心位置，反映了标识符的语义特性：例如上面提到的类型信息、标识符的作用域和隶属关系等（隶属关系是我自己加的说法，单指类和它的成员之间的关系。成员的标识符隶属于类的标识符）。

符号表的作用域使用是个Block来定义，Block可认为是由大括号{}包括的一条或者多条语句构成的。很显然，作用域是可以嵌套的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Symbol
{
  Block* m_block; // 所属域
  Type* m_type; // 符号的类型，例如TYPE_INT, TYPE_FLOAT, TYPE_STRING, TYPE_USER等
  Symbol* m_parent; // 所隶属的符号，也就是隶属的类的类名
  std::vector<Symbol*> m_members; // 类的成员们
  Token* m_token; // 相关的token，在出错的时候可以定义到对应的文本位置，另外token包含的lexeme同样也是该Symbol的名称
};

struct Block
{
  Block* m_parent; // 父作用域
  std::vector<Symbol> m_symbols; // 包含的符号们
  std::vector<Statement*> m_stms; // 块中包含的语句
};

注意到Block中包含了表示语句的成员，这是因为语法与语义并非同一个概念。例如string s = s1 + b1;中，如果b1是一个用户定义的类型，那么很显然是不合适的；但是语法层面，两个标识符之间的相加是没有问题的。

那么对于一个符号是否在作用域中重复出现，以及是否未定义，就可以通过Block的链表来上溯查找。

对于每一个程序，需要额外分配一个全局域以便分析能够正确进行。

整个分析过程的运行类似于单线程下的函数调用，使用一个栈就可以进行模拟了——进入一个作用域，将其压栈，然后进行分析，出作用域的时候弹出即可。

至于单条语句，像上面提到的string s = s1 + b1;，就需要进行逐条语句的检查了。在这个过程中，类型检查开始发挥作用。

结束

写得很是惶恐，感觉说了些什么又好像什么都没说，而且稍微涉及到一些理论啊名词啊之类的东西还不知道用没有搞错……终究是没有整个搞透彻，况且又忘掉了很多东西。

如果有可能，我打算慢慢把代码配上来，代码尽量过程化一些，能够凸显思路，就像Lexer里面那样。不过……代码质量不会好就是了。

嗯……如果问到一些理论问题的话，应该会死得很难看吧……