發表於   |   分類於

Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length.

Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:

s: “barfoothefoobarman”

words: [“foo”, “bar”]

You should return the indices: [0,9].

(order does not matter).

首先将word list制成一个map。

然后逐个字符循环：

  • 每次取一个单词，判断在不在map中，不在的话直接可以进行下一次循环；
  • 取得的单词如果存在于map中，将这个单词加入到一个新的mapNew中；在这一过程中注意更新已有单词的计数，如果计数超过map中的对应值，进行下一次循环；
  • 如果取够足量的单词后依旧未触发两个中断循环的条件，那么可以认为取单词时的位置为正确位置。

解这道题目的时候脑袋瓜子抽了……

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
	map<string, int> wordset;
	map<string, int> test;

	vector<int> findSubstring(string s, vector<string>& words) {

		vector<int> result;

		if (words.size() == 0)
		{
			return result;
		}

		int size = words[0].size();
		for (int i = 0; i < words.size(); ++i)
		{
			auto it = wordset.find(words[i]);
			if (it == wordset.end())
			{
				pair<string, int> p(words[i], 1);
				wordset.insert(p);
			}
			else
			{
				it->second++;
			}
		}

		string substr;
		int cont = words.size() * size; //每一小段的长度
		int i = 0;
		while ((i + cont) <= s.length())
		{
			int counter = 0;
			while (counter < cont)
			{
				substr.push_back(s[i]);
				if (substr.size() == size)
				{
					auto wit = wordset.find(substr);
					if (wit == wordset.end())
					{
						substr.clear();
						break;
					}
					auto it = test.find(substr);
					if (it != test.end())
					{
						it->second++;
					}
					else
					{
						pair<string, int> p(substr, 1);
						test.insert(p);
					}
					if (wordset[substr] < test[substr])
					{
						substr.clear();
						break;
					}
					substr.clear();
				}
				++counter;
				++i;
			}
			i -= counter;
			if (counter == cont)
			{
				result.push_back(i);
			}
			test.clear();
			++i;
		}

		return result;
	}
};

發表於   |   分類於

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

定义运动方向，使用状态来解决这个问题，注意坐标的计算即可。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> result;
		int row = matrix.size();
		int col = 0;

		if (row != 0)
		{
			col = matrix[0].size();
		}

		if (col * row == 0)
		{
			return result;
		}

		int ri = 0;
		int ci = 0;
		bool left = false;
		bool right = true;
		bool up = false;
		bool down = false;
		int br = 0, er = row - 1;
		int bc = 0, ec = col - 1;

		while (result.size() != col * row)
		{
			result.push_back(matrix[ri][ci]);
			if (!left && right && !up && !down)
			{
				if (ci == ec)
				{
					ci = ec;
					right = false;
					down = true;
					br++;
					ri++;
				}
				else
				{
					ci++;
				}
			}
			else if (left && !right && !down && !up)
			{
				if (ci == bc)
				{
					ci = bc;
					left = false;
					up = true;
					er--;
					ri--;
				}
				else
				{
					ci--;
				}
			}
			else if (!left && !right && down && !up)
			{
				if (ri >= er)
				{
					ri = er;
					down = false;
					left = true;
					ec--;
					ci--;
				}
				else
				{
					ri++;
				}
			}
			else
			{
				if (ri <= br)
				{
					ri = br;
					up = false;
					right = true;
					bc++;
					ci++;
				}
				else
				{
					ri--;
				}
			}
		}
		return result;
    }
};

發表於   |   分類於

LeetCode: Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If nums = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

从一个集合生成它的子集，要求所有子集元素非递减排序，不能有重复的子集。

使用增量法生成子集（增量法是一个回溯算法），在此过程中判断集合是否重复。

AC代码：

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
class Solution {
public:

    vector<vector<int>> result;

    bool isVectorEqual(vector<int>& l,vector<int>& r)
    {
        if (l.size() != r.size())
        {
            return false;
        }
        else
        {
            for(int i = 0 ; i < l.size(); ++i)
            {
                if (l[i] != r[i])
                {
                    return false;
                }
            }
        }
        return true;
    }

    // 增量生成子集
    void subsets(vector<int>& nums, int begin, vector<int>& v)
    {
        for(int i = begin; i < nums.size(); ++i)
        {
            v.push_back(nums[i]);
            bool exist = false;
            // 判断是否有重复的
            for(int j = 0 ; j < result.size(); ++j)
            {
                if (isVectorEqual(result[j],v))
                {
                    exist = true;
                }
            }
            if (!exist)
            {
                result.push_back(v);
            }
            subsets(nums,i+1,v);
        }
        v.pop_back(); // 回溯
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());// 不排序是无法得到正确输出的
        vector<int> prefix;
        result.push_back(prefix);// 空集显然放在首位
        subsets(nums,0,prefix);
        return result;
    }
};

發表於   |   分類於

LeetCode: Add Two Numbers

You are given two linked lists representing two non-negative numbers.

The digits are stored in reverse order and each of their nodes contain a single digit.

Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

模拟两个非负整数相加。注意进位，以及对应位之和为0时的情况即可。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        bool l1ended = false;
        bool l2ended = false;
        int i1 = 0;
        int i2 = 0;
        int t = 0;
        bool carry = false;
        ListNode head(0);
        ListNode* ptail = &head;
        while(true)
        {
            if (l1)
            {
                i1 = l1->val;
                l1 = l1->next;
            }
            else
            {
                i1 = 0;
                l1ended = true;
            }

            if (l2)
            {
                i2 = l2->val;
                l2 = l2->next;
            }
            else
            {
                i2 = 0;
                l2ended = true;
            }

            if (carry)
            {
                t = i1 + i2 + 1;
            }
            else
            {
                t = i1 + i2;
            }

            if (t != 0)
            {
                if (t > 9) // 进位
                {
                    t %= 10;
                    carry = true;
                }
                else
                {
                    carry = false;
                }
                ListNode* n = new ListNode(t);
                ptail->next = n;
                ptail = n;
            }
            else
            {
                if (l1ended && l2ended)
                {
                    break;
                }
                else
                {
                    ListNode* n = new ListNode(0); // 有可能为0
                    ptail->next = n;
                    ptail = n;
                }
            }
        }
        return head.next;
    }
};

發表於   |   分類於

LeetCode: Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

不知为何会将这道题目设置为Hard……

解题的主要思路是：

  • 将原来的链表分割为若干块，记录下每一块的起始节点与终结节点；
  • 将每一小段逆置；
  • 将逆置后的段落拼接起来；

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <vector>
using namespace std;

