Ylin's Blog
0%

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

今天接着来认识一下图，结束了图的学习，数据结构的部分就告一段落了。之后就是涉及到一些基本的算法问题，感觉也会越来越难。

图

认识图

和之前的数据结构不同，图是一种非线性的结构，由顶点和边组成，以下面为例，我们可以将图G抽象的表示成一组顶点和一组边的集合：

1
2
3
V = {1,2,3,4,5}
E = {(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}
G = {V,E}

如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数 据结构。

image.png

图的常见类型和术语

结合不同的场景，我们可以从不同的角度对图进行分类：

  • 根据边是否具有方向，分为有向图和无向图
  • 根据顶点直接是否全部联通，分为联通图和非联通图
  • 根据边上的权重，非为无权图和有权图
  • ….

在不同的场景中我们选择合适的类型，来解决问题。

图的数据结构有以下常用术语：

  • 邻接：当两顶点之间存在边相连时，称这两个顶点邻接
  • 路径：从顶点A到顶点B经过的边构成的序列被称为从A到B的路径
  • 度：一个顶点拥有的边数。对有向图，根据边的方向，还分为入度和出度。

图的表示

图通常使用两种表示方式，我们这里均以无向图为例：

邻接矩阵

设图的顶点数量为𝑛，邻接矩阵使用一个n×n大小的矩阵来表示图，每一行（列）代 表一个顶点，矩阵元素代表边，用1或0表示两个顶点之间是否存在边。

设邻接矩阵为𝑀、顶点列表为𝑉 ，那么矩阵元素𝑀[𝑖,𝑗]=1表示顶点𝑉[𝑖]到顶点𝑉[𝑗] 之间存在边，反之𝑀[𝑖,𝑗]=0表示两顶点之间无边。

image.png

邻接矩阵有以下性质：

  • 在简单图中，顶点不能和自己相连，所以邻接矩阵主对角线上的元素是没有意义的
  • 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称
  • 将邻接矩阵的元素替换成权重就是有权图

邻接表

邻接表使用n个链表来表示图，链表节点表示顶点。第i个链表对应顶点i，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。如下图：

image.png

两种表示方法的比较

对于邻接矩阵，我们可以直接访问矩阵元素实现对边的CRUD，时间效率高达O(1)。但是矩阵存储的空间复杂度为O(n2)

对于邻接表，由于表中只存储实际已存在的边数，而边数通常小于n2，所以空间存储的效率上来看，邻接表要更加的节省空间。但是对于CRUD的操作，邻接表需要通过遍历搜索的方式来进行，所以时间效率更差。

但是结合先前的只是，对于这种链表较长的情况，我们可以将它优化成哈希表或者AVL树等结构，实现对时间效率的优化，所以对于大规模的图的使用场景，邻接表也更加普遍。

图的基本操作

图的操作主要可以分为对顶点和对边的操作，这里分别通过邻接矩阵和邻接表的方式进行实现。

基于邻接矩阵的实现

给定给一个顶点数量为n的无向图，我们需要完成以下操作：

  • 添加或删除边：直接在邻接矩阵修改指定的边，只不过要注意同时更新两个方向的边（无向图）
  • 添加顶点：在邻接矩阵的尾部添加一行一列，并初始化为0即可。
  • 删除顶点：在邻接举证中删除一行一列，将剩下的元素向左上补齐。对于最坏的情况（删除首行首列）需要移动(n − 1)2个元素
  • 初始化：传入n个顶点，初始化长度为n的顶点列表和nxn大小的邻接矩阵
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class GraphMap{
    private:
        vector<int> vertices;           // 顶点列表
        vector<vector<int>> adjMat;     // 邻接矩阵
    
    public:
        GraphMap(const vector<int> &vertices, const vector<vector<int>> &edges){
            for(int val : vertices)
                addVertex(val);
            for(const vector<int> &edge : edges)
                addEdge(edge[0],edge[1]);
        }

        int size() const{
            return vertices.size();
        }

        void addVertex(int val){
            int n = size();
            vertices.push_back(val);
            // 向邻接矩阵中添加一行
            adjMat.emplace_back(vector<int>(n,0));
            for(vector<int> &row: adjMat)
                row.push_back(0);
        }

        void removeVertex(int index){
            if(index >= size())
                throw out_of_range("顶点不存在");
            vertices.erase(vertices.begin() + index);
            // 删除行
            adjMat.erase(adjMat.begin() + index);
            // 删除列
            for(vector<int> &row : adjMat)
                row.erase(row.begin() + index);
        }

        void addEdge(int i,int j){
            if(i<0 || i>=size() || j<0 || j>=size() || i==j)
                throw out_of_range("顶点不存在");
            adjMat[i][j] = 1;
            adjMat[j][i] = 1;
        }

        void removeEdge(int i,int j){
            if(i<0 || i>=size() || j<0 || j>=size() || i==j)
                throw out_of_range("顶点不存在");
            adjMat[i][j] = 0;
            adjMat[j][i] = 0;
        }
};

基于邻接表的实现

设无向图的顶点总数为n、边总数为m，我们需要完成以下操作：

  • 添加边：在顶点对应链表的末尾添加边就行了。但是要注意无向图要加两个方向的边
  • 删除边：在顶点管理的链表中查找并删除指定的边。无向图中删两个方向。
  • 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点
  • 删除顶点：遍历整个邻接表，删除包含指定顶点的所有边
  • 初始化：在邻接表中创建n个顶点和2m条边
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class GraphList{
    private:
        unordered_map<Vertex* ,vector<Vertex*>> adjList;

        void remove(vector<Vertex*> &vec, Vertex* vet){
            for(int i=0;i<vec.size();i++){
                if(vec[i]==vet){
                    vec.erase(vec.begin()+i);
                    break;
                }
            }
        }

    public:
        GraphList(const vector<vector<Vertex*>> &edges){
            for(const vector<Vertex *> & edge: edges){
                addVertex(edge[0]);
                addVertex(edge[1]);
                addEdge(edge[0],edge[1]);
            }
        }

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

        void addVertex(Vertex* vet){
            if(adjList.count(vet))
                return;
            adjList[vet] = vector<Vertex*>();
        }

        void removeVertex(Vertex* vet){
            if(!adjList.count(vet))
                throw invalid_argument("不存在顶点");
            adjList.erase(vet);
            for(auto &adj : adjList)
                remove(adj.second,vet);
        }

        void addEdge(Vertex* vet1, Vertex* vet2){
            if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
                throw invalid_argument("不存在顶点");
            adjList[vet1].push_back(vet2);
            adjList[vet2].push_back(vet1);
        }

        void removeEdge(Vertex* vet1, Vertex* vet2){
            if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
                throw invalid_argument("不存在顶点");
            remove(adjList[vet1],vet2);
            remove(adjList[vet2],vet1);
        }
};

这里为了方便，我们使用动态数组代替了链表。用哈希表来表示邻接表结构。

同时需要注意在邻接表中我们使用Vertex类来表示顶点，也是为了方便。如果我们使用列表索引来区分不同德顶点的话，那么每当我们删除一个索引为i的顶点，就需要遍历整个邻接表，把所有索引大于i的顶点重新更新一遍，这样的话效率就很差。

图的遍历

树代表的是一对多的关系，图代表的是多对多的关系，所以我们可以将树视作图的一个特例。所以说树的遍历操作实际上也是图的遍历操作的一种特例。

和树类似的，我们有两种遍历方式实现对图的遍历操作：广度优先遍历和深度优先遍历

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外 扩张。以下图为例：

image.png

从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻 接顶点，以此类推，直至所有顶点访问完毕。

算法实现

BFS通常需要一个辅助队列来实现，通过队列先进先出的性质，实现BFS由近及远的思路。我们的实现流程如下：

  • 将遍历起始顶点startVet加入队列中，开始循环
  • 在每次迭代中，弹出队首顶点并访问，将该顶点的所有邻接点加入到队列尾部
  • 循环上一步，知道队列为空

同时我们还需要一个哈希集合visited来记录哪些节点被访问，以防止重复遍历顶点。

我们的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<Vertex*> graphBFS(GraphList &graph, Vertex* startVet){
    vector<Vertex*> res;				// 返回的顶点序列
    unordered_set<Vertex*> visited;		 // 哈希集合,用来记录被访问过的顶点	
    queue<Vertex*> que;					// 辅助队列	
    que.push(startVet);
    while(!que.empty()){
        Vertex* vet = que.front();
        que.pop();
        res.push_back(vet);
        for(auto adjVet : graph.adjList[vet]){
            if(visited.count(adjVet))
                continue;				// 跳过已访问的顶点
            que.push(adjVet);
            visited.emplace(adjVet);
        }
    }
    return res;
}

可以通过画图的方法帮助理解一下这个过程

深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。以下图为例

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
void dfs(GraphList &graph, unordered_set<Vertex*> &visited,
         vector<Vertex*> &res, Vertex * vet){
    // 记录访问节点
    res.push_back(vet);
    // 标记已访问节点
    visited.emplace(vet);
	// 遍历所有邻接顶点
    for(Vertex* adjVet : graph.adjList[vet]){
        if(visited.count(adjVet))
            continue;
        // 递归访问邻接顶点
        dfs(graph,visited,res,adjVet);
    }
}

vector<Vertex*> graphDFS(GraphList &graph, Vertex* startVet){
    // 顶点遍历序列
    vector<Vertex*> res;
    // 以访问过的顶点
    unordered_set<Vertex*> visited;
    dfs(graph,visited,res,startVet);
    return res;
}

可以自己尝试手推一下这个过程，加深理解。

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

学一种新的数据结构——“堆”，但是貌似和底层原理中的堆并不一样。之前总是略有耳闻，但是一直都很少仔细去了解。

堆

堆是一种满足特定条件的完全二叉树，根据性质可以分为两种类型：

  • 小顶堆：任意节点的值 <= 子节点的值
  • 大顶堆：任意节点的值 >= 子节点的值
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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int>> minheap;
    priority_queue<int, vector<int>, less<int>> maxheap;

    maxheap.push(1);
    maxheap.push(5);
    maxheap.push(4);
    maxheap.push(2);
    maxheap.push(2);
    maxheap.push(3);

    cout << "The size is " << maxheap.size() << endl;
    int top = maxheap.top();
    cout << "The top is " << top << endl;

    bool isEmpty = maxheap.empty();

    return 0;
}

