compileR - PL0

只是一个编译原理课上的作业，分析的是清华版《编译原理》后面附录中的代码，本文中所用的PL0编译器代码是由王磊老师修改后的版本，而且还贴心的加了很多注释🥰。可以在这里获取：PL0.zip

在开始阅读前，建议使用jb家的clion，代码配色可以使用vscode的代码配色，这样读起来轻松点，实际上这一套就是我的设置方案，平常写代码也是这一套配置，jb的ide + vscode的配色。

虽然有非常详细的注释，但是源代码的变量的命名以及一个文件全局变量满天飞的写法对我来说还是过于难受了点…

序章：从分析结构开始！

在分析之前，咱们先来看看这个一千多行的程序的结构：

图图不见了哦

看起来并不是特别复杂，通过函数名称，可以大致知道这些函数都是干什么的，比如 main():int 是主程序的入口 (…呃呃呃这要说吗) ；init():void 应该是初始化一些常数和定义之类的；addset(bool *, bool *, bool *, int n):int 可能是添加集合并操作之类的…实在不行咱还有注释

这下心里就有底了。

主线：万物起源 - main

一般来说，读一些比较大的工程或者程序时，可以只关心自己想需要了解的部分即可，不过这次是要分析整个程序，所以直接从main开始分析整个程序执行过程。

这里就先把main函数的代码贴上来吧：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
int main() {
  /* symnum在头文件pl0.h中声明，#define symnum 32 */
  /* bool在头文件pl0.h中声明，是枚举类型，包含两个成员false和true */
  bool nxtlev[symnum];

  printf("Input pl/0 file?");
  scanf("%s", fname);          /* 输入PL/0源程序文件名 */
  fin = fopen(fname, "r");      /* fin在头文件pl0.h中声明，FILE * fin */
  if (fin != NULL) {
    printf("List object code? (Y/N)");    /* 是否输出虚拟机代码 */
    scanf("%s", fname);
    //listswitch在头文件pl0.h中声明，是bool型数据
    listswitch = (fname[0] == 'y' || fname[0] == 'Y');

    printf("List symbol table? (Y/N)");    /* 是否输出名字表 */
    scanf("%s", fname);
    //tableswitch在头文件pl0.h中声明，是bool型数据
    tableswitch = (fname[0] == 'y' || fname[0] == 'Y');

    fa1 = fopen("fa1.txt", "w");
    fprintf(fa1, "Input pl/0 file?");
    fprintf(fa1, "%s\n?", fname);

    init();
    err = 0;
    cc = cx = ll = 0;  //这三个变量的含义是什么？
    /*
      cx是虚拟机代码指针，初值为0
      cc和ll两个变量用在getch()函数中。
      getch()读取一个字符，每次读源文件的一行，存入line缓冲区，缓冲区中的字符被getsym函数取空以后，读下一行。
      ll是本行字符数。cc是在line数组中，当前正准备读取的字符下标。因此当cc与ll相等时，line缓冲区中的数据已被读取完毕。
    */
    ch = ' ';    /* ch初始赋值为空格 */
    //getym()是词法分析函数，返回-1表示出错了。
    if (-1 != getsym()) {
      fa = fopen("fa.txt", "w");
      fas = fopen("fas.txt", "w");
      addset(nxtlev, declbegsys, statbegsys, symnum);  //addset函数做什么事？集合并运算，集合nxtlev是declbegsys与statbegsys的并
      nxtlev[period] = true;              //后跟符号可以是句号period
      if (-1 == block(0, 0, nxtlev)) {         /* 调用编译程序 */
        fclose(fa);
        fclose(fa1);
        fclose(fas);
        fclose(fin);
        printf("\n");
        return 0;
      }
      listcode(0);
      fclose(fa);
      fclose(fa1);
      fclose(fas);
      if (sym != period) {
        error(9);
      }
      if (err == 0) {
        fa2 = fopen("fa2.txt", "w");
        interpret();              /* 调用解释执行程序 */
        fclose(fa2);
      } else {
        printf("Errors in pl/0 program");
      }
    }
    fclose(fin);
    if (fa1 != NULL)
      fclose(fa1);
  } else {
    printf("Can't open file!\n");
  }
  printf("\n");
  return 0;
}

看起来好像好多东西的样子，但其实也就那几个过程，大部分都能一眼看出来在做什么，况且且还有注释。

不过有一说一，原版代码中的变量命名有时候真让人摸不着头脑

