上两篇文章给出了词法分析的完整代码：
用C语言实现一个真正的词法分析器
用C语言写一个真正的词法分析器，细节代码
它只需要动态字符串和双向链表，这两个基础数据结构就可以。
接下来，是比较有难度的语法分析。
在说语法分析之前，先说一个基础的数据结构：动态数组。
动态数组，也就是C++的STL模板类中的vector。
C语言没有自带的vector，需要自己做个简单的实现。
动态数组，首先是一个数组，它的所有元素都可以通过数组索引访问，随机访问的效率是O(1)。
其次，它与通常的固定数组一样，可以使用索引正向或反向遍历。例如：
for (i = 0; i < vec->size; i++);
for (i = vec->size - 1; i >= 0; i--);
vec为动态数组的结构体指针，vec->size为它当前存储的元素个数。
再就是，它可以存储多种数据类型，即可以作为基础数据结构使用，而与所存储的数据类型无关。
最后，与固定数组不同，它可以随着元素的增加或删除，动态地改变大小。
它的所有元素，自然是顺序存储的，而且每个元素的大小一致。
在C语言中，一个可行的办法就是，只让它存储void*类型的指针：如果存储复杂的结构体类型，那么只存储结构体的指针；如果存储数字，因为指针的大小是机器的字长，数字的大小不会超过这个值，所以可以把数字当作void*类型存储。
具体定义如下图：
数据部分是二级指针void** data，它的每个元素都是void*类型。
capacity表示当前的最大容量，size表示当前的元素个数。
在最大容量不够时，每次增加16个位置，这样可以减少realloc()的次数。
上图为scf_vector_alloc()和scf_vector_clone()函数，
下图为scf_vector_add()和scf_vector_del()函数。
因为要保持元素的连续存储，删除的复杂度与双链表不一样，需要移动后半部分的元素，这个复杂度不是O(1)，而是O(N)。
如果删除元素之后，空闲的内存过多，则执行realloc()从新分配小一点的内存，把不用的部分及时还给系统。
下图是scf_vector_find()、scf_vector_find_cmp()、scf_vector_qsort()，分别用于查找元素，根据传入的cmp函数指针查找元素，以及给元素排序。
再就是提供两个函数scf_vector_clear()和scf_vector_free()。
scf_vector_clear()，如果需要在销毁动态数组之前释放所存储的元素的内存，可以先调用这个函数(需要传入释放元素内存的free函数指针)，然后再调用scf_vector_free()。
如果所存储的元素没有占用额外的内存，例如是个被当作void*存储的数字，就可以直接调用scf_vector_free()。
动态数组的实现还是比较简单的，因为都是一些小函数，直接static inline写在头文件里了。
最后，使用这个动态数组实现一个数据结构：栈。
栈，在语法分析时使用的比较多，因为语法分析存在大量的复杂递归，需要栈来保存上下文。
栈，也是个动态数组，区别就是只从最后一个元素添加、删除、访问。
scf_stack_push()，用于压栈。
scf_stack_pop()，用于出栈。
scf_stack_top()，用于访问栈顶元素，它与scf_stack_pop()的区别就是它不会把栈顶元素弹出，不会改变栈的大小。
下一篇，说一下有限自动机的实现，使用它来分析语法。
举报/反馈