常用的可以总结为以下几类：

image.png

堆的实现

现在我们尝试从底层实现一个堆，这里我们用大顶堆演示，小顶堆只需要将所有的大小逻辑判断反转即可。

堆的存储和表示

堆是一种完全二叉树，我们之前提到过完全二叉树十分适合用数组来进行存储，所以这里我们的底层实现选择用数组，和之前的实现一样。我们使用索引的映射公式来代替节点指针：

1
2
3
4
5
6
7
8
9
10
11
int left(int i){
    return 2*i+1;
}

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

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

访问堆顶元素

堆顶元素就是二叉树的根节点，也就是我们数组的首元素：

1
2
3
4
5
6
7
8
9
10
class Heap{
    public:
		...
        int peek(){
            return heap[0];
        }
		...
    private:
        vector<int> heap;
};

元素入堆

给定val，我们将其添加到堆底。但是此时插入的值可能会破坏当前到根节点的路径，导致堆的成立条件被破坏。所以我们需要遍历修复从插入节点到根节点路径上的所有节点，这个过程我们称之为堆化

从入堆节点开始，我们从底执行堆化。我们依次比较当前节点和父节点的大小，如果插入节点更大就讲他们交换，知道修复所有的节点关系。

image.png

我们可以通过以下方式实现这个过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      void push(int i){
          heap.push_back(i);
          // 从堆底开始堆化
          siftUp(heap.size()-1);
      }
	