class Solution {
public:

    struct ListPair
    {
        ListNode* head;
        ListNode* tail;
        int nums; // 有多少节点
        ListPair()
        {
            head = NULL;
            tail = NULL;
        }
    };

    vector<ListPair> pairs;

    void reverse(ListNode* head, ListNode* tail, ListNode** nhead, ListNode** ntail)
    {
        ListNode* th = head;
        ListNode* tt = tail->next;
        ListNode* h = NULL;
        ListNode* t = head;
        while (head != tt)
        {
            t = head;
            head = head->next;
            t->next = h;
            h = t;
        }
        *nhead = tail;
        *ntail = th;
    }

    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (head == NULL)
        {
            return NULL;
        }
        else if (head->next == NULL)
        {
            return head;
        }
      	int i = 0;
        ListPair lpair;

        while (head) // 切分链表
        {
            i++;
            if (head->next == NULL)
            {
                lpair.tail = head;
                lpair.nums = i;
                i = 0;
                pairs.push_back(lpair);
                lpair.head = NULL;
                lpair.tail = NULL;
                lpair.nums = 0;
            }
            else
            {
                if (i == 1)
                {
                    lpair.head = head;
                }
                else if (i == k)
                {
                    lpair.tail = head;
                    lpair.nums = k;
                    i = 0;
                    pairs.push_back(lpair);
                    lpair.head = NULL;
                    lpair.tail = NULL;
                    lpair.nums = 0;
                }
            }
            lpair.nums = i;
            head = head->next;
        }

        for (int i = 0; i < pairs.size(); ++i) // 逆置每一段
        {
            if (pairs[i].nums == k)
            {
                reverse(pairs[i].head, pairs[i].tail, &pairs[i].head, &pairs[i].tail);
            }
        }

        for (int i = 0; i < pairs.size() - 1; ++i) // 重新连接
        {
            pairs[i].tail->next = (pairs[i + 1].head==NULL)?(pairs[i + 1].tail):(pairs[i + 1].head);
        }

        return pairs[0].head;
    }
};

發表於   |   分類於

前面

本来是想在CPP相关的文里面讨论一下内存管理的事情，不过想了一想，还是放到编译相关的文章里面谈会更合适一些。

这次关于CG的讨论只关注一些基本原理以及算法，不涉及到并行GC等高级话题（水平不够Hold不住）。

正文

作用域(RAII的一个应用)

在C++中，我们知道一个对象的生存周期是与它的作用域有关的。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
struct Info
{
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
};
int main(int argc, char** argv)
{
	{
		Info info(1);
		{
			Info i(2);
		}
	}
	return 0;
}

这就在一定程度上给我们一个方案：用一个对象包裹分配的内存地址，当该对象出了它作用域之后自动调用free/delete，如下：

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
#include <stdio.h>
struct Info
{
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void say() { printf("this is %d\n", this->a); }
};

template<typename T>
struct SmartPtr
{
	T* ptr;
	SmartPtr(T* p) :ptr(p) {}
	~SmartPtr() { delete ptr; }
};

int main(int argc, char** argv)
{
	{
		SmartPtr<Info> i1(new Info(1));
		{
			SmartPtr<Info> i2(new Info(2));
			i2.ptr->say();
      // 注意赋值操作符带来的错误！！！
      // 如果i2是从i1而来： SmartPtr<Info> i2 = i1;
      // 那么，i2一旦出了作用域，就会连带将i1的内存释放掉，而这显然是不正确的！
		}
	}
	return 0;
}

这当然是不足以解决问题的——如果分配的内存希望能够在出了作用域之后继续存在怎么办？况且依旧无法对上面的代码注释中提到的情况作出应对。

引用计数

引用计数其实是很常见的，比如在操作系统中需要记录某内核对象的引用次数，只有当该对象的计数为0的时候才能销毁该对象；再比如COM对象的引用计数。示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
class Info
{
public:
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void say() { printf("this is %d\n", this->a); }
};

template<typename T>
class SmartPtr
{
public:
	struct refStruct
	{
		T* ptr;
		int refc;

	}* sptr; // 注意这里并非是直接将计数放在Smartprt中，而是加了一层。
	SmartPtr() :sptr(0)
	{

	}
	SmartPtr(T* p) :sptr(0)
	{
		if (sptr == NULL)
		{
			sptr = new refStruct;
			printf("new refStruct here\n");
			sptr->ptr = p;
			sptr->refc = 1;
		}
	}
	~SmartPtr()
	{
		if (sptr != NULL)
		{
			--sptr->refc; // 析构的时候减少计数
			if (sptr->refc <= 0)
			{
				delete this->sptr->ptr;
				this->sptr->ptr = NULL;
				printf("dead refStruct here\n");
				delete this->sptr;
				this->sptr = NULL;
			}
		}
	}
	SmartPtr<T>& operator=(SmartPtr<T>& sp)
	{
		if (this != &sp)
		{
			this->sptr = sp.sptr;
			this->sptr->refc++; // 赋值的时候增加计数
		}
		return * this;
	}
	int refCount()
	{
		if (this->sptr)
		{
			return this->sptr->refc;
		}
	}
};

int main(int argc, char** argv)
{
	{
		SmartPtr<Info> i1(new Info(1));
		printf("i1 ref count: %d\n",i1.refCount());
		{
			SmartPtr<Info> i2(new Info(2));
			printf("i2 ref count: %d\n", i1.refCount());
			SmartPtr<Info> i3;
			i3 = i1;
			printf("i1 ref count: %d\n", i1.refCount());
			printf("i3 ref count: %d\n", i3.refCount());
		}
		printf("i1 ref count: %d\n", i1.refCount());
	}
	return 0;
}

其实上面的例子也就是shared_ptr的原理了。注意到引用计数字段并没有直接放在Smartptr对象中——因为计数只与原始指针有关，一旦直接放入Smartptr对象中，赋值的时候就会产生副本，计数递减就只是对副本的操作，从而使得内存泄漏。

附上面代码的结果：

result

僵局：循环引用

仅从结果来看，引用计数工作的很好。

然而确实如此么？请注意这样一个事实：上面的对象是没有包含其他对象的指针的！