main函数中主要干了这些事：

  1. 根据指定的路径读入文件
  2. 执行init()，初始化一些常量定义，干了什么详见支线：欲善其事，必先利其器 - 初始化
  3. 定义一些需要用到的变量，如cc, cx, ll
    • 搬自注释：

    • 这三个变量的含义是什么？

      cx是虚拟机代码指针，初值为0
      cc和ll两个变量用在getch()函数中。
      getch()读取一个字符，每次读源文件的一行，存入line缓冲区，缓冲区中的字符被getsym函数取空以后，读下一行。
      ll是本行字符数。cc是在line数组中，当前正准备读取的字符下标。因此当cc与ll相等时，line缓冲区中的数据已被读取完毕。

  4. 63行if (-1 != getsym()) {调用一次getsym()进行一次初步的词法分析，进入主线：间章：文字的拆解 - 词法分析，做过词法分析实验的话应该都知道怎么一回事吧
  5. 68行if (-1 == block(0, 0, nxtlev)) {调用block()开始进行真正的编译分析，进入主线：本体 - block下的真面目，编译生成下面解释器虚拟机使用的指令码。
  6. 编译完了之后，就是收尾工作了，关闭文件，释放资源
  7. 解释运行生成编译生成的代码（先把它叫做『字节码』吧），在第85行中调用interpret();来执行解释器，进入主线：终之章：代理人 - 解释器。
  8. 完结。

63行调用了一次getsym()之后，if分支里有这么一段代码：

1
2
addset(nxtlev, declbegsys, statbegsys, symnum);  //addset函数做什么事？集合并运算，集合nxtlev是declbegsys与statbegsys的并
nxtlev[period] = true;              //后跟符号可以是句号period

乍一看有些迷惑，declbegsys, statbegsys这俩是从哪来的？？？是什么东西？

根据ide和注释的提示，这两分别是声明开始的符号集合和语句开始的符号集合，这句话就是把声明开始的符号集合和语句开始的符号集合并起来，加到nxtlev中。

但是之前好像都没动过啊？不应该是未初始的状态吗？

其实并不是，还记得之前的那个init()吗？对，没错，就是这个函数。这两个家伙在init()的时候就已经被初始化了：

展开阅读 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 设置符号集 */
for (i = 0; i < symnum; i++) {
  declbegsys[i] = false;
  statbegsys[i] = false;
  facbegsys[i] = false;
}

/* 设置声明开始符号集 */
declbegsys[constsym] = true;
declbegsys[varsym] = true;
declbegsys[procsym] = true;

/* 设置语句开始符号集 */
statbegsys[beginsym] = true;
statbegsys[callsym] = true;
statbegsys[ifsym] = true;
statbegsys[whilesym] = true;

/* 设置因子开始符号集 */
facbegsys[ident] = true;
facbegsys[number] = true;
facbegsys[lparen] = true;

至于为什么要先getsym()，等到主线：本体 - block下的真面目的时候再讲。

支线：欲善其事，必先利其器 - 初始化

这节的任务的是main函数中调用的init()。

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
void init() {
  int i;

  /* 设置单字符符号 */
  for (i = 0; i <= 255; i++) {
    ssym[i] = nul;
  }
  ssym['+'] = plus;
  ssym['-'] = minus;
  ssym['*'] = times;
  ssym['/'] = slash;
  ssym['('] = lparen;
  ssym[')'] = rparen;
  ssym['='] = eql;
  ssym[','] = comma;
  ssym['.'] = period;
  ssym['#'] = neq;
  ssym[';'] = semicolon;

  /* 设置保留字名字，按照字母顺序，便于折半查找 */
  strcpy(word[0], "begin");
  strcpy(word[1], "call");
  strcpy(word[2], "const");
  strcpy(word[3], "do");
  strcpy(word[4], "end");
  strcpy(word[5], "if");
  strcpy(word[6], "odd");
  strcpy(word[7], "procedure");
  strcpy(word[8], "read");
  strcpy(word[9], "then");
  strcpy(word[10], "var");
  strcpy(word[11], "while");
  strcpy(word[12], "write");

  /* 设置保留字符号 */
  wsym[0] = beginsym;
  wsym[1] = callsym;
  wsym[2] = constsym;
  wsym[3] = dosym;
  wsym[4] = endsym;
  wsym[5] = ifsym;
  wsym[6] = oddsym;
  wsym[7] = procsym;
  wsym[8] = readsym;
  wsym[9] = thensym;
  wsym[10] = varsym;
  wsym[11] = whilesym;
  wsym[12] = writesym;

  /* 设置指令名称 */
  strcpy(mnemonic[lit], "lit");
  strcpy(mnemonic[opr], "opr");
  strcpy(mnemonic[lod], "lod");
  strcpy(mnemonic[sto], "sto");
  strcpy(mnemonic[cal], "cal");
  strcpy(mnemonic[inte], "int");
  strcpy(mnemonic[jmp], "jmp");
  strcpy(mnemonic[jpc], "jpc");

  /* 设置符号集 */
  for (i = 0; i < symnum; i++) {
    declbegsys[i] = false;
    statbegsys[i] = false;
    facbegsys[i] = false;
  }

  /* 设置声明开始符号集 */
  declbegsys[constsym] = true;
  declbegsys[varsym] = true;
  declbegsys[procsym] = true;

  /* 设置语句开始符号集 */
  statbegsys[beginsym] = true;
  statbegsys[callsym] = true;
  statbegsys[ifsym] = true;
  statbegsys[whilesym] = true;

  /* 设置因子开始符号集 */
  facbegsys[ident] = true;
  facbegsys[number] = true;
  facbegsys[lparen] = true;
}

这节其实挺好懂的，看注释就知道了，这里就不细讲了。

主线：间章：文字的拆解 - 词法分析

这里先贴出getsym()的代码：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
 * 词法分析，获取一个符号      
 * 这里的符号指的是：一个标识符、保留字、整数、运算符或者标点符号（逗号、分号、句号）
 */
int getsym() {
  int i, j, k;

  while (ch == ' ' || ch == 10 || ch == 9) {   /* 忽略空格、换行和TAB */
    getchdo;
  }
  if (ch >= 'a' && ch <= 'z') {                    /* 名字或保留字以a~z开头*/
    k = 0;
    do {
      if (k < al) {         //al是10，al表示标识符的最大长度为10
        a[k] = ch;
        k++;
      }
      getchdo;
    } while (ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9');
    //当do while循环结束时，ch的值是源代码中刚读取的标识符右边一个字符
    a[k] = 0;            //数组a[]，char a[11]
    strcpy(id, a);
    i = 0;
    j = norw - 1;            //norw值为13，共13个保留字
    do {                  /* 搜索当前符号是否为保留字 */
      k = (i + j) / 2;
      /*
        这里的折半查找代码逻辑有点怪，但是正确。
        第一种情形，当strcmp(id,word[k]) == 0时，j=k-1，i=k+1， while(i<=j)循环结束，if(i-1>j)条件成立
        第二种情形，word数组中找不到id这个保留字，当while(i<=j)循环结束时，j值等于i-1，if(i-1>j)条件不成立
      */
      if (strcmp(id, word[k]) <= 0) {
        j = k - 1;
      }
      if (strcmp(id, word[k]) >= 0) {
        i = k + 1;
      }
    } while (i <= j);
    if (i - 1 > j) {
      sym = wsym[k];      // 在pl0.h中声明了全局变量sym    enum symbol sym;
    } else {
      sym = ident;            /* 搜索失败，则是名字或数字 */
    }
  } else {
    if (ch >= '0' && ch <= '9') {                  /* 检测是否为数字：以0~9开头 */
      k = 0;
      num = 0;
      sym = number;
      do {
        num = 10 * num + ch - '0';
        k++;
        getchdo;
      } while (ch >= '0' && ch <= '9');    /* 获取数字的值 */
      k--;      //k是整数的位数减1，例如读取整数108，则执行完k--以后，k值为2
      if (k > nmax) {   //在pl0.h文件中将nmax设为9，int数据最大为10位整数2147483247，各位编号从0到9
        error(30);
      }
    } else {
      if (ch == ':') {           /* 检测赋值符号 */
        getchdo;
        if (ch == '=') {
          sym = becomes;
          getchdo;
        } else {
          sym = nul;        /* 不能识别的符号 */
        }
      } else {
        if (ch == '<')          /* 检测小于或小于等于符号 */
        {
          getchdo;
          if (ch == '=') {
            sym = leq;
            getchdo;
          } else {
            sym = lss;
          }
        } else {
          if (ch == '>')          /* 检测大于或大于等于符号 */
          {
            getchdo;
            if (ch == '=') {
              sym = geq;
              getchdo;
            } else {
              sym = gtr;
            }
          } else {
            sym = ssym[ch];      /* 当符号不满足上述条件时，全部按照单字符符号处理 */
            if (sym != period) {
              getchdo;
            }
          }
        }
      }
    }
  }
  return 0;
}

卧槽这满屏的if谁看得懂啊.jpg

别慌，这其实就是一个自动机的实现罢了。自动机可以有很多实现方法，最简单的就是if大法和switch-case，有时候也可以基于事件来实现，这些上网搜搜就知道是怎么一回事了。

？还是看不懂？

那就换个写法，咱不要if了，用switch-case写：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
void Lexer::lexToken(Token &token) {
    LexStart:
    // 过滤空格等
    if (isWhitespace(*buffer)) {
        do {
            ++buffer;
            ++currPos;
        } while (isWhitespace(*buffer));
    }

    switch (*buffer) {
        case '\0':
            stop = true;

        // 换行，重置相关参数
        case '\r':
            buffer++;
            currLine++;
            currPos = 0;
            goto LexStart;
        case '\n':
            buffer++;
            currLine++;
            currPos = 0;
            goto LexStart;
        // 处理小于号和小于号开头的符号
        case '<': {
            char next = *(buffer+1);
            if (next == '=') {
                int length = 2;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);

            // 实际上TokenType其实应该更详细点，例如大于等于号，大于号，逗号这种具体的符号
            // 为简单起见，只分成五大类，况且题目只要求分成五大类（
            // 这里加了个"<<"这种符号的解析只不过是为了展示分类具体符号情况下的实现
            } else if (next == '<') {
                int length = 2;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);

            } else {
                int length = 1;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);
            }
        }
        
        case '>': {
            char next = *(buffer+1);
            if (next == '=') {
                int length = 2;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);

            } else {
                int length = 1;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);
            }
        }

        case ':': {
            char next = *(buffer+1);
            if (next == '=') {
                int length = 2;
                Lexer::setToken(token, TokenType::OPERATOR, buffer, length);
                return Lexer::move(length);

            } else {
                int length = 1;
                Lexer::setToken(token, TokenType::UNKNOWN, buffer, length);
                return Lexer::move(length);
            }
        }

        // 单符号运算符
        case '+': case '-': case '*':
        case '/': case '#': case '=': {
            Lexer::setToken(token, TokenType::OPERATOR, buffer, 1);
            return Lexer::move(1);
        }

        // 界符，句号'.'特别关照
        case '.':
