Ylin's Blog
0%

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

书接上回，接着研究一下AVL树。

AVL树

在二叉搜索树中，我们可以知道，在多次的插入和删除之后，二叉树的左右可能会失去平衡，从而导致退化成链表，在这样的情况下我们的算法的效率会从O(logn)退化到O(n)：

image.png
image.png

但是我们接下来将要提到的AVL树，将解决这些问题

AVL树的常见术语

AVL树本质是二叉搜索树和二叉平衡树的结合，所以同时满足这两种树的性质：

  1. 节点高度

“节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。这里我们让叶子节点的高度为0，把空节点的高度设置为-1。我们将根据这些性质来编写我们的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct TreeNode{
    int val{};
    int height = 0;
    TreeNode* left{};
    TreeNode* right{};
    TreeNode() = default;
    explicit TreeNode(int x): val(x) {} 
};

// 获取高度
int height(TreeNode* node){
    return node == nullptr ? -1 : node->height;
}

// 更新节点高度
void updateHeight(TreeNode* node){
    // 当前节点的高度 = 最高子树高度 + 1
    node->height = max(height(node->left),height(node->right)) + 1;
}
  1. 节点的平衡因子

节点的平衡因子定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。对于AVL树，我们要求树中任意节点的平衡因子-1<=f<=1，否则这个树就进入了失衡状态。我们可以写出以下函数：

1
2
3
int balance(TreeNode* node){
    return node == nullptr ? 0 : height(node->left) - height(node->right);
}

AVL树的旋转

AVL树的精髓就在于旋转操作，当我们的树中存在失衡节点时，我们可以通过“旋转”操作，在不影响中序遍历序列的前提下，使失衡的节点重新回到平衡的状态。

我们将|平衡因子| > 1的节点称为失衡节点，根据不同的失衡情况，我们有四种旋转操作：

右旋

image.png

结合这张图来看，从底至顶看，二叉树中首个失衡节点是“节点3”。我们关注以该失衡 节点为根节点的子树，将该节点记为 node ，其左子节点记为 child ，执行“右旋”操作。完成右旋后，子树 恢复平衡，并且仍然保持二叉搜索树的性质。

但是对于，当节点child有右节点（记作grand_child）的情况下，我们需在右旋中添加一步：将grand_child设置为node的左子节点。

image.png

我们可以通过修改节点指针的方法来实现：

1
2
3
4
5
6
7
8
9
10
11
TreeNode* rightRotate(TreeNode* node){
    TreeNode* child = node->left;
    TreeNode* grandChild = child->right;
    child->right = node;
    // 当grandChild为null时无影响
    node->left = grandChild;
    updateHeight(child);
    updateHeight(node);
    // 右旋后child作为左子树的根节点
    return child;
}

左旋

左旋作为右旋的镜像版本，对应右节点失衡的情况，同样是下面的两种情况：

image.png
image.png

我们可以写出：

1
2
3
4
5
6
7
8
9
TreeNode* leftRotate(TreeNode* node){
    TreeNode* child = node->right;
    TreeNode* grandChild = child->left;
    child->left = node;
    node->right = grandChild;
    updateHeight(child);
    updateHeight(node);
    return child;
}

先左旋后右旋

对于下面这种情况，我们需要先对child进行左旋，再对node进行右旋：

image.png

先右旋后左旋

这种情况依旧是上一种情况的镜像对称情况：

image.png

旋转的选择

讲完了四种旋转的操作，现在我们需要分析，在什么情况下需要对我们的树进行哪些操作了，这里的话我推荐看一个视频：平衡二叉树(AVL树)_哔哩哔哩_bilibili

我们的步骤总结如下：

  • 先检查失衡节点的子节点child的平衡因子，大于0则需要进行右旋操作，小于0则需要进行左旋操作。
  • 然后检查失衡节点node的平衡因子，大于1则需要进行右旋操作，小于1则需要左旋操作。
  • 最后比较对子节点chlid和失衡节点node的需要进行的操作，如果相同则合并，不同则先操作子节点后操作失衡节点。

我们也可以用一张表来进行这个判断：

image.png

现在我们可以写出AVL树的平衡函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* rotate(TreeNode* node){
    int _balanceFactor = balance(node);
    TreeNode* child = node->left;
    if(_balanceFactor > 1){
        // 右旋
        if(balance(child)<-1)
            // 先左旋
            child = leftRotate(child);
        return rightRotate(node);
    }else if(_balanceFactor < -1){
        // 左旋
        if(balance(child)>1)
            // 先右旋
            child = rightRotate(child);
        return leftRotate(node);
    }else{
        // 平衡
        return node;
    }
}

AVL树的常用操作

  1. 插入节点

AVL树的节点插入操作和二叉搜索树一样，只不过在AVL树插入节点之后，从这个节点到根节点的路径上可能会出现一系列的失衡节点。所以我们需要从这个节点开始，自底向上的执行平衡操作，知道所有的失衡节点都恢复平衡。我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* _insert(TreeNode* node, int num){
    if(node==nullptr)
        return new TreeNode(num);
    if(num < node->val)
        node->left = _insert(node->left,num);
    else if(num > node->val)
        node->right = _insert(node->right,num);
    else 
        return node;
    
    updateHeight(node);
    return rotate(node);
}
  1. 删除操作

删除也是差不多，需要在删除的基础之上，从底部到顶部进行平衡操作，确保所有的失衡点都恢复平衡：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* _remove(TreeNode* node, int num){
    if(node==nullptr)
        return nullptr;
    if(num < node->val)
        node->left = _remove(node->left,num);
    else if(num > node->val)
        node->right =_remove(node->right,num);
    else{
        if(node->left==nullptr||node->right==nullptr){
            TreeNode* child = node->left==nullptr ? node->right : node->left;
            delete node;
            return child;
        }else{
            TreeNode* tmp = node->right;
            while(tmp->left !=nullptr)
                tmp = tmp->left;
            int val = tmp->val;
            node->right = _remove(node->right,tmp->val);
            node->val = val;
        }
    }
    updateHeight(node);
    return rotate(node);
}
  1. 查找操作

和二叉搜索树一样，没有变化

发表于 更新于 分类于
本文字数： 841 阅读时长 ≈ 1 分钟

十一月份已经过去了一半。回顾这个月我都做了什么，做到了什么呢？仔细一想是没有的，感觉时间过的好快，转眼间就过去了大半个学期，自己也是没什么收获，定下的很多目标都没有做到。

马上就要期中考试了，我希望能在各科都拿到一个比较好的成绩吧，因为这个学期对我的绩点来说是十分重要的。所以一定要好好加油，尤其是408相关的课程，一定要好好学，不能只是满足于书上的内容，不仅要掌握概念，也要会做题。要做好考研的准备吧，因为推免资格对我而言还是有点困难的，所以一定要好好加油。

这个月接触到了各种语言吧，学的很杂，接触到了Lua和他的游戏开发引擎，我之前说过想做一个游戏，但是思路上仍然是一头雾水，做一个什么样的游戏呢，要做哪些内容呢？我一点idea也没有，所以只能慢慢积累了，还有一些游戏开发相关的技术。所以我选择去了解一下星露谷物语的mod制作，它是用C#进行编写的，语法结构和Java差不多，所以我勉强能看懂一些，但是对于整个项目结构一点也不够了解。

我发现自己总是半途而废，我经常会突然想做什么，但是没办法一直做下去，我感觉要做的事情太多了，我不知道该怎么安排过来，所以也比较晕头转向的。接下来的一个月里，我打算好好夯实一下课内的知识吧，比如操作系统和数据结构，目前学习的过程中也明显感受到了清晰的需求。争取在这个学期把王道的课程也看掉一部分，感觉他讲的还是十分详细的。然后是概率论和离散数学，我也打算好好学一下了，每天坚持做一点题目，因为到现在为止，我对这两门科目都是不太了解。

还有的就是密码学 信息安全基础 程序设计一类的课程了，要想办法把平时分搞高一点，争取一下满绩吧。拉一拉我上上个学期拖得后腿。我发现密码学的很多知识还是比较有用的，因为会涉及到一些简单的数论和密码学体制。我以前总是抗拒听老师的课，但是其实我自己也不知道要做什么，何妨不听一听呢。

然后感觉最近心态好了很多吧，平时不会想那么多了。以后有空的话我也想试试出去旅游，然后玩一点剧情类的游戏。有空的话想拍一点游戏视频。尝试各种各样的事情。我想自己的人生开阔一点，可是我总是半途而废，总是做不到，但是既然有这样的想法就试一试吧。希望未来会越来越好，有很多开心的事在等着我。

我也想坚持锻炼身体，希望能健健康康的

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

打算系统性的学一下数据结构与算法，这个就相当于笔记做一下记录了。 # 树

二叉树

二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。我们可以用以下数据结构表示：

1
2
3
4
5
6
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

这里每个节点都有两个引用，分别为左右子节点，中间的节点为这两个节点的父节点。左右子树的概念也可以类推。在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

二叉树常用的术语

二叉树中的性质较为复杂，所以我们需要记住许多相关的术语：

  • 根节点：位于二叉树顶层的节点，没有父节点。
  • 叶节点：没有子节点的节点，其两个指针均指向 None
  • 边：连接两个节点的线段，即节点引用（指针）
  • 节点所在的层：从顶至底递增，根节点所在层为1。
  • 节点的度：节点的子节点的数量。在二叉树中，度的取值范围是0、1、2。
  • 二叉树的高度：从根节点到最远叶节点所经过的边的数量
  • 节点的深度：从根节点到该节点所经过的边的数量。
  • 节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量。
image.png

二叉树的基本操作

  1. 初始化二叉树

​ 初始化节点，并构造引用：

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);

    n1->left = n2;
    n1->right = n3;
    n2->left = n4;
    n2->right = n5;
}
  1. 插入与删除节点

