Ylin's Blog
0%

92:c4编译器回顾(2)

发表于 更新于 分类于 ，
本文字数： 2.4k 阅读时长 ≈ 9 分钟

上一节中完成了对虚拟机的实现和初始化，还有指令集的定义，接下来就是对源文件的词法分析部分

词法分析

什么是词法分析

源文件的内容对于我们的解释器而言，本质上就是一系列ASCII字符串，是毫无意义的，我们需要通过语法分析将其解析为简单的指令，然后再执行。可是这样一来，这就使得语法分析的部分十分庞大。所以编译器一般会对整个过程进行前后端的分离。前端负责对源文件进行预处理，将其解析为一系列标识符流，如下：

1
2
3
2 + 3 * (4 - 5)
=>
(Number, 2) Add (Number, 3) Multiply Left-Bracket (Number, 4) Subtract (Number, 5) Right-Bracket

然后后端就可以根据直接对标识符流进行处理，就避免了中间处理过程臃肿的情况。

词法分析和编译器

词法分析从某种意义上来讲，本质上也是一种编译器，它以源代码作为输入流，然后输出标识符流：

1
2
3
                   +-------+                      +--------+
-- source code --> | lexer | --> token stream --> | parser | --> assembly
                   +-------+                      +--------+

直接从源代码编译成汇编代码是很困难的，因为输入的字符串比较难处理。所以我们先编写一个较为简单的编译器（词法分析器）来将字符串转换成标记流，而标记流对于语法分析器而言就容易处理得多了。

词法分析器的实现

这里我们就不用现有的词法分析器了，我们手动的实现这一部分。当然我们需要注意，词法分析并不是一次性的将所有的源码转换成标记流。因为在代码中的大多数操作符，和字符关键字都是和代码有上下文关系的。

所以实际的做法是，提供一个next()函数，每次调用这个函数就返回下一个标识。

支持的标识

我们的编辑器支持以下标识符：

1
2
3
4
5
enum {
	Num = 128, Fun, Sys, Glo, Loc, Id,
	Char, Else, Enum, If, Int, Return, Sizeof, While,
	Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak
};

这里之所以让标识符从128开始，是为了避免和前面设置的指令枚举变量发生冲突。

上面的运算符的枚举变量是有顺序的，实际上他们是按优先级进行排列的，之后的语法分析过程中会用到。现在我们就要进行token的匹配了。例如将==匹配成Eq，将=匹配成Assign。在下面的实现中，我们会分析这些匹配是怎么实现的。

当然这里还需要注意一些字符，他们自己就构成了标记，如右方括号]和波浪号~等，我们不需要对他们做额外的处理，因为他们不属于多字符的共同标记，也不参与运算（没有优先级关系）

框架

我们的next()的主体框架如下：

1
2
3
4
5
6
7
void next(){
    char *last_pos;
    while(*src){
        ++src;
	// 具体的匹配逻辑
    }
}

这里我们使用whlie来跳过我们分析过程中的遇到的空白字符和未知的符号。下面我们先把几个比较特殊的标识符进行一下处理：

换行符号

换行符也和空格类似，只不过遇到换行符号，我们需要将当前的行号+1：

1
if(token == '\n') {++line;}

宏定义

我们的解释器不支持宏定义所以直接跳过#后面部分的内容:

1
2
3
else if(token == '#'){
    while (*src == 0 || *src == ' ') {++src;}
}

标识符和符号表

标识符可以理解为变量名。对于语法分析而言，我们并不关心一个变量叫什么，而是在意这个变量的标识符，我们需要从它唯一的标识符中获取这个变量的信息。

基于这个理由，我们让词法分析器将扫描到的标识符保存在一张表中，每当我们遇到标识符，就去表中查找，如果标识符存在就返回它的唯一标识符，不存在则创建有一个新的标识符存放在表中。

我们用结构体来存放标识符的信息：

1
2
3
4
5
6
7
8
9
10
11
12
// 标识符信息
typedef struct _id{
    int token;
    int hash;
    char *name;
    int class;
    int type;
    int value;
    int Bclass;
    int Btype;
    int Bvalue;
} ID;

这里解释一下各个字段的具体含义：

  • token：该标识符返回的标记，这里主要是存储变量的信息，所以标记类型注意要是Id
  • hash： 这个标识符的hash值，用于快速比较标识
  • name：存放标识符的变量名
  • class： 存放标识符的类型，例如全局、局部、数字等
  • type： 标识符的类型，如果是个变量，可能是指针、int或者char
  • value： 存放这个标识符的值，如果标识符是函数的，则存放函数地址
  • BXXX： C语言的标识符中可能是全局的也是局部的，当我们局部标识符和全局标识符冲突时，这个字段用于保存全局变量的信息。

上面这些信息用于我们在语法分析部分进行解析，更加方便快捷：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int token_val;          // 当前标识符的值
ID *Symbols;            // 符号表
ID *current_id;         // 当前标识符

...
	else if(token>='a'&&token<='z' || token>='A'&&token<='Z' || (*src >= '0' && *src <= '9') || token=='_'){
            // 标识符处理
            last_pos = src - 1; // 标识符起始位置
            while(*src>='a'&&*src<='z' || *src>='A'&&*src<='Z' || *src>='0'&&*src<='9' || *src=='_')
                hash = hash * 147 + *(src++);
            // 查找符号表
            current_id = Symbols;
            while(current_id->token){
                if(current_id->hash == hash && !memcmp(current_id->name, last_pos, src - last_pos)){
                    token = current_id->token;
                    return;
                }
                current_id++;
            }
            // 新标识符
            token = current_id->token = Id;
            current_id->hash = hash;
            current_id->name = (int)last_pos;
            return;
        }  