//            stop = true;
        case '(': case ')': case ',':
        case ';': /*   '.' */ {
            Lexer::setToken(token, TokenType::DELIMITER, buffer, 1);
            return Lexer::move(1);
        }

        // 数字
        case '0' ... '9': {
            return Lexer::lexNumber(token);
        }

        // 标识符，为简单起见，这里只接受ascii字母'a'-'z','A'-'Z'以及下划线'_'作为标识符，utf8字符不考虑
        case 'A' ... 'Z':
        case 'a' ... 'z':
        case '_' : {
            return Lexer::lexIdentifier(token);
        }

        default:
            Lexer::setToken(token, TokenType::UNKNOWN, buffer, 1);
            return Lexer::move(1);
    }
}

这一部分代码存档在lensfrex/compile-work中

这里的buffer++，就代表指针向下移动，输入下一个字符，对应着原函数的getch()，本质上是一样的。

还是太长了看不懂？…好吧，咱就再简化一下，把他的本质给显现出来：

展开阅读 
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
void Lexer::lexToken(Token &token) {
    LexStart:
    // 过滤空格等
    if (isWhitespace(*buffer)) {/*...*/}

    switch (*buffer) {
        case '\0':
            stop = true;

        // 换行，重置相关参数
        case '\r':
        case '\n':
          // 当前状态遇到了'\r'或者'\n'符号进行的动作
        case '<': 
          // 当前状态遇到了'<'符号进行的动作
        
        case '>': 
          // 当前状态遇到了'>'符号进行的动作
        
        case ':':
          // 同上

        // 单符号运算符
        case '+': case '-': case '*':
        case '/': case '#': case '=': 
          // 同上

        // 界符，句号'.'特别关照
        case '.':
          // 同上

        // 数字
        case '0' ... '9': 
          // 同上

        case 'A' ... 'Z':
        case 'a' ... 'z':
        case '_' : 
          // 同上

        default:
          // 啥都不是
    }
}