我们将代码改动一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
template<typename T>
class SmartPtr
{
public:
	struct refStruct
	{
		T* ptr;
		int refc;

	}* sptr;
	SmartPtr() :sptr(0)
	{

	}
	SmartPtr(T* p) :sptr(0)
	{
		if (sptr == NULL)
		{
			sptr = new refStruct;
			printf("new refStruct here\n");
			sptr->ptr = p;
			sptr->refc = 1;
		}
	}
	~SmartPtr()
	{
		if (sptr != NULL)
		{
			--sptr->refc; // 析构的时候减少计数
			if (sptr->refc <= 0)
			{
				delete this->sptr->ptr;
				this->sptr->ptr = NULL;
				printf("dead refStruct here\n");
				delete this->sptr;
				this->sptr = NULL;
			}
		}
	}
	SmartPtr<T>& operator=(const SmartPtr<T>& sp)
	{
		if (this != &sp)
		{
			this->sptr = sp.sptr;
			this->sptr->refc++; // 赋值的时候增加计数
		}
		return * this;
	}
	int refCount()
	{
		if (this->sptr)
		{
			return this->sptr->refc;
		}
	}
};

class Info
{
public:
	int a;
	SmartPtr<Info> link; // 注意这里的link！！！
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void Say() { printf("this is %d\n", this->a); }
	void LinkTo(const SmartPtr<Info>& link) { this->link = link; }
};

int main(int argc, char** argv)
{
	int* r1 = NULL;
	int* r2 = NULL;
	{
		SmartPtr<Info> i1(new Info(1));
		r1 = &i1.sptr->refc; // 取地址
		printf("i1 ref count: %d\n",i1.refCount());
		{
			SmartPtr<Info> i2(new Info(2));
			r2 = &i2.sptr->refc; // 取地址
			printf("i2 ref count: %d\n", i2.refCount());
			// 令其发生循环引用
			i1.sptr->ptr->LinkTo(i2);
			i2.sptr->ptr->LinkTo(i1);
			// 打印计数值
			printf("i1 ref count: %d\n", i1.refCount());
			printf("i2 ref count: %d\n", i2.refCount());
		}
		printf("i1 ref count: %d\n", i1.refCount());
	}
	//
	printf("Final: ref i1 = %d, ref i2 = %d\n", * r1, * r2);
	return 0;
}

附上上面的代码执行结果：

result

发现引用计数不再发挥效用了！！

图示会更加清楚：

eg

注意，这里在Info对象中添加的link字段。实际上，该字段可以认为是与Java/C#/Python中的引用一致的东西。前面的文章里面有提到过引用和指针之间是不同的，在这里将会有实际的体会：引用的概念比指针要更加高级与抽象。

如何破解这个僵局呢？

破局

破局的要点还是在上面那张图中：link->连线->方向+节点->有向图！

如果我们能够在GC之前把回边砍掉，从而恢复正确的引用计数，那么就可以正确完成垃圾回收了！

这里说明一下，上面的那张图实际上不是很正确：为了与计数对应而删掉了有向边——事实上有向边是没有删掉的（因为计数的减少并非有向边去掉导致的）。

在图中找出一个回边并不是个难事——遍历扫描一下就可以了。发现回边之后更改边两端的节点的引用计数即可。

然而在对一个图进行扫描的时候需要知道起点，而很多时候，分配的内存相互引用形成的图并非是一个连通图，于是这就引出了另外一个概念：Root集合。

Root集合与Mark-Sweep

所谓Root集合，其实就是GC回收时，扫描开始的“点”。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SmartPtr<Info> g_i1(new Info(123));
SmartPtr<Info> g_i2(new Info(456));   // ----> ①

void addLinkTo(SmartPtr<Info>& ptr, int num)
{
	ptr.sptr->ptr->link = SmartPtr<Info>(new Info(num));
}

int main(int argc, char** argv)
{
	{
		addLinkTo(g_i1,789);						// ----> ②
		SmartPtr<Info> i1(new Info(1)); // ----> ③
		{
			SmartPtr<Info> i2(new Info(2)); // ----> ④
			addLinkTo(i1,11);			// ----> ⑤
		}
	}
	// ----> ⑥
	addLinkTo(g_i1,1234); // 这里把以前的789那个对象给顶替了。如果不对其进行回收的话，将会产生内存泄漏。
	//
	...
}

不难发现，Root集合一般而言，是由全局变量，静态变量，寄存器值，方法参数，或者是由程序入口所在域及其子域中的变量等构成的。

前面我们已经知道每次加一个Link，就可以在相应的节点上加上一条有向边，那么上面的代码可以对应下面的图，表号对应代码中的注释：

.

注意内容为789的那个节点。这个节点是可以确定属于垃圾的。通过以上的描述，也不难发现Root集合应当包含的节点。

当我们根据Root集合进行扫描的时候，把可达节点做上标记（Mark）并收集起来，然后将不可达节点删除（Sweep）掉，就可以完成GC过程了——这就是Mark-Sweep算法的原理。

至于Root节点们，当它们出了自己的作用域之后必然将会被删除，到那时，剩下的所有节点都不再是可达节点，从而会被全部回收（当然对于全局变量，程序一旦结束，OS也会回收这些内存的）。

更进一步：三色标记模型

注意，截至到上一个部分，我们都是在对图的结构稳定情况下进行处理的，也就是要求当GC进行的时候，整个程序都应当停下来，不再对内存进行分配，直到GC过程处理完毕，也就是通常所说的“Stop The World”。

对于实时性要求不高的场合，这不失为一种有效的解决方法，然而对于交互式系统和实时系统这是无法接受的——至少，对于一个自动驾驶系统，如果该减速停车的时候来了一次GC，后果不堪设想。

这就需要另外一系列行之有效的办法来将这个时间碎片化，分散出去。引用计数可以在一定程度上做到这些，但还不够，于是，增量收集登场了。

在这个过程中，增量/并行算法将“无用垃圾信息收集穿插于程序执行过程中，避免对程序的长时间打断”。通常，由于应用程序本身总是在改变图的结构，因此将程序视为“改变器”；而GC模块，则视为“回收器”。

三色标记模型作为对Mark-Sweep的拓展补充，在增量标记中发挥了重要的作用。

在前面介绍LCA的文章中已经对染色法有过一定的介绍了，这里依旧是分阶段进行染色的，不过略有不同。

  • 对于未访问过的对象，标记为白色；
  • 对于已经访问过，但是其子对象还没有访问过的对象，标记为灰色；
  • 对于连子对象也访问过的对象，标记为黑色。