​ 二叉树中的插入与删除节点可以通过修改指针实现，效果见下图：

image.png

二叉树的类型

完美二叉树

完美二叉树的所有层的节点都被完全填满。且在完美二叉树中，叶节点的度为0，其余所有节点的度都为2；若树的高度为ℎ，则节点总数为2ℎ+1−1，呈现标准的指数级关系：

image.png

关于完美二叉树，我们需要注意到它的几个性质：

  • 第i层的节点数量： 2i − 1
  • 高度为h的树的叶节点数量：2h
  • 高度为h的树的节点总数： 2h + 1 − 1
  • 节点总数为n的树的高度：log2(n + 1) − 1

完全二叉树

完全二叉树只有最底层的节点未被填满，且最底层的节点尽量靠左边。

注：完美二叉树是一种特殊的完全二叉树

image.png

完满二叉树

完满二叉树除了叶子节点之外，其余所有节点都有两个子节点：

image.png

平衡二叉树

平衡二叉树中的任意节点的左子树和右子树的高度之差的绝对值不超过1，|左子树高度-右子树高度|<=1

image.png

二叉树遍历

常见的二叉树遍历有：层序遍历、前序遍历、中序遍历和后序遍历

层序遍历

层序遍历是从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。这种遍历方式本质上属于广度优先遍历，我们也称之为广度优先搜索：

image.png

其代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> BFS(TreeNode* root){
    queue<TreeNode*> q;		// 用于存放遍历序列
    q.push(root);
    vector<int> vec;
    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();			// 将需要处理的节点出列
        vec.push_back(node->val);
        if(node->left!=nullptr)
            q.push(node->left);
        if(node->right!=nullptr)
            q.push(node->right);
    }
    return vec;
}

前中后序遍历

相应的这种遍历方式实际上是一种深度优先的遍历，我们称之为深度有限的搜索。这里我们有三种不同的遍历顺序，我们可以通过简单的递归来实现，具体实现如下。就不做过多的说明，因为很直观：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 前序
void preOrder(TreeNode* root){
    if(root==nullptr)
        return;
    cout << root->val << endl;
    preOrder(root->left);
    preOrder(root->right);
}
// 中序
void inOrder(TreeNode* root){
    if(root==nullptr)
        return;
    inOrder(root->left);
    cout << root->val << endl;
    inOrder(root->right);
}
// 后序
void pastOrder(TreeNode* root){
    if(root==nullptr)
        return;
    pastOrder(root->left);
    pastOrder(root->right);    
    cout << root->val << endl;
}

二叉树的数组表示

我们先前对二叉树的实现是通过链表进行实现的，节点之间则通过指针连接。但是实际上我们也可以通过数组实现二叉树的结构。

表示完美二叉树

对于一颗完美二叉树，我们可以将所有的节点按照层序遍历的顺序存储一个数组中，则每个节点都对应唯一的数组索引，根据层序遍历的特性，我们也可以推导出父子节点之间的索引关系：

若某节点的索引为𝑖， 则该节点的左子节点索引为2𝑖+1，右子节点索引为2𝑖+2

这里的映射关系就相当于先前的指针，我们只需要知道当前的索引，就能找到其对应的左右节点

image.png

表示任意二叉树

完美二叉树是一个特例，在实际情况中，我们的二叉树中间层有很多None，如果层序遍历不包含这些None，那么我们就无法根据一个数组来还原二叉树的形态：

image.png

所以我们尝试在层序遍历的序列中显式的写出所有的None:

image.png

就可以清晰的表示一个二叉树的结构。当然需要注意的是，完全二叉树十分适合用数组来表示，我们知道其None只会出现在最底层的右边，一定出现在层序遍历序列的末尾。这意味着当我们对完全二叉树进行存储时，我们可以忽略所有的None

二叉树的数组实现

现在我们尝试用数组实现二叉树的结构，我们需要支持以下操作：

  • 给定某节点，获取其值、左右子节点、父节点
  • 获取前序、中序、后序遍历、层序遍历序列
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
#include <vector>
#include <iostream>

using namespace std;

class ArrayBinaryTree{
public:
    ArrayBinaryTree(vector<int> arr){
        tree = arr;
    }

    int size(){
        return tree.size();
    }

    int val(int i){
        if(i<0 || i>=size())
            return -1;
        return tree[i];
    }

    int left(int i){
        return 2*i+1;
    }

    int right(int i){
        return 2*i+2;
    }

    int parent(int i){
        return (i-1)/2;
    }

    vector<int> BFS(){
        vector<int> res;
        for(int i=0;i<size();i++)
            if(val(i)!=-1)
                res.push_back(val(i));
        return res;
    }

    void preOrder(int index){
        if(val(index)==-1)
            return;
        cout << val(index) << endl;
        preOrder(left(index));
        preOrder(right(index));
    }

    void inOrder(int index){
        if(val(index)==-1)
            return;
        inOrder(left(index));
        cout << val(index) << endl;
        inOrder(right(index));
    }

    void pastOrder(int index){
        if(val(index)==-1)
            return;
        pastOrder(left(index));
        pastOrder(right(index));
        cout << val(index) << endl;
    }
    
private:
    vector<int> tree;
};

二叉搜索树

如下图所示，二叉搜索树需要满足以下条件：

  • 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树所有节点的值
  • 任意节点的左右子树也时二叉搜索树，满足上一个条件
image.png

二叉搜索树的操作

我们将二叉搜索树封装为一个类BinarySerchTree，并声明一个成员变量root，指向树的节点。

  1. 查找节点

给定一个目标节点值num，我们可以很快的根据二叉搜索树的性质来查找，我们可以声明一个节点cur，从二叉树的根节点root出发，循环比较值，知道找到对应的节点。

二叉搜索树的查找操作实际上和二分查找差不多，循环次数最多为树的高度：

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode* search(int num){
           TreeNode* cur = root;
           while(cur != nullptr){
               if(cur->val < num)
                   cur = cur->right;
               else if(cur->val > num)
                   cur = cur->left;
               else
                   break;
           }
           return cur;
       }
  1. 插入节点

给定一个等待插入的元素num，为了保持二叉树的性质，我们进行以下步骤：

  • 查找插入位置：和查找操作相似，从根节点出出发，直到越过叶节点时退出循环。
  • 在该位置插入节点：初始化节点num，将该节点置于none的位置。
image.png

在编写的过程中我们需要注意两点：

  • 如果插入的数值已经存在，那么则不插入。
  • 使用pre节点保存cur的上一个位置，以为我们指定插入位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(int num){
           if(root == nullptr) return;
           TreeNode* cur = root;
           TreeNode* pre = nullptr;
           while(cur != nullptr){
               if(cur->val == num)
                   return;
               pre = cur;
               if(cur->val < num)
                   cur = cur->right;
               else
                   cur = cur->left;
           }
           TreeNode* node = new TreeNode(num);
           if(num > pre->val)
               pre->right = node;
           else
               pre->left = node;
       }
  1. 删除节点

在二叉树中查找到目标节点，并将其删除，和插入节点类似，我们需要保证在删除操作完成之后仍然保持着二叉树的性质。所以我们需要根据目标子节点的数量，分为0\1\2三种情况进行相应的处理。

对于度为0的情况，我们只需要简单的删除：

image.png

当度为1时，我们需要将待删除的节点替换成其子节点：

image.png

对于度为2的节点，我们则需要谨慎处理。首先我们需要找到一个能替换它的节点（左子树的最大值或是右子树的最小值），并将其删除，覆盖待删除的节点：

  • 找到待删除节点在中序遍历序列中的下一个节点，记为tmp
  • 用tmp的值覆盖待删除节点的值，并在书中递归删除节点tmp
image.png

代码实现如下：

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
void remove(int num){
    if(root == nullptr) return;
    TreeNode* cur = root;
    TreeNode* pre = nullptr;
    while(cur != nullptr){
        if(cur->val == num)
            break;
        pre = cur;
        if(cur->val < num)
            cur = cur->right;
        else
            cur = cur->left;
    }
    if(cur == nullptr) return;
    // 度为0/1
    if(cur->left==nullptr || cur->right==nullptr){
        TreeNode* child = cur->left==nullptr?cur->right:cur->left;
        if(cur!=root){
            if(pre->left==cur)
                pre->left = child;
            else
                pre->right = child;
        }else{
            root = child;
        }
        delete cur;
    }else{
        TreeNode* tmp = cur->right;
        // 寻找后继节点
        while(tmp->left!=nullptr)
            tmp = tmp->left;
        // 递归删除后继节点
        remove(tmp->val);
        cur->val = tmp->val;
    }
}
  1. 中序遍历有序

由于搜索二叉树的性质，当我们对其进行中序遍历时，总是会优先遍历下一个最小节点，所以我们知道：搜索二叉树的中序遍历时升序的。所以我们可以直接得到搜索二叉树的有序数据。

AVL树

之后单独开一篇讲 感觉比较复杂

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

在上一章中，我们完成了对函数体的解析，现在我们需要进一步解析函数体中的语句，还有程序中的表达式。我们需要将程序中的语句解析成我们的虚拟机能直接执行的语句，所以这一章中会有一点难度：

语句

我们的编译器中识别以下六种语句：

  • if(...) <statement>; [else <statement>;]
  • while (...) <statement>;
  • {<statement>;}
  • return xxx;
  • <;(empty statement)>
  • expression(这个我们稍后单独讨论)

现在我们要将这些语句转换成对应的汇编代码：

IF语句

IF语句的作用是跳转，根据条件表达式决定跳转的位置：

1
2
3
4
5
6
7
8
9
if (...) <statement> [else <statement>]

if (<cond>)                   <cond>
JZ a
<true_statement>   ===>     <true_statement>
else:                         JMP b
a:                           a:
<false_statement>           <false_statement>
b:                           b:

对应的流程就是：

  • 先执行条件表达式<cond>
  • 如果条件失败，则跳转到a的位置，执行else语句
  • 如果条件成功，则在执行<true_statement>之后，无条件跳转到b，结束判断。

我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(token==If){
       match(If);
       match('(');
       expression();
       match(')');
       *++text = JZ;
       b = ++text;
       statement();
       if(token==Else){
           match(Else);
           *b = (int)(text + 2);
           *++text = JMP;
           b = ++text;
           statement();
       }
       *b = (int)(text);
   }

我们可以从栈的视角进行解释，text始终是指向下一条要执行的指令的。我们希望JZ后面跟着的是else的代码块的入口或是if判断之后的地址。

这里我们使用了延迟绑定地址的方式，我们来看看以下两种情况：

  • 只有if，我们将在执行完if_statement之后，将JZ之后的跳转地址设置成下一条指令的地址text
  • 有else，我们希望能够跳转到else的起始地址，我们需要在当前text指向的地址基础上+2，因为我们需要跳过JMP和出口地址所占用的指令空间。同时我们需要将if_statement之后的地址设置成判断的出口，即else_statement的后一条指令

While语句

While语句的汇编代码更加简单，如下：

1
2
3
4
5
6
a:                     a:
while (<cond>)        <cond>
JZ b
<statement>          <statement>
JMP a
b:                     b:

我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
else if(token==While){
       match(While);
       a = text;
       match('(');
       expression();
       match(')');
       *++text = JZ;
       b = ++text;
       statement();
       *++text = JMP;
       *++text = (int)a;
       *b = (int)(text);
   }

在跳转之前用a保存expression开始的指令，用于重新计算cond。然后延迟绑定地址b，作为while逻辑的出口

Return 语句

遇到Return语句则代表函数将要退出了，这一部分很简单，实现如下:

1
2
3
4
5
6
7
else if(token==Return){
        match(Return);
        if(token!=';'){
            expression();
        }
        *++text = LEV;
    }

其他语句

其他语句并不生成汇编代码，所以简单的匹配消耗即可:

1
2
3
4
5
6
7
8
9
10
11
12
else if(token=='{'){
       match('{');
       while(token!='}'){
           statement();
       }
       match('}');
   }else if(token==';'){
       match(';');
   }else{
       expression();
       match(';');
   }

expresion

我们已经完成了对语句的解释，现在我们需要实现对表达式的解释，在此之前我们要明确什么是表达式？怎么解析我们的表达式，并计算他们。

怎么计算表达式

对于表达式中的运算符，每一个符号都有自己的优先级，在进行运算的时候，我们希望运算符优先级高的子式先被计算。例如在2 + 3 * 4中，我们希望*先被计算，然后再是+。对于我们生成的汇编代码而言，我们应该优先为优先级高的运算符生成目标代码，所以如何确定一个表达式的优先运算顺序十分重要。

这里我们使用递归下降的方法实现对表达式运算符的解析，我们在一开始定义标识符时，实际上就对运算符的优先级进行了排序：

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
};

我们首先明确，一元运算符的优先级始终是高于二元运算符的，所以这里我们需要，首先完成对一元运算符的解析，这里先罗列几个较为特殊的：

  • Num 当我们遇到一个数字时 要返回它的数值
  • "..." 当我们遇到一个字符串时 要返回它的指针
  • PTR 当我们遇到一个指针类型时 我们要正确的解析它的解引用
  • Func 当我们遇到一个函数调用时，我们要正确的执行它，并返回返回值
  • Id 当我们遇到一个变量时，需要返回它的存储的值
  • …

然后，对一元预算符的判断结束后，我们需要对二元运算符的解析，但是对于二元运算符，我们需要考虑运算符号的优先级。我们给每一个运算符都设置一个当前的level，每次只对高于/等于当前level的运算符进行解析，每次解析完一个运算符之后，都将当前的优先级提高。这样我们就实现了对运算符的递归下降分析，我们的框架代码如下：

1
2
3
4
5
6
7
8
9
10
11
int expression(int level){
    // 解析一元运算符
    {
        ... // 解析顺序按一元运算符优先级进行解析
    }
    
    // 解析二元运算符
    while(token>=level){
        ...
    }
}

接下来，我们给出具体的实现：

常量

Num用IMM指令将其加载到ax中即可：

1
2
3
4
5
if(token==Num){
        *++text = IMM;
        *++text = token_val;
        expr_type = INT;
    }

然后是字符串常量

1
2
3
4
5
6
7
8
else if(token=='"'){
        *++text = IMM;
        *++text = token_val;
        expr_type = PTR;
        // while(token=='"') match('"');
        // 对data段进行地址对齐
        data = (char*)(((int)(data) + sizeof(int)) & (-sizeof(int)));
    }

这里有两点需要注意，如果你想支持"Hello""World" = "HelloWorld"的语法，那么你要设置while(token=='"') match('"');，这里我不想支持就不开了。

然后是data = (char*)(((int)(data) + sizeof(int)) & (-sizeof(int)));，这一部分的作用是将数据段进行对齐，我们希望每次的data指针都是四字节对齐的，这样可以方便我们进行索引，或是避免了字符串访问越界的可能。

sizeof

这个关键字我们也将其作为一元运算符进行处理，我们需要根据后面参数的类型，并返回它的大小。这里我们只支持Int Char Ptr三种类型，其中Ptr类型的大小同int

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
else if(token==Sizeof){
        match(Sizeof);
        match('(');
        if(token==Int){
            match(Int);
            expr_type = INT;
        }else if(token==Char){
            match(Char);
            expr_type = CHAR;
        }
        while(token==Mul){
            match(Mul);
            expr_type = expr_type + PTR;
        }
        match(')');
        *++text = IMM;
        *++text = (expr_type==CHAR) ? sizeof(char) : sizeof(int);
        expr_type = INT;
    }

变量与函数调用

由于我们将函数和变量的值的词法分析都是以Id开头，所以我们对他们的目标代码生成也放在一起：

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
else if(token==Id){
           match(Id);
           id = current_id;
           // 函数调用
           if(token=='('){
               match('(');
               tmp = 0;
               while(token!=')'){
                   expression(Assign);
                   *++text = PUSH;
                   tmp++;
                   if(token==',') match(',');
               }
               match(')');
               if(id->class==Sys){
                   *++text = id->value;
               }else if(id->class==Fun){
                   *++text = CALL;
                   *++text = id->value;
               }else{
                   printf("%d: 错误的函数调用\n",line);
                   exit(-1);
               }
               // 清除栈上的变量
               if(tmp>0){
                   *++text = ADJ;
                   *++text = tmp;
               }
               expr_type = id->type;
           }else if(id->class == Num){
               *++text = IMM;
               *++text = id->value;
               expr_type = INT;
           }else{
               if(id->class = Glo){
                   *++text = IMM;
                   *++text = id->value;
               }else if(id->class == Loc){
                   *++text = LEA;
                   *++text = -id->value;
               }else{
                   printf("%d: 未知变量类型\n", line);
                   exit(-1);
               }
               expr_type = id->type;
               *++text = (expr_type==CHAR) ? LC : LI;
           }
       }

指针取值

说实话有点写不下去了，最近有点忙，心情也不好，写这个的过程中断断续续的，所以先到此为止吧。

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

我们完成了对词法分析的获取函数next()，现在我们尝试根据token分析，和我们的语法规则，进行简单的语法分析。

解析变量

我们的解释器的语法结构，可以用下面的EBNF的表示法直观的体现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
program ::= {global_declaration}+

global_declaration ::= enum_decl | variable_decl | function_decl