再回想一下书上的那个词法分析状态机，是不是有点头绪了？没错，就是自动机代码的实现。读入了一个字符，就根据case来进入相应的状态处理，处理完之后就goto LexStart;，重新读入下一个字符（转换下一个状态），直到进入终态，生成token（词法单元）

再来看看原来的那一大串if，耐着性子慢慢看（可以把所有的if都折叠起来再一层一层展开来看）。自己照着这段代码人脑运行，就能发现，欸，就是自动机的模拟实现：首先是遇到小写字母 ‘a’ ~ ‘z’，就进入输入a~z的自动机状态（也就是if分支），如果不是，就进入另一个自动机状态（else分支），以此类推下去不断地转换状态，直到进入相应的终态。

实际上就是“遇到一个输入，进入对应的状态分支，然后再接受下一个输入”这么一个过程。只不过因为词法分析的状态机比较复杂，用if实现就会过于吓人，也不好维护。翻看clang和gcc编译器的源码就能发现他们的词法分析也都是基于switch-case实现的。

回到主题，状态机最后进入到了终态，运行getchdo;。这是一个宏，展开之后的代码就是if (-1 == getch()) return -1，输入下一个符号并返回，重新运行自动机。在此之前，还得对符号进行分类呢，在getchdo;的前面通常有sym = [符号类型]，就是对这些符号进行分类，比如大于号，等于号，标识符等等，以供后续编译分析使用。