显然Sweep阶段完成之后，白色节点是属于不可达节点的，应当删除。但就上面描述而言，似乎没有什么特别的地方。而三色标记模型则明确了两个要点：

  • 黑色节点是不能够直接指向白色节点的。
  • 所有的灰色节点都处于一个待处理的数据结构中，也就是说，灰色节点属于一个中间态。

应该明确这样的一点：标记颜色的目的，是为了保留当前结点的状态。

很显然，当改变器对图中的一个黑色结点进行更改的时候（注意，出现了黑色节点也就说明了Mark过程是正在进行（或者已经Sweep了）），例如进行了一个LinkTo的操作，这个操作使得黑色节点变成了灰色节点。这个更改必须被及时、高效地的通知给收集器，通常情况下，这需要使用到“写障碍”或者是“读障碍”，他们基本都是利用OS，对相应的内存加上“读/写”锁来完成的。

另一种流派，复制收集（Copying GC）

相对于Mark-Sweep而言，复制收集更加易于理解，但一样要进行一次扫描阶段。

复制收集的主要做法是首先为应用程序分配一个大内存，然后将其一分为两个Pool。

  • 初始化阶段任选一块内存作为Pool，命名为SrcPool，另一个命名为DestPool，应用程序的所有内存申请均从SrcPool中划分。

  • 当SrcPool中没有足够的可用空间时，触发GC。

  • GC的扫描阶段标记完毕可达节点。

  • GC的复制阶段将SrcPool中所有标记的可达节点复制到DestPool，复制完毕之后，交换两个Pool的引用。

剩下的就是以上过程的迭代了。很显然，两个Pool起到了内存池的作用，并且内存经过了整理压缩，一定程度上解决了内存碎片的问题，并提高内存页的命中率；但这种方式的一个不好的地方在于它至少要浪费一半的内存空间；更有甚者，如果采用DFS（无论是否显式栈），还是基于额外队列的BFS，都需要另外的空间。

由于Copying GC也是有着扫描这一过程，因此三色标记模型实际也是可以在这上面采用的。

Cheney算法

为了解决额外空间的问题，Cheney算法利用复制对象过程中的特点（对象复制过后是紧凑的），采用destPool中的scan到next中间部分的记录作为BFS的队列（scan与next是两个指针），从而解决了这一问题。

现在使用四个对象来简单说明一下这个算法：

Cheney

首先是R对象作为Root被首先复制到DestPool中。R中保存了对象C与D的引用，这两个引用依旧指向SrcPool。

于是复制C和D到DestPool中，同时更改R中两个引用的指向，使其正确。

此时D中的引用仍旧指向SrcPool。

复制对象E到DestPool中，更改对象D中对E的引用的指向。

图中的S与N代表了scan指针与next指针。当scan最终等于next的时候，对该Root的处理结束。

引用与指针的区别再一次体现了出来：这里的引用包含了指向SrcPool的指针，被以此为标识来说明引用的对象是否还处于SrcPool中。

在编译课程中的GC就使用了该算法，当然实际过程会相对麻烦一些。

世代收集

分代的思想是基于这样的事实的：

  • 总是有那么一部分内存是变化不大的；
  • 当一块内存在一次或者多次GC中存活下来，那么它继续存活的几率会比较高；
  • 新分配的对象总是会马上死亡，无法经过第二次GC。

于是可以按照“代”将堆划分出来，比如将堆为老中青三代：

  • 新分配的对象总是从青年堆中分配，GC总是首先在青年堆中进行；
  • 将青年堆中存活的对象复制到中年堆中；
  • 当中年堆满的时候进行一次在中年堆上的GC，存活下来的对象复制到老年堆中；
  • 当老年堆满的时候，进行一次老年队上的GC，此时可以用Mark-Sweep或者Copy-Compact（这是在当前堆上进行的，该方法类似于内存碎片整理）等方法进行回收，一般来讲，尽量还是在回收后将对象紧凑放置。

上面只是世代收集的思想，当然也可以分成更多世代，视设计而定。

發表於   |   分類於

前面

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

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

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

正文

类型

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

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

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

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

类型检查

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

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

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

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

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

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

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

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

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

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

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

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

struct SB
{
  char b;
  int a;
};

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

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

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

struct Derived : public Base
{
  int derived;
};

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

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

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

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

符号表

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

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

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

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

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

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

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

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

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

结束

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

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

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

發表於   |   分類於

前面

说了一大堆杂七杂八的东西，今天换一换，简单总结一下STL——但是不考虑新的C++11标准，无它，用的不多，不熟。虽然多少知道一些新标准里面的东西是怎么一回事：比如左值右值，λ表达式，类型推导等，也不是不会用，但怎么用好则又是一回事情。就像OS与网络，虽然并非对其一无所知，且并不忌惮，但一直没有进行太多投入。因为我个人觉得这些都是属于系统编程的，相较之下工程意味更重，去公司锻炼事半功倍，不似图形或者编译这种需要有理论撑起来的，搞不清就是搞不清。

当然，我本人并无一丝对OS，网络的轻视之意。此二者之难，难在它们把现实中遇到的各种复杂问题的解决方案放到一个系统中行了巧妙的解决，是集多年以来经验之大成者。在学习过程中，“这么做就是为了解决这个问题的！”，此种想法不止一次出现过——当然，也很有可能是我自己见识尚浅，自以为是。

上面想法是在我大致学习了MIT的JOS之后形成的。虽然曾经跟了MIT JOS 2014实验课的几个关键Labs，但放下的时间稍嫌久了些，竟是没有剩下许多印象——然而终归有迹可循，日后想要重新拿起，想来应该不会无从下手。

正文

谈到STL，便不能不谈到泛型编程与Iterator模式。

CPP泛型编程的基础已经在首篇的《View CPP Template》里面演示过了，这里不再多说。这里主要说一下Iterator模式以此作为“设计模式”这 个话题的补充，并说明其在STL中的应用。

迭代器模式

事实上，迭代器模式是通过增加一个迭代器层来实现数据与算法分离的。例如在STL中，对于vector和list的遍历都可以通过：

1
2
3
4
for(auto it = container.begin(); it != container.end();++it)
{
  //do sth...
}

来完成（当然使用for_each也可），而众所周知vector是一个使用了变长数组的容器而list则是一个使用了双向链表的容器，两者的数据存储方式完全不同。

接下来就用一个固定长度的数组与一个链表来简单演示一下通常情况下的迭代器模式（不将Iterator类作为嵌套类的原因是为了更凸显“加一层”的做法，下面的代码实际不可取！）。