// 堆化
      void siftUp(int i){
          while(true){
              int p = parent(i);
              if(p<0 || heap[i] <= heap[p])
                  break;

              swap(heap[i],heap[p]);
              // 向上堆化
              i=p;
          }
      }

堆顶元素出栈

堆顶元素是二叉树的根节点，如果我们直接从数组中删除首元素，那么会破坏整个树的树状结构，这导致后续的堆化难以修复。所以我们采取以下步骤将堆顶元素出栈：

  • 交换堆顶元素（根节点）和堆底元素（最右元素）
  • 交换完成之后，我们将堆底删除
  • 从根节点开始自顶向底执行堆化

自顶向下的堆化和自底向上的堆化逻辑相反，我们将当前节点和较大的子节点进行比较，然后进行交换，直到没有子节点或者无需再交换了：

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
void pop(int i){
    if(heap.empty())
        throw out_of_range("堆为空");
    swap(heap[i], heap[heap.size()-1]);
    heap.pop_back();
    siftDown(0);
}

void siftDown(int i){
    while(true){
        // ma为较大的节点
        int l=left(i), r=right(i), ma = i;
        if(l < heap.size() && heap[i] < heap[l])
            ma = l;
        if(r < heap.size() && heap[i] < heap[r])
            ma = r;
        // l,r越界或者i已经是最大节点 则退出堆化
        if(ma==i)
            break;
        swap(heap[i],heap[ma]);
        i = ma;
    }
}