总之，如果能理解自动机理论，这个其实不难阅读和理解，只是东西多了有点吓人罢了。

主线：本体 - block下的真面目

这个程序真正的精华就在这个block()函数了。

快把代码端上来罢：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
int block(int lev, int tx, bool *fsys) {
  int i;
  int dx;      /* 名字分配到的相对地址 */
  int tx0;    /* 保留初始tx */
  int cx0;    /* 保留初始cx */
  bool nxtlev[symnum];  /* 在下级函数的参数中，符号集合均为值参，但由于使用数组实现，传递进来的是指针，为防止下级函数改变上级函数的集合，开辟新的空间传递给下级函数 */

  dx = 3;
  tx0 = tx;    /* 记录本层名字的初始位置 */
  //在main函数中第一次调用block函数时，table[tx].adr = cx;  实际上就是table[0].adr = 0;
  table[tx].adr = cx;
  gendo(jmp, 0, 0);
  if (lev > levmax) {
    error(32);
  }
  do {
    if (sym == constsym)    /* 收到常量声明符号，开始处理常量声明 */
    {
      getsymdo;
      do {
        /* dx的值会被constdeclaration改变，使用指针 */
        constdeclarationdo(&tx, lev, &dx);
        while (sym == comma) {
          getsymdo;
          constdeclarationdo(&tx, lev, &dx);
        }
        if (sym == semicolon) {
          getsymdo;
        } else {
          error(5);    /* 漏掉了逗号或者分号 */
        }
      } while (sym == ident);
    }
    if (sym == varsym)      /* 收到变量声明符号，开始处理变量声明 */
    {
      getsymdo;
      do {
        vardeclarationdo(&tx, lev, &dx);
        while (sym == comma) {
          getsymdo;
          vardeclarationdo(&tx, lev, &dx);
        }
        if (sym == semicolon) {
          getsymdo;
        } else {
          error(5);
        }
      } while (sym == ident);
    }
    while (sym == procsym)    /* 收到过程声明符号，开始处理过程声明 */
    {
      getsymdo;
      if (sym == ident) {
        //printf("procedure tx = %d dx = %d\n", tx, dx);
        enter(procedur, &tx, lev, &dx);    /* 记录过程名字 */
        //printf("procedure tx = %d dx = %d\n", tx, dx);
        getsymdo;
      } else {
        error(4);    /* procedure后应为标识符 */
      }
      if (sym == semicolon) {
        getsymdo;
      } else {
        error(5);    /* 漏掉了分号 */
      }
      memcpy(nxtlev, fsys, sizeof(bool) * symnum);  //将当前模块的后跟符号集合复制给procedure
      nxtlev[semicolon] = true;          //procedure的后跟符号可以是分号
      if (-1 == block(lev + 1, tx, nxtlev)) {
        return -1;    /* 递归调用 */
      }
      if (sym == semicolon) {
        getsymdo;
        memcpy(nxtlev, statbegsys, sizeof(bool) * symnum);
        nxtlev[ident] = true;
        nxtlev[procsym] = true;
        testdo(nxtlev, fsys, 6);
      } else {
        error(5);    /* 漏掉了分号 */
      }
    }
    memcpy(nxtlev, statbegsys, sizeof(bool) * symnum);
    nxtlev[ident] = true;
    nxtlev[period] = true;
    testdo(nxtlev, declbegsys, 7);
  } while (inset(sym, declbegsys));    /* 直到没有声明符号 */
  //printf("tx0=%d\n",tx0);
  //printf("table[tx0].adr=%d\n",table[tx0].adr);
  //printf("cx=%d\n",cx);

  /*
    在main函数第一次调用block函数时，table[0].adr = 0
    所以下面的table[tx0].adr就是0，tx0目前是0
    我们暂时不考虑嵌套的procedure，不考虑block递归调用block函数。
    code[0].a = cx;  cx目前是1
    相当于把code[0]这条指令从jmp 0 0，改为jmp 0 1
    主过程从code[1]开始执行
  */
  code[table[tx0].adr].a = cx;    /* 开始生成当前过程代码 */
  table[tx0].adr = cx;        /* 当前过程代码地址 */
  /* 可以认为：table[0]是存储主过程信息的。
     table[tx0].adr = cx;
     table[0].adr = 1;  表示主过程的第一条指令地址是1，主过程从code[1]对应的指令开始执行
  */
  /* 声明部分中每增加一条声明都会给dx增加1，声明部分已经结束，dx就是当前过程数据的size */
  //当前过程需要dx个内存单元，每个内存单元存储一个整数
  table[tx0].size = dx;
  //cx0是当前过程的入口地址。code[cx0]是当前过程的第一条指令。
  cx0 = cx;
  gendo(inte, 0, dx);          /* 生成分配内存代码 */
  if (tableswitch)            /* 输出名字表 */
  {
    printf("TABLE:\n");
    if (tx0 + 1 > tx) {
      printf("NULL:\n");
    }
    for (i = tx0 + 1; i <= tx; i++) {
      switch (table[i].kind) {
        case constant:
          printf("%d const %s ", i, table[i].name);      //在%s右边加一个空格以分隔输出的字符串
          printf("val=%d\n", table[i].val);
          fprintf(fas, "%d const %s ", i, table[i].name);  //在%s右边加一个空格以分隔输出的字符串
          fprintf(fas, "val=%d\n", table[i].val);
          break;
        case variable:
          printf("%d var %s ", i, table[i].name);      //在%s右边加一个空格以分隔输出的字符串
          printf("lev=%d addr=%d\n", table[i].level, table[i].adr);
          fprintf(fas, "%d var %s ", i, table[i].name);    //在%s右边加一个空格以分隔输出的字符串
          fprintf(fas, "lev=%d addr=%d\n", table[i].level, table[i].adr);
          break;
        case procedur:
          printf("%d proc %s ", i, table[i].name);      //在%s右边加一个空格以分隔输出的字符串
          printf("lev=%d addr=%d size=%d\n", table[i].level, table[i].adr, table[i].size);
          fprintf(fas, "%d proc %s ", i, table[i].name);    //在%s右边加一个空格以分隔输出的字符串
          fprintf(fas, "lev=%d addr=%d size=%d\n", table[i].level, table[i].adr, table[i].size);
          break;
      }
    }
    printf("\n");
  }
  /* 语句后跟符号为分号或end */
  memcpy(nxtlev, fsys, sizeof(bool) * symnum);  /* 每个后跟符号集都包含上层后跟符号集合，以便补救 */
  nxtlev[semicolon] = true;
  nxtlev[endsym] = true;
  statementdo(nxtlev, &tx, lev);  //////////////////////////////////////看这个函数，当前已读取的符号为beginsym
  gendo(opr, 0, 0);      /* 每个过程出口都要使用的释放数据段命令 */
  memset(nxtlev, 0, sizeof(bool) * symnum);    /* 分程序没有补救集合 */
  test(fsys, nxtlev, 8);            /* 检测后跟符号正确性 */
  //listcode(cx0);								/* 输出代码 */
  return 0;
}