首先，定义一个如下的数组与链表，并初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define ARRAY_LEN 5
int myArray[5] = {5,4,3,2,1};

struct ListNode
{
  int m_data;
  ListNode* m_next;
  ListNode(int data, ListNode* next):m_data(data),m_next(next)
  {

  }
};

ListNode n1(9,NULL);
ListNode n2(8,&n1);
ListNode n3(7,&n2);
ListNode n4(6,&n3);
ListNode n5(5,&n4); //很显然链表头节点是n5

接下来定义迭代器：

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
struct Iterator
{
	void* m_ptr;
	virtual void operator++() = 0; // 强制重载
	virtual char* end() = 0;
	virtual int* operator*() = 0;
	virtual char* iterator() = 0;
};

struct ArrayIterator :public Iterator
{
	ArrayIterator(int* array)
	{
		m_ptr = (void*)array;
	}
	virtual void operator++()
	{
		int* ptr = (int*)m_ptr;
		ptr++;
		m_ptr = (void*)ptr;
	}
	virtual char* end()
	{
		return (char*)(myArray+ARRAY_LEN);  //注意，这里为了省事直接填了，实际情况不是这样的
	}
	virtual int* operator*()
	{
		return (int*)m_ptr;
	}
	virtual char* iterator()
	{
		return (char*)m_ptr;
	}
};

struct ListIterator :public Iterator
{
	ListIterator(ListNode* head)
	{
		m_ptr = (void*)head;
	}
	virtual void operator++()
	{
		ListNode* ptr = (ListNode*)m_ptr;
		ptr = ptr->m_next;
		m_ptr = (void*)ptr;
	}
	virtual char* end()
	{
		return NULL;  //注意，这里为了省事直接填了，实际情况不是这样的
	}
	virtual int* operator*()
	{
		ListNode* ptr = (ListNode*)m_ptr;
		return &ptr->m_data;
	}
	virtual char* iterator()
	{
		return (char*)m_ptr;
	}
};

最后定义一个只与Iterator相关的遍历算法：

1
2
3
4
5
6
7
void printAll(Iterator& it)
{
	for (; it.iterator() != it.end(); ++it)
	{
		std::cout << * (* it) << std::endl;
	}
}

至此，我们可以这样来输出数组和链表中的内容：

1
2
3
4
5
6
7
8
9
10
ArrayIterator arrayIt(myArray);
ListIterator listIt(&n5);
int main(int argc, char** argv)
{
	std::cout << "Array:" << std::endl;
	printAll(arrayIt);
	std::cout << "List:" << std::endl;
	printAll(listIt);
	return 0;
}

再次重申，上述代码很差，仅为说明思想。

其实加一层实际上是为了能够为上层统一接口，这一思想在实际应用十分常见。例子中，对于存储方式迥异的数组和链表加了一个迭代器层之后就可以使用同一个方法对其进行遍历了。

那么，STL中的迭代器模式有是如何的呢？

STL Iterator

其实理解了迭代器模式，再加上前面博文中对C++ Template的讲述，STL中的迭代器已经很好理解了。

回看上面的例子，我们可以整理出一下信息：两个不同的存储类型（array， list）；两个不同类型的迭代器（array iterator，list iterator）；迭代器与存储类型的紧耦合性。

然后回顾Template的核心：类型运算。

接着说STL中的迭代器。还是上代码吧，一个小例子，还是以vector和list为主的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>

template <typename T>
struct MyVector
{
private:
	T* m_array;
	int m_size;
	int m_cap;
public:
	MyVector()
	{
		m_array = NULL;
		m_size = 0;
		m_cap = 0;
	}
	typedef T* iterator;
	iterator begin()
	{
		return m_array;
	}
	iterator end()
	{
		return (m_array + m_size);
	}
	void push_back(T&& t)
	{
		if (m_array == NULL)
		{
			m_array = new T[2];
			m_cap = 2;
		}
		else if (m_size == m_cap)
		{
			m_cap *= 2;
			T* A = new T[m_cap];
			for (int i = 0; i < m_size; ++i)
			{
				A[i] = m_array[i];
			}
			delete[] m_array;
			m_array = A;
		}
		m_array[m_size] = t;
		m_size++;
	}
};

template <typename T>
struct MyList
{
private:
	struct Node
	{
		T m_data;
		Node* m_next;
	};
	Node* m_head;
	Node* m_tail;
public:
	MyList()
	{
		m_head = NULL;
		m_tail = NULL;
	}
	struct iterator
	{
		Node* m_ptr;
		iterator(Node* n)
		{
			m_ptr = n;
		}
		void operator++()
		{
			m_ptr = m_ptr->m_next;
		}
		T operator*()
		{
			return m_ptr->m_data;
		}
		bool operator!=(iterator& it)
		{
			return this->m_ptr != it.m_ptr;
		}
	};
	iterator begin()
	{
		return iterator(m_head);
	}
	iterator end()
	{
		return iterator(NULL);
	}
	void push_back(T&& t)
	{
		if (m_head == NULL)
		{
			m_head = new Node;
			m_head->m_data = t;
			m_head->m_next = NULL;
			m_tail = m_head;
		}
		else
		{
			Node* n = new Node;
			n->m_data = t;
			n->m_next = NULL;
			m_tail->m_next = n;
			m_tail = n;
		}
	}
};

MyVector<int> myArray;
MyList<int> mylist;
int main(int argc, char** argv)
{
	myArray.push_back(0);
	myArray.push_back(1);
	myArray.push_back(2);
	myArray.push_back(3);
	myArray.push_back(4);

	mylist.push_back(9);
	mylist.push_back(8);
	mylist.push_back(7);
	mylist.push_back(6);
	mylist.push_back(5);

	std::cout << "Array:" << std::endl;
	for (auto it = myArray.begin(); it != myArray.end(); ++it)
	{
		std::cout << (* it) << std::endl;
	}
	std::cout << "List:" << std::endl;
	for (auto it = mylist.begin(); it != mylist.end(); ++it)
	{
		std::cout << (* it) << std::endl;
	}
	return 0;
}

代码为了突出迭代器而简化了很多，但个人觉得说明STL里面的迭代器已经差不多足够了。

从上面也可以看出来，实际上迭代器并非仅仅是一个指针或者而已，如同所谓的“引用”——“引用（Reference）”会在后面的文里面涉及到，如果不出意外应该是会被归在“编译相关”的文章里面而不是在CPP相关的文章中。

现在也可以理解为什么标准库中的sort方法采用的是归并而不是快排了——快排作为对数据储存形式依赖严重的排序算法，显然不适合。