enum_decl ::= 'enum' [id] '{' id ['=' 'num'] {',' id ['=' 'num'} '}'

variable_decl ::= type {'*'} id { ',' {'*'} id } ';'

function_decl ::= type {'*'} id '(' parameter_decl ')' '{' body_decl '}'

parameter_decl ::= type {'*'} id {',' type {'*'} id}

body_decl ::= {variable_decl}, {statement}

statement ::= non_empty_statement | empty_statement

non_empty_statement ::= if_statement | while_statement | '{' statement '}'
| 'return' expression | expression ';'

if_statement ::= 'if' '(' expression ')' statement ['else' non_empty_statement]

while_statement ::= 'while' '(' expression ')' non_empty_statement

对于我们的程序而言，一切都是从对global_delartion开始：

  • 变量定义
  • 类型定义（目前只支持enum）
  • 函数定义

我们的program()作为语法解析函数，框架如下:

1
2
3
4
5
6
void program() {
    next();
    while(token > 0){
        global_declaration();
    }
}

global_declaration

即全局定义的语句，我们通过递归下降的方法，来判断当前的定义类型，具体实现如下：

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
void global_declaration(){
    int type;
    int i;
    basetype = INT;
    if(token == Enum){
        match(Enum);
        if(token != '{') match(Id);
        else{
            match('{');
            enum_declaration();
            match('}');
        } 
        match(';');
        return;
    }else if(token==Int){
        match(Int);
    }else if(token==Char){
        match(Char);
        basetype = CHAR;
    }

    while(token != ';' && token != '{' && token != '}'){
        type = basetype;
        // 指针处理
        while(token==Mul){
            match(Mul);
            type = type + PTR;
        }
        if (token!=Id){
            printf("%d: bad global declaration\n", line);
            exit(-1);
        }
        if (current_id->class != 0){
            printf("%d: duplicate global declaration\n", line);
            exit(-1);
        }
        match(Id);
        current_id->type = type;

        if (token=='('){
            current_id->class = Fun;
            current_id->value = (int)(text);
            function_declaration();
        }else{
            current_id->class = Glo;
            current_id->value = (int)(data);
            data += sizeof(int);
        }
        if(token==','){
            match(',');
        }
    }
    next();
}

这里我们使用的依旧是lookahead的思想，我们无法根据一个token信息就实现对这一部分的语法功能解析，所以我们需要结合之后的信息，来对定义进行判断。

我们的解释器同时也支持指针类型，我们这里使用type = type+PTR的方式，来表示其包含指针的信息。

enum_declaration

主要用来解析用,分隔的变量，这里我们需要注意编译器对枚举变量的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void enum_declaration(){
    int i=0;
    while(token!='}'){
        if(token!=Id){
            printf("%d: 错误的枚举变量声明\n", line);
            exit(-1);
        }
        next();
        if(token=='='){
            match('=');
            if(token!=Num){
                printf("%d: 枚举变量赋值错误\n", line);
                exit(-1);
            }
            i = token_val;
            next();
        }
        current_id->class = Num;
        current_id->type = INT;
        current_id->value = i++;
        if(token==',') next();
    }
}

辅助函数match

这里我们使用match来匹配并获取下一个token:

1
2
3
4
5
6
7
8
void match(int tk){
    if(token == tk){
        next();
    }else{
        printf("%d: 语法错误, 缺少 %c\n", line, tk);
        exit(-1);
    }
}

函数定义的解析

我们在先前的函数Id判断中：

1
2
3
4
5
6
7
...
if (token == '(') {
current_id[Class] = Fun;
current_id[Value] = (int)(text); 
function_declaration();
} else {
...

在确定是函数类型之后，我们开始对函数结构的解析，我们对函数体的解析结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void function_declaration(){
    match('(');
    function_parameters();
    match(')');
    match('{');
    function_body();
    // match('}');
    while(current_id->token){
        if(current_id->class==Loc){
            current_id->class=current_id->Bclass;
            current_id->type=current_id->Btype;
            current_id->value=current_id->Bvalue;
        }
        current_id++;
    }
}

这里需要注意两个点：

  • 一是在对函数体的分析结束之后，不需要match("}")，因为函数体解析的函数会匹配他
  • 二是在函数解析完毕之后，我们需要将用到的token信息还原。这是因为在函数体解析的过程中，同名的局部变量会把原来定义的全局变量信息覆盖。

进一步的实现，则分别是对参数和函数体的内容的解析，首先是对参数的解析：

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
void function_parameters(){
    int type;
    int params = 0;
    type = basetype = INT;
    while(token!=')'){
       if(token==Int) match(Int);
       else if(token==Char){
            match(Char);
            type = CHAR;
       }
       while(token==Mul){
            match(Mul);
            type = type + PTR;
       }
       if(token!=Id){
            printf("%d: 错误的函数参数声明\n", line);
            exit(-1);
        }
        if (current_id->class != 0){
            printf("%d: 重复定义了局部变量-^-\n", line);
            exit(-1);
        }
        match(Id);

        current_id->Bclass = current_id->class;
        current_id->Btype = current_id->type;
        current_id->Bvalue = current_id->value;
        current_id->class = Loc;
        current_id->type = type;
        current_id->value = ++params;
        
        if(token==',') match(',');
    }
}

这里我们需要注意两点，首先是index_of_bp，这个变量用于确定参数在栈上的偏移值，因为从bp到函数传参之间隔着一个返回地址，所以在计算时需要将index_of_bp加一。

其次是，当我们遇到一个Id类型的token，我们将其所有的信息都备份一遍，并且将值赋值为参数的索引

然后是对函数体的解析，我们可以进一步分成局部变量声明和语句部分：

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
void function_body(){
    int pos_local = 0;
    int type;

    while(token==Int||token==Char){
        basetype = (token==Int ? INT : CHAR);
        match(token);
        while(token!= ';'){
            type = basetype;
            while(token==Mul){
                match(Mul);
                type = type + PTR;
            }
            if (token!=Id){
                printf("%d: 错误的局部变量声明\n", line);
                exit(-1);
            }
            if (current_id->class != 0){
                printf("%d: 重复定义了局部变量-^-\n", line);
                exit(-1);
            }
            match(Id);
            current_id->Bclass = current_id->class;
            current_id->Btype = current_id->type;
            current_id->Bvalue = current_id->value;
            current_id->class = Loc;
            current_id->type = type;
            current_id->value = ++pos_local;
            if(token==',') match(',');
        }
        match(';');
    }
    *++text = ENT;  // 函数入口指令
    *++text = pos_local; // 局部变量大小
    // 语句处理
    while(token != '}'){
        statement();
    }
    *++text = LEV;  // 函数返回指令
}

这一部分需要注意的就是*++text的含义，相当于我们在栈上为局部变量预留了空间，后面的LEV则是用来返回函数调用。

至此我们对全局变量和函数定义的解析完成了，之后我们将着重实现对语句的实现，并为他们生成可用的字节码指令。

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

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

词法分析

什么是词法分析

源文件的内容对于我们的解释器而言，本质上就是一系列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
21
22
// 预处理关键字
    {
        Symbols = malloc(poolsize);
        memset(Symbols, 0, 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;
    }

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

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

我们将尝试构建一个C语言的解释器，这个项目也是我C语言的大作业。现在回顾看来，当时对整个项目都是知其然不知其所以然，从现在的眼光来看，当时很多做法都是很稚嫩的。尤其是对于这个项目结构的理解也远远不足，所以打算重构一遍。

构建流程

首先是整个编译器的构建流程，一般来讲，编译器的编写有三个步骤：

  1. 词法分析器，用于将文本文件转换为内部的表示结构
  2. 语法分析器，在词法分析得到的标记的基础之上，构建一棵语法树
  3. 目标代码的生成，将语法树转换成目标代码

但是由于这里我们编写的是一个解释器，所以我们自定义自己的虚拟机框架和指令。我们通过语法分析词法分析之后得到的语法树，来生成使用自定义虚拟机框架的指令的目标代码。

编译器的框架

仿照c4编译器的写法：

这里我们的解释器主要包括4个函数：

  • next() 用于词法分析，获取下一个标记
  • program() 用于语法分析，分析整个C语言的程序
  • expression(level) 用于解析一个表达式
  • eval() 虚拟机的入口，用于执行目标代码

可能在此基础之上我会做出一点自己的改动，但是总体框架还是确定的，首先是实现对要解释的文件的处理：

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 源文件全局变量
int line;       // 当前行数
char *src;      // 源文件内容
char *old_src;  // 源文件备份

int main(int argc, char *argv[]) {
    int i, fd;

    argc--;
    argv++;

    int poolsize = 256*1024; // 内存池大小
    line = 1;

    // 读取源文件
    {
        if((fd = open(*argv,0)) < 0){
        printf("Could not open %s\n", *argv);
        exit(1);
        }

        if(!(src = old_src = malloc(poolsize))){
            printf("Could not malloc %d bytes\n", poolsize);
            exit(1);
        }

        if((i=read(fd, src, poolsize-1)) <= 0){
            printf("Could not read %s\n", *argv);
            exit(1);
        }
        src[i] = 0; // 文件结束符
        close(fd);
    }

    program();
    return eval();
}

我们将读取到的文件内容复制到src内存空间中。

现在我们就需要开始模拟一台计算机应有的功能了，我们的指令需要运行在我们的虚拟机上。那么首先，我们就需要定义一个自己的虚拟机，一台机器必须要有以下几个部分：

  • 内存： 这是用来存放数据的主要空间，我们的代码段数据 还有函数调用时的栈段都存放在这里
  • 寄存器：我们需要寄存器帮助我们实现各种命令，同时也需要程序计数器指向我们的指令
  • CPU：本来这一部分应该是一大堆电路，但是这里我们可以通过操作指针和寄存器的方式，用一系列程序，简单的模拟它

计算机内部实现

内存

首先是内存部分，一般情况下，内存会被分成几个段。由于我们是简单实现的理想模型，我们只需要设置几个最基本的部分就可以了：

  • 代码段： 我们分析得到的指令就被存放在这里
  • 数据段： 这里用来存放我们源程序中用的数据，通常和token信息绑定
  • 栈段： 我们处理函数调用将会用到它，存放栈帧和局部变量等数据

现在我们就可以简单的对我们的模拟的计算机内存进行初始化：

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
......
// 内存布局
int *text;          // 代码段
int *old_text;      // 代码段备份
int *stack;         // 栈
char *data;         // 数据段

int main(int argc, char *argv[]) {
	......
    // 内存初始化
    {
        if(!(text = old_text = malloc(poolsize))){
            printf("Could not malloc %d bytes for text\n", poolsize);
            exit(1);
        }
        if(!(stack = malloc(poolsize))){
            printf("Could not malloc %d bytes for stack\n", poolsize);
            exit(1);
        }
        if(!(data = malloc(poolsize))){
            printf("Could not malloc %d bytes for data\n", poolsize);
            exit(1);
        }
        memset(text, 0, poolsize);
        memset(stack, 0, poolsize);
        memset(data, 0, poolsize);
    }

    program();
    return eval();
}

寄存器

寄存器用来存放计算机的运行状态，我们的虚拟机中只简单的使用四个寄存器，分别是：

  • PC程序计数器，用于存放一个内存地址，该地址中用于存放下一条要执行的指令
  • SP寄存器，永远指向当前的栈顶（注意这里的栈是从高地址向低地址增长的）
  • BP基址寄存器，用于指向栈底，当我们在函数调用解析参数时需要用到它
  • AX通用寄存器，用来存放一条指令执行后的结果

我们对他们进行简单的初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
......
// 寄存器
int *pc;            // 程序计数器
int *bp;            // 基址指针
int *sp;            // 栈指针
int ax;             // 通用寄存器
int cycle;          // 时钟周期

int main(int argc, char *argv[]) {
	......
    // 寄存器初始化
    {
        bp = sp = (int*)((char*)stack + poolsize);
        ax = 0;
        cycle = 0;
    }

    program();
    return eval();
}

指令

现在我们的虚拟机已经有了基本的骨架，我们可以开始尝试实现我们我们虚拟机最基本的指令集。不过首先我们需要明确我们需要用到哪些指令。这里我们直接照搬C4的指令集就行了：

1
2
3
4
5
6
7
enum {
       LEA, IMM, JMP, CALL, JZ, JNZ, ENT, ADJ, LEV,
       LI, LC, SI, SC, PUSH,
       OR, XOR, AND, EQ, NE, LT, GT, LE, GE,
       SHL, SHR, ADD, SUB, MUL, DIV, MOD,
       OPEN, READ, CLOS, PRTF, MALC, MSET, MCMP, EXIT 
};

这些指令顺序是有意的，带有参数的指令在前，没有参数指令的放在后面，为了方便我们之后打印调试信息。

MOV

MOV dest,srcx86中最基础重要的一个公式，它将SOURCE中的内容放在DEST中。但在我们的虚拟机中只提供了一个通用寄存器AX，加上由于对参数类型的识别是一件复杂的事情，所以我们将MOV拆分成五个子操作来实现：

  • IMM <num> 将num放入寄存器ax中
  • LC 将对应地址中的字符载入ax中，要求ax中存放地址
  • LI 将对应地址中的整数载入ax中，要求ax中存放地址
  • SC将ax中的数据作为字符存放入地址中，要求栈顶存放地址
  • SI将ax中的数据作为整数存放入地址中，要求栈顶存放地址

这样的拆分，极大程度上的减小了指令实现的复杂度，现在我们可以开始具体的实现了：

1
2
3
4
5
6
7
8
9
10
11
int eval() {
    int op, *tmp;
    while(1){
        if(op == IMM) {ax = *pc++;}
        else if(op == LC) {ax = *(char*)ax;}
        else if(op == LI) {ax = *(int*)ax;}
        else if(op == SC) { *(char*)*sp++ = ax;}
        else if(op == SI) { *(int*)*sp++ = ax;}
    }
    return 0;
}

这里得*sp++实际上就是一个退栈操作，将值存储到弹出得地址中。

这里我之前一直没有搞懂，为什么LI/LC要将对应地址中的字符载入ax中，因为我们的默认的计算结果是存储在ax中的，也就是我们指令计算出的地址，可以直接被LI/LC所使用，这样就很高效。

PUSH

PUSH的作用很简单，就是将值或者寄存器压入到栈中。在这里我们PUSH的作用给就是将ax的值压入栈中，因为我们只有这一个寄存器：

1
else if(op == PUSH) {*--sp = ax;}

JMP

JMP <addr>是跳转指令，无条件的将当前的PC寄存器设置为指定的<addr>，实现如下：

1
else if(op == JMP) {pc = (int*)*pc;}

pc始终指向的是下一条指令，所以此时它存放的存放的是JMP指定的参数，即<addr>的值

JZ/JNZ

为了实现if语句 我们也需要条件判断相关的指令。这里我们只需要实现两个最简单的条件判断，即ax==0/ax!=0的情况下的跳转：

1
2
else if(op == JZ) {pc = ax ? pc+1 : (int*)*pc;}
else if(op == JNZ) {pc = ax ? (int*)*pc : pc+1;}

子函数调用

这个是比较重要的一部分，我很大程度上也是为了这一部分重新回头别写这个编译器。这里我们将根据子函数调用约定，用几个最简单的指令来实现这个过程，我们要引入的指令有CALL ENT ADJ LEV。

首先我们介绍CALL，它用于跳转到一个子函数的开始地址。程序将会跳转到地址<addr>，并将当前的位置信息保存起来，以用于函数调用后的返回。这里我们将返回的PC存放在栈中：

1
else if(op == CALL) {*--sp = (int)(pc+1); pc = (int*)*pc;}

现在我们能进入调用函数了，那么我们便需要进一步的规范我们的函数调用规则。在实际的函数调用中，我们不仅要考虑函数的地址，也要考虑如何传递参数和返回结果，这里我们将每次的返回结果保存在ax中，对于参数传递，我们需要遵循C语言的调用标准：

  • 由调用者将参数入栈
  • 调用结束时，由调用者将参数出栈
  • 参数逆序入栈（因为先进后出）

我们可以看下面的这个例子：

1
2
3
4
5
6
7
8
int callee(int, int, int);

int caller(void){
	int i, ret;
	ret = callee(1, 2, 3);
	ret += 5;
	return ret;
}

会生成下面的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
caller:
; make new call frame
push    ebp
mov     ebp, esp
sub     1, esp       ; save stack for variable: i
; push call arguments
push    3
push    2
push    1
; call subroutine 'callee'
call    callee
; remove arguments from frame
add     esp, 12
; use subroutine result
add     eax, 5
; restore old call frame
mov     esp, ebp
pop     ebp
; return
ret

但是我们的虚拟机难以解决其中的几个问题：

  • push ebp 我们的PUSH无法指定寄存器
  • mov ebp,esp 我们的MOV也无法直接指定源和目的
  • add esp,12 我们的ADD也无法直接实现两个操作数的加法

所以我们需要额外的指令来代替这几个的功能，所以我们需要定义以下几个指令：

ENT

ENT <size>指的是enter我们用它实现make new call frame的操作，即保存当前的栈指针，并在栈上保留一定的空间，用来存放局部变量，汇编代码的表现形式如下：

1
2
3
4
; make new call frame
push    ebp
mov     ebp, esp
sub     size, esp       ; save stack for variable

我们可以通过以下形式实现它：

1
else if(op == ENT) {*--sp = (int)bp; bp = sp; sp = sp - *pc++;}

ADJ

ADJ <size>用于实现remove argument from frame。用于将调用子函数时压入栈中的数据清楚，之所以单独定义这个指令，是对我们ADD功能局限做出的妥协。其汇编实现如下：

1
2
; remove arguments from frame
add     esp, size

我们可以通过以下形式实现它：

1
else if(op == ADJ) {sp = sp + *pc++;}    // add esp <size>

LEV

本质上这个指令并不是必需的而且我们的指令集中并没有POP的指令，所以为了简洁的进行函数的退出操作，我们专门定义了LEV的封装。对应的汇编操作如下：

1
2
3
4
5
; restore old call frame
mov     esp, ebp
pop     ebp
; return
ret

我们用以下形式实现：

1
else if(op == LEV) {sp = bp; bp = (int*)sp++; pc = (int*)*sp++;}

LEA

上述的指令解决了调用帧的问题，解决了我们函数的运行和返回的问题。现在，为了进一步的执行调用函数，我们需要想办法获取先前压入的参数。在此之前，我们首先需要了解当参数调用时，栈中的调用帧是什么样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sub_function(arg1, arg2, arg3);

|    ....       | high address
+---------------+
| arg: 1        |    new_bp + 4
+---------------+
| arg: 2        |    new_bp + 3
+---------------+
| arg: 3        |    new_bp + 2
+---------------+
|return address |    new_bp + 1
+---------------+
| old BP        | <- new BP
+---------------+
| local var 1   |    new_bp - 1
+---------------+
| local var 2   |    new_bp - 2
+---------------+
|    ....       |  low address

我们首先将参数压入栈中，然后进行调用，调用会将返回地址压入栈中，然后保存当前的栈基址（我们将这个保存的栈帧称为old_bp），准备创建下一个栈帧。当前视图就是进行push rbp; mov rbp,rsp;之后的栈帧状态。此时如果我们想要访问函数的第一个参数，我们就需要访问new_bp+4地址上的内容。

但是这里有一个问题，我们的ADD指令无法对bp进行运算，所以我们需要设置一个新的指令，用于访问栈帧上的地址LEA <offset>。我们具体的实现如下：

1
else if(op == LEA) {ax = (int)(bp + *pc++);}

现在，我们就完成了实现函数调用的所有指令了。

运算符指令

我们在C语言中支持的各种运算符号都是二元的，所以我们指令的参数也应该是由两个的，但是我们只有一个通用寄存器，这就导致我们需要将其中一个参数放在栈上，另一个参数存放在ax中，我们通过指令计算出来的结果也存放在ax上。

我们的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
else if (op == OR)  ax = *sp++ | ax;
else if (op == XOR) ax = *sp++ ^ ax;
else if (op == AND) ax = *sp++ & ax;
else if (op == EQ)  ax = *sp++ == ax;
else if (op == NE)  ax = *sp++ != ax;
else if (op == LT)  ax = *sp++ < ax;
else if (op == LE)  ax = *sp++ <= ax;
else if (op == GT)  ax = *sp++ >  ax;
else if (op == GE)  ax = *sp++ >= ax;
else if (op == SHL) ax = *sp++ << ax;
else if (op == SHR) ax = *sp++ >> ax;
else if (op == ADD) ax = *sp++ + ax;
else if (op == SUB) ax = *sp++ - ax;
else if (op == MUL) ax = *sp++ * ax;
else if (op == DIV) ax = *sp++ / ax;
else if (op == MOD) ax = *sp++ % ax;

内置命令

有很多由系统支持的函数，我们往往难以在机器上支持实现，所以这里我们简单的对函数进行封装，设置为内置的指令，用来支持一些常用的库函数调用。

这里我们就简单的对exit open close read printf malloc memset指令进行封装以确保我们的程序有基本的能力：

1
2
3
4
5
6
7
8
else if(op == EXIT) {printf("exit(%d)", *sp); return *sp;}
      else if(op == OPEN) {ax = open((char *)sp[1], sp[0]);}
      else if(op == CLOS) {ax = close(*sp);}
      else if(op == READ) {ax = read(sp[2], (char*)sp[1], *sp);}
      else if(op == PRTF) {tmp = sp+pc[1]; ax = printf((char*)tmp[-1],tmp[-2],tmp[-3],tmp[-4],tmp[-5],tmp[-6]);}
      else if(op == MALC) {ax = (int)malloc(*sp);}
      else if(op == MSET) {ax = (int)memset((char*)sp[2], sp[1], *sp);}
      else if(op == MCMP) {ax = memcmp((char*)sp[2], (char*)sp[1], *sp);}

这里我们的参数在函数调用时是顺序入栈，所以看起来比较反直觉，结合栈是自顶向下索引的，所以我们最终可以很好的理解我们的参数调用顺序。

最后在加上一个错误判断，我们的虚拟机指令就完成了：

1
2
3
4
else {
            printf("unknown instruction:%d\n", op);
            return -1;
        }

测试

现在我们的虚拟机指令就完成了，我们可以做一个简单的测试，来看我们的机器能否正确的运行：

1
2
3
4
5
6
7
8
9
10
11
12
i = 0;
pc = text;
text[i++] = IMM;
text[i++] = 12;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 5;
text[i++] = DIV;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 1;
text[i++] = EXIT;

程序执行的结果是：

1
2
ylin@Ylin:~/Program/c4$ ./a.out
exit(2)

至此我们的虚拟机以及指令架构就完成了

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

自从上个学期之后，就怎么接触过图形学了。但是仔细感受下来，图形学是最让人有收获感的方向。它通过模拟真实的物理规则，通过计算模拟出真实的模拟场景，十分有趣，就是给人一种融汇贯通的感觉，学到的知识能结合在一起，我感觉这才是最有意义的地方。

然后进度的话是接着上一次”图形学(12)“最终的场景，在此之前，我把之前的项目代码熟悉了一下，在WSL环境上重构了一遍，感觉效率相对于原来还是快了一点。现在就正式开始吧

运动模糊

在真实的世界中，当我们按下快门，相机会接受一段时间内的光线信息，在此期间内，世界中的物体可能会发生移动，这样排除来的照片，我称之为运动模糊。为了真实的再现这个效果，需要对我们现有的程序进行补充：

简介

我们可以在快门开启的期间随机选择一个时间点发射一条射线从而得到，这条射线上的光子信息。只要我们能够知道在那个随机时间点上，场景中每个物体的位置和姿态。我们就可以像处理静态场景一样，计算这条光线与物体的交点、着色等。这样，这条光线就能准确反映那个特定瞬间的光照情况。

因此光线追踪的过程只需要，在处理每条光线时，更新物体的位置，就可以是实现对物体动态的追踪了。为了实现这一点，我们需要让每条线携带时间信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ray {
public:
    ray() {}
    ray(const point3& origin, const vec3& direction, double time)
        : orig(origin), dir(direction), tm(time) {}
	// 默认初始化时间为0
    ray(const point3& origin, const vec3& direction)
        : orig(origin), dir(direction), tm(0.0) {}

    point3 origin() const { return orig; }
    vec3 direction() const { return dir; }
    double time() const { return tm; }

    point3 at(double t) const {
        return orig + t * dir;
    }

private:
    point3 orig;
    vec3 dir;
    double tm;
};

时间管理

真实世界中的快门时间是由两部分决定的：

  • 帧间隔：连续两帧画面之间的时间间隔
  • 快门开启时长：在每一帧的帧间隔中，快门实际打开、允许光线进入的时间长度（一般情况下开启时间越长，运动模糊越明显）

但是这里为了简化光线追踪的实现，我们只对一帧的画面进行捕捉。当然，如果想要渲染一个完整的动画，只需要设置好适当的快门时间就可以了。如果世界是静态的，只有相机的位置在移动，那么我们的代码无需做出改变。但如果世界中的物体在进行运动，那么我们需要为hittable设置一种方法，使得每个物体都能感知到当前帧的时间周期，并更新他们此时的位置。

为了简化墨香，我们只渲染一帧，我们把时间设置为从时间t=0到t=1。我们将让相机在时间[0,1]之间随机发射光线，并更新我们的球体类。

更新相机

我们更新相机，使其在开始和结束时间之间随机生成光线，这里我们通过相机类来对光线信息进行管理和生成：

1
2
3
4
5
6
7
8
ray get_ray(int i, int j){
    auto offset = sample_pixel_offset();
    auto pixel_sample = pixel_origin + (i + offset.x()) * pixel_delta_u + (j + offset.y()) * pixel_delta_v;
    auto ray_origin = (defocus_angle > 0.0) ? defocus_disk_sample() : camera_origin;
    auto ray_direction = pixel_sample - ray_origin;
    auto ray_time = random_double();
    return ray(ray_origin, ray_direction, ray_time);
}

球体运动属性

现在我们要让我们的世界动起来，我们需要更新球体类，使其中心在t=0到t=1的时间中，从center1线性速度的移动到center。我们将center属性修改成一个从t=0时刻指向t=1时刻的射线向量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class sphere: public hittable {
public:
    // 静态球体
    sphere(const point3& center, double radius, shared_ptr<material> mat)
        : center(center,vec3(0,0,0)), radius(radius), mat(mat) {}
    // 动态球体
    sphere(const point3& center1, const point3& center2, double radius, shared_ptr<material> mat)
        : center(center1,center2-center1), radius(radius), mat(mat) {}
	...

private:
    ray center;
    double radius;
    shared_ptr<material> mat;
};

然后我们需要更新hit方法，需要需要在更新动画中心的位置之后，也能正确的进行相交判断：

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
bool hit(const ray& r, interval t_range, hit_record& rec) const override {
    point3 cur_center = center.at(r.time());
    vec3 oc = r.origin() - cur_center;
    auto a = r.direction().length_squared();
    auto half_b = dot(oc, r.direction());
    auto c = oc.length_squared() - radius * radius;
    auto discriminant = half_b * half_b - a * c;
    if (discriminant < 0) {
        return false;
    }
    auto sqrtd = std::sqrt(discriminant);
    auto root = (-half_b - sqrtd) / a;
    if (!t_range.contains(root)) {
        root = (-half_b + sqrtd) / a;
        if (!t_range.contains(root)) {
            return false;
        }
    }
    rec.t = root;
    rec.p = r.at(rec.t);
    vec3 outward_normal = (rec.p - cur_center) / radius;
    rec.set_face_normal(r, outward_normal);
    rec.mat = mat;
    return true;
}

我们只需要根据射线携带的时间信息，更新我们的球心位置，然后正常的进行计算就行了，如果r.time()等于0，就说明位置不变。就算变了，我们也不需要花费额外的计算开销。

追踪光线的相交时间

现在光线有了时间属性，我们也需要记录每次光线和世界相交的时间信息，我们只需要简单的更新一下相交光线的信息就行了：

1
scattered = ray(rec.p, scatter_direction, r_in.time());

最终效果

现在我们想世界中添加球体的运动属性，以实现最终的动态渲染效果，让我们看看怎么样：

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
#include "utils.h"
#include "hittable_list.h"
#include "sphere.h"
#include "camera.h"
#include "material.h"

int main(){
    // 世界场景
    hittable_list world;

    auto ground_material = make_shared<lambertian>(color(0.5, 0.5, 0.5));
    world.add(make_shared<sphere>(point3(0,-1000,0), 1000, ground_material));

    for (int a = -8; a < 8; a++) {
        for (int b = -8; b < 8; b++) {
            auto choose_mat = random_double();
            point3 center(a + 0.9*random_double(), 0.2, b + 0.9*random_double());

            if ((center - point3(4, 0.2, 0)).length() > 0.9) {
                shared_ptr<material> sphere_material;

                if (choose_mat < 0.5) {
                    // diffuse
                    auto albedo = color::random() * color::random();
                    sphere_material = make_shared<lambertian>(albedo);
                    auto center2 = center + vec3(0, random_double(0,0.2), 0);
                    world.add(make_shared<sphere>(center, center2, 0.2, sphere_material));
                } else if (choose_mat < 0.8) {
                    // metal
                    auto albedo = color::random(0.5, 1);
                    auto fuzz = random_double(0, 0.1);
                    sphere_material = make_shared<metal>(albedo, fuzz);
                    world.add(make_shared<sphere>(center, 0.2, sphere_material));
                } else {
                    // glass
                    sphere_material = make_shared<dielectric>(1.5);
                    auto center2 = center + vec3(0, random_double(0,0.1), 0);
                    world.add(make_shared<sphere>(center, center2, 0.2, sphere_material));
                }
            }
        }
    }

    auto material1 = make_shared<dielectric>(1.5);
    world.add(make_shared<sphere>(point3(0, 1, 0), 1.0, material1));

    auto material2 = make_shared<lambertian>(color(0.4, 0.2, 0.1));
    world.add(make_shared<sphere>(point3(-4, 1, 0), 1.0, material2));

    auto material3 = make_shared<metal>(color(0.7, 0.6, 0.5), 0.0);
    world.add(make_shared<sphere>(point3(4, 1, 0), 1.0, material3));
    
    // 相机
    camera cam;
    cam.aspect_ratio = 25.0 / 16.0;
    cam.image_width = 1250;
    cam.samples_per_pixel = 100;
    cam.max_depth = 30;


    cam.vfov     = 20;
    cam.lookfrom = point3(13,2,3);
    cam.lookat   = point3(0,0,0);
    cam.vup      = vec3(0,1,0);

    cam.defocus_angle = 0.6;
    cam.focus_distance = 10;

    cam.render(world);
}

可以看到较为明显的运动痕迹：

image.png

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

MAKEFILE教程

之后要尝试做一些项目，在加上前一段时间接触PA，发现自己对自动构建项目一类的操作实在是一知半解，而且之后也需要要尝试自动化编译一些大型的源码，所以学习一下makefile的基本使用，完善一下自己对工具链的认知。这里我看的教程是廖雪峰的makefile入门

Makefile基础

在Linux中我们使用make命令时，他就会在当前目录下找一个名为Makefile的文件，并根据里面的内容进行自动化的执行。我们以下面这个需求为例子：

1
2
a.txt + b.txt -> m.txt
m.txt + c.txt -> x.txt

上述逻辑我们编写makefile

规则

Makefile由各种规则构成，每一条规则需要指出一个目标文件和若干个依赖文件，以及用于生成目标文件的命令，例如我们想要生成m.txt则规则如下：

1
2
3
# 目标文件: 依赖文件1 依赖文件2 依赖文件...
m.txt: a.txt b.txt
	cat a.txt b.txt > m.txt

其中#用来注释，一条规则的格式如上，Tab后使用命令来实现目标文件

现在我们就可以完整的实现上述的规则：

1
2
3
4
5
x.txt: m.txt c.txt
	cat m.txt c.txt > x.txt

m.txt: a.txt b.txt
	cat a.txt b.txt > m.txt

我们可以尝试执行一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
ylin@Ylin:~/Program/test$ make
cat a.txt b.txt > m.txt
cat m.txt c.txt > x.txt
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile  m.txt  x.txt
ylin@Ylin:~/Program/test$ cat x.txt
I am a.txt
I am b.txt
I am c.txt
ylin@Ylin:~/Program/test$ cat m.txt
I am a.txt
I am b.txt
ylin@Ylin:~/Program/test$

make默认执行第一条规则，也就是创建x.txt，但是由于x.txt依赖的文件m.txt不存在（另一个依赖c.txt已存在），故需要先执行规则m.txt创建出m.txt文件，再执行规则x.txt。执行完成后，当前目录下生成了两个文件m.txt和x.txt。

所以我们可以知道，实际上Makefile就是一堆规则(即你些的目标文件和依赖)，当满足规则时，就调用规则后的命令，创建出一个新的目标文件

把默认的规则放在第一条，其他规则的顺序makefile会自动判断依赖。make会把每次执行的命令输出出来，便于我们观察调试。

如果我们在不对任何目标文件进行修改的情况下，我们在此使用make就会得到：

1
2
ylin@Ylin:~/Program/test$ make
make: 'x.txt' is up to date.

make会根据文件的创建和修改时间来判断是否应该更新一个目标文件，例如我们这里只修改c.txt，并不会触发对m.txt的更新，因为他的依赖文件没有发生改变：

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ make
cat m.txt c.txt > x.txt
ylin@Ylin:~/Program/test$ cat x.txt
I am a.txt
I am b.txt
I am c.txt (modified)
ylin@Ylin:~/Program/test$

make只会重新编译那些依赖被修改，或者是尚未完成的部分，重新编译的过程并不是每一条命令都会执行，make只会选择必要的部分执行，我们称这种编译为增量编译。能否正确的实现增量编译，取决于我们编写的规则。

伪目标

为了进一步的便于自动化的构建，有时候我们会需要定义一些常用的规则。例如在我们使用make之后，我们自动生成了m.txt和x.txt，现在我们可以定义一个规则用于清理这些生成的文件:

1
2
3
clean:
	rm -f m.txt
	rm -f x.txt

然后我们可以通过make clean来调用这个规则：

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile  m.txt  x.txt
ylin@Ylin:~/Program/test$ make clean
rm -f m.txt
rm -f x.txt
ylin@Ylin:~/Program/test$ ls
a.txt  b.txt  c.txt  Makefile

但是make这里实际上是把clean当作一个目标文件，我们使用make clean规则时，make检查到没有目标文件clean，于是调用命令尝试构建目标文件，但是clean文件不会被生成，所以我们总可以使用它。可是如果目录中有一个clean文件怎么办呢？make认为clean已经被构建了，就不会再使用命令。为了解决这个问题，我们希望make不要将clean视作文件，我们可以添加一个标识：

1
2
3
4
.PHONY: clean
clean:
	rm -f m.txt
	rm -f x.txt

此时，clean就不再被视作一个文件，而是伪目标。一般大型项目会有clean，install一类的常用的伪目标规则，方便用户快速的构建一些任务

执行多条命令

一个规则可以有多条命令：

1
2
3
4
cd:
	pwd
	cd ..
	pwd

运行结果如下： 

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make cd
pwd
/home/ylin/Program/test
cd ..
pwd
/home/ylin/Program/test

我们发现命令cd ..并没有修改当前目录，导致每次输出的pwd都是一样的，这是因为make针对每条指令都会创建一个独立的shell环境，所以命令之间无法互相影响。但是我们可以用以下方法实现

1
2
cd_ok:
	pwd; cd ..; pwd;		# 使用;可以将多个命令写在一行(顺序执行,不管成功还是失败)

我们查看新的执行结果：

1
2
3
4
ylin@Ylin:~/Program/test$ make cd_ok
pwd; cd ..; pwd;
/home/ylin/Program/test
/home/ylin/Program

当然也可以再;后加\便于分行阅读：

1
2
3
4
cd_ok:
	pwd; \
	cd ..; \
	pwd

我们需要注意，在shell中;代表无论当前命令是否生效，都会执行下一个命令。与其相反的一个执行多条命令的语法是&&，当前面的命令执行失败时，后续的命令就不会再继续执行了

控制打印

默认情况下，make会打印出执行的每一条命令，如果我们不想打印某一条命令，我们只需要在命令前面加上@，告诉make不打印该命令：

1
2
3
no_output:
	@echo 'no display'
	echo 'will display'

执行结果如下：

1
2
3
4
ylin@Ylin:~/Program/test$ make no_output
not display
echo 'will display'
will display

控制错误

make在执行命令时，会检查每一条命令的返回值，如果返回值错误，就会中断执行。

例如我们手动构建一个错误（用rm删除一个不存在的文件）：

1
2
3
has_error:
	rm zzz.txt
	echo 'OK'

会发生：

1
2
3
4
ylin@Ylin:~/Program/test$ make has_error
rm zzz.txt
rm: cannot remove 'zzz.txt': No such file or directory
make: *** [Makefile:25: has_error] Error 1

但是有时候我们希望忽略错误，我们可以在特定的指令前面加上-用来忽略错误的命令：

1
2
3
ignore_error:
	-rm zzz.txt
	echo 'ok'

输出结果如下：

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make ignore_error
rm zzz.txt
rm: cannot remove 'zzz.txt': No such file or directory
make: [Makefile:29: ignore_error] Error 1 (ignored)
echo 'ok'
ok

对于执行可能出错，但是不影响逻辑的命令，可以使用-忽略

编译C程序

现在我们尝试一下编译一个简单的C语言程序，其依赖文件如下：

1
2
3
main.c + hello.h -> main.o
hello.c -> hello.o
hello.o + main.o -> a.out

文件内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// main.c
#include "hello.h"
#include <stdio.h>

int main() {
    printf("starting main\n");
    hello();
    printf("ending main\n");
    return 0;
}

// hello.h
int hello();

// hello.c
#include <stdio.h>
int hello() {
    printf("Hello, World!\n");
    return 0;
}

我们可以编写以下规则，用于自动构建可执行程序：

1
2
3
4
5
6
7
8
a.out: main.o hello.o
	cc -o a.out main.o hello.o
main.o: main.c hello.h
	cc -c main.c
hello.o: hello.c hello.h
	cc -c hello.c
clean:
	rm -f a.out main.o hello.o

同时也可以通过make clean来删除中间文件：

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ ls
a.out  hello.c  hello.h  hello.o  main.c  main.o  Makefile
ylin@Ylin:~/Program/test$ make clean
rm -f a.out main.o hello.o
ylin@Ylin:~/Program/test$ ls
hello.c  hello.h  main.c  Makefile

我们可以看到完整的命令流程如下：

1
2
3
4
5
ylin@Ylin:~/Program/test$ make clean && make
rm -f a.out main.o hello.o
cc -c main.c
cc -c hello.c
cc -o a.out main.o hello.o

隐式规则

为了编译这个项目，我们一共编写了三条规则，现在我们尝试删除两个.o文件的规则，然后再编译试试：

1
2
3
4
5
a.out: main.o hello.o
	cc -o a.out main.o hello.o

clean:
	rm -f a.out main.o hello.o

然后我们执行make，输出如下：

1
2
3
4
ylin@Ylin:~/Program/test$ make
cc    -c -o main.o main.c
cc    -c -o hello.o hello.c
cc -o a.out main.o hello.o

然后可以发现 我们并没有制定相关的规则，可是程序还是正常的进行了编译，这是make中的隐式规则，因为make本来就是为了编译C程序设计的，所以为了避免重复的编译.o文件，在一开始没有找到对应的规则时，会自动的调用隐式规则。对于C C++ ASM ...等程序，都有内置的隐式规则，这里不展开叙述。

使用变量

我们在编译时难免会遇到许多重复的文件名，为了方便使用，我们引入变量用来解决重复的问题。我们以上一节的Makefile为例：

1
2
3
4
5
a.out: main.o hello.o
	cc -o a.out main.o hello.o

clean:
	rm -f a.out main.o hello.o

我们可以定义一个变量来替换它：

1
2
3
4
5
6
7
TARGET = a.out

$(TARGET): main.o hello.o
	cc -o $(TARGET) main.o hello.o

clean:
	rm -f $(TARGET) main.o hello.o

对于变量定义，我们使用变量名 = 值，变量名通常使用大写。在引用变量时通常使用$(变量名)

当然，对于我们的依赖文件列表，也可以使用变量进行替换：

1
2
3
4
5
6
7
8
TARGET := a.out
OBJS := main.o hello.o

$(TARGET): $(OBJS)
	cc -o $(TARGET) $(OBJS)

clean:
	rm -f $(TARGET) $(OBJS)

但是对于依赖文件很多的情况下，我们可能需要一个自动化的方式，来将我们的源文件批量编译成目标文件。我们注意到每个.o文件都是由对应的.c文件编译产生的，我们可以让make先获取.c文件列表再替换生成得到.o文件列表：

1
2
3
4
5
6
7
8
9
10
TARGET := a.out
# wildcard意为通配符,即使用通配符去匹配*.c
# patsubst是pattern substitute的缩写,即模式替换,参数为(源模式,目标模式,文件列表)
OBJS := $(patsubst %.c,%.o,$(wildcard *.c))

$(TARGET): $(OBJS)
	cc -o $(TARGET) $(OBJS)

clean:
	rm -f $(TARGET) $(OBJS)

内置变量

为了方便我们使用，make也内置了很多的内置变量，例如我们可以用$(CC)替换命令cc:

1
2
$(TARGET): $(OBJS)
	$(CC) -o $(TARGET) $(OBJS)

这样方便我们在交叉编译时，指定编译器。诸如此类的内置变量还有很多，遇到了再学吧。

自动变量

在makefile中，经常会看到$@、$<之类的变量，这种变量称为自动变量，它们在一个规则中自动指向某个值。例如$@标识目标文件，$^表示所以依赖文件，所以我们也可以这样写：

1
2
3
4
5
a.out: hello.o main.o
	@echo '$$@ = $@' # 变量 $@ 表示target
	@echo '$$< = $<' # 变量 $< 表示第一个依赖项
	@echo '$$^ = $^' # 变量 $^ 表示所有依赖项
	cc -o $@ $^

模式规则

我们前面提到隐式转换可以在必要时自动创建.o文件，但实际上隐式规则的命令是固定的：

1
$(CC) $(CFLAGS) -c -o $@ $<

我们只能修改编译器变量和编译选项变量，但没办法运行多条命令。

此时我们就要引入自定义模式规则，它使用make的匹配模式规则，如果匹配上了，就自动创建一条模式规则，我们可以把我们的makefile写成以下内容：

1
2
3
4
5
6
7
8
9
10
11
12
TARGET := a.out
OBJS := $(patsubst %.c,%.o,$(wildcard *.c))

$(TARGET): $(OBJS)
	$(CC) -o $(TARGET) $(OBJS)

%.o: %.c
	@echo "Compiling $< to $@"
	$(CC) -c $< -o $@

clean:
	rm -f $(TARGET) $(OBJS)

当程序执行a.out: hello.o main.o时，发现没有hello.o，于是查找以hello.o为目标文件的规则，结果匹配到模式规则*.o : *.c，于是模式规则会动态的创建以下规则：

1
2
3
hello.o: hello.c
	@echo "Compiling $< to $@"
	$(CC) -c $< -o $@

我们可以尝试执行一下make:

1
2
3
4
5
6
ylin@Ylin:~/Program/test$ make
Compiling hello.c to hello.o
cc -c hello.c -o hello.o
Compiling main.c to main.o
cc -c main.c -o main.o
cc -o a.out hello.o main.o

这样他可以比隐式的规则更灵活。但是我们现在也遇到一个问题，就是当我们修改hello.h头文件时，不会触发main.c重新编译的问题，我们之后在解决。

自动完成依赖

我们刚刚提到，在我们可以解决自动把.c编译成.o文件，但是难以解决.c文件对.h文件的依赖规则。因为要想知道.h的依赖关系，我们需要分析文件内容才能做到，并没有一个简单的文件名映射规则。

好在我们可以使用gcc提供的-MM参数，自动分析我们所需要的.h文件参数：

1
2
ylin@Ylin:~/Program/test$ cc -MM main.c
main.o: main.c hello.h

因此，我们可以利用这个功能，为每个.c文件都生成一个依赖项，并把它保存到.d(中间文件中)，再使用include将其导入makefile中，这样我们就精准的实现了.c文件的依赖分析。

我们可以更新我们的makefile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TARGET := a.out
SRCS := $(wildcard *.c)
OBJS := $(SRCS:.c=.o)
DEPS := $(SRCS:.c=.d)

$(TARGET): $(OBJS)
	$(CC) -o $@ $^

%.d: %.c
	rm -f $@; \
	$(CC) -MM $< >$@.tmp; \
	sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.tmp > $@; \
	rm -f $@.tmp

%.o: %.c
	$(CC) -c $< -o $@

clean:
	rm -f $(TARGET) $(OBJS) $(DEPS)

include $(DEPS)

当我们运行时，通过include会引入.d文件，但是一开始.d文件并不存在，这时会通过模式规则匹配到%.d: %.c。这里用了一个复杂的sed将.d文件创建了出来。我们运行make结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
ylin@Ylin:~/Program/test$ make
rm -f main.d; \
cc -MM main.c >main.d.tmp; \
sed 's,\(main\)\.o[ :]*,\1.o main.d : ,g' < main.d.tmp > main.d; \
rm -f main.d.tmp
rm -f hello.d; \
cc -MM hello.c >hello.d.tmp; \
sed 's,\(hello\)\.o[ :]*,\1.o hello.d : ,g'< hello.d.tmp > hello.d; \
rm -f hello.d.tmp
cc -c hello.c -o hello.o
cc -c main.c -o main.o
cc -o a.out hello.o main.o

我们可以看到.d文件中类似：

1
main.o main.d : main.c hello.h

现在，我们文件的依赖就加入了头文件，当我们对头文件进行修改时，就会触发重新编译

1
2
3
4
5
6
7
ylin@Ylin:~/Program/test$ make
rm -f main.d; \
cc -MM main.c >main.d.tmp; \
sed 's,\(main\)\.o[ :]*,\1.o main.d : ,g' < main.d.tmp > main.d; \
rm -f main.d.tmp
cc -c main.c -o main.o
cc -o a.out hello.o main.o

完善Makefile

我们现在对项目目录进行整理，我们将源码放入src目录，将编译生成的文件放入build目录：

1
2
3
4
5
6
7
8
ylin@Ylin:~/Program/test$ tree .
.
├── build
├── Makefile
└── src
    ├── hello.c
    ├── hello.h
    └── main.c

现在我们可以使用我们上述的操作，更新我们的makefile:

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
SRC_DIR := ./src
BUILD_DIR := ./build
TARGET = $(BUILD_DIR)/a.out

CC = gcc
CFLAGS = -Wall

SRCS = $(wildcard $(SRC_DIR)/*.c)
OBJS = $(patsubst $(SRC_DIR)/%.c,$(BUILD_DIR)/%.o,$(SRCS))
DEPS = $(patsubst $(SRC_DIR)/%.c,$(BUILD_DIR)/%.d,$(SRCS))

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CC) -o $@ $^

$(BUILD_DIR)/%.d: $(SRC_DIR)/%.c
	@mkdir -p $(BUILD_DIR)
	rm -f $@; \
	$(CC) -MM $< >$@.tmp; \
	sed 's,\($*\)\.o[ :]*,$(BUILD_DIR)\1.o $@ : ,g' < $@.tmp > $@; \
	rm -f $@.tmp

$(BUILD_DIR)/%.o: $(SRC_DIR)/%.c
	@mkdir -p $(BUILD_DIR)
	$(CC) $(CFLAGS) -c -o $@ $<

clean:
	@echo "Cleaning up..."
	rm -rf $(BUILD_DIR)

include $(DEPS)

我们通过设置目录路径变量实现了对一个简单项目的自动化编译。至此我们的对makefile的基本使用就了解了

对于makefile，它还有很多的复杂的用法，但是之后我会更好的利用它去做更多的项目。

发表于 更新于 分类于
本文字数： 802 阅读时长 ≈ 1 分钟

上个月都没怎么学习，几乎每天都在发呆想事情，因为我和一个傻瓜的事情。前几天去北京和她在一起呆了很久呀，感觉她还是像以前一样对我很好。但是可能异地恋的负担对于她来说还是太大了，所以我也不强求什么了。只求我能努力一点，以后和她一起去北京读书。我和她约好了我会去找她，会陪着她。

她对我一直都很好，很爱我的一个女生，我们从高一在一起，到十月底我们就刚好在一起四年了。我们俩的感情很好，但是我感觉自己还总是没有考虑到她的感受，导致我们的感情总是她一个人承担，所以她真的好幸苦。现在她累累的，就轮到我来照顾她了。我打算好好学习，研究生去北京陪她一起，在她需要我的时候能一直在她身边。

然后这次去北京，听北理的老师和其他高校的学生交流，感觉触动还是很大的吧。感觉他们的眼里都是有光的，他们有自己想做的事，想要做到的事，和自己热爱的事情。而且他们的技术氛围也很好，我感觉自己一直是固步自封，偏于一隅，眼光和格局一直放的很小，总是安于当下。我感觉自己就像一个游魂，每天就是想干啥就干啥，以前我觉得这是一种坦然，现在我感觉这是一种迷茫吧。我应该好好接受生活，体验各种事情，学习各种事情，我想接受更多的东西，不仅仅是知识和技术上的内容。

要做的事情很多呀，确实会很辛苦，但是我认为这是一件很值得的事情。我想和我喜欢的女生在一起，希望自己优秀一点，以后能一直陪在她身边，保护她，我爱她。现在我也不知道应该做什么吧，先把这个学期要学的东西都先学起来，争取这个学期把绩点做好一点，如果有机会保研的话就保研，如果不行的话就考研。

这个月暂时就是整理一下自己，然后开始学一些概率论和离散数学好了，还有一些408的课程。以前我总是不太能接受这些干巴巴的知识，我也更喜欢自己亲自动手实践，但是现在也慢慢开始理解和去接受他们的重要性了。接下来的时间，重要的事情就是先把概率论和离散数学好好学一下。尤其是离散数学，其实我一直都很感兴趣，但是苦于不知道怎么开始学习。

有空的话我想把图形学捡起来好好学一下，打算重构一遍上个学期写的内容，然后进一步的学习一下。

感觉身体也很重要，要做的事情很多，我还要接着加油。