太长不看？

好吧，咱先把所有的if和while折叠起来看，待会再慢慢剥开分析：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
 * 编译程序主体
 *
 * lev: 当前分程序所在层
 * tx: 名字表当前尾指针
 * fsys: 当前模块后跟符号集合
 */
int block(int lev, int tx, bool *fsys) {
  int i;
  int dx;      /* 名字分配到的相对地址 */
  int tx0;    /* 保留初始tx */
  int cx0;    /* 保留初始cx */
  bool nxtlev[symnum];  /* 在下级函数的参数中，符号集合均为值参，但由于使用数组实现，传递进来的是指针，为防止下级函数改变上级函数的集合，开辟新的空间传递给下级函数 */

  dx = 3;
  tx0 = tx;    /* 记录本层名字的初始位置 */
  //在main函数中第一次调用block函数时，table[tx].adr = cx;  实际上就是table[0].adr = 0;
  table[tx].adr = cx;
  gendo(jmp, 0, 0);
  if (lev > levmax) {
    error(32);
  }
  do {
    if (sym == constsym) {   /* 收到常量声明符号，开始处理常量声明 */ }
    if (sym == varsym) {     /* 收到变量声明符号，开始处理变量声明 */ }
    while (sym == procsym) {   /* 收到过程声明符号，开始处理过程声明 */}
    memcpy(nxtlev, statbegsys, sizeof(bool) * symnum);
    nxtlev[ident] = true;
    nxtlev[period] = true;
    testdo(nxtlev, declbegsys, 7);
  } while (inset(sym, declbegsys));    /* 直到没有声明符号 */

  /*
    在main函数第一次调用block函数时，table[0].adr = 0
    所以下面的table[tx0].adr就是0，tx0目前是0
    我们暂时不考虑嵌套的procedure，不考虑block递归调用block函数。
    code[0].a = cx;  cx目前是1
    相当于把code[0]这条指令从jmp 0 0，改为jmp 0 1
    主过程从code[1]开始执行
  */
  code[table[tx0].adr].a = cx;    /* 开始生成当前过程代码 */
  table[tx0].adr = cx;        /* 当前过程代码地址 */
  /* 可以认为：table[0]是存储主过程信息的。
     table[tx0].adr = cx;
     table[0].adr = 1;  表示主过程的第一条指令地址是1，主过程从code[1]对应的指令开始执行
  */
  /* 声明部分中每增加一条声明都会给dx增加1，声明部分已经结束，dx就是当前过程数据的size */
  //当前过程需要dx个内存单元，每个内存单元存储一个整数
  table[tx0].size = dx;
  //cx0是当前过程的入口地址。code[cx0]是当前过程的第一条指令。
  cx0 = cx;
  gendo(inte, 0, dx);          /* 生成分配内存代码 */
  if (tableswitch) {           /* 输出名字表 */}
  /* 语句后跟符号为分号或end */
  memcpy(nxtlev, fsys, sizeof(bool) * symnum);  /* 每个后跟符号集都包含上层后跟符号集合，以便补救 */
  nxtlev[semicolon] = true;
  nxtlev[endsym] = true;
  statementdo(nxtlev, &tx, lev);  //////////////////////////////////////看这个函数，当前已读取的符号为beginsym
  gendo(opr, 0, 0);      /* 每个过程出口都要使用的释放数据段命令 */
  memset(nxtlev, 0, sizeof(bool) * symnum);    /* 分程序没有补救集合 */
  test(fsys, nxtlev, 8);            /* 检测后跟符号正确性 */
  //listcode(cx0);								/* 输出代码 */
  return 0;
}