结束

本文算是图形编译说了一堆之后的“偷闲”文。有了上面的铺垫，再去看旧标准的STL应该会清晰很多。

至于新标准，给我个人的感觉就是：那些个曾经高贵冷艳（或者说很多时候认为不知道也不影响写程序）的理论距离C++程序员越来越近了！由于我没怎么用过Boost库，所以从C++03到C++11的过渡对我而言并非很平滑。后面肯定继续会有对新标准（其实已经是出了五年的“旧标准”了）的学习总结，不过应该是编译与CPP两边相互照应着进行了。

發表於   |   分類於

正文

今次总结Paser相关的一些东西，主要说明Top-Down的LL(1)解析以及Down-Top的LR(1)解析，最后说明抽象语法树（AST）。

LL(1)

LL(1)的缩写表明了该方法的运作方式：左端移进，最左推导，也就是输入串中的字符（或者Token）从左至右逐个扫描，当遇到某一条规约的终结符的时候，从扫描部分的最左端开始进行规约。

例如对于某文法有如下规约（名词）:

r0: S -> Expression

r1: Expression -> Expression + Expression

r2: Expression -> Expression - Expression

r3: Expression -> 1,2…N

可有串： 2+3-4+1

当扫描至+的时候，即为r3的终结符号，于是对已扫描到的2进行归约（动词），得到一个Expression = 2，同时移动到规约r1。

接着扫描3，是为规约r3。

然后是-，得到一个Expression = 3。

此时已经扫描过的部分已有：Expression = 2 + Expression = 3，从而可以按照r1进行归约，得到一个Expression = (Expression = 2) + (Expression = 3)。

剩余部分以此而行，便可以得到整个串了。

LL(1)中的1就是指：每次判定需要使用哪一条规约进行归约的时候，只需要多扫描一个符号即可，例如上面例子中的+和-。

递归子程序法与优先级

优先级一个比较麻烦的地方，上面的例子中+和-是同优先级的，如果哪天有个奇葩规定要求当-和+同时出现时需要优先计算-，则当如何？

先来看看前面两者优先级相同时的“语法图”：

+ == -

再来看看-的优先级比较高的时候的“语法图”：

+ < -

请忽略下面代码对于错误边界的处理，并且一下代码仅为说明过程，递归返回值等的细节也请暂时不要去追究……

首先定义一个过程parseAddExp()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Expression* parseAddExp()
{
  Expression* result = new Expression;
  Expression* left = NULL;
  Expression* right = NULL;
  left = parseMinusExp(left);  
  // 注意这里！！！如果只是一个单独的数字，或者下一个符号不是`+`
  if (NULL == curToken || curToken->m_tkCode != TK_ADD)  
  {
    return left;
  }
  if(curToken->m_tkCode == TK_ADD)
  {
    right = parseMinusExp(right);
  }
  result->m_leftExp = left;
  result->m_rightExp = right;
  return result;
}

再定义一个过程parseMinusExp()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Expression* parseMinusExp()
{
  Expression* left = NULL;
  Expression* right = NULL;
  left = parseNumberExp();
  // 注意这里！！！如果只是一个单独的数字，或者下一个符号不是`-`
  if (NULL == curToken || curToken->m_tkCode != TK_MINUS)  
  {
    return left;
  }
  Expression* result = new Expression;
  if(curToken->m_tkCode == TK_MINUS)
  {
    right = parseNumberExp(right);
  }
  result->m_leftExp = left;
  result->m_rightExp = right;
  return result;
}

最后定义一个过程parseNumberExp()：

1
2
3
4
5
6
7
8
Expression* parseNumberExp()
{
  if (curToken->m_tkCode == TK_INTNUM)
  {
    return new Expression(ToIntNumber(curToken->m_lexeme));
  }
  return NULL;
}

仍旧以串2+3-4+1为例，下面我们将上述过程依次述略述为ADD，MINUS，NUM。

那么对于2，ADD调用MINUS，MINUS解析它，并得知下一个符号是+，于是知道这是仅仅是一个Expression = 2，于是直接返回给Expression Add的左操作数为Expression = 2。

接下来是ADD知晓下一个符号是+，然后将表达式的整个剩余部分送入MINUS中，以期望得到一个右操作数。

串剩余部分是3-4+1。MINUS可以正确捕获到一个Expression Minus = (Expression = 3) - (Expression = 4)，从而将其作为Expression Add的右操作数返回。于是我们得到了一个完整的Expression Add = (Expression = 2) + ( (Expression = 3) - (Expression = 4) )

等等，解析怎么就停止了？后面还有一个+1呢？实际上，只需要对过程ADD进行一些修改，使它支持对连续的N个+进行解析就可以了，对于连续个-，同样可这么干。

那么我们的最终解析过程就极有可能是这样的（视编码而定，但是优先级是肯定对的）：

AST

结果是一个二叉树是因为+和-都是二元运算符的原因；如果全是是一元运算符则是一个单链表，例如成员运算符；全是三元运算符，例如Exp?Exp:Exp，则是一个三叉树；混起来就看起来像是一个普通的树了。

回顾一下前面的解析过程，发现在建立这棵树的时候，每次都是从一颗子树的根节点开始创建，然后递归进行创建它的子节点，所谓的Top-Bottom就是由此而来。

抽象语法树(AST)

前面既然提到了树，那么就顺势说一下吧，很容易理解了。

抽象语法树实际上就是语言无关的，代码的抽象表示，可以认为是代码的一种中间表示形式：单单从上面的那个串：2+3-4+1，根本无法断定它是用哪个语言的来写的。当然设计思想不同的语言，其对应的抽象语法树还是有差别的——比如函数式编程语言与C。

抽象语法树带来的最大好处就是语法制导的翻译和中间代码生成，这个留待以后说明。

顺带一提：上面的树想要恢复原有的表达式，只需要对其进行后序遍历即可（当然需要控制一下左右子节点先后顺序），不妨尝试把原来的数学表达式翻译为三地址码序列：

1
2
3
4
OP  dest  op1  op2
SUB r1    3    4,
ADD r1    2    r1,
ADD r1    r1   1,

LR(1)

实际上，LR分析在《数据结构》课程上已经是接触过的，只不过那时的说法并非如此而已：基本上在学习Stack之后都会有一个处理四则混合运算的“计算器”作业，这个作业实际上就是LR分析的应用。

这里就从四则混合运算入手来说明一下LR(1)解析。