建堆操作

我们希望能直接根据一个列表中的所有元素来构建一个堆。我们有两种可行的方案：

  • 创建一个空堆，然后遍历列表，对每一个元素都进行入堆操作。但是对于n个元素执行复杂度为O(logn)的入堆操作，时间复杂度会增长到O(nlogn)
  • 另一个方法就是，将列表中的元素添加到完全二叉树中，尽管现在的堆的性质并没有被满足。接下来我们倒序遍历堆，并对每个非叶节点进行一次自顶向下的堆化。这样每当我们堆化一个节点之后，都会以该节点为根节点形成一个子堆。

这里我们着重分析一下第二种方法。我们可以通过以下方法实现：

1
2
3
4
5
6
Heap(vector<int> vec){
    heap = vec;
    // 倒序遍历的第一个非叶节点 就是最后一个叶节点的父节点
    for(int i=parent(heap.size()-1); i>=0; i--)
        siftDown(i);
}

这个方法下的复杂度被优化到了O(n)，更加的便捷。

Top-k问题

所谓top-k问题，就是给定一个长度为n的无序数组nums，请返回数组中最大的k个元素。

对于这个问题我们有很多种解决方案：

遍历选择

我们可以像这样对一个长度为n的序列进行k次遍历，每轮遍历都提取出当前序列中的最大的数据。时间复杂度为O(nk)。当k接近n时，时间复杂度增长到O(n^2)

image.png

排序

先对数组nums进行排序，然后再返回最右边的k个数据。这个方法主要取决于对数组排序的时间复杂度，对于std::sort，这个方法的复杂度是O(nlogn)

堆

我们可以基于堆更加高效的完成这个任务，我们遵循以下步骤实现：

  • 初始化一个小顶堆，此时其堆顶元素最小。
  • 然后将数组的前k个元素依次入堆
  • 从第k+1个元素开始，如果当前元素大于堆顶元素，我们就将堆顶出堆，并将当前元素入堆。
  • 遍历完成之后，堆中保存的就是最大的k个元素。

我们可以写出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
priority_queue<int, vector<int>, greater<int>> topHeap(vector<int> nums, int k){
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i=0;i<k;i++)
        heap.push(nums[i]);
    for(int i=k;i<nums.size();i++){
        if(heap.top() < nums[i]){
            heap.pop();
            heap.push(nums[i]);
        }
    }
    return heap;
}

总共进行了n轮入堆和出堆，由于堆大小是固定的k，所以我们只需要维护k个元素，所以实际上我们的计算复杂度只有O(nlogk)，在k较小时，我们的时间复杂度约等于O(n)

由此可以看到通过堆的思路，对解决TopK问题的显著提升。尤其是对于这种方法，适用于动态数据流的使用场景。在不断加入数据时，我们可以持续维护堆内的元素，从而实现 最大的𝑘个元素的动态更新。

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

书接上回，接着研究一下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 阅读时长 ≈ 3 分钟

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

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

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

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

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

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

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

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

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

二叉树

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

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 阅读时长 ≈ 7 分钟

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

语句

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

  • 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 阅读时长 ≈ 5 分钟

我们完成了对词法分析的获取函数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 阅读时长 ≈ 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
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 阅读时长 ≈ 14 分钟

我们将尝试构建一个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 阅读时长 ≈ 6 分钟

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

然后进度的话是接着上一次”图形学(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