在block()函数里，主要做了这么几个事：

  1. 生成第一行指令：jmp
    这里调用了gendo(jmp, 0, 0);，这也是个宏，展开之后就是if (-1 == gen(jmp, 0, 0)) return -1的函数调用，这样，当虚拟机开始运行的时候就能够跳转到程序开始的地方开始执行。详见支线：魔导书 - 虚拟机指令

    第一步之后，有一个判断程序块嵌套是不是套娃套太深了：

    1
    2
    3
    if (lev > levmax) {
      error(32);
    }

    咱们的pl0语言是支持程序块（可以理解成函数）的嵌套，也就是块里面再定义另一个程序块。但是也不能无限套娃吧，所以咱就设定最大套娃层数为levmax层，套娃太深了就报错，不继续编译了。

  2. 循环分析声明语句，生成符号表。名称表等等。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    do {
      if (sym == constsym) {   /* 收到常量声明符号，开始处理常量声明 */ }
      if (sym == varsym) {     /* 收到变量声明符号，开始处理变量声明 */ }
      while (sym == procsym) {   /* 收到过程声明符号，开始处理过程声明 */}
      memcpy(nxtlev, statbegsys, sizeof(bool) * symnum);
      nxtlev[ident] = true;
      nxtlev[period] = true;
      testdo(nxtlev, declbegsys, 7);
    } while (inset(sym, declbegsys));    /* 直到没有声明符号 */

    还记得之前在main()中进入这个block()前在if里面调用了一次getsym()吗？是的，就是为这里的几个if和while准备的。如果首次进入block()前没有调用getsym()，这里就会出错。

支线：魔导书 - 虚拟机指令

翻看咱们的pl0.h头文件，可以知道咱们的虚拟机有这些指令：

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 虚拟机代码 */
enum fct {
  lit, opr, lod,
  sto, cal, inte,
  jmp, jpc,
};

/* 虚拟机代码结构 */
struct instruction {
  enum fct f;    /* 虚拟机代码指令 */
  int l;      /* 引用层与声明层的层次差 */
  int a;      /* 根据f的不同而不同 */
};

此外，有一个用来生成虚拟机代码的函数：
s

展开阅读 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * 生成虚拟机代码
 *
 * x: instruction.f;
 * y: instruction.l;
 * z: instruction.a;
 */
int gen(enum fct x, int y, int z) {
  if (cx >= cxmax) {
    printf("Program too long");
    return -1;
  }
  code[cx].f = x;
  code[cx].l = y;
  code[cx].a = z;
  cx++;
  return 0;
}

这里的code就是咱们程序的指令组，是个数组，至于cx，可以理解为程序计数器，或者指令地址。

主线：终之章：代理人 - 解释器