这里举例要用到的串：4+2*3-6/3。暂且不去考虑括号对运算的影响。

r0: S -> Expression

r1: Expression -> Expression + Expression

r2: Expression -> Expression - Expression

r3: Expression -> Expression * Expression

r4: Expression -> Expression / Expression

r5: Expression -> 1,2…N

先对解析过程有个印象：

LR

下面LR(1)的Parser伪码来自《Engineering a Compiler, 2nd》，Figure 3.15：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
push $;
push start state, s0;
word ← NextWord( );
while (true) do;
  state ← top of stack;
  if Action[state,word] = ‘‘reduceA→ β’’ then begin;
    pop 2 × | β | symbols;
    state ← top of stack;
    push A;
    push Goto[state, A];
  end;
  else if Action[state,word] = ‘‘shift si’’ then begin;
    push word;
    push si ;
    word ← NextWord( );
  end;
  else if Action[state,word] = ‘‘accept’’
    then break;
  else
    Fail( );
end;
report success; /* executed break on ‘‘accept’’ case */

大致回忆一下“计算器”作业的过程：使用两个Stack，一个是装载运算符，一个装载读取到的数字；从左到右逐个读取字符，遇到数字就把数字放进数字栈，遇到运算符就把运算符放进运算符栈；如果将要入栈的运算符是*或者\，就从数字栈弹出两个数字，用将要入栈的运算符计算结果，并将结果入数字栈；如果将要入栈的运算符是+或者-，那么就从运算符栈中弹出一个运算符，数字栈中弹出两个数字，计算并将结果压入数字栈；迭代这一过程，直到运算符栈为空，此时数字栈中应该只剩下一个数字，便是最后结果。

再看上面的伪代码：注意到if块中有一个“pop 2 × | β | symbols”。

再注意：四则运算文法中的规约，对于r1~r4都能找出一个代表性的符号，而这个符号，恰好就是运算符。

另外，在之前的表驱动编程和基于状态编程中，曾经提到过：对于由于if-else分支过多而冗长的程序，可以使用状态与表来解决，而在计算器的程序中，需要经常判定读取到的符号的意义。回看上面的伪代码：state，Action[ ]，Goto[ ]。

再有：LR的分析栈包含两个：状态栈以及文法符号栈，而“计算器”也有两个栈。

先把四则运算文法的Action与Goto表填出来。GoTo表实际上就是一个状态转移表。

补充：Action表中有些许错误：单一的number直接accept了，严格来讲应该reduce r5

1
2
3
4
5
6
7
8
9
10
11
Action Table: 空白表项说明是遇到了错误。

     |   number  |    +      |     -     |    *      |     /     |   EOF   |
s0   |  shift s5 |           |           |           |           |  Accept | 初始状态
s1   |  shift s6 |           |           |           |           |         | number +
s2   |  shift s7 |           |           |           |           |         | number -
s3   | reduce r3 |           |           |           |           |         | number * 或者 number + number * 或者 number - number *
s4   | reduce r4 |           |           |           |           |         | number * 或者 number + number * 或者 number - number *
s5   |           |  shift s1 |  shift s2 |  shift s3 |  shift s4 |  Accept | 在已经有了一个数字 number 之后读取到了运算符/EOF
s6   |           | reduce r1 | reduce r1 |  shift r3 |  shift r4 |         | s6是指当前已经分析到 number+number的情况了
s7   |           | reduce r2 | reduce r2 |  shift r3 |  shift r4 |         | s7是指当前已经分析到 number-number的情况了

之所以先填写Action表，是为了说明为何需要一个GoTo表：注意Action表中的reduce ri，如果只有一个Action表的话，一旦归约之后，就有可能会出现无法进行接下来的分析的情况——因为无法得知当前的状态了！

例如：number + number * number，规约之后应当是 number + number，此时的状态应当为s6，但是在只有一个Action表的情况下无法获取。因此需要一个Goto表来协助。

1
2
3
4
5
6
7
8
9
10
Goto Table:
     |   number  |    +      |     -     |    *      |     /     |   EOF   |
s0   |           |           |           |           |           |         |
s1   |           |           |           |           |           |         |
s2   |           |           |           |           |           |         |
s3   |    s5     |    s6     |    s7     |           |           |         | number * 或者 number + number * 或者 number - number *
s4   |    s5     |    s6     |    s7     |           |           |         | number * 或者 number + number * 或者 number - number *
s5   |           |           |           |           |           |         | 在已经有了一个数字 number 之后读取到了运算符/EOF
s6   |           |    s5     |    s5     |           |           |         | s6是指当前已经分析到 number+number的情况了，一旦规约则只剩单个number
s7   |           |    s5     |    s5     |           |           |         | s7是指当前已经分析到 number-number的情况了，一旦规约则只剩单个number

表填完了，接下来使用上面的伪码与这两张表对例串4+2*3-6/3进行分析：

Table

最后一步可以根据需要来组成最后的语法树——C语言中，运算的结合方向为从右向左，应该与此有关。

LR分析中的每一个reduce过程实际上都可以看作是一个语法树的结点的生成过程（如果对每一个number也加入一个reduce的话，这一事实将更加明显），很显然，整个过程自子节点开始，逐步生成整个语句的语法树，这即是Down-Top。

结束

需要注意的是，这里对于LR(1)分析的说明中，由于每个人对具体细节的不同，两个表的内容可能有一些出入；又，由于对LR分析的理解不是足够深刻，文中关于LR(1)的分析可能有错误的地方，还请诸位看官邮件至solaxu@outllook.com不吝指出。

然而LR分析最重要的部分并非分析过程，而是Action表和Goto表的构建。例子因为比较简单，所以可以手工填写，但是对于一门实际语言这显然是不可能的。于此部分本人仅略知皮毛，不敢妄言，还请众位见谅则个。

發表於   |   分類於

前面

说起来，我的这些个总结如果放到简历上给人看，大概会堵了不少实习机会吧，毕竟个人痕迹以及倾向表现的太重……

总结一下之前在编译课程上学到的东西，能写多少写多少吧，能代码示例就用代码示例，理论大部分人不喜欢，我也不喜欢，况且前面文里也有提到学到的编译理论大部分都还给老师去了。其实我倒是觉得把个编译搞得让人觉得索然无味大部分时候都是理论太多，讲了也不知道能干嘛……

就从词法分析开始吧。

正文