...

我们通过以上形式实现对标识符的识别。

数字

当遇到数字时我们也需要，进行对应的解析，这一部分的难点在于不同进制的识别。然后将数字转换为对应的数据并求值，我们把它的值保存在token_value中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
else if(token>='0'&&token<='9'){
           // 数字处理
           token_val = token - '0';
           if(token_val > 0){
               while(*src>='0'&&*src<='9')
                   token_val = token_val *10 + *(src++) - '0';
           }else{
               if(*src == 'x' || *src == 'X'){
                   token = *(++src);
                   while((token>='0'&&token<='9') || (token>='a'&&token<='f') || (token>='A'&&token<='F')){
                       token_val = token_val *16 + (token&15) + (token>='A' ?9:0);
                       token = *(++src);
                   }
               }else{
                   while(*src>='0'&&*src<='7')
                       token_val = token_val *8 + *(src++) - '0';
               }
           }
           token = Num;
           return;
       }

字符串

在实际的分析过程中，当我们遇到字符串，我们需要将它的内容保存在data段中，然后返回它data段中的地址，之后我们对字符串的使用都指向这个地址。另一个特殊的地方在于，我们需要支持部分转义字符的实现，这里我们只对\n做一个支持，也支持\x表示字符x的语法。

在分析时，我们将单个字符'a'按Num的形式保存并返回，我们将"a string"按字符串的形式进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
else if(token=='"'||token=='\''){
          last_pos = data;
          while(*src!=token && *src!=0){
              token_val = *src++;
              if(token_val=='\\'){
                  token_val = *src++;
                  if(token_val=='n') token_val = 10;
                  else if(token_val=='t') token_val = 9;
                  else if(token_val=='r') token_val = 13;
                  else if(token_val=='\\') token_val = '\\';
              }
              if(token == '"')
                  *data++ = token_val;
          }
          src++;  // 跳过结束符
          if(token == '"') {
              *data++ = 0;
              token_val = (int)last_pos;
          }else {token = Num;}
          return;
      }

这一部分可能比较难理解，首先就是判断这个是单字符还是多字符的字符串。然后分别做不同的处理即可。

注释

在我们的C中，只支持//类型的注释，不支持多行/**/的注释方法。处理方式和前面对#的方式差不多，需要注意的是，这里要前瞻的观察下一位是什么/可能是除法，也可能是//注释

1
2
3
4
5
else if(token=='/'){
          if(*src=='/')
              while(*src!=0 && *src!='\n') ++src;
          else {token = Div; return;}
      }

这里我们利用src比token快一个字符的特点，实现了对多个字符的观察，我们称这个概念为前瞻（lookahead）

其他

其他的大多数是一些简单的操作符，我们简单的附上代码即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
else if(token=='='){
          if(*src=='='){++src; token = Eq;} 
          else {token = Assign;}
          return;
      }else if(token=='+'){
          if(*src=='+'){++src; token = Inc;} 
          else {token = Add;}
          return;
      }else if(token=='-'){
          if(*src=='-'){++src; token = Dec;} 
          else {token = Sub;}
          return;
      }else if(token=='!'){
          if(*src=='='){++src; token = Ne;} 
          return;
      }else if(token=='<'){
          if(*src=='='){++src; token = Le;} 
          else if(*src=='<'){++src; token = Shl;}
          else {token = Lt;}
          return;
      }else if(token=='>'){
          if(*src=='='){++src; token = Ge;} 
          else if(*src=='>'){++src; token = Shr;}
          else {token = Gt;}
          return;
      }else if(token=='|'){
          if(*src=='|'){++src; token = Lor;} 
          else {token = Or;}
          return;
      }else if(token=='&'){
          if(*src=='&'){++src; token = Lan;} 
          else {token = And;}
          return;
      }else if(token=='^'){
          token = Xor;
          return;
      }else if(token=='%'){
          token = Mod;
          return;
      }else if(token=='*'){
          token = Mul;
          return;
      }else if(token=='['){
          token = Brak;
          return;
      }else if(token=='?'){
          token = Cond;
          return;
      }else if(token=='~' || token==';' || token=='{' || token=='}' || token=='(' || token==')' || token==']' || token==',' || token==':')
          return;

基本的思想就是利用前瞻确定标记。

关键字和内置函数

完成了上述的词法分析之后，我们需要在正式开始词法分析之前，预处理我们的关键字和内置的函数。我们将它们加入符号表，并提前为他们赋予必要的信息。

我们在main函数中对其进行初始化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{
    ID *Symbols = current_id = malloc(poolsize);
    src = "char else enum if int return sizeof while "
          "open read close printf malloc memset memcmp exit void main";
    i=Char;
    while(i<While){
        next();
        current_id->token = i++;
    }
    i = OPEN;
    while(i<=EXIT){
        next();
        current_id->value = i++;
        current_id->class = Sys;
        current_id->type = INT;
    }
    next(); current_id->token = Char;
    next(); idmain = current_id;
}

至此我们就完成了对源代码的词法分析，程序会通过词法分析将我们的源代码转换成标记流。