有一说一，个人感觉解释器部分非常好懂好懂（可能是最近在研究模拟器的原因吧）。实际上就是模拟一个cpu运行的过程（其实也是状态机的实现）。

还是先把解释器的代码端上来看看吧：

展开阅读 
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/*
 * 解释程序
 */
void interpret() {
  int p, b, t;        /* 指令指针，指令基址，栈顶指针 */
  struct instruction i;  /* 存放当前指令 */
  int s[stacksize];    /* 栈 */

  printf("start pl0\n");
  t = 0;
  b = 0;
  p = 0;
  s[0] = s[1] = s[2] = 0;
  do {
    i = code[p];    /* 读当前指令 */
    p++;
    switch (i.f) {
      case lit:    /* 将a的值取到栈顶 */
        s[t] = i.a;
        t++;
        break;
      case opr:    /* 数学、逻辑运算 */
        switch (i.a) {
          case 0:
            t = b;
            p = s[t + 2];
            b = s[t + 1];
            break;
          case 1:
            s[t - 1] = -s[t - 1];
            break;
          case 2:
            t--;
            s[t - 1] = s[t - 1] + s[t];
            break;
          case 3:
            t--;
            s[t - 1] = s[t - 1] - s[t];
            break;
          case 4:
            t--;
            s[t - 1] = s[t - 1] * s[t];
            break;
          case 5:
            t--;
            s[t - 1] = s[t - 1] / s[t];
            break;
          case 6:
            s[t - 1] = s[t - 1] % 2;
            break;
          case 8:
            t--;
            s[t - 1] = (s[t - 1] == s[t]);
            break;
          case 9:
            t--;
            s[t - 1] = (s[t - 1] != s[t]);
            break;
          case 10:
            t--;
            s[t - 1] = (s[t - 1] < s[t]);
            break;
          case 11:
            t--;
            s[t - 1] = (s[t - 1] >= s[t]);
            break;
          case 12:
            t--;
            s[t - 1] = (s[t - 1] > s[t]);
            break;
          case 13:
            t--;
            s[t - 1] = (s[t - 1] <= s[t]);
            break;
          case 14:
            printf("%d", s[t - 1]);
            fprintf(fa2, "%d", s[t - 1]);
            t--;
            break;
          case 15:
            printf("\n");
            fprintf(fa2, "\n");
            break;
          case 16:
            printf("?");
            fprintf(fa2, "?");
            //数组下标[]是1级运算符，取地址&是2级运算符。不需要写成&(s[t])
            scanf("%d", &s[t]);
            fprintf(fa2, "%d\n", s[t]);
            t++;
            break;
        }
        break;
      case lod:  /* 取相对当前过程的数据基地址为a的内存的值到栈顶 */
        s[t] = s[base(i.l, s, b) + i.a];
        t++;
        break;
      case sto:  /* 栈顶的值存到相对当前过程的数据基地址为a的内存 */
        t--;
        s[base(i.l, s, b) + i.a] = s[t];
        break;
      case cal:  /* 调用子过程 */
        s[t] = base(i.l, s, b);  /* 将父过程基地址入栈 */
        s[t + 1] = b;        /* 将本过程基地址入栈，此两项用于base函数 */
        s[t + 2] = p;        /* 将当前指令指针入栈 */
        b = t;          /* 改变基地址指针值为新过程的基地址 */
        p = i.a;        /* 跳转 */
        break;
      case inte:          /* 分配内存 */
        t += i.a;
        break;
      case jmp:          /* 直接跳转 */
        p = i.a;
        break;
      case jpc:          /* 条件跳转 */
        t--;
        //王磊 2022.12.10 按照C语言的规定，0表示假，非0表示真。所以jpc是条件不满足时，跳转
        if (s[t] == 0) {
          p = i.a;
        }
        break;
    }
  } while (p != 0);
}

归根到底，就是根据指令的动作来对内存数据进行处理，取指，取址，然后读写对应的内存数据。如果学了计组的话，很好懂，就是cpu的运行和过程。

这种运行时还有一个名字，就是『虚拟机』。早期的java等等vm语言就是基于这种解释器来运行编译后的『字节码』。咱们上面编译出的东西其实就类似于这个『字节码』。

可以把咱们的这个『虚拟机』看成一个真正的计算机，上面编译出来的东西（字节码），就是他的程序，只不过没有操作系统，程序来直接控制机器。

实际上操作系统的本质就是一类程序，只不过有了操作系统，那些启动初始化，内存的底层分配，IO调度，线程调度之类的脏活累活操作系统都帮我们干了，咱们写程序的时候只需要调用系统接口就行了。

一些后话