Lexer的主要目的是将源代码文件切割成一个个的词素（lexeme），然后这些词素与其代表的类型、所在行号、列号等一系列属性组成一个记号（Token），以得到一个Token Stream来供语法分析使用。相对来Lexer说还是比较容易理解与实现的，至少比LR分析要好理解。

呃，概念性的东西就不多讲了，举个例子：

1
while (result) { print ("Hello"); }

上面的一句代码可以切分由下列Token组成：

1
2
3
4
5
6
7
8
9
10
11
while  -> 关键字while，第0行，第0列
(      -> 左小括号，第0行，第6列
result -> 标识符，第0行，第7列
)      -> 右小括号，第0行，第13列
{      -> 左大括号，第0行，第15列
print  -> 函数名，实际上也是标识符，第0行，第17列
(      -> 左小括号，第0行，第24列
"Hello"-> 字符串，第0行，第25列
)      -> 右小括号，第0行，第32列
;      -> 分号，第0行，第33列
}      -> 右大括号，第0行，第35列

可以看到空格是被略去了的。事实上，词法分析在进行分析的时候是将空格以及Tab都过滤掉了，当然还有换行。

假定我们要实现一个类似于“C”的脚本语言，它的Tokens的类型包含：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
enum TokenCode
{
  TK_START, // 解析开始
  TK_PLUS, TK_MINUS,T K_MUL, TK_DIV,T K_MOD, // + - * / %
  TK_GT, TK_LT, TK_EQUAL, TK_LQ, TK_GQ, TK_NEQ, // > < ==  <= >= !=
  TK_ASSIGN, TK_DOT, // = .(成员运算符)
  TK_AND, TK_OR, // && ||
  TK_OPENPA, TK_CLOSEPA, TK_OPENBRKT, TK_CLOSEBKT, TK_OPENBRE, TK_CLOSEBRE, // ( ) [ ] { }
  TK_SEMI, TK_COMMA, // ; ,
  TK_INT, TK_FLT, TK_STRING, // int float string
  TK_CSTR, TK_CLASS, TK_FUNC, // 常量字符串 class func
  TK_WHILE, TK_CONTINUE, TK_BREAK, // while continue break
  TK_IF, TK_IFELSE, TK_ELSE, // if ifelse else
  TK_RETURN, // return
  TK_POINTER, //  ->
  TK_LIST, // list
  TK_IDENT, // 标识符
  TK_EOF, // end of file
  TK_SELF, // self
};

然后是Token的结构：

1
2
3
4
5
6
struct Token
{
  string m_lexeme;
  int m_lineNum;
  int m_tkCode;
};

注意，为了集中说明词法分析，这里暂且不引入符号表，只需要暂时先保留这个概念即可：标识符在语法分析阶段是要到符号表中进行查找的，并且符号表在链接阶段也是一个核心数据结构。另外标识符有时候可能是一个结构体或者一个函数，此时还需要一个指向表示标识符类型的指针。这些都将会在语法、语义分析的时候使用到。

Lexer的实现

直观上看，Lexer其实就是一个字符一个字符，同类型的Token下按照最长读取原则来进行读取到一个Stack中，当Token类型发生改变的时候将Stack中的所有字符拿出来与关键字进行比较以确定结果标识符还是关键字。

基于以上描述，我们就有了一个简单实用的实现方法：

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 curCode = TK_START;
char* stream = srcFile;
char curChar = *stream;
char charStack[MAX_ID_LEN];
int stackTop = -1;
vector<Token> tokens;
while(true)
{
  if (curCode == TK_START)
  {
    if (isAlpha(curChar) )
    {
      Token* tk = readId(stream,charStack,stackTop,tokens);
      isKeyWord(tk);
    }
    else if (isNumber(curChar))
    {
      Token* tk = readNumber(stream,charStack,stackTop,tokens)
    }
    ...
    else if(isEOF(curChar))
    {
      break;
    }
  }
}

在此方法中，对于ifqwe这样的串一定不能在读到if之后就去与关键字比较，这样得到的结果是错误的，所以在readId处理之后再去判断它是不是关键字。

貌似没看到状态机？实际上状态机已经是有了的：对于ifqwe[2]这样的串，很显然readId在读到[的时候已经可以意识到标识符已经读完了，此时就可以切换curCode为初始状态再进行读取。

然而上述方法需要进行字符串的比较，即便是采用了HashTable，其时间耗费也是在O(N)+的。为了提高效率，我们自然是想要一个O(N)的解决方案。

这个方案需要使用到字典树，在前面基于状态的编程一文中已经介绍过了。相比前面一种方法，该方法在编码上要稍微麻烦一些——要多维护一棵树，而且空间耗费也多起来了，并且有一些注意事项（至少是在我编码的时候出现过的）：在构建字典树的时候，对于具有共同前缀的关键字，例如：if与ifelse，最好先构建if的路径，再构建ifelse的路径。因为先构建if，那么i->f需要首先设置f后面的所有指针都是空的，接下来的if->else直接把代表e的槽覆盖掉就可以了；而如果先处理ifelse，那么在处理if的时候就要小心，不要将已经建好的路径破坏掉了（如果按照i->f->结束，无匹配，i->f->else的路径就会断掉）。

结束

关于Lexer的实现，我知道的也就是前面的两种方案，其中第一种方案易于编码，简单直观，第二种则需要稍微花点心思。就我看过的一些资料而言，方案一用得更多一些（当然这些都只是教材，而并非商业级的东西，然而貌似Lua的Lexer也是采用第一种方案的），我自己两种方案都使用过，也踩过一些坑，上面也已经提到过了。总的来讲实现一个玩具级的Lexer并非一个难事。

最后说一下语法高亮（Syntax Lighting）的问题。

实际上语法高亮并不会涉及到语法分析跟语义分析，只需要词法分析就够了，唯一的要点在于采用语法分析的程序需要编辑器能够嵌入一个实时词法分析引擎，并进行字体渲染的工作，输入自动补完同样是这个要求。当然如果是要用Pretty Print进行重新排版，那么除了词法分析器，还需要用到语法分析（之前做Pretty Print的时候用到了语法分析，因此不确定只用词法分析是否可以做到，不过感觉有点悬）。

补充：

花了差不多一天时间为本文写了对应的代码，按照第一种方式写的。时间仓促，一定有考虑不周的地方，比如一些各种错误处理等。代码（VS2015通过，使用到了Win32的API）可以在这里找到。附上截图：

这是要解析的代码：

code1

这是词法分析的结果：

result01
result02

重新打印后的代码高亮效果:

snytaxlighting