开发自己的编程语言-zengl编程语言v0.0.2初始化抽象语法树
zenglong 2012-10-21 10:06:53
上一节中通过词法扫描器将标示符，数字，操作运算符等token扫描出来，这节将这些扫描出来的token放入抽象语法树节点中保存起来，以后将会利用这 些节点构建完整的抽象语法树结构，有关抽象语法树的概念可以...
上一节中通过词法扫描器将标示符，数字，操作运算符等token扫描出来，这节将这些扫描出来的token放入抽象语法树节点中保存起来，以后将会利用这 些节点构建完整的抽象语法树结构，有关抽象语法树的概念可以在《龙书》中找到，这里只做简单说明：比如表达式 c = a + b ，这么一个表达式经过词法扫描器扫描后，将会得到 ‘c’ ,‘ =’ ,‘a’ , ‘+’ , ‘b’ 这五个token,将这5个token放入AST（抽象语法树）结构的nodes（节点列表）中，再根据赋值运算符和加法运算符的优先级关系，以及具体的 程式算法，就可以构建这5个token的相互之间的父子关系。从上到下的父子关系图就像一棵树一样，如图：
在这个树形结构中，越在下面的运算优先级越高，那么在以后要生成汇编代码的时候，就可以先根据加法运算符先生成a+b的汇编码，最后生成赋值运算的汇编码，这样就可以完成一个简单的编译（这些具体内容以后再说）。
现在知道语法树的意义和重要性了，那么这一节的程式主要是为构建这样的抽象语法树结构做准备，即将token以节点的形式加入到语法树的节点列表。
本节代码还是放在sourceforge上面，下载链接：http://sourceforge.net/projects/zengl/files/zengl_lang_v0.0.2_forXP.rar/download （此链接为zengl v0.0.2版本的xp版本，解压后将得到vs2008的项目解决方案，请使用火狐浏览器点开此链接并下载，IE浏览器请右键目标另存为...）。 http://sourceforge.net/projects/zengl/files/zengl_language_v0.0.2_forLinux.tar.gz/download （此链接为zengl v0.0.2的Linux版本，这次用的是tar.gz压缩包，解压后有usage.txt使用说明文档），http://sourceforge.net/projects/zengl/files/v0.0.2-v0.0.1-diffs.txt/download （此为v0.0.2与v0.0.1版本的代码变化），本想发布到爱问等网盘上面去，不过这些网盘要 审核，所以先放到sourceforge上。
百度盘共享链接地址： http://pan.baidu.com/share/link?shareid=85544&uk=940392313
现在以XP版本为例进行说明，在该版本里有三个代码文件，main.c ，parser.c ，global.h
在v0.0.1版本里的main.c开头的一些声明，比如include ，#define FALSE 0等的定义都放到了global.h 全局头文件里。这样不同的C文件里就可以共用一些结构体和宏定义了。在main.c的main()入口函数里，while循环getToken部分，前一 个版本是直接调用printToken(token)将token信息打印出来，在这个版本里，是先调用AddNode(token) 将扫描到的元素加入到语法树的Node节点中，最后在循环结束后，调用printASTnodes函数将所有节点信息打印出来。
该版本的主要部分是在parser.c源文件里，该文件的代码将作为处理抽象语法树的主程式。该文件里的initTreeNode函数用于初始化抽象语法 树的动态节点数组AST_nodes结构，该结构定义在文件的开头：TreeNode_Type AST_nodes; 其中TreeNode_Type在global.h的定义如下：
typedef struct{
int size;
int count;
Node_Type *nodes;
}TreeNode_Type;
其中size成员表示动态数组中一共可以存放多少元素，在初始化zl_malloc函数分配动态内存空间时，会根据size和Node_Type类型的大 小决定要分配的内存大小，count成员表示当前动态数组中存放了多少个节点元素，nodes指针成员指向zl_malloc分配的内存空间的指针。
在以后还会遇到很多这样的动态数组结构，组成结构都差不多。当动态数组的count等于size时，表示动态数组当前分配的空间已用完，需要加入更多的元 素的话，就需要增加size的值，再根据新的size，调用zl_realloc函数调整动态数组的内存大小，同时更新nodes指针成员，使其指向新的 空间大小，zl_realloc函数内部会调用realloc系统库函数来调整内存大小，再调整时会将原来的数据也拷贝到新空间里，所以该函数可以在不丢 失原有数据的情况下进行扩容。这样就实现了一个动态数组。在AddNode函数添加新节点时就用到了这点：
if(AST_nodes.count == AST_nodes.size)
{
AST_nodes.size += TREENODE_SIZE; //TREENODE_SIZE为数组的初始大小，也是每次扩容时要增加的大小，定义在global.h中，默认为40
AST_nodes.nodes = zl_realloc(AST_nodes.nodes,
AST_nodes.size * sizeof(Node_Type));
memset(AST_nodes.nodes+(AST_nodes.size - TREENODE_SIZE),0,
TREENODE_SIZE * sizeof(Node_Type)); //将扩容后的新内存空间用0填充。
}
AST_nodes里的nodes指向节点的内存空间，每个节点的类型都是Node_Type，该类型在global.h中的定义如下：
typedef struct{
bool isvalid; //节点是否有效，有效表示该节点存放了一个token信息，已被占用，不能再存信息。无效则表示该节点还没存放token信息，可以用来存放信息。
enum TOKENTYPE toktype; //表示该节点存放了什么类型的token，如ID表示标示符，NUM表示数字等。
char * tokstr; //该token的字符串信息，如标示符 abc的节点，则在toktype里会存放ID表示这是一个标示符，在tokstr里则存放的是"abc"的字符串。
}Node_Type;
在该版本里每个节点的tokstr成员都会由zl_malloc分配一个字符串的内存空间用来存放标示符的字符串信息，如果节点数很多的情况 下，zl_points的内存池就需要分配很多的内存指针来存放这些字符串信息，效率和性能上都会出问题，这个问题在后面的版本中会用一个特殊方法进行处 理。
在parser.c的最后定义了printASTnodes函数，通过循环调用printNode函数来打印所有的节点信息，而printNode则根据指定节点的toktype类型，将该节点的tokstr字符串信息打印出来。
由于代码最初是在linux上进行开发的，采用的是git做的版本控制，但是在开发时因时间关系，没有给代码做注释，所以导致git里所有的历史版本都没 有注释，如果现在要给代码加上注释的话，那么所有的历史版本都要加一遍注释，重复的工作量太大，所以就暂时不在代码里加注释，先通过这里发布的网页说明文 档和程序调试的方法来理解代码吧，在最后一个版本中将会加入注释信息。
为了方便查看上个版本和当前版本的不同，所以从git提取了信息存放在v0.0.2-v0.0.1-diffs.txt文件里，从该文件里可以看出两个版本的代码变化情况。
v0.0.2-v0.0.1-diffs.txt文件的下载地址：http://sourceforge.net/projects/zengl/files/v0.0.2-v0.0.1-diffs.txt/download
最后linux下的用户在解压Linux版代码后，根据usage.txt的说明，先make clean 清理原来生成的二进制文件，再make生成当前环境下的可执行文件，最后./zengl test.zl 来测试，当然前提是安装了gcc编译器。
本例的抽象语法树等很多高级的原理都可以在《龙书》中找到。
网上可以搜索（龙书 编译原理） 来下载pdf电子档。
最后的最后，如果转载请注明来源 http://www.zengl.com ， OK ， 先到这里，休息，休息一下 O(∩_∩)O~